《数据结构与算法实验学期总结(14页).doc》由会员分享，可在线阅读，更多相关《数据结构与算法实验学期总结(14页).doc（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-数据结构与算法实验学期总结我的数据结构 班级：09计本一班 学号：2009810020 姓名：吴伟 摘要数据结构实验的目的是为了加深对课堂知识的理解，培养实验者的动手能力和思维能力。实验中，能体会到了算法和源程序之间的区别，理解到要实现算法要做的事情，解决编写源程序时遇到的各类问题。关键字：算法、源程序、算法实现、解决问题一、 数据结构与算法课程实验的主要意义的目的 数据结构课程的实践性很强，许多内容如果只进行单纯的课堂讲授是根本不能够深刻认识的。例如，第二章线性表的多种存储结构的对比分析，如不上机练习，就只能靠自己背，但这样就不能有更直观、形象的认识了。因此，实验是数据结构课程的一个重要环
2、节。首先，在实验的过程中，可以会体会到源程序与算法的区别。算法是一种算法描述语言。它不是一种现实存在的编程语言。使用算法的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal, C, Java, etc)实现。它可能综合使用多种编程语言中语法、保留字，甚至会用到自然语言。 因此，算法必须结构清晰，代码简单，可读性好，并且类似自然语言。源程序(source code)是指未编译的按照一定的程序设计语言规范书写的，一系列人类可读的计算机语言指令。其实现起来，有时并不像算法那样看起来那么简单。例如，希尔排序的算法：void ShellSort(SSTable &L, int dlta,
3、 int t) / 按增量序列dlta0.t-1对顺序表L做希尔排序 for (int k=0; kt; +k) ShellInsert(L, dltak); / 一趟增量为dltak的插入排序 / ShellSort看到该算法，基本都会明白：对L执行t次ShellInsert(L,dlatk)操作就能完成希尔排序。然而，要真正的实现该功能，必须有完整的代码：bool LT(char a,char b)return ab;/ 重建静态查找表为按关键字非降序排序。void ShellInsert(SSTable &L, int dk) int i,j; for (i=dk+1; i0 & LT(
4、L.elem0.key, L.elemj.key); j-=dk) L.elemj+dk = L.elemj; / 记录后移，查找插入位置 L.elemj+dk = L.elem0; / 插入 / ShellInvoid ShellSort(SSTable &L, int dlta, int t) for (int k=0; k=2）裴波那契序列的第m项值的不同算法，并编程实现。k和m均以值调用的形式在函数参数中表现。要求：至少用两种不同的算法（如，递推、递归等等）。实验中涉及的主要实验原理：k=1时，fac(0)=0,fac(1)=1fac(n)=fac(n-1)+fac(n-2) n=2,
5、3,4,5.k=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=new intk+1;）主要算法：void fac(int k,int m,int a)/k是斐波那契序列的阶数，m是要输出的项数，a是进行排列操作的数组int *a=new intk+1; for(
6、i=0;i=k;i+) ai=0; ak=1;/进行阶斐波那契序列的输出，如果要输出的项m不大于阶数k，则直接/输出数组的第m+1项if(m=k) fac(m)=am; else /如果项大于阶数，则先进行递推计算，再输出for(int l=1;l=m-k;l+) /因为序列的前k项已经给出，所以要输出第m项只用循环m-k次for(i=0;ik;i+)ai=ai+1; for(t=0,j=0;jnext=L;for(i=0;ik;i+) /参加游戏者为k人，所以循环k次后游戏结束for(j=1;jnext; /并将他的密码作为下一个m值，依次循环，直到游戏结束r=p-next;coutdata
7、1data2;p-next=r-next;p=r;实验结果和结论：根据约瑟夫环的游戏规则，上述三个结果都正确。实验分析：算法用到的是循环链表。在进行链表数据输入的时候由于有两个数据，所以要循环两次，这样辅助指针就比较多，后面执行游戏规则的函数里也用到了比较多的辅助指针，用起来比较复杂，这个算法我感觉在这方面不太好，容易搞混淆。但是，当时能做到这里我感觉已经不错了。实验三实验名称：栈和队实验目的及要求： 熟悉对栈和队的应用,熟悉其基本操作。增强自己的动手能力和实验能力。实验主要内容： 输入一个十进制数（整数和小数）和进制数，要求程序输出转换后的数。例如，输入5，再输入进制数为2，则应该输出101
8、。实验中涉及的主要实验原理： 十进制数和其他进制数之间的转换。整数部分为除进制数（如除2）取余最后逆置，小数部分为乘进制数取整，最后顺序放置。概要设计和存储结构：本算法用了栈和队两类存储结构。其中，栈：typedef struct int *base;int *top;int size;sqstack;用来存储整数部分；队：struct QNodedouble data;struct QNode *next;typedef QNode *QueuePtr;typedef structQueuePtr front;QueuePtr rear;Linkqueue;用来存储小数部分。主要算法：Sta
9、tus jzzh(sqstack &s,Linkqueue &Q, SElemType m, SElemType n) /进制转换，包含整数部分和小数部分的转换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); return OK; 实验四实验名称：二叉树实验目的及要求： 熟悉对二叉树的应用,熟悉其各种遍历的基本规则，了解树的创建的基本原理。增强自己的动手能力和实验能力。实验主要内容： 创建一颗二叉树，对其进行先序、中序、后序遍
10、历以及其他操作。概要设计和存储结构：typedef struct BiTNodeTElemType data; /数据域struct BiTNode *lchild,*rchild;/指向左右孩子的指针lchild,rchildBiTNode,*BiTr主要算法：Status PreOrderTraverse(BiTree T) /先序遍历if(T) /判断二叉树是否为空coutdata; /访问DataPreOrderTraverse(T-lchild); /递归遍历左子树PreOrderTraverse(T-rchild); /递归遍历右子树return OK; Status InOrde
11、rTraverse(BiTree T) /中序遍历if(T) /判断二叉树是否为空InOrderTraverse(T-lchild); /递归遍历左子树coutdata; InOrderTraverse(T-rchild); /递归遍历右子树return OK;Status PostOrderTraverse(BiTree T) /后序遍历if(T) /非空二叉树PostOrderTraverse(T-lchild); /递归遍历左子树PostOrderTraverse(T-rchild); /递归遍历右子树coutdata;return OK;int CountNode (BiTree T)
12、 /统计结点总数if(T)return 1+CountNode (T-lchild)+CountNode (T-rchild);/递归遍历左右子树，每过一个结点else /加，最后加上根结点return 0;int CountLeaf (BiTree T) /统计叶子总数if (T)if (!T-lchild & !T-rchild) return 1;elsereturn CountLeaf(T-lchild) + CountLeaf(T-rchild);elsereturn 0;Status Exchange(BiTree &T) /交换左右子树if(T)temp=T-lchild;T-l
13、child=T-rchild;T-rchild=temp;if(T-lchild)Exchange(T-lchild);if(T-rchild)Exchange(T-rchild);return OK;实验结果和结论： 由于在该程序中，加了一个可选择菜单，因此，该程序的执行是一直连续的，如上图，执行顺序是从左到右，从上到下。首先，先序创建二叉树为：ABC$D$EF$G$($代表空格),由于是先序创建，所以先序遍历的结果也是ABCDEFG，因此第一个结果正确；打一键继续后选择后序遍历，如图所示二叉树，后序遍历的结果为CDBGFEA,因此第二个结果正确；由输入的字母数可知第三个结果也是正确的；后面
14、两个结果都是判断输入的合法性，并且都判断正确。 A B E C D F G实验分析：本次所做的实验难度不是很高，同时我认为该实验的创建二叉树算法并不是很好，因为只有保证输入空格的数量和位置绝对正确才能保证创建函数的结束，否则将无法继续。而且这里无法判断输入的合法性。实验五实验名称：查找和排序实验目的及要求：学习和掌握排序和查找这两个计算机程序设计中的重要操作。加强自己的动手能力和错误分析能力。实验主要内容： 选择一种查找和排序算法，实现查找造和排序。概要设计和存储结构：本程序中用到了顺序表存储结构和儿茶链表存储结构，两种结构的作用为：顺序表用来存储顺序查找表；二叉链表用来存储次优查找树。/ 顺
15、序表的顺序存储表示typedef structchar key;int weight;ElemType;typedef structElemType *elem;int length;SSTable;/ 二叉树的二叉链表存储表示typedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild; BiTNode,*BiTree;主要算法：/ 重建静态查找表为按关键字非降序排序。void ShellInsert(SSTable &L, int dk) for (i=dk+1; i0 & LT(L.elem0.key, L.elem
16、j.key); j-=dk) L.elemj+dk = L.elemj; / 记录后移，查找插入位置 L.elemj+dk = L.elem0; / 插入 / ShellIn/ 由有序表Rlow.high及其累计权值表sw(其中sw0=0)递归构造/ 次优查找树T。int SecondOptimal(BiTree &T,ElemType R,int sw,int low,int high)min=abs(swhigh-swlow);/fabs函数是求绝对值的dw=swhigh+swlow-1;for(j=low+1;j=high;+j) / 选择最小的Pi值if(fabs(dw-swj-swj
17、-1)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); / 构造右子树return 1;/ 在次优查找树T中查找关键字等于key的元素。找到则返回，否则返回int Search_SOSTree(SOSTree &T,char key) while(T) / T非空if(T-data.key=key)retur
18、n 1;else if(T-data.keykey)T=T-lchild;elseT=T-rchild;return 0; / 顺序表中不存在待查元素实验结果和结论：测试方案：随机输入查找表，权值有随机函数产生。则随后将输出查找表的非降序排列。接着输入要查找的关键字，接着应该输出和该关键字相匹配的权值；如果该表中没有要查找的关键字则应该报错。根据测试方案，该结果正确。该结果和测试方案一致。 该结果正确。实验分析： 该选题相对比较容易，因此实现起来感觉不是很困难。由于至此已经做过很多实验，实验经验已经积累不少，所以本次实验过程中没有出现很大错误。三、 总结 该学期的五个实验我都圆满完成了，虽然有
19、的实验拖得时间较长，但总体结果我自己还是比较满意的。在这么多次试验中遇到的最主要问题是有的时候不能很好的把算法的思想很好融合到源程序中。这类问题的解决只有一遍一遍的实验才能解决，因为只有在实验中才能体会到源程序的欠缺。在本学期的这些实验中，最合理的是可以选题，这就意味着实验难度对于每个人来说都适中，因为对于每一类实验，总会有能做的。大体来说，我对实验有点小小的建议，就是实验时间问题。本学期的实验时间没有限制，这对我们学生的独立思考不利，我认为想法是逼出来的，如果给太多时间，会让同学们产生这种想法：今天这个问题就是想不明白，哎，算了，明天再想吧，反正还有时间。有的同学，甚至会这样想：等吧，等他们会做的人做好了，我再看看他们怎么做的，这样最不好，尽管有的人会很认真的看别人写的东西，但终究没有自己想出来的好。所以我认为如果时间留得相对较少，就会让他们不得不自己想想该怎么写这个程序。四、 附录参考资料：数据结构（C语言版）、数据结构实验与算法-第 14 页-