你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。
06040722 郭啸 2006-9-7
课程题目：编程实现希尔、快速、堆、归并四种排序算法，并计算每种算法的比较、移动次数。要求待排序数据从磁盘文件读入，实施排序后将数据写入另一文件。
开发平台：处理器：intel pentium 4 2.4ghz
物理内存：512m
操作系统：microsoft windows xp
开发环境：microsoft visual 2003
实现语言：采用 ansi c++作为实现语言，与课本的c实现相比，有如下区别：
封装性：传统的面向过程编程语言c结构体（struct）这样的自定义类型来设计排序表，缺点是它只能将排序表的数据集合到一起，而仅针对这一数据进行的一系列操作（如初始化、打印等）却必须与数据分开，采取具有全局作用域的函数来实现，这样不能很好的体现出两者的联系，**难以组织、维护，并且为了让全局函数可以访问，数据必须不设任何保护，用户也必然可以访问，这有可能使数据被改为无效值，引起程序被挂起甚至崩溃。面向对象的c++克服了这些问题，新设计的类（class）将排序表所包含的数据及其专有的操作集合到了一起，并且可以将数据设为私有，只通过公共接口访问数据，而公共接口可以作有效性检查，这样的封装使数据更安全，类的实现细节也可以隐藏在类内部，只通过接口提供给用户功能，这样，当类需要改进时，接口可以不作更改，这样，用户不作更改就可以升级他的系统，程序更易维护，也更易理解。
多态性：c/c++都是强类型语言，对int和float分别排序就必须要定义两种操作，虽然这两种操作除数据类型外完全一样。这样就造成**冗余，而且带来函数命名和程序员记忆负担等诸多问题，c++通过函数重载、函数模板、类模板这些多态性技术解决了这一问题，通过定义一种将类型作为参数传递的模板，在调用时编译器自动生成对应数据类型的**，这样一份**就可以针对各种数据类型，程序易理解、易维护。
继承：虽然本程序没有用到继承，但它仍值得一提。继承的特性使程序的层次更分明，当一个类含有大量的特性，但如果不同的用户在需要其中一些必须的特性以外，分别只需要其他部分不同的特性时，只实现一个包含所有特性的类会造成严重的**冗余，而单独实现所有的类又会使原本相联系类之间的关系不够明确，而且倘若共性部分需要修改时，需要修改大量拷贝，**不易维护，c++支持从一个基类继承其所有特性，然后再扩展进自己的特性，针对刚才的问题，我们可以实现一个包含每个用户的共性的类，然后为不同的用户从这个类继承新类，并扩展他们所需要的特性，这样既满足了不同用户的需求，使得各类之间关系明确，也使**量减到最小，而且如果共性的实现需要更改时，只需修改被继承的基类即可，可维护性大大增强，按各用户的新需求扩展某个子类的功能时也不会影响到其他用户，可见继承是这个问题的最佳解决方案。
可读性：c++是面向对象的程序设计语言，与现实世界较为接近，加上多态性技术的一种――重载，程序更易被理解，可读性更强。
自定义数据结构：
template
class element;
排序表的每一个元素，其接口包括：
element默认构造函数。
inline t getkey获取关键值。
void setkey( const t keyvalue );设置关键值。
template
class sortlist:
排序表类，其成员包括：
sortlist( int sizevalue构造一个含sizevalue个元素的排序表。
sortlist( char * pf从文件pf读取数据建立排序表。
inline ~sortlist析构函数。
inline int getsize获取记录数。
element & operator int pos );重载的运算符，用于访问记录。
void read( char * pf从文件向已构造的排序表读取数据。
void write( char * pf将排序表写入文件。
template
class sort
排序类，其成员包括：
static void shellsort( sortlistshell排序。
static void quicksort( sortlist快速排序。
static void heapsort ( sortlist堆排序。
static void mergesort( sortlist归并排序。
inline static int getnumofcmp获取本次排序比较次数。
inline static int getnumofexg获取本次排序移动次数。
算法描述：希尔排序：
shell排序又称缩小增量排序，属插入类排序法，它的基本思想是：先将整个待排序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。shell是针对普通插入排序的缺陷进行的改进。
快速排序：快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将待排记录分割成两部分，其中一部分记录的关键字均比另一部分的小，则可分别对这两部分记录进行递归快速排序。
堆排序：堆排序利用了堆结构的特点，以一维数组来存储这个堆，将堆调整为大（小）顶堆，然后取出堆顶元素，余下的继续调整为大（小）顶堆，如此直到取出所有元素，排序完成。
归并排序：归并排序的前提是待排记录的两个子表分别有序，然后将其归并至一个有序的新表中，归并前的有序子表也是归并排序的结果。从最原始的只含一个元素的两子表，可看成有序的，经上述归并完成最终排序。
性能分析：由于计算机实现的排序算法，没有标准的数据交换操作，因此用交换次数作为衡量性能的标准很不准确，这里计算移动次数，即内存发生赋值操作则计数一次。
即使计算了内存的拷贝操作，实际的性能仍与很多因素关联，因此，程序作了耗时测试，研究在排序表数据结构发生变化时，算法消耗的时间随之变化的规律。
数据量对性能的影响：
为降低其他因素的影响，每组数据均按比例平均分布。
如：100个数据则分布在[0，100]，500个数据则分布在[0，500]。
运行结果：图表表示：
★直观分析：
由两张折线图可以看出，数据量在1000以内，各排序算法各方面性能都几乎一致。数据增多至一定值时，各算法开始各自的稳定增长，但相互之间有明显差别。1000－15000时，希尔和堆排序仍有重叠迹象，15000后，按照希尔、堆、快速、归并的顺序，可近似认为前者斜率分别是后者的2倍。
理论性能：移动操作时间、空间复杂度均远超过比较操作，因此，以移动次数衡量，快速排序性能最好。综合比较、移动次数来看，仍然是快速排序性能最好，归并次之，但这仅是理论分析，实际运行时，还要考虑诸多因素，如归并排序大量的递归函数调用及数据移动操作，会占用过多的cpu及时间，极大的影响性能。
数据结构课程设计 报告 样例
数据结构与算法 课程设计报告。王婧 龚丹 宋毅编写 题目 航空订票管理系统。学期 秋 班号。学号。姓名。成绩 哈尔滨华德学院电子与信息工程学院。年月。一 实训设计的目的与要求 注 正文为宋体，五号字，为单倍行距 一 课程设计目的 不少于字 数据结构课程设计是综合运用数据结构课程中学到的几种典型数据结...
数据结构课程设计报告
东莞理工学院城市学院。题目 二叉排序树 专业 计算机科学与技术 本 年级 2010级计算机科学与技术专业 1 班。个人姓名 何振江。指导教师 张娟老师 时间 2010至2011第二学期第18周 地点 实验楼615机房 东莞理工学院城市学院计算机与信息科学系制。2011年 6月。实习报告的内容。一 问...
数据结构课程设计报告
设计一个校园导游程序，为来访的客人提供信息查询服务。1 设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图 无向网 以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。2 存放景点代号 名称 简介等信息供用户查询。3 为来访客人提供图中任意景点相关信息的查询。4 为来访客人提供...