数据结构课程设计报告(各种排序实现及对比)

1、课 程 设 计 报 告课程名称 数据结构 课题名称 1.成绩排序 2.通讯录管理 专 业 计算机科学与技术 班 级 计算机1281 学 号 04 姓 名 刘恒 指导教师 刘铁武 2014年 6月 22日 设计题目 成绩各种排序一、 算法设计的思想3.1简单选择排序     <1> 基本思想 每一趟在n-i+1(i=1,2,n-1)个记录中选取关键字最小的记录作为有序序列的第i个关键字。3.5快速排序  <1> 基本思想     &#

2、160;快速排序的基本思想是基于分治策略的。对于输入的子序列Lp.r，如果规模足够小则直接进行排序，否则分三步处理：     分解(Divide)：将输入的序列Lp.r划分成两个非空子序列Lp.q和Lq+1.r，使Lp.q中任一元素的值不大于Lq+1.r中任一元素的值。     递归求解(Conquer)：通过递归调用快速排序算法分别对Lp.q和Lq+1.r进行排序。   合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在Lp.q和Lq+1.r都排好序后不

3、需要执行任何计算Lp.r就已排好序。   二、 算法的流程图4.1主函数的算法流程图开始输入数据个数lengthcreate(),visit()输入select7select6543210select_sort(L); Zhijie(L); ShellSort(L,dlta,4); Maopao(L); QuickSort(L); print(num);select_sort(L);QuickSort(L);Maopao(L);ShellSort()Zhijie(L)Exit(0)输入y/nny结束4.6快速排序的算法流程图（1）开始Low<high真-hi

4、gh假+low真Low<high&&L.rhigh.key<=pivotkey77L.rlow=L.rhighLow<high&&L.rhigh.key>=pivotkey77真L.r0=L.rlowPivotkey=L.rlow.key假L.rhigh=L.rlow结束L,low,high假4.7快速排序的算法流程图（2）开始真Low<highL,low=pivotloc+1,high=highPivotloc=partioion(L,low,high),low=low,high=pivotloc-1;Low<highL，l

5、ow，high假真假Pivotloc=partioion(L,low,high),low=low,high=pivotloc-1;QSort(L,low,pivotloc-1)结束算法设计分析5.5快速排序快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序列分成两部分。其中，一部分所有记录的关键码大于等于支点记录的关键码，另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键码有序。【效率分析】空间效率：快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递归调用层次

