[工学]中 国 地 质 大 学数据结构报告1.doc

《[工学]中 国 地 质 大 学数据结构报告1.doc》由会员分享，可在线阅读，更多相关《[工学]中 国 地 质 大 学数据结构报告1.doc（36页珍藏版）》请在三一办公上搜索。

1、 中 国 地 质 大 学 数据结构上机实习报告 课程名称 数据结构 教师姓名 李桂玲 本科生姓名 杜攀洪 本科生学号 20111003732 本科生专业 网络工程 所在院系 计算机学院 类别: 报告 日期: 2012-12 目录1. 需求分析42. 设计4 （1）设计思想4 （2）概要设计5 （3）详细设计.3. 调试分析.4. 用户手册5. .测试结果6. 源程序清单 一元稀疏多项式运算器1.需求分析 设计一个一元稀疏多项式简单计算器。 要求：（1）输入并建立两个多项式； （2）多项式a与b相加，建立和多项式c； （3）多项式a与b相减，建立和多项式d； （4）输出多项式a,b,c,d。输出

2、格式：比如多项式a为：A(x)=c1xe1+ c2xe2+ cmxem， 其中，ci和ei分别为第i项的系数和指数，且各项按指数的升幂排列，即0e1e2em。2. 设计 （1）设计思路： 定义线性表的动态分配顺序存储结构，建立多项式存储结构，定义指针*next ，利用链表实现队列的构造。定义如下的结构体 typedef struct node int x,z; /z是指数，x是系数 struct node *next;*pnode每次输入一项的系数和指数，可以输出构造的一元多项式 ；演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运

3、行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为：c1xe1+c2xe2+cnxen （2）概要设计 ：本程序主要包括三个函数：结点创建函数，将输入的多项式化为字符串转化成一个只有系数、指数、后继的结构体。pnode create(char *c,int i,int j) if(ji) return NULL;int a=0,b=0,flag=0; /处理系数。 主函数void main() cout*endl; cout*一元多项式的计算(和差)*next; free(t); （3）详细设计多项式的相加（1）功能：将两

4、多项式相加。（2）数据流入：输入函数。（3）数据流出：多项式相加后的结果。（4）程序流程图：多项式的加法流程图如图2所示。（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。 开始输入ch1和ch2是 否合并同类项结束是否同指数项系数相加后存入H中直接把q1中各项存入H中直接把q2中各项存入H存储多项式ch2的空链q2是否为空存储多项式ch1的空链q1是否为空输出H 多项式相减（1）功能：将两多项式相减。（2）数据流入：调用输入函数。（3）数据流出：多项式相减后的结果。（4）程序流程图：多项式的减法流程图如图3所示。（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，

