期末实验报告总

1、数据结构实验报告作者：朱之凯设 n3，m=4,停车价格为p=2。输入数据为：(A,101,5),( A,102,10),(D,101,15),(A,103,20),(A,104,25）,(A,105,30）,( D,102,35）,( D,104,40）,( E,0,0)。其中A 表示到达，D表示离开，E表示结束。时间为相对分钟数。4）输入输出:输入数据：程序接受5个命令，分别是:到达(A,车牌号,时间)；离去(D,车牌号,时间)；停车场(P,0,0)显示停车场的车；候车场(W,0,0)显示候车场的车;(E,0,0)程序。输出数据：对于车辆到达，要输出汽车在停车场内或者便道上的停车位置；对于车

2、辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上不）。【需求分析】1.本程序主要是顺序栈、链表队列的2.用户输入完毕后，程序自动建立输出文件，可直接看结果【概要分析】1.为了实现上述功能，需要栈与队列的抽象数据类型：1)栈的抽象数据类型：ADT Stack 数据对象：D=ai|aiElemSet,i=1,2,.,n,n>=0,ElemSet 为元素所有2数据结构实验报告作者：朱之凯集合数据关系：R=<ai-1,i>|ai-1,aiD,i=1,2,.,n基本操作：InitStack(&S);/构造空栈DestroyStack(&S);/销毁栈Clear

3、Stack(&S);/将栈置空StackEmpty(S);/检查栈是否为空StackLength(S);/返回栈中元素个数GetTop(S,&e);/返回栈顶元素赋予ePush(S,e);/e 为新的栈顶元素Pop(S,&e);/删除栈顶元素并赋予eStackTravers(S);/依次输出栈中元素2)队列的抽象数据类型：ADT Queue 数据对象：D=ai|aiElemSet,i=1,2,.,n,n>=0,ElemSet 为元素集合数据关系：R=<ai-1,i>|ai-1,aiD,i=1,2,.,n基本操作：InitQueue(&Q);/构

4、造空队列DestroyQueue(&Q);/销毁队列所有3数据结构实验报告作者：朱之凯ClearQueue(&Q);/将队列置空QueueEmpty(Q);/检查队列是否为空QueueLength(Q);/返回队列中元素个数GetHead(Q,&e);/返回队首元素赋予eEnQueue(Q,e);/在队尾新元素eDeQueue(Q,&e);/删除队首元素并赋予eQueueTravers(Q);/依次输出队列中元素2.本程序保护模型：主程序模块栈单元模块：实现栈的抽象数据类型队列单元模块：实现队列的抽象数据类型调用关系：主程序模块=栈单元模块+队列单元模型【程序】

5、1.头文件：#include <stdlib.h>#include <stdio.h>#include <fstream>using namespace std;所有4数据结构实验报告作者：朱之凯ifstream fin ("park.in");ofstream fout ("park.out");2.定义栈、队列的元素、节点和节点指针类型：typedef int QElemType;/QElemType 定义为inttypedef struct LNode QElemType number,start;struct

6、LNode *next;LNode,*LinkList;typedef LinkList Queueptr;typedef struct Queueptr front;Queueptr rear;LinkQueue;/以上为队列的类型typedef struct int number,start;Stack;/此为栈的类型3.全局变量：Stack stack100;LinkQueue Q;所有5数据结构实验报告作者：朱之凯int n,m,pp;int p1,p2;4.：1）进站：void GetIn (int nu,int mi)Queueptr p;if (p1<n) /看 p1 的值

7、，若小于 n，则说明停车场还有车位stackp1.number=nu;/添加栈元素并赋予信息stackp1.start=mi;fout<<"No."<<nu<<": Stack "<<p1+1<<endl;p1+;else /若 p1 不小于n，说明满位，让车在便道等候p=new LNode;/添加队列元素并赋予信息p->number=nu;p->start=mi;p->next=NULL;Q.rear->next=p;Q.rear=p;fout<<"

8、;No."<<nu<<": Queue "<<p2+1<<endl;所有6数据结构实验报告作者：朱之凯p2+;2）出站：void GetOut (int nu,int mi)int i=0,j,x;Queueptr p;while (stacki.number!=nu && i<p1) i+;/找到要离开的车位if (i!=p1) /如果车是在停车场，计算费用x=mi-stacki.start;/计算停车时间fout<<"No."<<nu<<

9、;": "<<x<<' '<<x*pp<<endl;for (j=i; j<p1-1; j+) /移动其余的栈元素，使之保持连续stackj.number=stackj+1.number;stackj.start=stackj+1.start;p1-;停车场的车数减 1if (p1=n-1 && p2>0) /将便道上的第一个车进入停车场p=Q.front->next;Q.front->next=p->next;stackp1.number=p->number

10、;所有7数据结构实验报告作者：朱之凯stackp1.start=p->start;p1+;p2-;if (Q.rear=p) Q.rear=Q.front;delete p;else fout<<"Wrong!"<<endl;/如果不在停车场，不符合题目输入要求3）打印停车场上的序列：void PrintStack ()int i;Queueptr p;fout<<"Stack: "if (p1=0) fout<<"Empty!"<<endl;/此时停车场没有车else

11、 /按顺序输出序列for (i=0; i<p1; i+)fout<<stacki.number<<' 'fout<<endl;所有8数据结构实验报告作者：朱之凯4）打印便道上的序列：void PrintQueue ()Queueptr p;fout<<"Queue: "if (p2=0) fout<<"Empty!"<<endl;/此时停车场没有车else /按顺序输出序列p=Q.front->next;while (p) fout<<p-&g

12、t;number<<' 'p=p->next;fout<<endl;5.主程序：int main ()所有9数据结构实验报告作者：朱之凯int num,minute;char c;Q.front=Q.rear=new LNode;fin>>n>>m>>pp;/输入停车场容量、便道容量和停车价格while (1) /按照所给指令一一操作fin>>c>>num>>minute;if (c='A') GetIn(num,minute);if (c='D'

13、;) GetOut(num,minute);if (c='P') PrintStack();if (c='W') PrintQueue();if (c='E') fout<<"Time to leave!"<<endl;return 0;【调试分析】1.该程序关于栈、队列的几个操作都是模块化的，程序调用较为方便。2.本程序主要包括栈、队列的、删除、移动、查找，每个操作的时间复杂度均为O(n+m)3.关于栈，用了顺序，空间复杂度为O(n)；关于队列，用了链表所有10数据结构实验报告作者：朱之凯，空间复杂度

14、为O(1)。综上，空间复杂度为O(n)【使用说明】用户在park.in里输入停车场容量、便道容量和停车价格，并输入各种操作；运行程序后，打开park.out直接看结果。【调试结果】park.in:（输入）34 2A1015A10210D10115A10320A10425A10530P0 0W0 0D10235D10440P00W00E00所有11数据结构实验报告作者：朱之凯park.out:（输出）No.101:Stack1No.102:Stack2No.101:10 20No.103:Stack2No.104:Stack3No.105:Queue1Stack: 102103 104Queue

15、: 105No.102: 2550No.104: 1530Stack: 103105Queue: Empty!Time to leave!【附录】源文件程序：fstreamstdio.hstdlib.hpark.cpppark.in所有12数据结构实验报告作者：朱之凯park.out【心得体会】这个题目，相比第一次的约瑟夫问题要略微复杂一点，因为这题需要综合栈与队列的操作知识。一开始我编出了它们的链表操作，然后根据该题目进行了修改。本次试验遇到的不是很多，总体来说还算顺利的。通过这次实验，我熟练掌握了栈与队列的操作，对其认识也加深了，所以说这次我有一定的收获。实验二Huffman编【题目描述】

16、1）内容：利用 Huffman 编码进行通信可以大大提高信道的利用率，缩息传输时间，降低传输成本。但是，这要求在端通过一个编码系统对待传数据进行预先编码，在接收端进行。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/系统。2）要求：一个完整的huffman编系统应该具有以下功能：A.初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立Huffman 树，并将它存入hfmTree 中。B.编码（Encoding）。利用已经建好的Huffman树（如果不在内存，则所有13数据结构实验报告作者：朱之凯应从文件hfmTree中），对文件ToBe

17、Tran中的正文进行编码，然后将结果存入文件CodeFile中。C.（Decoding）。利用已经建立好的Huffman树将文件CodeFile中的代码进行，结果存入TextFile中。D.打印代码文件（Print）。将文件CodeFile以紧凑的格式显示在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件CodePrint中。E.打印Huffman树（Tree Printing）。将已经在内存中的Huffman树以直观的形式（树或者凹入的形式）显示在终端上，同时将此字符形式的Huffman 树写入文件TreePrint中。3) 测试数据:用下表给出的字符集和频度的实际统计数据建立

18、 Huffman 树，并对以下报文进行编码和译码：“THIS PROGRAM IS MY FAVORITE”。4）输入输出:字符集大小 n，n个字符和 n个权值均从终端读入，初始化后的huffman树在hfmTree文件中，待编码文件为ToBeTran,编码结果以文本的方式在文件CodeFile中，文件存在TextFile中,打印的编码和赫夫曼树分别在CodePrint和TreePrint文件中。所有14数据结构实验报告作者：朱之凯【需求分析】1.本程序主要求哈夫曼树的建立、编码与译码应用。2.根据题目要求编辑输入文件，运行程序后可以直接在输出文件中看结果。【概要设计】1.为了实现上述功能，需

19、要二叉树的抽象数据类型：ADT BinaryTree数据对象：D=ai|aiElemSet,i=1,2,.,n,n>=0,ElemSet 为元素集合数据关系：R=若 D=，则二叉树为空数；否则满足1）D 中存在唯一的根元素root,它没有前驱2）若D-root=,则R=；否则存在D-root的一个划分 Dl 和Dr，则DrDl=；3）若 D1，则 Dl 中存在唯一元素x1，root,x1R,且存在 Dl 上的关系Rl 是 R 的子集；同样若Dr，则Dr 中存在唯一元素Xr，<root,xr>R，且存在 Dr 上的关系Rr 属于R；R=<root,xl>,<r

20、oot,xr>，Rl，Rr4）（Dl，Rl）和（Dr，Rr）也是一棵符合定义的二叉树基本操作：InitBiTree(&T);/初始化空二叉树所有15数据结构实验报告作者：朱之凯DestroyBiTree(&T);/销毁二叉树CreateBiTree(&T);/创建二叉树ClearTree(&T);/清空二叉树TreeEmpty(T);/是否空树TreeDepth(T);/返回二叉树深度Root(T);/返回二叉树树根Parent(T,x);/返回T 中 x 的双亲LeftChild(T,x);/返回T 中 x 的左孩子RightChild(T,x);/返回

21、T 中 x 的右孩子LeftSibling(T,x);/返回T 中 x 的左兄弟RightSibling(T,x);/返回T 中 x 的右兄弟InsertChild(&T,x,LR,c);/二叉树子树DeleteChild(&T,x,LR);/删除二叉树子树TraverseTree(T,visit();/遍历二叉树2.本程序保护模块主程序模块树单元模块：实现数的抽象数据类型调用关系：主函数=树单元模块【程序】所有16数据结构实验报告作者：朱之凯1.头文件：#include <stdio.h>#include <stdlib.h>#include <

22、string.h>#include <fstream>#include <assert.h>using namespace std;ifstream fin ("huff.in");ifstream fin1 ("ToBeTran.txt");ifstream fin2 ("CodeFile.txt");ifstream fin3 ("CodeFile.txt");ofstream fout ("huff.out");ofstream fout1 ("hf

23、mTree.txt");ofstream fout2 ("CodeFile.txt");ofstream fout3 ("TextFile.txt");ofstream fout4 ("CodePrint.txt");ofstream fout5 ("TreePrint.txt");2.树的元素、结构类型：struct Huffchar code100;char name;所有17数据结构实验报告作者：朱之凯int weight;int parent,lChild,rChild;HT70;struct i

24、nfochar name;int weight;w30;3.全局变量：int n;char S100;4.建立哈夫曼树以及编码：1）选择最小的两个点：void Select (int x, int &s1, int &s2)int i,min1,min2;min1=min2=10000000;/初值视为无穷大for (i=1; i<x; i+)/寻找权值最小的点，if (HTi.weight<min1 && HTi.parent=0) min1=HTi.weight;所有18数据结构实验报告作者：朱之凯s1=i;for (i=1; i<x; i

25、+) /寻找权值第二小的点if (i=s1) continue;if (HTi.weight<min2 && HTi.parent=0) min2=HTi.weight;s2=i;2）建立哈夫曼树：void HuffmanTree ()/根据给定的n个权值，构造哈夫曼树int m,i,s1,s2;m=n*2-1;/计算哈夫曼树节点总数for (i=1; i<=m; i+) /初始化HT数组HT=i<=n?:'0'HTi.weight=i<=n?wi.weight:0;HTi.lChild=HTi.rChild=H

26、Ti.parent=0;所有19数据结构实验报告作者：朱之凯for (i=n+1; i<=m; i+) /主循环，完成n-1次合并Select(i,s1,s2);/*在HT1.i-1中选择parent为0且weight为最小的两个节点，其下标分别为s1和s2*/HTi.lChild=s1;HTi.rChild=s2;HTi.weight=HTs1.weight+HTs2.weight;HTs1.parent=HTs2.parent=i;3）根据编好的哈夫曼树来编码：/*先序遍历哈夫曼树HT，求得每个叶子节点的编码字符串，存入HTroot.code里面，其中S为字符串，用来遍历路径，roo

27、t是HT中根节点的位置下标，len为S的长度*/void Coding (int root,int len)int i;if (root!=0) /当树为空if (HTroot.lChild=0) /root为树叶Slen='0'/字符串结束标志0进栈for (i=0; i<=len; i+)叶子的哈弗曼编码所有20数据结构实验报告作者：朱之凯HTroot.codei=Si;Slen='0'/向左转，进栈Coding(HTroot.lChild,len+1);/遍历左子树Slen='1'/向右转，进栈Coding(HTroot.rChild

28、,len+1);/遍历右子树4）综合：void Initialization ()int i;fin>>n;/输入字母种类数=' '/第一个元素存空格fin>>w1.weight;for (i=2; i<=n; i+)fin>>>>wi.weight;HuffmanTree();/建立哈夫曼树Coding(2*n-1,0);/哈夫曼编码for (i=1; i<=n; i+) /打印哈夫曼树建立情况fout1<<HT<<": "<&

29、lt;HTi.weight<<' '所有21数据结构实验报告作者：朱之凯fout1<<HTi.parent<<' '<<HTi.lChild<<' 'fout1<<HTi.rChild<<' '<<HTi.code<<endl;5.对段落进行编码：void Encoding ()int i,j;string st;char ch;fin1>>st;/输入一串明文while (!fin1.eof() /直到读完明文

30、for (i=0; i<st.length(); i+) ch=sti;/取明文中的一个字符for (j=0; j<=n; j+)/找出该字符所对应的编码if (HT=ch) fout2<<HTj.code;break;fin1>>st;所有22数据结构实验报告作者：朱之凯if (fin1.eof() break;/文件最后一个字符将会读两遍fout2<<HT1.code;fout2.seekp(0,ios:beg);/将写文件指针置首，便于下面读文件6对已编码的文件复原（）：void Decoding ()int node;char

31、 ch;node=2*n-1;fin2.seekg(0,ios:beg);/读文件指针置首fin2>>ch;while (!fin2.eof() if (ch='0') node=HTnode.lChild;/遇0则左转if (ch='1') node=HTnode.rChild;/遇1则右转if (HTnode.lChild=0) /找到叶子节点了，目前一段编码就对应那个字母fout3<<HT;node=2*n-1;所有23数据结构实验报告作者：朱之凯fin2>>ch;7.以标准形式打印编码：void Pr

32、int ()int i=0;char ch;fin3>>ch;while (!fin3.eof() fout4<<ch;i+;if (i=50) /一行输出50个字母fout4<<endl;i=0;fin3>>ch;所有24数据结构实验报告作者：朱之凯8.打印哈夫曼树：void Tree_Printing(int root,int len)/*先右子树，再根节点，最后左子树，这样就可以看到竖立状态的哈夫曼树*/int i;if (root!=0) Tree_Printing(HTroot.rChild,len+1);for (i=0; i<

33、len*2; i+) fout5<<' 'if (root=1) fout5<<'1'<<endl;else fout5<<HT<<endl;Tree_Printing(HTroot.lChild,len+1);9.主程序：int main ()Initialization();Encoding();Decoding();Print();所有25数据结构实验报告作者：朱之凯Tree_Printing(2*n-1,0);return 0;【调试分析】1.该程序由题目所给小题分模块处理，程

34、序调用直观而且方便。2.程序部分为编码与，所需时间复杂度为O(m*log2n) 其中m为明文长度，n为明文字母种类数。别的算法平均来说时间复杂度为O(n)。综合上述，整个程序的时间复杂度为 O(n2)3.所有算法的空间复杂度都为O(n)【使用说明】用户在huff.in输入题目中表的信息，在ToBeTran.txt输入待编码的文字，在hfmTree.txt看哈夫曼树的建立情况，在 CodeFile.txt和CodePrint.txt看编码的结果（后者为标准输出），在TextFile.txt中看的结果，在TreePrint.txt中看打印好的哈夫曼树（由于给的数据过多，不是很直观）【调试结果】tr

35、ee.in:（输入）27186所有26数据结构实验报告作者：朱之凯A64B13C22D32E103F21G15H47I57J1K5L32M20N57O63P15Q1R48S51T80U23V8所有27数据结构实验报告作者：朱之凯W18X1Y16Z1hfmTree.txt:（输出）: 1865000111A:6445001010B:133300100000C:22370000000D:32390010110E:103 48 0 0 010F:213600110011G:153300100001H:4741000001I:5743000110J:1 28 0 0 1100001000K:5 31

36、0 0 11000011L:32390010111M:203600110010N:5743000111O:6344001001所有28数据结构实验报告作者：朱之凯P:15 34 0 0 100010Q:1 28 0 0 1100001001R:4842000010S:5142000011T:8046001101U:23370000001V:8 32 0 0 1100000W:18 35 0 0 110001X:1 29 0 0 1100001010Y:16 34 0 0 100011Z:1 29 0 0 1100001011ToBeTran.txt：（输入）THIS PROGRAM IS MY

37、 FAVORITECodeFile.txt：（输出+输入）实际上为1行0001100000TextFile.txt：（输出）THIS PROGRAM IS MY FAVORITE所有29数据结构实验报告作者：朱之凯CodePrint.txt：（输出）0010010101011000001011000001001001001101101010TreePrint.txt：（输出）10T0F0M0W0K0Z0X0Q0J0V0L0D0A0O0Y0O表示中间节点所有30数据结构实验报告作者：朱之凯P0G0B0N0I0E0S0R0H0U0C【附录】源文件程序：fstreamstdio.hstdlib.hs

38、tring.hassert.hhuff.inhfmTree.txtToBeTran.txt所有31数据结构实验报告作者：朱之凯CodeFile.txtTextFile.txtCodePrint.txtTreePrint.txt【心得体会】这次实验我花了10天左右，耗时是最长的，遇到的也是非常多的。这道题本身就是非常繁琐复杂的，但是，再大的问题也总是由无数个小问题所的，要想解决这个问题，必须一步步把子问题一一解决。我先是按照书上的哈夫曼树算法把一些基本问题解决了，并模仿其算法将编好了。前期工作遇到的麻烦不是很多，但到了后来出现了一个大：其中的一个文件CodeFile，它既是输入，也是输出，况且输

39、入两遍。一开始我束手无策，不知如何是好。好在通过袁的耐心指导，加之我查的资料，终于知道C+环境下的关于文件的操作，最后了！这次试验，收获是巨大的。我不仅掌握了哈夫曼树的各种操作，也对树有了进一步的了解。当然，我了领悟到了一人生哲理：生活中复杂的事情其实都是由一个个小的事情所，要想做成大事，必须认真地把每一件小事做好。实验三管道铺设施工的最佳方案所有32数据结构实验报告作者：朱之凯【题目描述】1）内容：需要在某个城市n个居民小区之间铺设煤道，则在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽

40、可能小，这个问题即为求无向网的最小生成树。2）要求：在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的采用邻接表的结构。3)测试数据:使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。所有33数据结构实验报告作者：朱之凯4）输入输出:参考示例中图的创建方式，从键盘或文件读入上图中的无向网，以顶点对(i,j)的形式输出最小生成树的边。【需求分析】1. 用图的领接表储存铺设网的信息2. 用Prim算法求该无向网的最小生成树3. 用户输入完毕后，程序自动建立输出文件，可直接看结果【概要分析】1.为

41、了实现上述功能，需要图的抽象数据类型：ADTGraph 数据对象：D=ai|aiElemSet,i=1,2,.,n,n>=0,ElemSet为元素集合数据关系：R=<ai-1,i>|ai-1,aiD,i=1,2,.,n基本操作：CreateGraph(&G,V,VR);/创建图GDestroyGraph(&G);/销毁图GLocateVex(G,u);/返回u 在 G 中的位置GetVex(G,v);/返回G 中 v 顶点的值PutVex(&G,v,value);/为G 中 v 结点赋值为valueFirstAdjVex(G,v,w);/返回G 中v

42、的第一个邻接点NextAdjVex(G,v,w);所有34数据结构实验报告作者：朱之凯/返回G 中相对于 w 的v 的下一个邻接点InsertVex(&G,u);/结点DeleteVex(&G,v);/删除结点InsertArc(&G,v,w);/在G 中v 和w 之间弧<v,w>DeleteArc(&G,v,w);/在G 中删除弧<v,w>DFSTraverse(G,v,visit();/深度优先遍历BFSTraverse(G,v,visit();/广度优先遍历2.本程序保护模块主程序模块图单元模块：实现图的抽象数据模型调用关系：主程序

43、模块=图单元模块【详细设计】1.头文件：#include <fstream>#include <stdio.h>#include <stdlib.h>using namespace std;所有35数据结构实验报告作者：朱之凯ifstream fin ("graph.in");ofstream fout ("graph.out");2.邻接表类型：typedef struct ArcNodeint AdjVex;float money;struct ArcNode *NextArc;ArcNode;typedef st

44、ruct VertexNode /float data;struct ArcNode *FirstArc;VertexNode;VertexNode vertices20;3.全局变量：int n,m;int adjvex10;/建立的最小生成树4.创建图：void CreateGraph ()所有36数据结构实验报告作者：朱之凯int i,x,y;float mo;ArcNode *p1,*p2;fin>>n>>m;for (i=0; i<m; i+) /此为无向图，所以经行两次操作fin>>x>>y>>mo;p1=new ArcNode;/分配边结点空间p1->money=mo;p1->AdjVex=y;p1->NextArc=verticesx.FirstArc;verticesx.FirstArc=p1;p2=new ArcNode;p2->AdjVex=x;p2->money=mo;p2->NextArc=verticesy.FirstArc;verticesy.FirstArc=p2;5.Prim 算法求最小生成树：void Prim (int v0) 所有37数据结构实验报告作者：朱之凯float lowcost20,min,mo;in