文档介绍：*******************
实践教学
*******************
兰州理工大学
计算机与通信学院
2011年春季学期
数据结构课程设计
题目:
专业班级:
姓名:
学号:
指导教师:
成绩:_____________________
目录
摘要 3
前言 4
正文 5
1. 采用类c语言定义相关的数据类型 5
2. 各模块的伪码算法 5
3. 函数的调用关系图 6
4. 调试分析 7
a、调试中遇到的问题及对问题的解决方法 7
b、算法的时间复杂度和空间复杂度 7
5. 源程序 8
总结 13
参考文献 14
致谢 15
摘要
排序是计算机程序设计中的一种重要操作。各种部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。
关键字:排序,性能分析。
前言
排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素的任意序列,重新排列成一个按关键字有序的序列。内部排序的方法很多,但是就其全面性能而言,很难提出一种被认为是最好的方法,每一种方法都有各自的优缺点,适合在不同的环境下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类,则大致可分为插入排序,交换排序,选择排序,归并排序和记数排序等五类。
这几种排序算法是在顺序存储结构上实现的,因此在排序过程中需要进行大量记录的移动。当记录很大时,时间耗费很大,此时可采用静态链表作存储结构。但是有的排序方法,无法实现表排序。在这种情况下可以进行地址排序,即另设一个地址向量指示相应记录。
正文
采用类c语言定义相关的数据类型
int整型, char字符型,
各模块的伪码算法
(1)插入排序伪码算法:
void InsertSort(Splist&L){
for(i=2;i<=;++i)
if(LT([i].key,[i-1].key)) //“《”,[i]插入有序子表
{ [0]= [i]; //复制为哨兵
[i]= [i-1];
For(j)i-2;LT([0].key,[j].key);--j)
[j+1]= [j]; //记录后移
[j+1]= [0]; //插入到正确位置
}
}//InsertSort
(2) 希尔排序
void shllInsert(Splist & L,int dk){
for(i=dk+1;i<=;++i)
if(LT([i].key,[i-dk].key)) {
[0]= [i]; //暂存
for(j=i-dk;j>0&&LT(].key,[j].key);j-=dk)
[j+dk]=[j]; //记录后移
[j+dk]=[0];} //插入
}//shellsort
void shllsort (Splist & L,int data[],int t){
for(k=0;k<t;++k)
shllInsert(L,data[k]);
}//shellsort
(3)快速排序
int part(sqlist&L,int low, int high){
// 交换顺序表L中子表L。R[low..high]的记录,使枢轴记录到位,并返回其所在位
// 此时在它之前(后)的记录均不大(小)于它。
pivotkey=L.[Low].key;
while(loe<high){
While(low<high&&[high].key>=pivotkey) --high;
[low [high];
while(low<high&&[low].key>=pivotkey) ++low;
[low [high];
}
return low
}//partition
(4) 选择排序
void selectsort(splist&L){
for(i=1;i<;++i){
j=selectMinKey(L,i);
if(i!=j) [i] [j];
}
}//selectsort
(5)其泡排序
void bubblesort(sqlist r,int n){
int I,j,w;
for (i=1;i<=n-1;i++)
for(j=n;j>=i+1;j--)
if(r[j].key<r[j-1].key) //比较
{
W=r[j];
R[j]=r[j