数据结构实验报告(重邮)5个(共41页).docx

《数据结构实验报告(重邮)5个(共41页).docx》由会员分享，可在线阅读，更多相关《数据结构实验报告(重邮)5个(共41页).docx（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构实验报告学院： 班级：姓名： 学号：实验一 线性链表的实现与操作题目：设计一个100位以内的长整数加减运算的程序班级： 姓名： 学号： 完成日期：一、需求分析1、 本实验中，100位长整数的每位上的数字必须为数字09之间，长整数的位数并要求100位以内。测试的时候输入数据，当输入回车键的时候结束输入，如果输入的字符不符合题目要求，则程序能过滤这些不符合要求的字符。2、演示程序以用户和计算机的对话方式执行，即在计算机显示“提示信息”后之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中不符合要求的字符）和运算结果显示在其后。3、程序执行的

2、命令包括：（1）创建第一个整数（100以内）；（2）执行加法或者减法；（3）创建第二个整数（100以内）；（4）结束。二、概要设计为实现上述程序功能，可以用链表或者长数组表示长整数，如果用数组表示长整数有个缺点就是长整数不能无限长，而链表能动态开辟空间，它克服了这个缺点，所以次试验用链表来表示长整数。1、链表的抽象数据类型定义为：ADT Number数据对象：D=ai| ai（0，1，9），i=0,1，2，n，n0数据关系：R=| ai-1, aiD,i=1,2，n基本操作：CreateList（&L）操作结果：创建一个链表L。PrintList（L）初始条件：链表L已存在。操作结果：在屏幕上

3、输出链表的值。PlusList（L1，L2，a）初始条件：链表L1，L2已存在，a为+ or 表示加减。操作结果：将两链表的值相加然后在屏幕上输出。DestroyList（&L）初始条件：链表L已存在。操作结果：销毁链表L。 ADT Number2、本程序包含五个模块：int main()定义变量；接受命令；处理命令；return 0；各模块之间的调用关系如下：主程序模块 L1 L2创建链表模块创建链表模块 +or - ： L2 L1输出链表模块输出链表模块 +or - =两链表加减模块 L1 L2销毁链表模块结束销毁链表模块三、详细设计1、定义头文件#include#include#defi

