发布时间 : 星期一 文章《数据结构》课程设计报告 排序算法比较 算术表达式求值更新完毕开始阅读953520f6ba0d4a7302763ade
数据结构课程设计——排序算法比较、表达式求值 080910119
XXXXX大学
《数据结构》课程设计报告
排序算法比较 算术表达式求值
班级： 学号： 姓名： 指导老师：
第 1 页 共 35 页
数据结构课程设计——排序算法比较、表达式求值 080910119
目 录
一 课程设计1——排序算法比较
一、需求分析
二、程序的主要功能 三、程序运行平台 四、数据结构
五、算法及时间复杂度 六、测试用例 七、程序源代码
二 课程设计2——算术表达式求值
一、需求分析
二、程序的主要功能 三、程序运行平台 四、数据结构
五、算法及时间复杂度 六、测试用例 七、程序源代码
三 感想体会与总结
第 2 页 共 35 页
数据结构课程设计——排序算法比较、表达式求值 080910119
排序算法比较
一、需求分析
利用随机函数产生N个随机整数（N = 500，1000，1500，2000，2500，?,30000），利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（统计为图表坐标形式）。
二、程序的主要功能
1.用户输入任意个数，产生相应的随机数
2.用户可以自己选择排序方式（直接插入排序、折半插入排序、起泡排序、快速排序、选择排序、堆排序、基数排序）的一种
3.程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间。
三、程序运行平台
Visual C++ 6.0版本
四、数据结构
本程序的数据结构为线形表，线性顺序表、线性链表。 。
1、结构体： typedef struct {
int *r; //r指向线形表的第一个结点。 r[0]闲置，不同的算法有不同
的用处，如用作哨兵等。
int length; //顺序表的总长度 }Sqlist;
2、空线性表
Status InitSqlist(Sqlist &L) { L.r=(int *)malloc(MAXSIZE*sizeof(int)); //分配存储空间 if(!L.r) { printf(\存储分配失败！\ exit(0); } //存储分配失败
第 3 页 共 35 页
数据结构课程设计——排序算法比较、表达式求值 080910119
}
L.length=0;//初始长度为0 return OK;
五、算法及时间复杂度
（一）各个排序是算法思想：
（1）直接插入排序：将一个记录插入到已排好的有序表中，从而得到一
个新的，记录数增加1的有序表。
（2）折半插入排序：插入排序的基本插入是在一个有序表中进行查找和
插入，这个查找可利用折半查找来实现，即为折半插入排序。 （3）起泡排序：首先将第一个记录的关键字和第二个记录的关键字进行
比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。
（4）快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一
部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。
（5）选择排序：通过N-I次关键字间的比较，从N-I+1个记录中选出关
键字最小的记录，并和第I（1<=I<=N）个记录交换。
（6）堆排序：在堆排序的算法中先建一个大顶堆，既先选得一个关键字
作为最大的记录并与序列中最后一个记录交换，然后对序列中前N-1记录进行选择，重新将它调整成一个大顶堆，如此反复直到排序结束。
（7）基数排序：按最低位优先法先对低位关键字进行排序，直到对最高
位关键字排序为止，经过若干次分配和收集来实现排序 （二）时间复杂度分析
排序算法 插入排序 冒泡排序 最差时间 O(n2) O(n2) 时间复杂度 O(n2) O(n2) 是否稳定？ 稳定 稳定 第 4 页 共 35 页