6、数与上述二叉树的深度一致。因而，存储开销在理想情况下为O(log2n)，即树的高度；在最坏情况下，即二叉树是一个单链，为O(n)。时间效率：在n个记录的待排序列中，一次划分需要约n次关键码比较，时效为O(n)，若设T(n)为对n个记录的待排序列进行快速排序所需时间。理想情况下：每次划分，正好将分成两个等长的子序列，则T(n)cn+2T(n/2) c是一个常数cn+2(cn/2+2T(n/4)=2cn+4T(n/4)2cn+4(cn/4+T(n/8)=3cn+8T(n/8)······cnlog2n+nT(1)=O(nlog2n)最坏情

7、况下：即每次划分，只得到一个子序列，时效为O(n2)。快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取支点记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。排序方法最好时间平均时间最坏时间稳定性插入排序直接插入排序O(n)O(n2)O(n2)稳定希尔排序O(n1.5)不稳定交换排序冒泡排序O(n)O(n2)O(n2)稳定快速排序O(nlogn)O(nlogn)O(n2)不稳定选择排序直接选择排序O(n2)O(n2

8、)O(n2)不稳定内部排序各种算法的性能比较(表)一、 源代码#include "stdlib.h"#include"stdio.h"#include"time.h"#define MAXSIZE 200typedef int KeyType;typedef struct /定义存储记录关键字及其他信息的结构体 KeyType key; char other;RedType;typedef struct /定义存储所有记录的结构体 RedType rMAXSIZE+1; int length;SqList;typedef struct

9、 int move; /*记录数据移动次数*/ int comp; /*记录数据比较次数*/ Recode;int dlta5=31,15,7,3,1; /初始化希尔排序的增量序列int num10=0; /记录每个排序方法的移动次数和比较次数int flag=0; /标记变量/利用产生的随即数模拟用户输入的数据void create(SqList *L,int length) int i; srand(time(0); L->length=length; for(i=1;i<=L->length;i+) L->ri.key=rand()%1000; L->ri.

10、other=rand()%26+65; /*输出元素*/ void visit(SqList L) int i; printf("n"); for(i=1;i<=L.length;i+) printf("%4d%2c",L.ri.key,L.ri.other); printf("n"); /*简单选择排序*/ void select_sort(SqList L) Recode r;p =0;r.move =0; int i,j,k; RedType t; for (i=1;i<L.length;i+) j=i; for (

11、k=i+1;k<=L.length;k+) p+; if (L.rj.key>L.rk.key) j=k; if (i!=j) t=L.rj; L.rj=L.ri; L.ri=t; r.move =r.move +3; if(!flag) printf("本次随机数据排序的移动次数为:"); printf("%dn",r.move); printf("本次随机数据排序的比较次数为:"); printf("%dn",p); printf("简单选择排序后的结果："); visit(L)

12、;elsenum0=r.move;num1=p; /直接插入排序void Zhijie(SqList L) Recode r;p =0;r.move =0; int j; for(int i=2;i<=L.length;+i) p +;if(L.ri.key<L.ri-1.key)L.r0=L.ri; /复制为哨兵L.ri=L.ri-1;r.move=r.move +2;for(j=i-2;L.r0.key < L.rj.key;-j)L.rj+1=L.rj; /记录后移r.move +;p +;L.rj+1=L.r0; /插入到正确位置r.move +;if(!flag)

13、printf("本次随机数据排序的移动次数为:"); printf("%dn",r.move); printf("本次随机数据排序的比较次数为:"); printf("%dn",p); printf("直接插入排序后的结果："); visit(L);elsenum2=r.move;num3=p; /希尔排序void ShellInsert(SqList *L,int dk,Recode *r)int i,j;for(i=dk+1;i<=L->length ;+i)r->comp

14、 +;if(L->ri.key<L->ri-1.key)L->r0=L->ri; /暂存r->move +;for(j=i-dk;j>0&&(L->r0.key < L->rj.key);j-=dk)L->rj+dk=L->rj; /记录后移r->move +;r->comp +;L->rj+dk=L->r0; /插入到正确位置r->move +;har c;int select,length; SqList L;doprintf("请输入需排序的数据个数(小于200

15、)：n");scanf("%d",&length); create(&L,length); printf("产生的随机序列为：n"); visit(L); do printf("nn * 欢迎进入排序系统 *n "); printf(" 1 选择排序 2.直接插入排序 3.希尔排序 4.冒泡排序 n "); printf(" 5 快速排序 6.比较以上排序 7.更改数据 0.退出 n "); printf(" Please input number（0-7）n

16、"); scanf("%d",&select); 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); Z QuickSort(L); print(num); flag=0; break;case 7: brea

17、k; default:printf("输入错误！请重新输入.n"); break; if(select=7) break;while(1);printf("是否更换数据重新进行排序？(y/n)"); getchar(); c=getchar(); if(c='n'|c='N') break; system("cls");while(1);二、 体会我们感受最深的一点是：以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。但现在编程感觉

18、完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。这样，即使在完整的还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。我们还体会到深刻理解数据结构的重要性。只有真正理解定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。这次实验中我们也出现过一些错误。但我们经过反复调试后，发现并做了修改，从而完成了此次课程设计。在这次的数据结构课程设计中

19、，我此次的题目是各种排序，排序实际上是编程设计中应用比较广泛的知识，通过本次设计，我对一些基本的内部排序有了很好的理解和掌握，并且通过此次课程设计中的程序运行结果很好的理解了排序各种算法的稳定性和时间复杂度，既巩固了课堂上学到的排序理论，又为自己的编程增强了实践。总之，在这次的数据结构课程设计中，收获还是蛮多的。算法分析整个系统共分为8模块，主函数加7个子函数，从而实现7大功能：写入数据，读取数据，追加数据，查找数据，备份数据，删除数据，还原数据；各个程序的算法分析如下：（1） 主函数main()：利用for( ; ; )和switch()实现主界面的显示与各选项的连接；流程图如下：开始输入要

20、运行的功能的序号判断用户的输入写入数据读取数据追加数据查找数据备份数据删除数据还原数据结束（2） 写入函数void input1()：利用文件的fwrite()语句来实现数据的保存；流程图如下：开始输入y或n用if判断输入了y还是nyn输入要输入的资料将数据保存到指定的文件里结束（3） 读取数据void read1()：利用文件的fread()语句来实现数据的读取；流程图如下开始打开文件定义变量int ifor(i=0；i<数据的行数；i+)fread()读出i行数据结束（4） 追加数据void append1()：利用fread()来读出文件里的数据，从而确定数据的数量，再在最后一条数

21、据后通过fopen(“文件名”,”ab”)来实现追加；流程图如下：开始定义变量int i,sum=0;for(i=0;i<数据行数；i+)读去i行的数据sum=sum+1for(i=sum;i<通讯录数据上限；i+)将数据加入到文件里用户输入要增加的数据结束（5） 查找数据void find1()通过strcmp()=0来实现数据的查找；流程图如下：开始定义变量int i;输入要查找的名字for(i=0;i<数据的行数；i+)判断strcmp(i行数据，输入名字)=0吗？YN输出该行数据结束（6） 备份数据void backup1()：通过将数据复制到另一个文件里的方法来实现

22、备份功能；流程图如下：开始打开保存数据的原文件打开一个新文件for(i=0;i<数据的行数；i+)定义变量int i;读取原文件里第i行的数据将读到的数据写入到新文件里结束 （7） 删除数据void delete1()：通过将后一行数据覆盖前一行数据的方法来实现删除功能；流程图如下：判断strcmp(i行数据，输入名字)=0吗？Yfor(j=i+1;j<数据的行数；j+)开始定义变量int i,j,n=0;for(i=0;i<数据的行数；i+)输入要删除的名字将第j行数据覆盖第j-1行数据n=n+1Nfor(i=0;i<n-1;i+)写入第i行数据结束（8） 还原数据c

23、omeback1()： 通过将已备份的数据复制到原来的这个文件里的方法来实现还原的功能；流程图如下：开始打开保存数据的原文件打开备份了数据的备份文件for(i=0;i<数据的行数；i+)定义变量int i;读取备份文件里第i行的数据将读到的数据写入到原文件里结束主要流程系统功能模块结构图： 主函数写入数据读取数据追加数据查找数据备份数据删除数据还原数据各模块功能的分析：（1）主函数：可让用户选择用系统的哪个功能，从而去连接到相应的子函数；（2）写入数据：让用户输入通讯录里的内容，并将内容保存好；（3）读取数据：显示通讯录里已保存的数据；（4）追加数据：让用户在通讯录原有数据中，再加上新的

24、数据；（5）查找数据：通过用户输入需要找的名字来找到相关资料；（6）备份数据：将已有数据进行备份；（7）删除数据：让用户删除想要删除的资料；（9）还原数据：使通讯录里的数据恢复到备份时的模样。程序源代码#include <stdio.h>#define N 50struct addresschar 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 sur

25、e to input?(y/n):777n");n=getchar();n=getchar();if(n!='y')return;elsefp=fopen("txl","wb");for(i=0;i<N;i+)printf("Input the name(Input exit return):n");scanf("%s",);if(strcmp(,"exit")=0)return;elseprintf("Input t

26、he city:n");scanf("%s",stui.city);printf("Input the email:n");scanf("%s",stui.email);printf("Input the phone:n");scanf("%ld",&stui.phone);printf("Input the zip:n");scanf("%ld",&stui.zip);fwrite(&stui,sizeof(struct

27、 address),1,fp);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("=n");for(i=0;fread(&stui,sizeof(struct address),1,

28、fp)!=0&&i<N;i+)printf("%15s%15s%20s%15ld%10ldn",,stui.city,stui.email,stui.phone,stui.zip);getch();fclose(fp);void append1()FILE *fp;int i,sum=0;if(fp=fopen("txl","rb")=NULL)printf("Can not to open the txl.n");return;for(i=0;fread(&stui

29、,sizeof(struct address),1,fp)!=0&&i<N;i+)sum+=1;fclose(fp);if(fp=fopen("txl","ab")=NULL)printf("Can not to open the txl.n");return;for(i=sum;i<N;i+)printf("Input the name(Input exit return):n");scanf("%s",);if(strcmp(,

30、"exit")=0)return;elseprintf("Input the city:n");scanf("%s",stui.city);printf("Input the email:n");scanf("%s",stui.email);printf("Inpute the phone:n");scanf("%ld",&stui.phone);printf("Inpute the zip:n");scanf("%l

31、d",&stui.zip);fwrite(&stui,sizeof(struct address),1,fp);fclose(fp);void find1()FILE *fp;int i,j;char s16;printf("Input the name:n");scanf("%s",s);if(fp=fopen("txl","rb")=NULL)printf("Can not to open the txl.n");return;for(i=0;fread(&

32、stui,sizeof(struct address),1,fp)!=0&&i<N;i+)if(strcmp(,s)=0)printf("=n");printf(" Name City Email Phone Zip n");printf("=n");printf("%15s%15s%20s%15ld%10ld",,stui.city,stui.email,stui.phone,stui.zip);getch(); fclose(fp);void backu

