资源预览内容
第1页 / 共14页
第2页 / 共14页
第3页 / 共14页
第4页 / 共14页
第5页 / 共14页
第6页 / 共14页
第7页 / 共14页
第8页 / 共14页
第9页 / 共14页
第10页 / 共14页
亲,该文档总共14页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
数据结构与算法实验学期总结我的数据结构 班级:09计本一班 学号:2009810020 姓名:吴伟 摘要数据结构实验的目的是为了加深对课堂知识的理解,培养实验者的动手能力和思维能力。实验中,能体会到了算法和源程序之间的区别,理解到要实现算法要做的事情,解决编写源程序时遇到的各类问题。关键字:算法、源程序、算法实现、解决问题一、 数据结构与算法课程实验的主要意义的目的 数据结构课程的实践性很强,许多内容如果只进行单纯的课堂讲授是根本不能够深刻认识的。例如,第二章线性表的多种存储结构的对比分析,如不上机练习,就只能靠自己背,但这样就不能有更直观、形象的认识了。因此,实验是数据结构课程的一个重要环节。首先,在实验的过程中,可以会体会到源程序与算法的区别。算法是一种算法描述语言。它不是一种现实存在的编程语言。使用算法的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal, C, Java, etc)实现。它可能综合使用多种编程语言中语法、保留字,甚至会用到自然语言。 因此,算法必须结构清晰,代码简单,可读性好,并且类似自然语言。源程序(source code)是指未编译的按照一定的程序设计语言规范书写的,一系列人类可读的计算机语言指令。其实现起来,有时并不像算法那样看起来那么简单。例如,希尔排序的算法:void ShellSort(SSTable &L, int dlta, 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(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,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(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;coutdata1data2;p-next=r-next;p=r;实验结果和结论:根据约瑟夫环的游戏规则,上述三个结果都正确。实验分析:算法用到的是循环链表。在进行链表数据输入的时候由于有两个数据,所以要循环两次,这样辅助指针就比较多,后面执行游戏规则的函数里也用到了比较多的辅助指针,用起来比较复杂,这个算法我感觉在这方面不太好,容易搞混淆。但是,当时能做到这里我感觉已经不错了。实验三实验名称:栈和队实验目的及要求: 熟悉对栈和队的应用,熟悉其基本操作。增强自己的动手能力和实验能力。实验主要内容: 输入一个十进制数(整数和小数)和进制数,要求程序输出转换后的数。例如,输入5,再输入进制数为2,则应该输出101。实验中涉及的主要实验原理: 十进制数和其他进制数之间的转换。整数部分为除进制数(如除2)取余最后逆置,小数部分为乘进制数取整,最后顺序放置。概要设计和存储结构:本算法用了栈和队两类存储结构。其中,栈:typedef struct int *base;int *top;int size;
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号