北邮数据结构实验三

北邮数据结构实验报告北京邮电大学信息与通信工程学院2009级数据结构实验报告实验名称：实验三哈夫曼编/解码器的实现学生姓名：陈聪捷日期：2010年11月28日1.实验要求一、实验目的：了解哈夫曼树的思想和相关概念;二、实验内容：利用二叉树结构实现哈夫曼编/解码器1.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。

2.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。

3.编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。

5.打印：以直观的方式打印哈夫曼树。

6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。

7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。

2.程序分析2.1存储结构二叉树templateclassBiTree{public:BiTree();//构造函数，其前序序列由键盘输入~BiTree(void);//析构函数BiNode*Getroot();//获得指向根结点的指针protected:BiNode*root;//指向根结点的头指针};//声明类BiTree及定义结构BiNodeData：二叉树是由一个根结点和两棵互不相交的左右子树构成data:HCode*HCodeTable;//编码表inttSize;//编码表中的总字符数二叉树的节点结构templatestructBiNode//二叉树的结点结构{Tdata;//记录数据Tlchild;//左孩子Trchild;//右孩子Tparent;//双亲};编码表的节点结构structHCode{chardata;//编码表中的字符charcode[100];//该字符对应的编码};待编码字符串由键盘输入，输入时用链表存储，链表节点为structNode{charcharacter;//输入的字符unsignedintcount;//该字符的权值boolused;//建立树的时候该字符是否使用过Node*next;//保存下一个节点的地址};示意图：2.2关键算法分析1.初始化函数(voidHuffmanTree::Init(stringInput))算法伪代码：1.初始化链表的头结点2.获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n 记录的是链表中字符的个数)3.从字符串第2个字符开始，逐个取出字符串中的字符3.1将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出的字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。

数据结构实验三实验报告数据结构实验三实验报告一、实验目的本次实验的目的是通过实践掌握树的基本操作和应用。

具体来说，我们需要实现一个树的数据结构，并对其进行插入、删除、查找等操作，同时还需要实现树的遍历算法，包括先序、中序和后序遍历。

二、实验原理树是一种非线性的数据结构，由结点和边组成。

树的每个结点都可以有多个子结点，但是每个结点只有一个父结点，除了根结点外。

树的基本操作包括插入、删除和查找。

在本次实验中，我们采用二叉树作为实现树的数据结构。

二叉树是一种特殊的树，每个结点最多只有两个子结点。

根据二叉树的特点，我们可以使用递归的方式实现树的插入、删除和查找操作。

三、实验过程1. 实现树的数据结构首先，我们需要定义树的结点类，包括结点值、左子结点和右子结点。

然后，我们可以定义树的类，包括根结点和相应的操作方法，如插入、删除和查找。

2. 实现插入操作插入操作是将一个新的结点添加到树中的过程。

我们可以通过递归的方式实现插入操作。

具体来说，如果要插入的值小于当前结点的值，则将其插入到左子树中；如果要插入的值大于当前结点的值，则将其插入到右子树中。

如果当前结点为空，则将新的结点作为当前结点。

3. 实现删除操作删除操作是将指定的结点从树中移除的过程。

我们同样可以通过递归的方式实现删除操作。

具体来说，如果要删除的值小于当前结点的值，则在左子树中继续查找；如果要删除的值大于当前结点的值，则在右子树中继续查找。

如果要删除的值等于当前结点的值，则有三种情况：- 当前结点没有子结点：直接将当前结点置为空。

- 当前结点只有一个子结点：将当前结点的子结点替代当前结点。

- 当前结点有两个子结点：找到当前结点右子树中的最小值，将其替代当前结点，并在右子树中删除该最小值。

4. 实现查找操作查找操作是在树中寻找指定值的过程。

同样可以通过递归的方式实现查找操作。

具体来说，如果要查找的值小于当前结点的值，则在左子树中继续查找；如果要查找的值大于当前结点的值，则在右子树中继续查找。

北邮数据结构实验报告摘要：本报告基于北邮数据结构实验，通过实际操作和实验结果的分析，总结和讨论了各实验的目的、实验过程、实验结果以及相关的问题和解决方法。

本报告旨在帮助读者了解数据结构实验的基本原理和应用，并为今后的学习和研究提供参考。

1. 实验一：线性表的操作1.1 实验目的本实验旨在掌握线性表的基本操作以及对应的算法实现，包括插入、删除、查找、修改等。

1.2 实验过程我们使用C++语言编写了线性表的相关算法，并在实际编程环境下进行了测试。

通过插入元素、删除元素、查找元素和修改元素的操作，验证了算法的正确性和效率。

1.3 实验结果经过测试，我们发现线性表的插入和删除操作的时间复杂度为O(n)，查找操作的时间复杂度为O(n)，修改操作的时间复杂度为O(1)。

这些结果与预期相符，并反映了线性表的基本特性。

1.4 问题与解决方法在实验过程中，我们遇到了一些问题，例如插入操作的边界条件判断、删除操作时的内存释放等。

通过仔细分析问题，我们优化了算法的实现，并解决了这些问题。

2. 实验二：栈和队列的应用2.1 实验目的本实验旨在掌握栈和队列的基本原理、操作和应用，并进行实际编程实现。

2.2 实验过程我们使用C++语言编写了栈和队列的相关算法，并在实际编程环境下进行了测试。

通过栈的应用实现表达式求值和逆波兰表达式的计算，以及队列的应用实现图的广度优先遍历，验证了算法的正确性和效率。

2.3 实验结果经过测试，我们发现栈的应用可以实现表达式的求值和逆波兰表达式的计算，队列的应用可以实现图的广度优先遍历。

这些结果证明了栈和队列在实际应用中的重要性和有效性。

2.4 问题与解决方法在实验过程中，我们遇到了一些问题，例如中缀表达式转后缀表达式的算法设计、表达式求值的优化等。

通过查阅资料和与同学的讨论，我们解决了这些问题，并完善了算法的实现。

3. 实验三：串的模式匹配3.1 实验目的本实验旨在掌握串的基本操作和模式匹配算法，并进行实际编程实现。

实验三DLG处理器程序设计1.实验目的学习简单编译优化方法，观察采用编译优化方法所带来的性能的提高。

2.实验原理采用静态调度方法重排指令序列，减少相关，优化程序。

3、实验内容和要求自编一段汇编代码，完成一维向量加法运算，并输出结果。

观察程序中出现的数据/控制/结构相关。

（注：使用一维数组表示一维向量。

）4．1向量加法代码清单及注释说明1、向量加法设计源代码.dataVectorLength:.word16Vector1:.word1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16Vector2:.word1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16；声明向量长度以及声明向量1、2Printf1:.asciiz"Vector="Printf2:.asciiz"%f".align2PrintPrompt:.wordPrintf1PrintPar:.wordPrintf2Result:.space4；存放打印数据的空间申请.teGtmain:addir14,r0,PrintPrompttrap5lwr20,VectorLengthaddir2,r0,0Loop:ldf10,Vector1(r2)ldf12,Vector2(r2)；循环体中读入向量cvti2df0,f10cvti2df2,f12adddf4,f2,f0；加法运算Finish:;GGGGFinish,writeresultintostdoutsdResult,f4addir14,r0,PrintPartrap5；系统中断，输出结果addir2,r2,4subir20,r20,1bnezr20,Loop;GGGGEndtrap02、运行结果5．1程序相关性分析结果（1）观察程序中出现的数据/控制/结构相关。

指出程序中出现上述现象的指令组合。

产生34.12%的数据相关。

数据结构实验报告1．实验要求(1)实验目的通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

(2)实验内容使用简单数组实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试排序算法的正确性。

2. 程序分析2.1 存储结构顺序表:示意图：2.2 关键算法分析（1）测试数据的产生：正序、逆序、随机数据用两个数组实现乱序、顺序以及逆序数据的排序。

基本思想为：随机序列产生一个指定长度的乱序序列，然后通过memcpy()函数拷贝到第二个数组里，第二个数组作为乱序序列的保存数组，每次对第一个数组进行排序，之后拷贝第二个数组中的乱序序列到第一个数组，实现各次乱序排列。

只要算法正确（第一步可以检验），之后顺序排列只需反复对第一个数组进行操作即可，再后用第二个数组保存逆序数组，然后同样在每次排序之后复制第二数组存储的乱序序列到第一组，对第一组反复排序即可。

<1> pRandom1=new long int[Max+1];pRandom2=new long int[Max+1];<2> srand((unsigned)time(NULL)); for(int i = 1; i <= Max;i++ ) pRandom2[i]=rand();<3> memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int));（2）排序算法：<1>插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。