4、ne LEN sizeof(Number)typedef struct number Number;struct numberint data;Number *next;Number *prior;/void main()void DestoryList(Number *);/释放链表void PutNumber(Number *);/将求得的结果输出Number *GetNumber();/创建链表，放被加数与加数Number *JiaFa(Number *num_1,Number *num_2);/加法函数Number *JianFa(Number *num_1,Number *num_2

5、);/减法函数Number *number_1,*number_2,*number;char ch;/存放运算符号printf(Enter the first long number:);number_1=GetNumber();printf(put +or-:);ch=getchar();fflush(stdin);/吸收不相关的字符printf(Enter the second long number:);number_2=GetNumber();if(ch=+)number=JiaFa(number_1,number_2);elseif(ch=-)number=JianFa(number

6、_1,number_2);printf(n=n);PutNumber(number);DestoryList(number);DestoryList(number_1);DestoryList(number_2);printf(链表释放完成。n);Number *GetNumber() /得到两个链表Number *p,*q,*List;char ch;p=(Number *)malloc(LEN);List=p;List-prior=NULL;List-data=0;/加法时，放最高位进的1，否者999+1=000ch=getchar();while(ch!=n)if(ch=0&chdata

7、=ch-0;p-next=q;q-prior=p;p=q;ch=getchar();p-next=NULL;List-prior=NULL;return List; /加法分两种情况长度相同与不同Number *JiaFa(Number *num_1,Number *num_2) /返回的数据为逆序Number *p,*q,*r,*s,*num=NULL;int i=0,j=0;r=num;p=num_1;while(p-next!=NULL)i+;p=p-next;/i表示number1数字的长度 p指向number节点q=num_2;while(q-next!=NULL)j+;q=q-ne

8、xt;/j表示number2数字的长度 q指向number节点s=(Number *)malloc(LEN);s-prior=NULL;s-next=NULL;num=s;while(i-&j-)s-data=p-data+q-data;if(s-data9)s-data-=10;/*处理两数相加大于9的情况，后面还有if(ij)/在长的数据上调整p-prior-data+;elseq-prior-data+;r=(Number *)malloc(LEN);s-next=r;r-prior=s;s=r;p=p-prior;q=q-prior;r=s=s-prior;/去掉最后一个没数据的节点f

9、ree(s-next);s-next=NULL;if(ij)while(i-)if(p-data9)p-data-=10;/*p-prior-data+;s=(Number *)malloc(LEN);s-data=p-data;p=p-prior;r-next=s;s-prior=r;r=s;if(p-data0)/*s=(Number *)malloc(LEN);s-data=p-data;r-next=s;s-prior=r;r=s;elsewhile(j-)if(q-data9)/*q-data-=10;q-prior-data+;s=(Number *)malloc(LEN);s-d

10、ata=q-data;q=q-prior;r-next=s;s-prior=r;r=s;if(q-data0)/*s=(Number *)malloc(LEN);s-data=q-data;r-next=s;s-prior=r;r=s;s-next=NULL;/将最后一个next置空return num; /减法分3中情况：被减数长度大于、小于、等于减数长度 Number *JianFa(Number *num_1,Number *num_2) /返回的数据也为逆序Number *p,*q,*r,*s,*num=NULL;int i=0,j=0;r=num;p=num_1;while(p-ne

11、xt!=NULL)/i表示number1数字的长度 p指向number节点i+;p=p-next;q=num_2;while(q-next!=NULL)/j表示number2数字的长度 q指向number节点j+;q=q-next;s=(Number *)malloc(LEN);s-prior=NULL;s-next=NULL;num=s;if(idata=q-data-p-data;if(s-datadata+=10;q-prior-data-;r=(Number *)malloc(LEN);s-next=r;r-prior=s;s=r;p=p-prior;q=q-prior;j-;/使i，

12、j同时变化r=s=s-prior;/去掉最后一个没数据的节点free(s-next);s-next=NULL;while(j-)if(q-datadata+=10;q-prior-data-;s=(Number *)malloc(LEN);s-data=q-data;q=q-prior;r-next=s;s-prior=r;r=s;s-data=0-s-data;/反号，因为节点里不能放符号，而直接在最高位前加负号最简单s-next=NULL;elseif(i=j)i=j=1;p=num_1;q=num_2;while(p-data=q-data)p=p-next;q=q-next;num_1

13、=(Number *)malloc(LEN);num_1-prior=NULL;num_1-data=0;num_1-next=p;num_2=(Number *)malloc(LEN);num_2-prior=NULL;num_2-data=0;num_2-next=q;while(p-next!=NULL)/i表示number1数字的长度 p指向number节点i+;p=p-next;q=num_2;while(q-next!=NULL)/j表示number2数字的长度 q指向number节点j+;q=q-next;if(num_1-next-datanum_2-next-data)whi

14、le(i-)s-data=p-data-q-data;if(s-datadata+=10;p-prior-data-;r=(Number *)malloc(LEN);s-next=r;r-prior=s;s=r;p=p-prior;q=q-prior;r=s=s-prior;/去掉最后一个没数据的节点free(s-next);while(s-data=0&s-prior!=NULL)/去掉前面多余的0，否则-=s=s-prior;free(s-next);if(num_1-next-datanext-data)while(i-)s-data=q-data-p-data;if(s-datadat

15、a+=10;q-prior-data-;r=(Number *)malloc(LEN);s-next=r;r-prior=s;s=r;p=p-prior;q=q-prior;r=s=s-prior;/去掉最后一个没数据的节点free(s-next);while(s-data=0&s-prior!=NULL)/去掉前面多余的0，否则-=s=s-prior;free(s-next);s-data=0-s-data;/反号，因为节点里不能放符号，而直接在最高位前加负号最简单s-next=NULL;elseif(ij)while(j-)s-data=p-data-q-data;if(s-datadat

16、a+=10;p-prior-data-;r=(Number *)malloc(LEN);s-next=r;r-prior=s;s=r;p=p-prior;q=q-prior;i-;r=s=s-prior;/去掉最后一个没数据的节点free(s-next);s-next=NULL;while(i-)if(p-datadata+=10;p-prior-data-;s=(Number *)malloc(LEN);s-data=p-data;p=p-prior;r-next=s;s-prior=r;r=s;while(s-data=0&s-prior!=NULL)/去掉前面多余的0，否则1000-1=

17、0999s=s-prior;free(s-next);/s-data=0-s-data;/反号，因为节点里不能放符号，而直接在最高位前加负号最简单s-next=NULL;return num;void PutNumber(Number *num) /链表的合并Number *p;int k=1,i;/k为数据长度，i控制,p=num;while(p-next!=NULL)p=p-next;k+;i=4-k%4;while(k-)i+;printf(%d,p-data);p=p-prior;if(k!=0&i%4=0)/长度为k的数据，在k%4个数字后开始输出,数据输出完后不输出,putchar

18、(,);putchar(n);void DestoryList(Number *list) /销毁链表Number *p,*q;p=list;while(p)q=p-next;free(p);p=q;四、调试分析1、这个程序是看了原模版的分析才了解到具体是怎样去存储长整数。进位的部分很纠结，不知道用什么去移动，然后才知道直接用指针去操作就好了。2、本程序有些代码重复出现，影响了代码的编译效率。 3、本程序模块划分比较合理，且把指针全部封装在链表模块中，操作方便。 五运行结果 六、实验环境（1）Win8系统，兼容（2）编程环境：VC6.0+简体中文版 七、实验体会通过此次实验，我理解了线性链表的

19、逻辑结构和链式存储结构并一定程度的掌握了线性链表的基本操作及应用。这是一个培养学生灵活使用结构解决实际问题的能力。开始想的是要用数组去存储长整数，但是看过实验报告的模版后，了解到原来还可以用链表来存如此大的长整数。这个思路很大的启发了我。觉得以后编程时也是可以运用的一种重要思想。 而且我了解到，在编写程序的时候养成良好编程风格很重要，这样可以使以后自己或者他人阅读这个程序的难度大大降低。实验二 栈和队列的应用题目：利用队列宽度优先进行迷宫求解班级： 姓名： 学号： 完成日期：一、需求分析1.本实验中，要求用数组表示迷宫，并建立队列，利用队列实现宽度优先搜索。从而得到迷宫的解。2. 队列是顺序存

20、储结构，其存储结构示意图如下: a1 a2 a3 a4 a5an 队头队尾3、程序执行的命令包括：（1）输出迷宫，并介绍迷宫规则；（2）输入测试数据；（3）输出迷宫解答方案；4、测试数据 Please input the start point:0 0Wrong start point,please input again: 2 3Output: 图示；2、算法概要设计1.建立如下函数，抽象数据类型定义为：ADT sqllistvoid EnterQ(int i,int j,int k);定义一个入队的函数 void DelectQ(int *i,int *j,int *k);获取当前结点的序

21、号和对应的迷宫坐标，然后出列，返回函数值； bool GetNextPos(int *i ,int *j,int count);布尔值，得到下一个邻接点的位置。void ShortestPath_BFS(int i,int j);利用广度优先遍历寻找最短路径的函数； void ShortestPath();输出最短路径2.函数声明；void main()初始化；建立变量；调用函数；本程序分为以下三个模块：变量声明模块 调用构建函数模块 调用主程序模块；三、 详细设计#include void EnterQ(int i,int j,int k); /定义一个入队的函数void DelectQ(i

22、nt *i,int *j,int *k); /出列函数，获取当前结点的序号和对应的迷宫坐标，然后出列，返回函数值 bool GetNextPos(int *i ,int *j,int count); /布尔值，得到下一个邻接点的位置。 void ShortestPath_BFS(int i,int j); /利用广度优先遍历寻找最短路径的函数 void ShortestPath(); /输出最短路径 void Print(); int Map1010 = 1,1,1,1,1,1,1,1,1,1, 1,0,0,1,0,0,0,1,0,1, 1,0,0,1,0,0,0,1,0,1, 1,0,0,0

23、,0,1,1,0,0,1, 1,0,1,1,1,0,0,0,0,1, 1,0,0,0,1,0,0,0,0,1, 1,0,1,0,0,0,1,0,0,1, 1,0,1,1,1,0,1,1,0,1, 1,1,0,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,1,1,1; struct Node int parent_id; /保存父结点的位置 int node_id; /当前结点的序号 int x,y; /当前结点对应的坐标 Q10*10; int front = 0,rear = 0;/队列头指针和尾指针void main() coutprogamming introduce：n1.

24、output the shortest path；n2.the exit is at the right botom,adjust it if you like.nn; coutstart maps：endl; Print(); int i,j; reinput: coutplease input the start point（x,y）example：x y：ij; if(Mapij) coutWrong start point,please input again！endl;goto reinput; ShortestPath_BFS(i,j); coutthe shortest path

25、 to get out：endl; ShortestPath(); void EnterQ(int i,int j,int k) Qrear.x = i; Qrear.y = j; /保存当前结点对应的坐标位置 Qrear.parent_id = k; /保存父结点的序号 Qrear.node_id = rear; /保存当前结点序号 rear+; void DelectQ(int *i,int *j,int *k) *i = Qfront.x; *j = Qfront.y; *k = Qfront.node_id; front+;/一个节点出列 bool GetNextPos(int *i

26、,int *j,int count) switch(count) case 1:(*j)+; return 1; /向右走 case 2:(*i)+; return 1; /向下走 case 3:(*j)-; return 1; /向左走 case 4:(*i)-; return 1; /向上走 default: return 0; void ShortestPath_BFS(int i ,int j) int count,m,n,k; EnterQ(i,j,-1); Map11 = 1;/入队起点,标记已走过的起点 while(true) count = 1; DelectQ(&i,&j,&

27、k); n = i,m = j; while(GetNextPos(&i,&j,count) count+; if(!Mapij) EnterQ(i,j,k); Mapij = 1; if(i = 8 & j = 9) return; /到达终点,(8,9)是默认终点，可以任意修改 i = n; j = m; /遍历当前坐标的所有相邻位置 void ShortestPath() int i,j,k,sum(0) ; k = rear-1; while(k != -1) i = Qk.x; j = Qk.y; Mapij = 2; k = Qk.parent_id; cout 0 1 2 3 4

28、 5 6 7 8 9endl; for(i = 0;i 10;i+) couti; for(j = 0;j 10;j+) if(Mapij=2) sum+; cout; else cout; coutendl; cout最短路径长度：sumendl; void Print() cout 0 1 2 3 4 5 6 7 8 9endl; for(int i = 0;i 10;i+) couti; for(int j = 0;j 10;j+) if(Mapij) cout; else cout; coutendl; 四程序调试1.对迷宫图进行了测试，用点（0，0），（4，2）（2，2）作为起点，在

29、终点位置相同的情况下进行了测试，看程序运行后输出的结果是否正确。 测试结论：对于测试地图在不同起始位置输出完全正确。2.测试时也有输入错误的数据，结果显示可以判别出来。五、运行结果截图如下：1.初始界面：2.输入错误的起点时：3.输入正确的起点时：给出了正确走出迷宫的路径。六实验环境1.win8操作系统，兼容。2.vc+6.0简体中文版七、实验体会这个迷宫的实验很有意思，虽然代码是在网上找到的，但是我了解了算法。并在此次编程中体会到了运用的乐趣。由于不太理解代码的含义，当初编译时有很多错误，调试了很长时间。第一次运行这个程序是在c-free5上，可能由于mingw编译器与vc不同，有很多不能识

30、别的c语言keywords出现，导致不能执行代码。至此，我知道了不同的编译器所支持的语言标准或是库函数是有一定差异的。实验三: 二叉树的实现及遍历题目：二叉树的实现与遍历班级： 姓名： 学号： 完成日期：一、需求分析 1.本实验要求构建二叉树，并完成二叉树的先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。 2.输出树的深度，最大元，最小元。 3.了解二叉树的特点及其存储结构。二、概要设计1.二叉树的抽象数据类型定义为：ADT BinaryTree D：D是具有相同特性的数据元素的集合 R：若D为空集，则R也为空，称BinaryTree为空二叉树 若D不为空集，则R=H，H是如

31、下二元关系：p: InitBiTree(&T); DestoryBiTree(&T); CreateBiTree(&T, definiation); ClearBiTree(&T); /将树清为空树 BiTreeEmpty(T); /判断树是否为空 BiTreeDepth(T); /返回树的深度 Root(T); /返回树的根 Value(T, e); /取出结点e的值 Assign(T, &e, value); /给结点e赋值为value Parent(T, e); /若e为根结点返回空，否则返回其双亲 LeftChild(T, e); /返回e的左孩子，若e无左孩子返回空 RightChi

32、ld(T, e); /返回e的右孩子，若e无右孩子返回空 LeftSibling(T, e); /返回e的左兄弟，若e是T的左孩子或无左兄弟返回空 RightSibling(T, e); /返回e的右兄弟，若e是T的右孩子或无右兄弟返回空 InsertChild(&T, &p, LR, c); /根据LR为0或1，插入c为T中p指结点的左或右子树,p所指结点的原有左或右子树则成为c的右子树 DeleteChild(&T, &p, LR); /根据LR为0或1，删除T中p所指结点的左或右子树 PreOrderTraverse(T, visit(); /先序遍历T InOrderTraverse(

33、T, visit(); /中序遍历T PostOrderTraverse(T, visit(); /后序遍历T LevelOrderTraverse(T, visit(); /层序遍历TADT Tree;2.基本操作： 函数定义；void mian()初始化；接受命令；处理命令；3.各模块间关系如下： 二叉树的构建 主程序模块 二叉树的遍历 Info的输出三详细设计1.定义头文件#include#include#include#define Max 30 /宏定义，设置结点的最大个数2.构建二叉树结构typedef struct node char data; struct node *lchild,*rchild;BinTNode; /自