数据结构与算法实验学期总结

1、数据结构与算法实验学期总结我的数据结构班级：09计本一班学号：2009810020姓名：吴伟摘要数据结构实验的目的是为了加深对课堂知识的理解，培养实验者的动手能力和思维能力。实验中，能体会到了算法和源程序之间的区别，理解到要实现算法要做的事情，解决编写源程序时遇到的各类问题。关键字：算法、源程序、算法实现、解决问题一、数据结构与算法课程实验的主要意义的目的数据结构课程的实践性很强，许多内容如果只进行单纯的课堂讲授是根本不能够深刻认识的。例如，第二章线性表的多种存储结构的对比分析，如不上机练习，就只能靠自己背，但这样就不能有更直观、形象的认识了。因此，实验是数据结构课程的一个重要环节。首先，在实

2、验的过程中，可以会体会到源程序与算法的区别。算法是一种算法描述语言。它不是一种现实存在的编程语言。使用算法的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal,C,Java,etc)实现。它可能综合使用多种编程语言中语法、保留字，甚至会用到自然语言。因此，算法必须结构清晰，代码简单，可读性好，并且类似自然语言。源程序(sourcecode)是指未编译的按照一定的程序设计语言规范书写的，一系列人类可读的计算机语言指令。其实现起来，有时并不像算法那样看起来那么简单。例如，希尔排序的算法：voidShellSort(SSTable&L,intdlta口，intt)/按增量序列