数据结构实验报告实验名称：实验3——简单数组实现排序学生姓名：XXXXNB班级：XXXXXXXX班内序号：学号：XXXXXXXX日期：2016年XXXXXXX1．实验要求使用简单数组实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

//3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。

2.程序分析在题目中要求测试不同的数据，可以手动输入待排序元素。

我在编程时为了界面的简洁易于监控，便选择了在主程序中把数组写好放入主程序里。

同时为了方便每种算法的比较，我将所有的函数包装为一个类，方便运行并监控。

比较遗憾的是，我没有做算法运行时间的相关程序，为了弥补这种缺陷，我选择了将界面做的更人性化一些。

2.1 存储结构采用数组进行顺序存储结构示意图如下:2.2 关键算法分析核心算法思想：1. 利用教材讲述的基本算法思想，实现其中五种排序算法，统计其运行相关数据。

2. 将五种排序函数封装到一个类中，使得程序代码可读性、结构更加优化。

排序算法分析：1.插入排序算法插入排序的思想是：每次从无序区取一元素将其添加到有序区中。

a.直接插入排序C++描述如下，其中形参a[]为待排序数组，n为待排序元素个数同时添加两个变量move,compare用于记录整个排序过程中的比较次数以及移动次数void Sort::DirectInsertSort(int a[], int n)//直接插入排序{int k;int move = 0;int compare=0;for (int i = 2; i <= n; i++)//第一个定然为有序，出现两个数据时开始进行排序{if (a[i] < a[i - 1]){a[0] = a[i];move++;//元素赋值移动+1for (int j = i - 1; j > 0 && a[0] < a[j]; j-- ){a[j + 1] = a[j];move++;//移动+1compare++;//for条件中比较+1k = j;//记录查找出的位置}a[k] = a[0];move++;//元素赋值移动+1}compare++;//if比较n大小+1}cout << "移动次数" << move << endl;cout << "比较次数" << compare << endl;}b.希尔排序希尔排序，设待排序对象序列有n个元素，先取d<n,比如d=n/2，作为间隔，将全部对象分为d个子序列，对每一个子序列分别进行直接插入排序，然后缩小间隔d，即减少子序列个数例如取d=d/2，重复子序列的划分和排序工作，直到取d=1，仅有一个子序列为止（ps：本质上仍为直接插入排序的改进）C++描述如下，其中形参a[]为待排序数组，n为待排序元素个数同时添加两个变量move,compare用于记录整个排序过程中的比较次数以及移动次数void Sort::ShellInsert(int a[], int n)//希尔排序，本质上为直接插入排序的改进{int k;int move = 0;int compare = 0;for (int d = n / 2; d >= 1; d = d / 2){for (int i = d + 1; i <= n; i++)//前d个元素是每个子序列头部，为初始有序区，从d + 1开始循环{if (a[i] < a[i - d])//并不是单独分别对各个子集分别排序，而是依次从每个子集第二个元素排起{a[0] = a[i];move++;//赋值移动+1for (int j = i - d; j > 0 && a[j] > a[0]; j = j - d){a[j + d] = a[j];move++;//元素后移+1compare++;//for循环中条件比较+1k = j;}a[k] = a[0];move++;//元素赋值移动+1}compare++;//if中比较+1}}cout << "移动次数" << move << endl;cout << "比较次数" << compare << endl;}//希尔排序利用了直接排序的两个特点：1.基本有序直接插入最快 2.记录个数很少的无序序列，直接插入也很快。