33、p1()FILE *fp1,*fp2;int i;if(fp1=fopen("txl","rb")=NULL)printf("Can not to open the txl.n");return;fp2=fopen("txl2","wb");for(i=0;fread(&stui,sizeof(struct address),1,fp1)!=0&&i<N;i+)fwrite(&stui,sizeof(struct address),1,fp2);fclose

34、(fp1);fclose(fp2);printf("The backup was done!n");getch();void delete1()FILE *fp;int i,j,n=0;char s16;printf("Input the name:n");scanf("%s",s);if(fp=fopen("txl","rb")=NULL)printf("Can not to open the txl.n");return;for(i=0;fread(&stui,s

35、izeof(struct address),1,fp)!=0&&i<N;i+)if(strcmp(,s)=0)for(j=i+1;fread(&stuj,sizeof(struct address),1,fp)!=0&&j<N;j+)strcpy(,);strcpy(stuj-1.city,stuj.city);strcpy(stuj-1.email,stuj.email);strcpy(stuj-1.phone,stuj.phone);strcpy(stuj-1.zip,stuj.z

36、ip);n+=1;fclose(fp);fp=fopen("txl","wb");for(i=0;i<n-1;i+)fwrite(&stui,sizeof(struct address),1,fp);fclose(fp);printf("The date was delete.");getch();comeback1()FILE *fp,*fp1;int i;if(fp1=fopen("txl2","rb")=NULL)printf("Can not to open th

37、e txl.n");return;fp=fopen("txl","wb");for(i=0;fread(&stui,sizeof(struct address),1,fp1)!=0&&i<N;i+)fwrite(&stui,sizeof(struct address),1,fp);fclose(fp1);fclose(fp);printf("The comback was done!n");getch();main()int a;for(;)printf(" * * * * *

38、 * * * * * * * * * * * * * * * * * * * *n");printf(" * * * * * * * * * * * * * * * * * * * * * * * * *n");printf(" * * * *n");printf(" * * * *n");printf(" * * (1)Input the data * *n");printf(" * * (2)Read the txl * *n");printf(" * * (3)Appe

39、nd the data * *n");printf(" * * (4)Find the data * *n");printf(" * * (5)Backup the data * *n");printf(" * * (6)Delete the data * *n");printf(" * * (7)Comeback the data * *n");printf(" * * * *n");printf(" * * * *n");printf(" * * *

40、* * * * * * * * * * * * * * * * * * * * * *n");printf(" * * * *n");printf(" * * (0)Exit * *n");printf(" * * * *n");printf(" * * * * * * * * * * * * * * * * * * * * * * * * *n");printf(" * * * * * * * * * * * * * * * * * * * * * * * * *n");printf

41、(" % % % % % % % % % % % % % % % % % % %n");printf(" % %n");printf(" % This program is make for Wu Feng! %n");printf(" % %n");printf(" % % % % % % % % % % % % % % % % % % %n");printf("Input 0-7:");scanf("%d",&a);switch (a)case 1: input1();break;case 2: read1();break;case 3: append1();break;case 4: find1();break;case 5: backup1();break;case 6: delete1();break;case 7: comeback1();break;case 0:printf("* * * * * * * * * * * * * * * * * * * * *n&quo