文档介绍：2010-2011学年第2学期《数据结构与算法实验》学期论文数据结构与算法实验学期总结我的数据结构班级:09计本一班 学号:2009810020 姓名:吴伟摘要数据结构实验的目的是为了加深对课堂知识的理解, 培养实验者的动手能力和思维能力。实验中,能体会到了算法和源程序之间的区别, 理解到要实现算法要做的事情,解决编写源程序时遇到的各类问题。关键字:算法、源程序、算法实现、解决问题一、 数据结构与算法课程实验的主要意义的目的数据结构课程的实践性很强,许多内容如果只进行单纯的课堂讲授是根本不能够深刻认识的。例如,第二章线性表的多种存储结构的对比分析,如不上机练****就只能靠自己背,但这样就不能有更直观、形象的认识了。因此,实验是数据结构课程的一个重要环节。首先,在实验的过程中,可以会体会到源程序与算法的区别。算法是一种算法描述语言。它不是一种现实存在的编程语言。 使用算法的目的是为了使被描述的算法可以容易地以任何一种编程语言 (Pascal,C,Java,etc)实现。它可能综合使用多种编程语言中语法、保留字,甚至会用到自然语言。 因此,算法必须结构清晰,代码简单,可读性好,并且类似自然语言。源程序(sourcecode)是指未编译的按照一定的程序设计语言规范书写的,一系列人类可读的计算机语言指令。其实现起来,有时并不像算法那样看起来那么简单。例如,希尔排序的算法:voidShellSort(SSTable&L, int dlta[], int t){// 按增量序列dlta[0...t-1] 对顺序表L做希尔排序for(int k=0;k<t;++k)ShellInsert(L,dlta[k]); // 一趟增量为dlta[k] 的插入排序} //ShellSort2010-2011学年第2学期《数据结构与算法实验》学期论文看到该算法,基本都会明白:对L执行t次ShellInsert(L,dlat[k]) 操作就能完成希尔排序。然而,要真正的实现该功能,必须有完整的代码:boolLT(chara,charb){return a<b;}重建静态查找表为按关键字非降序排序。voidShellInsert(SSTable&L, int dk){int i,j;for(i=dk+1;i<=;++i)if (LT([i].key, [i-dk].key)) {// [i] [0]=[i]; // [0]for(j=i-dk;j>0&&LT([0].key,[j].key);j-=dk)[j+dk] =[j]; // 记录后移,[j+dk]=[0]; // 插入}} //ShellInvoidShellSort(SSTable&L, int dlta[], int t){for(int k=0;k<t;++k)ShellInsert(L,dlta[k]); // 一趟增量为dlta[k] 的插入排序}//ShellSort所以,算法只用来说明复杂的问题,并不一定可以执行。再次,实验会增强你的算法实现能力,锻炼你的思维和解决问题的能力。在我们的数据结构课上,能学到的都是各种功能算法,没有源代码。所以,如果要做实验,你就必须思考,想各种方法来实现算法。在此过程中需要解决各类问题,使源代码尽可能正确的达到算法的思想。实验中,算法的实现会让我更容易的记住所学的知识, 用一个开玩笑的引用:“一朝被蛇咬,十年怕井绳”。二、 概述本学期的实验内容和目的实验一实验名称:《对比算法的时空效率》实验目的及要求:2010-2011学年第2学期《数据结构与算法实验》学期论文熟悉开发工具的编程环境。熟悉算法语言并完成简单的算法。熟悉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,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号