北京邮电大学实验报告课程名称数据库系统原理实验内容实验（三）实验名称数据查询实验班级2013211***姓名***指导老师卢向群成绩_________2016年4月20日实验三数据查询实验实验目的通过对实验二中建立的数据库关系表和视图的各种查询的操作，加深对SQL语言和Transact SQL查询语言的了解，掌握相关查询语句的语法和使用方法。

实验内容数据库关系表查询：（1）简单的查询操作，包括单表的查询、选择条件、结果排序等的练习；（2）多表的连接查询，包括等值连接、自然连接等；（3）复杂的查询操作，包括使用分组函数等库函数的查询操作；（4）练习带有IN、比较符的嵌套查询。

具体内容包括：1.简单查询:(1)查询班号为g99401班的学生的学号和姓名；表中没有该班级的学生，故查询结果为空。

(2) 查询“数据库开发技术”课程的学分；(3) 查询选修了课程编号为“dep04_s003”的学生的学号和成绩，并将成绩按降序输出；(4) 查询学号为“g9940205”的学生选修的课程编号和成绩；(5) 查询选修了课程编号为“dep04_s001”且成绩高于85分的学生的学号和成绩。

2.在多表连接的查询实验中，在SQL SERVER提供的交互式语言环境下用TransactSQL语句完成以下查询操作：(1)查询选修了课程编号为“dep04_s002”且成绩高于85分的学生的学号、姓名和成绩；该题与上一题的差别在于学生姓名，这一属性与成绩不在同一张表中，故需要对两张表做自然连接。

