《数据结构课程设计报告(各种排序实现及对比)》由会员分享，可在线阅读，更多相关《数据结构课程设计报告(各种排序实现及对比)（35页珍藏版）》请在金锄头文库上搜索。
1、课 程 设 计 报 告课程名称课程名称 数据结构数据结构 课题名称课题名称 1.成绩排序 2.通讯录管理 专专 业业 计算机科学与技术计算机科学与技术 班班 级级 计算机计算机 1281 学学 号号 04 姓姓 名名 刘恒刘恒 指导教师指导教师 刘铁武刘铁武 2014 年年 6 月月 22 日日 2设计题目设计题目成绩成绩各种排序一、算法设计的思想算法设计的思想3.1 简单选择排序简单选择排序基本思想每一趟在n-i+1(i=1,2,n-1)个记录中选取关键字最小的记录作为有 序序列的第 i 个关键字。 3.5 快速排序快速排序基本思想快速排序的基本思想是基于分治策略的。对于输入的子序列 Lpr
2、， 如果规模足够小则直接进行排序，否则分三步处理 ：分解(Divide)：将输入的序列 Lpr划分成两个非空子序列 Lpq和 Lq+1r，使 Lpq中任一元素的值不大于 Lq+1r中任一元素的值 。递归求解(Conquer)：通过递归调用快速排序算法分别对 Lpq和 Lq+1r进行排序。合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以 在 Lpq和 Lq+1r都排好序后不需要执行任何计算 Lpr就已排好序。302135467ny二、二、算法的流程图算法的流程图4.1 主函数的算法流程图主函数的算法流程图开始输入数据个数 lengthcreate(), visit()sele
3、ctExit( 0)select _sort( L);Zhiji e(L)Shell Sort( )Mao pao( L);Quic kSor t(L);select_sort(L); Zhijie(L); ShellSort(L,dlta,4); Maopao(L); QuickSort(L); print(num);输入select输入 y/n结束44.6 快速排序的算法流程图（快速排序的算法流程图（1）真L.r0=L.rlow Pivotkey=L.rlow.keyL,low,highLow=pivotkey7754.7 快速排序的算法流程图（快速排序的算法流程图（2）算法设计分析算法设
4、计分析 5.5 快速排序快速排序 快速排序是通过比较关键码、交换记录，以某个记录为界(该记 录称为支点)，将待排序列分成两部分。其中，一部分所有记录真假L，low，highLowlength=length;for(i=1;ilength;i+) L-ri.key=rand()%1000;L-ri.other=rand()%26+65; 定 选择排 序直接选择排 序O(n2)O(n2)O(n2)不稳 定8/*输出元素*/void visit(SqList L)int i;printf(“n“);for(i=1;iL.rk.key)j=k; if (i!=j)t=L.rj;L.rj=L.ri;L.
5、ri=t;r.move =r.move +3;if(!flag) printf(“本次随机数据排序的移动次数为:“);printf(“%dn“,r.move);printf(“本次随机数据排序的比较次数为:“);printf(“%dn“,p);9printf(“简单选择排序后的结果：“);visit(L); elsenum0=r.move;num1=p; /直接插入排序 void Zhijie(SqList L) Recode r; p =0; r.move =0;int j;for(int i=2;ilength ;+i) r-comp +; if(L-ri.keyri-1.key) L-r
6、0=L-ri; /暂存 r-move +; for(j=i-dk;j0j-=dk) L-rj+dk=L-rj; /记录后移 r-move +; r-comp +; L-rj+dk=L-r0; /插入到正确位置 r-move +; har c; int select,length;SqList L; do printf(“请输入需排序的数据个数(小于 200)：n“); scanf(“%d“,create(printf(“产生的随机序列为：n“);visit(L);do printf(“nn * 欢迎进入排序 系统 *n “);printf(“ 1 选择排序 2.直接插入排序 3.希尔排序 4.
7、冒泡排序 n “);11printf(“ 5 快速排序 6.比较以上排序 7.更改数据 0.退出 n “);printf(“ Please input number（0-7）n“);scanf(“%d“,switch (select) case 0:exit(0);case 1: select_sort(L); / break; case 2: break;case 3:ShellSort(L,dlta,5); break;case 4:Maopao(L); break;case 5:QuickSort(L); break; case 6: flag=1;select_sort(L);ZQui
8、ckSort(L);print(num);flag=0;break; case 7: break;default:printf(“输入错误！请重新输入n“); break;if(select=7) break; while(1); printf(“是否更换数据重新进行排序？(y/n)“);12getchar();c=getchar();if(c=n|c=N)break;system(“cls“); while(1);二、二、体会体会我们感受最深的一点是：以前用 C 编程，只是注重如何编写函 数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的 意识和简单的语句来堆砌出一段程序。但现在编程感
9、觉完全不同 了。在编写一个程序之前，自己能够综合考虑各种因素，首先选 取自己需要的数据结构，然后选定一种或几种存储结构来具体的 决定后面的函数的主要风格。最后在编写每一个函数之前，可以 仔细斟酌比对，挑选出最适合当前状况的算法。这样，即使在完 整的还没有写出来之前，自己心中已经有了明确的原图了。这样 无形中就提高了自己编写的程序的质量。我们还体会到深刻理解 数据结构的重要性。只有真正理解定义数据类型的好处，才能用 好这样一种数据结构。了解典型数据结构的性质是非常有用的， 它往往是编写程序的关键。这次实验中我们也出现过一些错误。 但我们经过反复调试后，发现并做了修改，从而完成了此次课程 设计。
10、在这次的数据结构课程设计中，我此次的题目是各种排序，排序 实际上是编程设计中应用比较广泛的知识，通过本次设计，我对 一些基本的内部排序有了很好的理解和掌握，并且通过此次课程 设计中的程序运行结果很好的理解了排序各种算法的稳定性和时 间复杂度，既巩固了课堂上学到的排序理论，又为自己的编程增 强了实践。总之，在这次的数据结构课程设计中，收获还是蛮多 的。13算法分析整个系统共分为 8 模块，主函数加 7 个子函数，从而实现 7 大功能：写入数据，读取数据，追加数据，查找数据，备份数据，删除数据，还原数据；各个程序的算法分析如下：（1） 主函数主函数 main()：利用 for( ; ; )和 sw
11、itch()实现主界面的显示与各选项的连接；流程图如下：14开始输入要运行的功 能的序号判断用户的 输入写入数据读取数据追加数据查找数据备份数据删除数据还原数据结束15（2） 写入函数写入函数 void input1()：利用文件的 fwrite()语句来实现数据的保存；流程图如下：开始输入 y 或 n用 if 判断输入 了 y 还是 nyn输入要输入 的资料将数据保存到指定 的文件里结束16（3） 读取数据读取数据 void read1()：利用文件的 fread()语句来实现数据的读取；流程图如下开始打开文件定义变量 int ifor(i=0；i #define N 50 struct a
12、ddress char name20; char city15; char email20; unsigned long phone; unsigned long zip; stuN; void input1() FILE *fp; int i; char n; printf(“Be careful!Do you sure to input?(y/n):777n“); n=getchar(); n=getchar(); if(n!=y) return; else fp=fopen(“txl“,“wb“); for(i=0;iN;i+) printf(“Input the name(Input
13、exit return):n“); scanf(“%s“,stui.name); if(strcmp(stui.name,“exit“)=0) return; else 25printf(“Input the city:n“); scanf(“%s“,stui.city); printf(“Input the email:n“); scanf(“%s“,stui.email); printf(“Input the phone:n“); scanf(“%ld“, printf(“Input the zip:n“); scanf(“%ld“, fwrite( fclose(fp); void read1() FILE *fp; int i; if(fp=fopen(“txl“,“rb“)=NULL) printf(“Can not to open the txl.n“); return; printf(“= =n“); printf(“ Name City Email Phone Zip n“); printf(“=26=n“); for(i=0;fread(i+) printf(“%15s%15s%20s%15ld%10ldn“,stui.name,stui.city,stui.email,stui.phone,stu
