数据结构课程设计报告样例1

《数据结构课程设计报告样例1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、排序算法的实现与比较数据结构课程设计报告06040722郭啸2006-9-7l课程题目：编程实现希尔、快速、堆、归并四种排序算法，并计算每种算法的比较、移动次数。要求待排序数据从磁盘文件读入，实施排序后将数据写入另一文件。l开发平台：处理器：IntelPentium42.4GHz物理内存：512M操作系统：MicrosoftWindowsXP开发环境：MicrosoftVisualStudio.NET2003l实现语言：采用ANSIC++作为实现语言，与课本的C实现相比，有如下区别：n封装性：传统的面向过程编程语言C结构体（struc

2、t）这样的自定义类型来设计排序表，缺点是它只能将排序表的数据集合到一起，而仅针对这一数据进行的一系列操作（如初始化、打印等）却必须与数据分开，采取具有全局作用域的函数来实现，这样不能很好的体现出两者的联系，代码难以组织、维护，并且为了让全局函数可以访问，数据必须不设任何保护，用户也必然可以访问，这有可能使数据被改为无效值，引起程序被挂起甚至崩溃。面向对象的C++克服了这些问题，新设计的类（class）将排序表所包含的数据及其专有的操作集合到了一起，并且可以将数据设为私有，只通过公共接口访问数据，而公共接口可以作有效性检查，这样的封装使

3、数据更安全，类的实现细节也可以隐藏在类内部，只通过接口提供给用户功能，这样，当类需要改进时，接口可以不作更改，这样，用户不作更改就可以升级他的系统，程序更易维护，也更易理解。n多态性：C/C++都是强类型语言，对int和float分别排序就必须要定义两种操作，虽然这两种操作除数据类型外完全一样。这样就造成代码冗余，而且带来函数命名和程序员记忆负担等诸多问题，C++通过函数重载、函数模板、类模板这些多态性技术解决了这一问题，通过定义一种将类型作为参数传递的模板，在调用时编译器自动生成对应数据类型的代码，这样一份代码就可以针对各种数据类型

4、，程序易理解、易维护。n继承：虽然本程序没有用到继承，但它仍值得一提。继承的特性使程序的层次更分明，当一个类含有大量的特性，但如果不同的用户在需要其中一些必须的特性以外，分别只需要其他部分不同的特性时，只实现一个包含所有特性的类会造成严重的代码冗余，而单独实现所有的类又会使原本相联系类之间的关系不够明确，而且倘若共性部分需要修改时，需要修改大量拷贝，代码不易维护，C++支持从一个基类继承其所有特性，然后再扩展进自己的特性，针对刚才的问题，我们可以实现一个包含每个用户的共性的类，然后为不同的用户从这个类继承新类，并扩展他们所需要的特性，

5、这样既满足了不同用户的需求，7排序算法的实现与比较使得各类之间关系明确，也使代码量减到最小，而且如果共性的实现需要更改时，只需修改被继承的基类即可，可维护性大大增强，按各用户的新需求扩展某个子类的功能时也不会影响到其他用户，可见继承是这个问题的最佳解决方案。n可读性：C++是面向对象的程序设计语言，与现实世界较为接近，加上多态性技术的一种――重载，程序更易被理解，可读性更强。l自定义数据结构：ntemplateclassElement;排序表的每一个元素，其接口包括：Element();//默认构造函数inlin

6、eTGetKey();//获取关键值voidSetKey(constTkeyValue);//设置关键值ntemplateclassSortList:排序表类，其成员包括：SortList(intsizeValue);//构造一个含sizeValue个元素的排序表SortList(char*pf);//从文件pf读取数据建立排序表inline~SortList();//析构函数inlineintGetSize();//获取记录数Element&operator[](intpos);//重载的[]运算符，用于

7、访问记录voidRead(char*pf);//从文件向已构造的排序表读取数据voidWrite(char*pf);//将排序表写入文件ntemplateclassSort排序类，其成员包括：staticvoidShellSort(SortList&);//Shell排序staticvoidQuickSort(SortList&);//快速排序staticvoidHeapSort(SortList&);//堆排序staticvoidMergeSort(SortList&);//归并排序in

8、linestaticintGetNumOfCmp();//获取本次排序比较次数inlinestaticintGetNumOfExg();//获取本次排序移动次数l算法描述：n希尔排序：Shell排序又称缩小增量排序，属插