(2)查询所有学生的学号、姓名、选修的课程名称和成绩；需要用到三张表，把三张表做自然连接，语句如下：查询结果如下：(3)查询计算机科学系林红同学选修的课程名称、学分和成绩。

(考试成绩>＝60有学分，否则无学分。

)这个查询看似困难，实际上只是因为设计的表格较多，所以麻烦而已，只要将五张表自然连接就可以了。

查询结果为空，说明计算机科学系没有叫“林红”的学生。

数据结构实验报告实验名称：实验三——栈和队列学生姓名：班级：班内序号：学号：日期：1.实验要求1.1 实验目的通过选择下面两个题目之一进行实现，掌握如下内容：➢掌握二叉树基本操作的实现方法➢了解赫夫曼树的思想和相关概念➢学习使用二叉树解决实际问题的能力1.2 实验内容根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。

二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试main()函数测试线性表的正确性2. 程序分析2.1 二叉链表2.2 二叉树的二叉链表存储示意图2.3 关键算法分析2.3.1算法1：void create(Binode<T> *&R, T data[], int i);[1] 算法功能：创建一个二叉树[2] 算法基本思想：通过构造函数创建一个二叉树，构造函数通过调用函数create()创建二叉树，关于函数create()的伪代码：1.定义根指针，输入节点储存的data，若输入“#”，则该节点为空；2.申请一个新节点，判断它的父结点是否不为空，如果不为空在判断其为左或者右孩子，并把地址付给父结点，把data写入。

[3] 算法空间、时间复杂度：O（n）[4] 代码逻辑（可用伪代码描述）：if(data[i-1]!=0){R = new Binode<T>;R->data= data[i-1];R->lch = R->rch = NULL;create(R->lch, data,2*i);create(R->rch, data, 2*i+1);}2.3.2算法2：void Destroy(Binode<T> *R);[1] 算法功能：二叉树的销毁[2] 算法基本思想：采用后序遍历的方法，释放节点。

实验二指令流水线相关性分析·实验目的通过使用WINDLX模拟器，对程序中的三种相关现象进行观察，并对使用专用通路，增加运算部件等技术对性能的影响进行考察，加深对流水线和RISC 处理器的特点的理解。

·实验原理：指令流水线中主要有结构相关、数据相关、控制相关。

相关影响流水线性能。

·实验步骤一．使用WinDLX模拟器，对Fact.s做如下分析：（1）观察程序中出现的数据/控制/结构相关。

指出程序中出现上述现象的指令组合。

（2）考察增加浮点运算部件对性能的影响。

（3）考察增加forward部件对性能的影响。

（4）观察转移指令在转移成功和转移不成功时候的流水线开销。

·实验过程一．使用WinDLX模拟器，对Fact.s做如下分析：浮点加、乘、除部件都设置为1，浮点数运算部件的延时都设置为4，如图1：图1 初始设置将fact.s和input.s加载至WinDLX中，如图2示。

图2 加载程序1.观察程序中出现的数据/控制/结构相关；指出程序中出现上述现象的指令组合。

1）数据相关点击F7，使程序单步执行，当出现R-Stall时停止，运行过程中出现下图3所示，输入整数6。

图3 输入整数6打开Clock Diagram，可以清楚的看到指令执行的流水线如图4所示。

图4 指令流水线双击第一次出现R-Stall的指令行，如图5所示。

图5 指令详细信息对以上出现的情况分析如下：程序发生了数据相关，R-Stall（R-暂停）表示引起暂停的原因是RAW。

lbu r3,0×0(r2)要在WB周期写回r3中的数据；而下一条指令seqi r5,r3,0×a要在intEX周期中读取r3中的数据。

上述过程发生了WR冲突，即写读相关。

为了避免此类冲突，seq r5,r4,0×a的intEX指令延迟了一个周期进行。

由此，相关指令为：2）控制相关由图6可以看出，在第4时钟周期：第一条指令处于MEM段，第二条命令处于intEX段，第三条指令出于aborted状态，第四条命令处于IF段。