3、dlta0t-1对顺序表L做希尔排序for(intk=0;k<t;+k)ShellInsert(L,dltak);/一趟增量为dltak的插入排序/ShellSort看到该算法，基本都会明白：又tL执行t次ShellInsert(L,dlatk)操作就能完成希尔排序。然而，要真正的实现该功能，必须有完整的代码：boolLT(chara,charb)returna<b;/重建静态查找表为按关键字非降序排序。voidShellInsert(SSTable&L,intdk)inti,j;for(i=dk+1;i<=L.length;+i)if(LT(L.elemi.key,

4、L.elemi-dk.key)/需将L.ri插入有序增量子表L.elem0=L.elemi;/暂存在L.r0for(j=i-dk;j>0&&LT(L.elem0.key,L.elemj.key);j-=dk)L.elemj+dk=L.elemj;/记录后移，查找插入位置L.elemj+dk=L.elem0;/插入/ShellInvoidShellSort(SSTable&L,intdlta,intt)for(intk=0;k<t;+k)ShellInsert(L,dltak);/一趟增量为dltak的插入排序/ShellSort所以，算法只用来说明复杂的问题

5、，并不一定可以执行。再次，实验会增强你的算法实现能力，锻炼你的思维和解决问题的能力。在我们的数据结构课上，能学到的都是各种功能算法，没有源代码。所以，如果要做实验，你就必须思考，想各种方法来实现算法。在此过程中需要解决各类问题，使源代码尽可能正确的达到算法的思想。实验中，算法的实现会让我更容易的记住所学的知识，用一个开玩笑的引用：“一朝被蛇咬，十年怕井绳”。二、概述本学期的实验内容和目的实验一实验名称：对比算法的时空效率实验目的及要求：1. 熟悉开发工具的编程环境。2. 熟悉算法语言并完成简单的算法。3. 熟悉C语言的语法，将算法上机编程实现。4. 区别算法和源程序。5. 体会用不同算法解决同

6、一个问题，体会存储结构不同对实现算法的影响。6. 学习对算法进行时空分析的基本方法。7. 了解评价一个算法的基本准则。实验主要内容：试编写求k阶(k>=2)裴波那契序列的第m项值的不同算法，并编程实现。k和m均以值调用的形式在函数参数中表现。要求：至少用两种不同的算法(如，递推、递归等等)。实验中涉及的主要实验原理：k=1时，fac(0)=0,fac(1)=1fac(n)=fac(n-1)+fac(n-2)n=2,3,4,5k=2时，fac(0)=0,fac(1)=0,fac(2)=1fac(n)=fac(n-1)+fac(n-2)n=3,4,5,6概要设计和存储结构：首先向内存申请大小

7、为k+1的空间，第0号空间用来做辅存。第k号空间放1，其他放0。然后按照斐波那契序列的计算方法计算下一项，再把整个数组左移，最后把计算出来的数放在最大位。一直循环直到算出你要的答案。存储结构为：一维数组(int*a=newintk+1;)主要算法：voidfac(intk,intm,inta)/k是斐波那契序列的阶数，m是要输出的项数，a是进行排列操作的数组int*a=newintk+1;for(i=0;i<=k;i+)ai=0;ak=1;/进行阶斐波那契序列的输出，如果要输出的项m大于阶数k,则直接/输出数组的第m+项if(m<=k)fac(m)=am;else/如果项大于阶数，

8、则先进行递推计算，再输出for(intl=1;l<=m-k;l+)/因为序列的前k项已经给出，所以要输出第nffi只用循环m-k次for(i=0;i<k;i+)ai=ai+1;for(t=0,j=0;j<k;j+)t+=aj;fac(m)=t;实验结果和结论：根据2斐波那契序列的推导公式：fac(0)=0,fac(1)=1,fac(2)=1,fac(3)=2,fac(4)=3,则上面的结果正确。同理，该结果也正确根据5斐波那契序列的推导公式：fac(0)=0,fac(1)=0,fac(2)=0,fac(3)=0,fac(4)=1,fac(5)=1,fac(6)=2,fac(7

9、)=4，由此，上面结果正确。实验分析：我的算法用的是顺序存储结构，并采用递推的计算法。我感觉好处是，代码不算太多，不是太累赘；坏处是，for循环比较多，容易混淆。一开始，程序能运行，但输出的数不对，经过查找发现是第四个for语句中的t做完一次后没有初始化(开始的程序t是在定义时初始化的)。接着，再运行，发现输出错位，经检查，第二个for循环次数不对，应该是m-k次，开始是m次，改过之后输出正确。虽然，该算法有的地方做的还算可以，但是现在看来在实验的其他方面做的不是很好，还有待改进，例如：没有考虑到斐波那契序列数据的数据类型，我用的是int这样要输出很大项的时候，int型的数据不够。实验二实验名

10、称：线性表实验目的及要求：熟悉如何使用单链表，掌握单链表的基本操作，巩固对单链表知识的认识。实验主要内容：约瑟夫环。假设有n个编号为1,2,3,，n的人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，并将其密码值作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，以此类推下去，直到所有的人全部出列为止。试设计一个程序，可以在用户确定了人数和密码的情况下，求出对应的出列顺序。实验中涉及的主要实验原理：有n个编号为1,2,3,，n的人按顺时针方向围坐一圈，每人持有一个密码（

11、正整数）。一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，并将其密码值作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，以此类推下去，直到所有的人全部出列为止。概要设计和存储结构：该算法的实现用循环链表：/data1 存储参加游戏者的编号/data2 存储参加游戏者的密码 /next 为结点指针structLNodeintdata1;intdata2;structLNode*next;/执行游戏规则主要算法：voidBuildGame(LinkList&L,intm,intk)p=(LinkList)mall

12、oc(sizeof(LNode);/参加游戏者为k人，所以循环/游戏规则：从第一个人开始报/并将他的密码作为下一个ms,依p->next=L;for(i=0;i<k;i+)k次后游戏结束for(j=1;j<m;j+)数，报到初始值m勺人出列，p=p->next;次循环，直到游戏结束r=p->next;cout<<r->data1<<''m=r->data2;p->next=r->next;p=r;实验结果和结论:请依次输入参加准戏名的密码，5463411109请输入初始E：2H依次出列的人K：2a3?

13、91564倩按任意键继续一.-富密小落吧噂薛堂耦蠢替巧请依七心前八（脂对在的洞r：蓍耙表能入叁加遁或者的宙科-fi9459清输.Aj初始E!3上次出列的人为.蒲森品餐融胜蟀-根据约瑟夫环的游戏规则，上述三个结果都正确实验分析：算法用到的是循环链表。在进行链表数据输入的时候由于有两个数据，所以要循环两次，这样辅助指针就比较多，后面执行游戏规则的函数里也用到了比较多的辅助指针，用起来比较复杂，这个算法我感觉在这方面不太好，容易搞混淆。但是，当时能做到这里我感觉已经不错了实验三实验名称：栈和队实验目的及要求：熟悉对栈和队的应用,熟悉其基本操作。增强自己的动手能力和实验能力。实验主要内容：输入一个十进

14、制数(整数和小数)和进制数，要求程序输出转换后的数。例如，输入5，再输入进制数为2，则应该输出101。实验中涉及的主要实验原理：十进制数和其他进制数之间的转换。整数部分为除进制数(如除2)取余最后逆置，小数部分为乘进制数取整，最后顺序放置。概要设计和存储结构：本算法用了栈和队两类存储结构。其中，栈：typedefstructint*base;int*top;intsize;sqstack;用来存储整数部分；队：structQNodedoubledata;structQNode*next;typedefQNode*QueuePtr;typedefstructQueuePtrfront;Queue

15、Ptrrear;Linkqueue;用来存储小数部分。主要算法：Statusjzzh(sqstack&s,Linkqueue&Q,SElemTypem,SElemTypen)/进制转换，包含整数部分和小数部分的转换while(m1!=0)/m1=int(m-modf(m,&p)push(s,m1%n);m1=m1/n;while(modf(m,&p)m=modf(m,&p)*n;enqueue(Q,m-modf(m,&p);returnOK;实验四实验名称：二叉树实验目的及要求：熟悉对二叉树的应用,熟悉其各种遍历的基本规则，了解树的创建的基本原理

16、。增强自己的动手能力和实验能力。实验主要内容：创建一颗二叉树，对其进行先序、中序、后序遍历以及其他操作。概要设计和存储结构：typedefstructBiTNodeTElemTypedata;structBiTNode*lchild,*rchild;BiTNode,*BiTr主要算法：StatusPreOrderTraverse(BiTreeT)if(T)/cout<<T->data;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);returnOK;StatusInOrderTraverse(BiTr

17、eeT)if(T)InOrderTraverse(T->lchild);cout<<T->data;InOrderTraverse(T->rchild);returnOK;StatusPostOrderTraverse(BiTreeT)if(T)/中序、后序遍历以及其他操作/数据域/指向左右孩子的指针lchild,rchild/先序遍历判断二叉树是否为空/访问Data/递归遍历左子树/递归遍历右子树/中序遍历/判断二叉树是否为空/递归遍历左子树/递归遍历右子树/后序遍历非空二叉树/ 递归遍历左子树/ 递归遍历右子树PostOrderTraverse(T->l

18、child);PostOrderTraverse(T->rchild);cout<<T->data;returnOK;intCountNode(BiTreeT)/统计结点总数if(T)return1+CountNode(T->lchild)+CountNode(T->rchild);/递归遍历左右子树，每过一个结点else/加，最后加上根结点return0;intCountLeaf(BiTreeT)/统计叶子总数if(T)if(!T->lchild&&!T->rchild)return1;elsereturnCountLeaf(T

19、->lchild)+CountLeaf(T->rchild);elsereturn0;StatusExchange(BiTree&T)/交换左右子树if(T)temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;if(T->lchild)Exchange(T->lchild);if(T->rchild)Exchange(T->rchild);returnOK;实验结果和结论：宜宜子 7FMFM 丁 n 力福左 0 1 2 3 4 LJ 61 .!V . “里 一 懒 隘饕 孝理 f

20、cIPJJUl B r一曷县十 中父 & 1 2 3 4 5 6一 耳直子一历历历就舌招叶左 簟中后施福刘 12 3 4 5 6人诜和一广超嗯察叶左 一麝中后统统交博输入城Fl一- -功能清单点后翁吉翠图并先序遍历请篁入矩束1±y，n,y帝技任意键让绥一由于在该程序中，加了一个可选择菜单，因此，该程序的执行是一直连续的，如上图，执行顺序是从左到右，从上到下。首先，先序创建二叉树为：AB（$D$EF$G$（$代表空格），由于是先序创建，所以先序遍历的结果也是ABCDEFG因此第一个结果正确；打一键继续后选择后序遍历，如图所示二叉树，后序遍历的结果为CDBGFEAI此第二个结果正

21、确；由输入的字母数可知第三个结果也是正确的；后面两个结果都是判断输入的合法性，并且都判断正确。'G实验分析:本次所做的实验难度不是很高，同时我认为该实验的创建二叉树算法并不是很好，因为只有保证输入空格的数量和位置绝对正确才能保证创建函数的结束，否则将无法继续。而且这里无法判断输入的合法性。实验五实验名称：查找和排序实验目的及要求：学习和掌握排序和查找这两个计算机程序设计中的重要操作。加强自己的动手能力和错误分析能力。实验主要内容：选择一种查找和排序算法，实现查找造和排序。概要设计和存储结构：本程序中用到了顺序表存储结构和儿茶链表存储结构，两种结构的作用为：顺序表用来存储顺序查找表；二叉

22、链表用来存储次优查找树。/顺序表的顺序存储表示typedefstructcharkey;intweight;ElemType;typedefstructElemType*elem;intlength;SSTable;/二叉树的二叉链表存储表示typedefstructBiTNodeElemTypedata;structBiTNode*lchild,*rchild;BiTNode,*BiTree;主要算法：/重建静态查找表为按关键字非降序排序。voidShellInsert(SSTable&L,intdk)for(i=dk+1;i<=L.length;+i)if(LT(L.elem

23、i.key,L.elemi-dk.key)/需将L.ri插入有序增量子表L.elem0=L.elemi;/暂存在L.r0for(j=i-dk;j>0&&LT(L.elem0.key,L.elemj.key);j-=dk)L.elemj+dk=L.elemj;/记录后移，查找插入位置L.elemj+dk=L.elem0;/插入/ShellIn/由有序表Rlow.high及其累计权值表sw(其中sw0=0)递归构造/次优查找树T。intSecondOptimal(BiTree&T,ElemTypeR,intsw,intlow,inthigh)min=abs(swhig

24、h-swlow);/fabs函数是求绝对值的dw=swhigh+swlow-1;for(j=low+1;j<=high;+j)/选择最小的Pi值if(fabs(dw-swj-swj-1)<min)i=j;min=fabs(dw-swj-swj-1);T=(BiTree)malloc(sizeof(BiTNode);if(!T)return0;T->data=Ri;/生成结点if(i=low)T->lchild=NULL;/左子树空elseSecondOptimal(T->lchild,R,sw,low,i-1);/构造左子树if(i=high)T->rchild=NULL;/右子树空elseSecondOptimal(T->rchild,R,sw,i+1,high);/构造右子树return1;/在次优查找树T中查找关键字等于key的元素。找到则返回，否则返回intSearch_SOSTree(SOSTree&T,charkey)while(T)/T非空if(T->data.key=key)return1;elseif(T->data.key>key)T=T->lchild;