5、进行运算。开始输入ch1和ch2是 否合并同类项结束是否调用相加函数直接把q1中各项存入H中把q2中系数改变后存H中存储多项式2的空链玩是否为空存储多项式ch1的空链q1是否为空输出H 将多余的结点空间释放 3、 调试分析 （1）测试的数据以及结果 （2） 算法的时间复杂度及改进算法的时间复杂度：一元多项式的加法运算的时间复杂度为O(m+n）,减法运算的时间复杂度为O(m-n)，其中m，n分别表示二个一元多项式的项数。问题和改进思想：在设计该算法时，出现了一些问题，在创建空间的时候没有好好地利用空间，特别是在多项式相加的时候会浪费空间使空间复杂度增加。为了使输入数据按指数降序排列，可在数据的输

6、入后先做一个节点的排序函数，通过对链表排序后再进行之后加减运算。4、 用户手册（1）本程序中包含七个函数：创建结点空间、存储多项式、相加函数、相减函数、输出函数、主函数、释放结点空间函数，利用主函数来调用其他函数来执行命令。（2）在输入多项式的时候注意不要多输入空格键，其中X要输入大写字母，否则会出现多项式不能合并同类项。（3）用户根据自己的要求来选择函数所要执行的功能。5数据测试以及结果 【测试数据示例】（1）(x+x100)+(x100+x200)（3）(2x+5x8-3x11)+(7-5x8+11x9)（4）(6x-3-x+4.4x2-1.2x9)-(-6x-3+4.4x2+7.8x15

7、) 6、源程序清单 源程序见电子档 唯一的确定一棵二叉树1、 需求分析 如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的一棵二叉树。 【基本要求】 已知一棵二叉树的前序和中序序列，试设计完成下列任务的一个算法： （1）构造一棵二叉树； （2）证明构造正确（即分别以前序和中序遍历该树，将得到的结果与给出的序列进行比较）。 （3）对该二叉树进行后序遍历，输出后序遍历序列。 （4）用凹入法输出该二叉树。2、 设计 （1）设计思想 存储结构：采用顺序结构 主要基本算法思想 ： 定义如下结构体来定义数据类型typedef struct Nodechar data;struct Node *L

8、eftChild;struct Node *RightChild;BiTNode; 而在主函数中创建两个数组char PreMaxSize和char InMaxSize，分别用来存储前序序列和中序序列： 将前序和中序序列分别读入数组char PreMaxSize和char InMaxSize。 根据定义，前序序列中第一个元素一定是树根，在中序序列中该元素之前的所有元素一定在左子树中，其余元素则在右子树中。所以， 首先从数组char PreMaxSize中取出第一个元素char Pre0作根结点，然后在数组char InMaxSize中找到char Pre0，以它为界，在其前面的是左子树中序序列

9、，在其后面的是右子树中序序列。 若左子树不为空，沿前序序列向后移动，找到左子树根结点，转。 左子树构造完毕后，若右子树不为空，沿前序序列向后移动，找到右子树根结点，转。 前序序列中各元素取完则二叉树构造完毕。 对二叉树进行前序和中序遍历，并将结果分别与数组char PreMaxSize和char InMaxSize进行比较，若相同，则证明二叉树构造正确。 （2）概要设计：本程序主要包括四个函数： 初始化函数， void Initiate(BiTNode *root)*root=(BiTNode *)malloc(sizeof(BiTNode);(*root)-LeftChild=NULL;(*

10、root)-RightChild=NULL; 前序、中序、后序遍历函数，用以遍历所产生的树的前序、中序和后序序列，并检验根据题设所创建的树是否是唯一正确的树 void PreOrder(BiTNode *T,void Visit(char item) /前序遍历函数 void InOrder(BiTNode *T,void Visit(char item) /中序遍历函数 void PostOrder(BiTNode *T,void Visit(char item) /后序遍历函数 创建树函数，根据题设中给出的前序和中序序列创建出唯一的树 void CreateTree(BiTNode *T,

11、int pre_f,int pre_l,int in_f,int in_l,char pre,char in)int interval=0;/int same=in_f;if(prepre_f!=insame) 主函数main（），void main()BiTNode *T;int Pre_len,In_len;char PreMaxSize;/前序序列char InMaxSize;/中序序列printf(请输入前序序列：);scanf(%s,&Pre); （3）详细设计 首先输入前序和中序序列，然后根据所输入的序列创建出唯一的二叉树void CreateTree(BiTNode *T,int

12、 pre_f,int pre_l,int in_f,int in_l,char pre,char in)int interval=0; /中序遍历数组的第一个下标int same=in_f; /*same为计数器，用来确定根节点的位置，初始化为中序的起始地址 if(prepre_f!=insame) while(prepre_f!=insame) /在中序序列中找到根节点 same+; interval+; /数组下标自增 if(interval=0)&(pre_f=pre_l) /找到了叶节点，也是递归出口 T-data=prepre_f; /确定根节点 T-LeftChild=NULL;

13、/根结点的左孩子制空 T-RightChild=NULL; /根结点的左孩子制空if(interval!=0)&(intervalLeftChild=(BiTNode *)malloc(sizeof(BiTNode); /*申请左子树根结点的内存*/ T-RightChild=(BiTNode *)malloc(sizeof(BiTNode); /*申请右子树根结点的内存*/ T-data=prepre_f; CreateTree(T-LeftChild,pre_f+1,pre_f+interval,in_f,in_f+interval-1,pre,in); /*递归调用creattree函数

14、，创建根节点左子树*/ CreateTree(T-RightChild,pre_f+interval+1,pre_l,in_f+interval+1,in_l,pre,in); /*递归调用creattree函数，创建根节点右子树*/if(interval!=0)&(interval=pre_l-pre_f)/只有左子树 T-LeftChild=(BiTNode *)malloc(sizeof(BiTNode); /*申请左子树根结点的内存*/ T-data=prepre_f; CreateTree(T-LeftChild,pre_f+1,pre_l,in_f,in_f+interval-1,

15、pre,in); /*递归调用creattree函数，创建根节点左子树*/ T-RightChild=NULL;if(interval=0)&(pre_f!=pre_l)/只有右子树 T-RightChild=(BiTNode *)malloc(sizeof(BiTNode); /*申请右子树根结点的内存*/ T-data=prepre_f; T-LeftChild=NULL; CreateTree(T-RightChild,pre_f+interval+1,pre_l,in_f+interval+1,in_l,pre,in);/*递归调用creattree函数，创建根节点右子树*/ 根据创建

16、出的树将其打印，然后调用遍历函数对其进行前序、中序和后序遍历 void PreOrder(BiTNode *T,void Visit(char item) /前序遍历函数 void InOrder(BiTNode *T,void Visit(char item) /中序遍历函数 void PostOrder(BiTNode *T,void Visit(char item) /后序遍历函数 函数调用关系 Main- Initiate(&T)- CreateTree(T,0,Pre_len-1,0,In_len-1,A,B)- PrintBiTree(T,0)- PreOrder(T,Visit)

17、- InOrder(T,Visit)- PostOrder(T,Visit) 3、调试分析（1） 调试遇到的主要问题以及解决方案： 最开始时写遍历函数时，还不知道为什么我的遍历函数有问题，原来是因为我没有Visit()函数，然后参看课本，在课本上找到Visit()函数，发现为题解决了；刚开始写时不知道怎么将二叉树表示出来，参看别人的也看不懂，结果在课本上发现了打印二叉树的函数，于是将他写在程序上。 写二叉树的函数时，不知道怎么在前序中找到它的左子树，然后参看网上的答案在中序中找根节点时设计了一个计数器same，然后在前序中从第二个元素找same个元素即为左子树。 （2） 对设计和编码的回顾讨论

18、和分析 本次编程在很大程度上参照了网上别人写的程序，虽然如此，还是对别人的程序有很多的不理解，这也让我意识到自己的编程能力有多弱。根据前序和后序唯一的确定一颗二叉树，在草稿纸上做很容易，但是要让他编译出来让计算机来完成还是一件很困难的事。整个程序设计费了很多的时间和精力，不过有了满意的结果也是一件很令人开心的事。 （3） 时间和空间复杂度的分析 时间复杂度： 空间复杂度：（4）经验与反思总结 本次编程用到了很多的递归调用，因此我们应该很好地掌握递归函数的编写以及使用；但是同时递归函数的使用会提高程序的时间复杂度，因此在有能力编写非递归程序的情况下，尽量少的用递归函数。当然还死要很好的掌握此用法

19、。 本次编程好大程度的参看了网上的答案，同时有很多的东西也是课本上的，但由于自己不熟悉课本，对哪些程序不熟，因此花了很长的时间来编写程序。这件事告诉了我，应该牢固掌握书本上的基础知识；也昂我认识到自己的编程能力很差，我还要更加努力学习。 4、用户手册 根据要求在运行程序时，输入前序和中序序列，然后看程序运行结果是否与自己在稿纸中预算的一样。 5、测试结构 【测试数据实例一】前序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC。6、 源程序清单 见电子档 求最短路径（未完成） 1、需求分析试设计一个算法，求图中一个源点到其他各顶点的最短路径基本要求 （1）以邻接表作为存储结构； （2）

20、用Dijkstra算法求最短路径； （3）按长度非递减次序打印输出最短路径的长度及相应路径。2. 设计 （1）设计思想 存储结构：选用邻接矩阵的存储结构。邻接矩阵costij定义为int cost nn采用邻接矩阵存储，很容易判断图中两个顶点是否相连，也容易求出各个顶点的度。 主要基本算法思想：采用邻接矩阵来存储有向图并利用Dijkstra算法求出但远点到各个定点的最短路径。 建 图输入顶点与边值信息定义顶点个数开始Dijkstra算法求最短路径显示最短路径结束 程序运行的主演步骤结构图如下 Dijkstra算法的结构如下图 N设定变量，初始化dist数组，使其与costV0i相对应定义顶点V

21、0与自身的距离为0;定义经过的顶点个数为0；定义顶点集合SMAX初始化数组Si，并规定i为顶点序号将起点V0加入数组首先初始最短路径mindis为无穷大；查找离顶点V0最近的顶点，并赋值距离给mindis=distj;根据找到的顶点寻找下一个路径最短的顶点Su，并记录最短路径dis=distu+costj；dis是否大于V0直接到Su的距离； 最短路径为dist记录经过的顶点;j为寻找下一个顶点的变量添加顶点到最短路径当中；输出顶点V0到各个顶点的最短路径结束（2）概要设计 本程序主要包含四个函数 建立建图的邻接矩阵 void display(int n1) int i,j;printf(n*

22、所建图的邻接矩阵*n);for(i=0;in1;i+) printf(_%d_,i); /利用for循环输出邻接矩阵的行标 利用Dijkstra算法求最短路径 void shortdjs() /求最短路径int sMAX; /顶点集合，初始时该集合只有源点v0，然后逐步将以求得最短路径的顶点加入到该集合中，直到全部顶点都在集合S中，算法结束int mindis,dis,i,j,v0=0,u=0; /mindis标志图中最短的那一条路径for(i=0;in;i+)/初始化disti=costv0i; /初始化dist数组，顶点v0 v1 v2是与0 1 2 一一对应的pathi.pnode0=v

23、0; /初始化求到每个顶点的最短路径时都经过v0顶点pathi.num=0; /初始化记录经过的顶点数都为0si=0; /顶点集合s为空，即还未开始sv0=1; /vo定点加入到s中，等于1表示已进入该集合for(i=1;in;i+)/将最短路径定点加入到s中mindis=up; /记录最短路径for(j=1;jn;j+) /查找当前的最短路径if(sj=0 & distjmindis)u=j; /找到离上一个顶点距离最短的结点mindis=distj;/将v0到此结点的距离赋值给mindissu=1; /u定点加入到s中，u记录的是距v0最短的顶点for(j=1;jdis) /如果v0直接到

24、j的距离，大于经过u结点， v0到j结点的距离distj=dis; /最短距离记录为distpathj.num+; /记录经过的顶点数 pathj.pnodepathj.num=u; /记录经过的结点pathi.num+; /将终点i添加到路径中pathi.pnodepathi.num=i; 输出函数，将求得的最短路径输出 void dispath() /输出最短路径/system(cls);int i,j;printf(n从V0到各顶点的最短路径长度如下：n);printf(起点-终点) 最短长度 最短路径n);printf(- - -n);for(i=1;iV%d): ,i); 主函数ma

25、in（） void main()int i,p=3;for(i=0;i distj+costji,则修改disti的值。同时V0到Vi的最短路径中经过的顶点数加1，即pathi.num+; 并将经过的顶点存入数组pnode即pathi.pnodepathi.num=j f) 此时一趟求最短路径完毕，将终点V1添加到路径中。循环执行d),e),f)操作，直到全部顶点加入到S中。输出最短路径根据输出函数，将最短路径输出 void dispath() /输出最短路径/system(cls);int i,j;printf(n从V0到各顶点的最短路径长度如下：n);printf(起点-终点) 最短长度

26、最短路径n);printf(- - -n);for(i=1;iV%d): ,i); 3、调试分析 （1）记录调试过程中遇到的错误和问题 a) 当输入格式不符合程序要求时，会提示错误输入，但会出现死循环，可以定义一个标志量contin，当要停止的时候，命令contin=0，循环结束。 b) 当两顶点间没有路径时，权值为无穷大，但在本程序中只能用一个具体的数字999代替抽象的无穷大。 c) 在程序的调试过程可暂时多加一些输出语句以便及时查看一下中间运行情况。 （2）算法的时间和空间性能分析 时间复杂度 对于n个顶点的有向图，求一个顶点到其他顶点的最短路径的时间为O(n)，调整最段路径的循环攻进行了

27、n-1次，是二层循环。所以时间复杂度是O（n2）。. 空间复杂度 采用邻接矩阵来存储图，应处理两个顶点之间的关系，所以空间复杂度为O（n2）。 （3）算法设计、调试的经验和体会 Dijkstra算法在上课的时候曾作为重点讲过，所以在做查找最短路径的算法时很流畅，但是在输出最短路径的时候遇到了很大的阻力。因为在定义结点时，使用的是结构体数组，所以当处理V0到每个结点的最短路径时，导致无法具体记录经过的顶点数，只能记录源点、 4、用户手册 该程序可应用在出行指南中，用020表示出行地点，输入路径，得出最优出行路线。用户操作方法如下： 1、输入顶点个数：最大不超过20，请输入罗马数字，若输入其他符号

28、，会显示警告； 2、以“数字 数字 数字”的格式输入图的信息，输入的数字0即表示源点，前两个数字应小于顶点个数，最后一个数字应小于999。当输入“0 0 0”时，输入完成； 3、在输入完成后屏幕上直接显示邻接矩阵和最短路径。 5、测试结构 测试图形 图1 图2图1输入及运行结果：图2的输入以及运行结果： 内部排序算法的性能测试 1、需求分析教材中，每种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，取得实际计算结果。基本要求（1）对以下6种常用的内部排序算法进行比较：冒泡排序、直接插入排序、简单选择排序、快速排

29、序、希尔排序、堆排序。 （2）待排序表的表长不小于100，其中的数据要用伪随机数产生程序产生，至少要用5组不同的输入数据作比较，比较的指标为关键字的比较次数和记录的移动次数。（3） 最后要对结果进行分析，包括对各组数据得出结果波动大小的解释。 2、设计 （1）设计思想 存储结构：定义如下数据类型的的结构体 typedef struct int key; datatype; 所待排序的数据存在放数组里 主要基本算法思想 由随机数生成器产生随机数，然后测试六种常用排序方法对关键字的比较次数和移 动次数来比较它们的算法的优劣程度。 （2）概要设计 可能排序表的抽象数据类型定义 ADT Orderab

30、leList数据对象：D=|IntegerSet，i=1，2，n，n0数据关系：R1=,|,D,i=2,n基本操作：InitList（n）操作结果：构造一个长度为n，元素值依次为1，2，n的有序表。RandomizeList(d,isInverseOrder)操作结果：首先根据isInverseOrder为True或False，将表置为逆序或正序，然后将表进行d（0d8）级随机打乱。d为0时表不打乱，d越大，打乱程度越高。RecallList（）操作结果：恢复最后一次用RandomizeList随机大乱的可排序表。ListLength（）操作结果：返回可排序的长度。ListEmpty（）操作结

31、果：若可排序表为空表，则返回True，否则返回False。BubbleSort（&c，&s）操作结果：进行冒泡排序，返回关键字比较次数c和移动次数s。InsertSort（&c，&s）操作结果：进行插入排序，返回关键字比较次数c和移动次数s。SelectSort（&c，&s）操作结果：进行选择排序，返回关键字比较次数c和移动次数s。QuickSort（&c，&s）操作结果：进行快速排序，返回关键字比较次数c和移动次数s。ShellSort（&c，&s）操作结果：进行希尔排序，返回关键字比较次数c和移动次数s。HeapSort（&c，&s）操作结果：进行堆排序，返回关键字比较次数c和移动次数s。

32、ListTraveres（visit()）操作结果：依次对L中的每个元素调用函数visit（）。ADT OrderableList 本程序包含两个模块： 主程序模块： void main()初始化；do接受命令；处理命令； while （命令!=退出）； 、 可排序表单元模块： 实现可排序表的抽象数据类型;主程序模块 可排序表单元模块 （3）详细设计 起泡排序： 冒泡排序的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。算法如下：void gensort(int b,int n)int i,j;int s=0,t=0;for(i=0;in-1;i+) f