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

/数据结构与算法实验学期总结我的数据结构班级：09计本一班学号：2009810020姓名：吴伟摘要数据结构实验的目的是为了加深对课堂知识的理解，培养实验者的动手能力和思维能力。实验中，能体会到了算法和源程序之间的区别，理解到要实现算法要做的事情，解决编写源程序时遇到的各类问题。关键字：算法、源程序、算法实现、解决问题数据结构与算法课程实验的主要意义的目的数据结构课程的实践性很强，许多内容如果只进行单纯的课堂讲授是根本不能够深刻认识的。例如，第二章线性表的多种存储结构的对比分析，如不上机练习，就只能靠自己背，但这样就不能有更直观、形象的认识了。因此，实验是数据结构课程的一个重要环节。首先，在实验的过程中，可以会体会到源程序与算法的区别。算法是一种算法描述语言。它不是一种现实存在的编程语言。使用算法的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal,C,Java,etc)实现。它可能综合使用多种编程语言中语法、保留字，甚至会用到自然语言。因此，算法必须结构清晰，代码简单，可读性好，并且类似自然语言。源程序(sourcecode)是指未编译的按照一定的程序设计语言规范书写的，一系列人类可读的计算机语言指令。其实现起来，有时并不像算法那样看起来那么简单。例如，希尔排序的算法：voidShellSort(SSTable&L,intdlta[],intt){//按增量序列dlta[0...t-1]对顺序表L做希尔排序for(intk=0;k<t;++k)ShellInsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序}//ShellSort看到该算法，基本都会明白：对L执行t次ShellInsert(L,dlat[k])操作就能完成希尔排序。然而，要真正的实现该功能，必须有完整的代码：boolLT(chara,charb){ returna<b;}//重建静态查找表为按关键字非降序排序。voidShellInsert(SSTable&L,intdk){inti,j;for(i=dk+1;i<=L.length;++i)if(LT(L.elem[i].key,L.elem[i-dk].key)){//需将L.r[i]插入有序增量子表L.elem[0]=L.elem[i];//暂存在L.r[0]for(j=i-dk;j>0&<(L.elem[0].key,L.elem[j].key);j-=dk)L.elem[j+dk]=L.elem[j];//记录后移，查找插入位置L.elem[j+dk]=L.elem[0];//插入}}//ShellInvoidShellSort(SSTable&L,intdlta[],intt){for(intk=0;k<t;++k)ShellInsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序}//ShellSort所以，算法只用来说明复杂的问题，并不一定可以执行。再次，实验会增强你的算法实现能力，锻炼你的思维和解决问题的能力。在我们的数据结构课上，能学到的都是各种功能算法，没有源代码。所以，如果要做实验，你就必须思考，想各种方法来实现算法。在此过程中需要解决各类问题，使源代码尽可能正确的达到算法的思想。实验中，算法的实现会让我更容易的记住所学的知识，用一个开玩笑的引用：“一朝被蛇咬，十年怕井绳”。概述本学期的实验内容和目的实验一实验名称：《对比算法的时空效率》实验目的与要求：熟悉开发工具的编程环境。熟悉算法语言并完成简单的算法。熟悉C语言的语法，将算法上机编程实现。区别算法和源程序。体会用不同算法解决同一个问题，体会存储结构不同对实现算法的影响。学习对算法进行时空分析的基本方法。了解评价一个算法的基本准则。实验主要内容：试编写求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概要设计和存储结构：首先向内存申请大小为k+1的空间，第0号空间用来做辅存。第k号空间放1，其他放0。然后按照斐波那契序列的计算方法计算下一项，再把整个数组左移，最后把计算出来的数放在最大位。一直循环直到算出你要的答案。存储结构为：一维数组（int*a=newint[k+1];）主要算法：voidfac(intk,intm,inta[]){//k是斐波那契序列的阶数，m是要输出的项数，a是进行排列操作的数组int*a=newint[k+1]; for(i=0;i<=k;i++) a[i]=0; a[k]=1;//进行阶斐波那契序列的输出，如果要输出的项m不大于阶数k，则直接//输出数组的第m+1项 if(m<=k)fac(m)=a[m]; else{//如果项大于阶数，则先进行递推计算，再输出 for(intl=1;l<=m-k;l++){//因为序列的前k项已经给出，所以要输出第m项只用循环m-k次 for(i=0;i<k;i++){ a[i]=a[i+1]; } for(t=0,j=0;j<k;j++) t+=a[j]; 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)=4，由此，上面结果正确。实验分析：我的算法用的是顺序存储结构，并采用递推的计算法。我感觉好处是，代码不算太多，不是太累赘；坏处是，for循环比较多，容易混淆。一开始，程序能运行，但输出的数不对，经过查找发现是第四个for语句中的t做完一次后没有初始化（开始的程序t是在定义时初始化的）。接着，再运行，发现输出错位，经检查，第二个for循环次数不对，应该是m-k次，开始是m次，改过之后输出正确。虽然，该算法有的地方做的还算可以，但是现在看来在实验的其他方面做的不是很好，还有待改进，例如：没有考虑到斐波那契序列数据的数据类型，我用的是int这样要输出很大项的时候，int型的数据不够。实验二实验名称：《线性表》实验目的与要求：熟悉如何使用单链表，掌握单链表的基本操作，巩固对单链表知识的认识。实验主要内容：约瑟夫环。假设有n个编号为1，2，3，…，n的人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，并将其密码值作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，以此类推下去，直到所有的人全部出列为止。试设计一个程序，可以在用户确定了人数和密码的情况下，求出对应的出列顺序。实验中涉与的主要实验原理：有n个编号为1，2，3，…，n的人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，并将其密码值作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，以此类推下去，直到所有的人全部出列为止。概要设计和存储结构：该算法的实现用循环链表：structLNode{ intdata1;//data1存储参加游戏者的编号 intdata2;//data2存储参加游戏者的密码 structLNode*next;//next为结点指针};主要算法：voidBuildGame(LinkList&L,intm,intk)｛//执行游戏规则 p=(LinkList)malloc(sizeof(LNode)); p->next=L; for(i=0;i<k;i++)｛//参加游戏者为k人，所以循环k次后游戏结束 for(j=1;j<m;j++)//游戏规则：从第一个人开始报数，报到初始值m的人出列, p=p->next;//并将他的密码作为下一个m值，依次循环，直到游戏结束 r=p->next; cout<<r->data1<<''; m=r->data2; p->next=r->next; p=r; }}实验结果和结论：根据约瑟夫环的游戏规则，上述三个结果都正确。实验分析：算法用到的是循环链表。在进行链表数据输入的时候由于有两个数据，所以要循环两次，这样辅助指针就比较多，后面执行游戏规则的函数里也用到了比较多的辅助指针，用起来比较复杂，这个算法我感觉在这方面不太好，容易搞混淆。但是，当时能做到这里我感觉已经不错了。实验三实验名称：《栈和队》实验目的与要求：熟悉对栈和队的应用,熟悉其基本操作。增强自己的动手能力和实验能力。实验主要内容：输入一个十进制数（整数和小数）和进制数，要求程序输出转换后的数。例如，输入5，再输入进制数为2，则应该输出101。实验中涉与的主要实验原理：十进制数和其他进制数之间的转换。整数部分为除进制数（如除2）取余最后逆置，小数部分为乘进制数取整，最后顺序放置。概要设计和存储结构：本算法用了栈和队两类存储结构。其中，栈：typedefstruct{ int*base; int*top; intsize;}sqstack;用来存储整数部分；队：structQNode{ doubledata; structQNode*next;};typedefQNode*QueuePtr;typedefstruct{ QueuePtrfront; QueuePtrrear;}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;}实验四实验名称：《二叉树》实验目的与要求：熟悉对二叉树的应用,熟悉其各种遍历的基本规则，了解树的创建的基本原理。增强自己的动手能力和实验能力。实验主要内容：创建一颗二叉树，对其进行先序、中序、后序遍历以与其他操作。概要设计和存储结构：typedefstructBiTNode{ TElemTypedata;//数据域 structBiTNode*lchild,*rchild;//指向左右孩子的指针lchild,rchild}BiTNode,*BiTr主要算法：StatusPreOrderTraverse(BiTreeT){//先序遍历 if(T){//判断二叉树是否为空 cout<<T->data;//访问Data PreOrderTraverse(T->lchild);//递归遍历左子树 PreOrderTraverse(T->rchild);//递归遍历右子树 } returnOK;}StatusInOrderTraverse(BiTreeT){//中序遍历 if(T){//判断二叉树是否为空 InOrderTraverse(T->lchild);//递归遍历左子树 cout<<T->data; InOrderTraverse(T->rchild);//递归遍历右子树 } returnOK;}StatusPostOrderTraverse(BiTreeT){//后序遍历 if(T){//非空二叉树 PostOrderTraverse(T->lchild);//递归遍历左子树 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; else returnCountLeaf(T->lchild)+CountLeaf(T->rchild); } else return0;}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;}实验结果和结论：由于在该程序中，加了一个可选择菜单，因此，该程序的执行是一直连续的，如上图，执行顺序是从左到右，从上到下。首先，先序创建二叉树为：ABC$$D$$EF$G$$$($代表空格),由于是先序创建，所以先序遍历的结果也是ABCDEFG，因此第一个结果正确；打一键继续后选择后序遍历，如图所示二叉树，后序遍历的结果为CDBGFEA,因此第二个结果正确；由输入的字母数可知第三个结果也是正确的；后面两个结果都是判断输入的合法性，并且都判断正确。ABECDFG实验分析：本次所做的实验难度不是很高，同时我认为该实验的创建二叉树算法并不是很好，因为只有保证输入空格的数量和位置绝对正确才能保证创建函数的结束，否则将无法继续。而且这里无法判断输入的合法性。实验五实验名称：《查找和排序》实验目的与要求：学习和掌握排序和查找这两个计算机程序设计中的重要操作。加强自己的动手能力和错误分析能力。实验主要内容：选择一种查找和排序算法，实现查找造和排序。概要设计和存储结构：本程序中用到了顺序表存储结构和儿茶链表存储结构，两种结构的作用为：顺序表用来存储顺序查找表；二叉链表用来存储次优查找树。//顺序表的顺序存储表示typedefstruct{ charkey; intweight;}ElemType;typedefstruct{ ElemType*elem; intlength; }SSTable;//二叉树的二叉链表存储表示typedefstructBiTNode{ ElemTypedata; structBiTNode*lchild,*rchild;}BiTNode,*BiTree;主要算法：//重建静态查找表为按关键字非降序排序。voidShellInsert(SSTable&L,intdk){for(i=dk+1;i<=L.length;++i)if(LT(L.elem[i].key,L.elem[i-dk].key)){//需将L.r[i]插入有序增量子表L.elem[0]=L.elem[i];//暂存在L.r[0]for(j=i-dk;j>0&<(L.elem[0].key,L.elem[j].key);j-=dk)L.elem[j+dk]=L.elem[j];//记录后移，查找插入位置L.elem[j+dk]=L.elem[0];//插入}}//ShellIn//由有序表R[low..high]与其累计权值表sw(其中sw[0]==0)递归构造//次优查找树T。intSecondOptimal(BiTree&T,ElemTypeR[],intsw[],intlow,inthigh){ min=abs(sw[high]-sw[low]); //fabs函数是求绝对值的 dw=sw[high]+sw[low-1]; for(j=low+1;j<=high;++j)//选择最小的△Pi值 if(fabs(dw-sw[j]-sw[j-1])<min){ i=j; min=fabs(dw-sw[j]-sw[j-1]); } T=(BiTree)malloc(sizeof(BiTNode)); if(!T) return0; T->data=R[i];//生成结点 if(i==low) T->lchild=NULL;//左子树空 else SecondOptimal(T->lchild,R,sw,low,i-1);//构造左子树 if(i==high) T->rchild=NULL;//右子树空 el