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

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