排序.docx
- 文档编号:11399717
- 上传时间:2023-05-31
- 格式:DOCX
- 页数:14
- 大小:472.64KB
排序.docx
《排序.docx》由会员分享,可在线阅读,更多相关《排序.docx(14页珍藏版)》请在冰点文库上搜索。
排序
课程名称:
《数据结构》课程设计
课程设计题目:
排序
姓名:
院系:
计算机科学与技术学院
专业:
计算机科学与技术
年级:
2011级
学号:
指导教师:
王爱平
2013年9月14日
目录
1课程设计的目的………………………………………………………………3
2需求分析………………………………………………………………………3
3课程设计报告内容……………………………………………………………3
3.1概要设计……………………………………………………………………3
3.2详细设计……………………………………………………………………4
3.3调试分析……………………………………………………………………4
3.4用户手册……………………………………………………………………4
3.5测试结果……………………………………………………………………4
4小结…………………………………………………………………………4
5程序清单………………………………………………………………………4
6参考文献……………………………………………………………………9
7程序截图……………………………………………………………………9
1.课程设计的目的
(1)熟练使用C语言编写程序,解决实际问题;
(2)了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力;
(3)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;
(4)提高综合运用所学的理论知识和方法独立分析和解决问题的能力;
2.需求分析
各种排序算法性能比较
利用随机函数产生N个随机整数(20000以上),对这些数进行多种方法进行排序。
要求:
①至少采用三种方法实现上述问题求解(提示,可采用的方法有插入排序、2-路插入排序、希尔排序、起泡排序、改进的冒泡排序、快速排序、选择排序、堆排序、归并排序、三部排序、计数排序、鸽巢排序、鸡尾酒排序、地精排序、奇偶排序、梳排序、耐心排序——标红的至少选择一种)。
并把排序后的结果保存在不同的文件中。
②统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比),找出其中两种较快的方法。
3排序的设计
3.1概要设计
typedefintElemType;
链表数据结构:
typedefstructSqList{
ElemType*elem;
intlength;
}SqList,*PList;
3.2详细设计
voidInitSqList(PListList)//函数功能:
链表初始化
voidRandomElemToSqList(PListList)//函数功能:
用随机数填充链表
voidCopySqList(PListList1,PListList2)//函数功能:
链表复制
voidSqListToFile(PListList,FILE*fp)//函数功能:
将链表的内容写入文件
voidInsertSort(PListList)//函数功能:
插入排序
intPartition(PListList,intlow,inthigh)//函数功能:
将链表分成两部分,前面小于pivotkey,后面大于pivotkey
voidQSort(PListList,intlow,inthigh)//函数功能:
快速排序
voidGnomeSort(PListList)//函数功能:
地精排序,冒泡排序的变种
voidPigeonholeSort(PListList)//函数功能:
鸽巢排序
3.3调试分析(略)
3.4用户手册(略)
3.5测试结果(略)
4总结(略)
5、程序清单:
#include
#include
#include
#include
#defineMAX80000
typedefintElemType;
typedefstructSqList{//链表
ElemType*elem;
intlength;
}SqList,*PList;
voidInitSqList(PList);
voidRandomElemToSqList(PList);
voidCopySqList(PList,PList);
voidSqListToFile(PList,FILE*);
voidInsertSort(PList);
voidQSort(PList,int,int);
voidGnomeSort(PList);
voidPigeonholeSort(PList);
intPartition(PList,int,int);
intmain()
{
FILE*fp;
longstart,end;
SqListList1,List2,List3,List4;
InitSqList(&List1);
InitSqList(&List2);
InitSqList(&List3);
InitSqList(&List4);
RandomElemToSqList(&List1);
CopySqList(&List2,&List1);
CopySqList(&List3,&List1);
CopySqList(&List4,&List1);
printf("**********排序元素个数%d***********\n",MAX);
fp=fopen("QSort.txt","w");
printf("快速排序用时:
");
start=clock();
QSort(&List1,1,MAX);
end=clock();
printf("%6dms\n",end-start);
SqListToFile(&List1,fp);
fclose(fp);
fp=fopen("InsertSort.txt","w");
printf("插入排序用时:
");
start=clock();
InsertSort(&List2);
end=clock();
printf("%6dms\n",end-start);
SqListToFile(&List2,fp);
fclose(fp);
fp=fopen("GnomeSort.txt","w");
printf("地精排序用时:
");
start=clock();
GnomeSort(&List3);
end=clock();
printf("%6dms\n",end-start);
SqListToFile(&List3,fp);
fclose(fp);
fp=fopen("PigeonholeSort.txt","w");
printf("鸽巢排序用时:
");
start=clock();
PigeonholeSort(&List4);
end=clock();
printf("%6dms\n",end-start);
SqListToFile(&List4,fp);
return0;
}
voidInitSqList(PListList)//函数功能:
链表初始化
{
if(!
(List->elem=(ElemType*)malloc((MAX+1)*sizeof(ElemType))))
exit
(1);
List->length=MAX;
}
voidRandomElemToSqList(PListList)//函数功能:
用随机数填充链表
{
time_tt;
ElemTypek;
inti;
srand((unsigned)time(&t));
for(i=1;i<=List->length;i++)
{
k=rand()%MAX;
List->elem[i]=k;
}
}
voidCopySqList(PListList1,PListList2)//函数功能:
链表复制
{
inti;
for(i=1;i<=List2->length;i++)
{
List1->elem[i]=List2->elem[i];
}
List1->length=List2->length;
}
voidSqListToFile(PListList,FILE*fp)//函数功能:
将链表的内容写入文件
{
inti;
for(i=1;i<=List->length;i++)
{
fprintf(fp,"%6d",List->elem[i]);
if(i%17==0)
fprintf(fp,"\n");
}
}
voidInsertSort(PListList)//函数功能:
插入排序
{
inti,j;
for(i=2;i<=List->length;i++)
{
if(List->elem[i]
{
List->elem[0]=List->elem[i];
List->elem[i]=List->elem[i-1];
for(j=i-2;;j--)
{
if(List->elem[0]>List->elem[j])
break;
List->elem[j+1]=List->elem[j];
}
List->elem[j+1]=List->elem[0];
}
}
}
intPartition(PListList,intlow,inthigh)//函数功能:
将链表分成两部分,前面小于pivotkey,后面大于pivotkey
{
ElemTypepivotkey;
List->elem[0]=List->elem[low];
pivotkey=List->elem[low];
while(low { while(low --high; List->elem[low]=List->elem[high]; while(low ++low; List->elem[high]=List->elem[low]; } List->elem[low]=List->elem[0]; returnlow; } voidQSort(PListList,intlow,inthigh)//函数功能: 快速排序 { intpivotloc; if(low { pivotloc=Partition(List,low,high); QSort(List,low,pivotloc-1); QSort(List,pivotloc+1,high); } } voidGnomeSort(PListList)//函数功能: 地精排序,冒泡排序的变种 { inti=1; ElemTypee; while(i { if(1==i||List->elem[i-1]<=List->elem[i]) { i++; continue; } else { e=List->elem[i]; List->elem[i]=List->elem[i-1]; List->elem[i-1]=e; i--; continue; } } } voidPigeonholeSort(PListList)//函数功能: 鸽巢排序 { inti,j,k=1; ElemType*ph; if(! (ph=(ElemType*)malloc(MAX*sizeof(ElemType)))) { printf("溢出\n"); return; } for(i=0;i ph[i]=0; for(i=1;i<=List->length;i++) { ph[List->elem[i]]++; } for(i=0;i { for(j=0;j List->elem[k++]=i; } } 6、参考文献 1严蔚敏,吴伟民编著.数据结构(C语言版)--北京: 清华大学出版社,2007. 2严蔚敏,吴伟民米宁编著.数据结构题集(C语言版)--北京: 清华大学出版社,2007. 3网上搜索相关程序作为参考 7、程序运行结果 运行截图 快速排序: 插入排序: 地精排序: 鸽巢排序:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排序