C语言课程设计说明书-排序算法系统设计.doc

课程设计说明书摘 要c是一种通用的程序设计语言，c语言在很多方面继承和发展了以往许多高级程序设计语言的成功经验和特色，具有书写格式自由、数据类型丰富、语句功能强大、执行速度快和存储控制能力强等优点。排序算法系统设计是关于顺序表排序算法来设计的一个系统。整个系统从符合操作简便、界面友好、灵活、实用、安全的要求出发，完成顺序表排序算法的全过程，包括直接插入排序、二分法插入排序、直接选择排序、冒泡排序、两路冒泡排序、分块归并排序、归并排序以及重新生成随机数组。本课程主要介绍了本课题的开发背景，所要完成的功能和开发的过程。重点说明了系统的设计思路、总体设计、各个功能模块的设计与实现方法。关键词：排序算法系统，c语言，数据结构，cfreev5.0目录1课题背景的介绍11.1 课题背景11.2 目的12需求分析22.1 数据需求分析22.2 功能需求分析23系统总体设计33.1 系统模块划分33.2 系统模块结构图34系统详细设计44.1 系统主界面设计44.2初始化学生信息44.3查找学生信息44.4删除学生信息54.5更新学生信息54.6排序74.7统计学生信息114.8插入学生信息115系统连编与运行126总 结13参考文献14第 2 页 共 18 页1 课题背景的介绍1.1 课题背景算法是程序的核心，对数据进行排序是各种管理系统中不可缺少的一部分，大量的数据进行排序处理，算法的好坏决定着程序的执行效率以及用户的使用感受，而作为最为常用的顺序表存储结构排序，我们针对其设计了一个排序算法系统，并将归并排序和冒泡排序进行优化设计，这也是我们研究这个课程的目的。为了能够更好的来实现对顺序表结构的数据排序，通过对日常工作的详细调查，搜集了大量的资料，从系统结构的组织，功能的实现，技术的要求以及可行性等多方面进行考虑，认为本课题是一个适应现今排序算法需求的计算机排序算法系统，具有一定的实际开发价值和使用价值。1.2 目的本课题运用c语言进行开发，c语言能够简单的进行编译一些程序，来实现对一些问题的解决。它虽然比较简单的处理一些问题，但却有更高的效率。它能够被大多数用户所接受，因为它能够呈现出清晰的界面，是人们能够很好的理解。能在一些方面给人们更好的服务，成为人们的好帮手。经过这一个学期对数据结构的学习，我们都学到了不少东西，可能有些学的还不够理想，但无论如何这些知识都为我们的下一步学习打下了坚实的基础。做这么一个课程设计，一方面是为了检查我们一个学期以来的学习成果，另一方面也是为了让我们进一步的掌握和运用它，同时也让我们认清自己的不足之处和薄弱环节，加以弥补和加强。2 需求分析随着日常处理数据规模的不断扩大，程序向着大型化，规模化发展，而对于数据排序效率的要求不断提高。在这种情况下单靠人工来处理信息不但显得大不从心，而且极容易出错。因此，需要开发排序算法系统，该系统可以实现由计算机代替人工执行一系列复杂而繁琐的排序操作，使得程序设计人员可以轻松快捷的完成对各种数据的排序管理的任务。2.1 数据需求分析本系统的主要数据是顺序表数组。为了有更好的排序算法展示效果，数组的数据由单独的随机数组生成函数创建。2.2 功能需求分析本系统主要实现对数据的各种排序算法，需要实现以下几个方面的功能：（1）直接插入排序（2）二分法插入排序（3）直接选择排序（4）冒泡排序（5）两路冒泡排序（6）分块归并排序（7）归并排序（8）重新生成随机数组3 系统总体设计3.1 系统模块划分本系统主要是对数据的排序算法，包括了排序算法有：直接插入排序，二分法插入排序，直接选择排序，冒泡排序，两路冒泡排序，分块归并排序，归并排序。整个系统分为以下几个模块。1、菜单模块 本模块实现菜单列表，通过用户选择列表调用相关函数实现功能。2、排序算法模块本模块用于实现对数据的各种排序算法。其中包括：1、直接插入排序2、二分法插入排序3、直接选择排序4、冒泡排序排序5、两路冒泡排序6、分块归并排序7、归并排序3.2系统模块结构图根据排序算法系统功能设计，对应的系统模块结构图如图3.2.1所示：图3.2.1 系统模块结构图冒泡排序归并排序法分块归并排序两路冒泡排序两路冒泡排序二分法排序直接插入法直接选择法退出各种排序算法重新生成数组程序菜单4 系统详细设计4.1 系统主界面设计统过对该系统设计的了解与讨论，同时也为了广大使用者的方便与快捷。我们最后设计了这样的一个界面。首先要让使用者明白怎样使用此系统。这就需要通过界面来给他们一个清晰而明白的空间。而我们设计的这个界面恰好符合了这一要求。通过调用界面函数来使使用者能够很方便的进行各种排序算法的操作。doputlogo();printf( 1直接插入排序n);printf( 2二分法插入排序n);printf( 3直接选择排序n);printf( 4冒泡排序n);printf( 5两路冒泡排序n);printf( 6分块归并排序 n);printf( 7归并排序n);printf( 8重新生成随机数组n);printf( 9退出n);printf(n 请用键盘选择：);key=userchoice(123456789); /提高运行效率 确保每一次循环都有效if(key != 9)cls;switch(key)case 1:/直接插入排序 tmp = straitsort(l); outputsqlist(tmp); break;case 2:/二分法插入排序 tmp = bisort(l); outputsqlist(tmp); break;case 3:/直接选择排序 tmp = directbisort(l); outputsqlist(tmp); break; case 4:/冒泡排序 tmp = maopaobisort(l); outputsqlist(tmp); break; case 5:/两路冒泡排序 tmp = twinbubblesort(l); outputsqlist(tmp); break; case 6:/分块归并排序 tmp = l; showmergerlistplus(l, s); break; case 7:/归并排序 tmp = l; mergesort(tmp); outputsqlist(tmp); break; case 8:/重新生成随机数组 createsqlist(l);/创建随机数数组 outputsqlist(l); break;if(key != 9)pause;while(key!=9);4.2创建部分有序随机数组为排序算法创建随机数组。void createsqlist(sqlist &l)sqlist tmp;l = tmp;int irand;/随机数 int rndlength;/随机有序数个数 printf(请输入数组长度：); do scanf(%d, &l.length); if (l.length maxsize) printf(输入有误！请重新输入n); while (l.length maxsize); srand(unsigned)time(null);/初始化随机数 for(int i=0; i= l.length)/检查生成随机数数量是否超过要求数量 rndlength = l.length - i; printf(n%d个随机数 已生成%d个:, rndlength,i); for(int j=0; jsta = -1; p-end = -1;/ -1 + 1 = 0 即为初个分组起始下标 for(i=0; i l.datai)/*找到位置！（当前数小于tmp）*/ r = (spscope *)malloc(sizeof(spscope) r-sta = p-end + 1;r-end = i - 1;p-next = r; p = r; tmp = l.datai; r = (spscope *)malloc(sizeof(spscope);/补上末尾最后一组元素 r-sta = p-end + 1;r-end = i - 1; p-next = r; p = r; p-next = null;/*合并两个数组块*/void mergerlist(sqlist &l, spscope *s1, spscope *s2)int *temp;/临时存储排序后的合并数组 int p=0;/p为temp数组下标 int i=s1-sta;int j=s2-sta;temp = (int *)malloc(s2-end - s1-sta + 1)*sizeof(int); while(iend & jend)/块比较后取数 if(l.datai l.dataj)tempp = l.datai;i+;elsetempp = l.dataj;j+;p+;if(i end)/剩余部分直接插入temp数组末尾 while(i end)tempp = l.datai;i+;p+;else if(j != s2-end)while(j end)tempp = l.dataj;j+;p+;for(int i=0,j=s1-sta; p0; p-,i+,j+)/用temp数组覆盖原数组 l.dataj = tempi;/*合并所有数组块*/ void mergerlistall(sqlist &l, spscope s)spscope *s1, *s2, *p;s1 = s.next;s2 = s1-next;int i=1;while(s.next-next != null)/只要分割表内有两个以上元素就继续循环 printf(nn%d-%d %d-%d, s1-sta,s1-end, s2-sta,s2-end);mergerlist(l, s1, s2);/合并块 p = s2;/分割表合并 s1-end = s2-end;s1-next = s2-next;s1 = s1-next;/将指针指向下两个元素if(s1 != null)/若s1为null，则访问s1-next将会出错！ s2 = s1-next;elses2 = null;free(p);if(s2 = null)/组合已到末尾 重头继续开始合并 s1 = s.next;s2 = s1-next;printf(n*第%d次合并*, i+);outputlist(l);4.4两路冒泡排序 本算法是对冒泡排序算法的改进算法。/*两路冒泡排序*/sqlist twinbubblesort(sqlist l) int i,j,k,l;int exchangemax, exchangemin;/是否发生交换标记 int tmp;/交换临时变量 for(i=0; il.length-1; i+) /冒泡出一个最大数 exchangemax = 0; j = i; while(j l.dataj+1)/找到位置！ 交换（找最大） exchangemax = 1; tmp = l.dataj; l.dataj = l.dataj+1; l.dataj+1 = tmp; j+; if(exchangemax = 0) return l; /冒泡出一个最小数 exchangemin = 0; k = i;/起始下标 l = l.length-1-i-1;while(k l)if(l.datal l.datal-1)/找到位置！ 交换（找最小） exchangemin = 1; tmp = l.datal; l.datal = l.datal-1; l.datal-1 = tmp; l-;if(exchangemin = 0) return l; /输出结果 printf(n); for(int p=0; pl.length; p+) printf(%d , l.datap); printf(n); return l;4.5直接插入排序/*直接插入排序*/sqlist straitsort(sqlist l) int i,j,x; for(i=1; i-1)&(l.datajx) l.dataj+1=l.dataj; j-; l.dataj+1=x; return l;4.6二分法插入排序/*二分法插入排序*/sqlist bisort(sqlist l) int i,low,high,mid,x,k; for(i=1; i=l.length-1; i+) x=l.datai; low=0; high=i-1; while(lowx) high=mid-1; else low=mid+1; for(k=i-1; k=low; k-) l.datak+1= l.datak; l.datahigh+1=x; return l;4.7直接选择排序/*直接选择排序*/sqlist directbisort(sqlist l) int i,k,j,x; for(i=0; i=l.length-2; i+) k=i; for(j=i+1; jl.dataj) k=j; if(k!=i) x=l.datak; l.datak=l.datai; l.datai=x; return l;4.8冒泡排序/*冒泡排序*/sqlist maopaobisort(sqlist l) int i,j,k,flag; for(i=0; i=l.length-2; i+) flag=0; j=0; while(j=l.dataj+1) flag=1; k=l.dataj; l.dataj=l.dataj+1; l.dataj+1=k; j+; if (flag=0) return l; return l;4.9归并排序/*归并排序*/void merge(sqlist &l, int low, int mid, int high)int *temp;/临时存储排序后的合并数组 int i=low, j=mid+1, k=0;temp = (int *)malloc(high - low + 1)*sizeof(int);/动态分配数组空间 while(i=mid & j=high)if(l.datai l.dataj)tempk = l.datai;i+;k+;elsetempk = l.dataj;j+;k+;while(i = mid)tempk = l.datai;i+;k+;while(j = high)tempk = l.dataj;j+;k+;for(k=0,i=low; i=high; k+,i+)/用temp数组覆盖原数组 l.datai = tempk;void mergepass(sqlist &l, int length, int n)int i;for(i=0; i+2*length-1n; i=i+2*length)merge(l,i,i+length-1,i+2*length-1);if(i+length-1 n)merge(l,i,i+length-1,n-1); void mergesort(sqlist &l)int length;for(length=1;lengthl.length;length=2*length)mergepass(l,length,l.length);5 系统连编与运行一个应用系统设计和创建完成后，还必须进行连编，以便生成一个可执行文件供最终用户使用。连编完成后还要运行，以检查整个系统的完整性和准确性，同时还可增加程序代码的保密性。（1）进行编译