数据结构课程设计报告

数据构造课程设计报告一． 前沿：排序是数据构造中的一块难点，也是重点。娴熟的把握各种各样的排序算法是对每个编程人员的根本的要求。历年的考研还是期末考中，排序都占了比较大的比重。二．程序实现的功能：本程序承受了各种不同的方法对同一个输入进展排序，且每一个元素其本身亦是一个构造体，又可以进展扩大，使其可以存储其他的相关的信息。在此我仅仅举了构造体本身只有一个元素的状况。a)承受的数据类型：为了争论的便利，本程序承受了复合型的构造体类型，且才用了静态〔留意。具体如下：typedefstruct{ //每个元素的类型定义，为了争论的便利本程序承受了单关键字；intkey; //但可以依据需要扩大，每个关键字令其为整型的；}redtype;typedefstruct{ //开拓的数组，以上述类型的元素组成；redtype*r; //存入要输入的元素的数组；intlength; //数组的长度，shellsort中要用到；}sqlist;四．对局部头文件和函数的说明：<conio.h>：改头文件主要用来实现清屏，使得出的结果更清楚明白。“shellsort(sqlistl,intd)”：该函数主要实现希尔排序，使无序的数据排列成有序的序列“quicksort(sqlistl,intlow,inthigh)”：该函数实现的功能同上，只是原理不同成为大顶堆，即树型构造的最上面是值最大的，这样进过一次的调整便得到了值最大的元素，即可进过屡次的排序使一个无序的序列又序。“heapsort(sqlist l)”：该函数实现建立堆的过程。在其中间调用heapadjust实现最终建立大顶的任务。“oesort(sqlistt”该函数进展奇偶排序将无序的数据排成有序的五． 核心程序算法：voidshellsort(sqlist&l,intd){//承受希尔排序，本程序中的l.r[0].key使暂存单元，非哨兵。d=l.length/2;while(d>0){for(i=d+1;i<=l.length;++i)if(l.r[i].key<l.r[i-d].key){l.r[0]=l.r[i];for(j=i-d;j>0&&l.r[0].key<l.r[j].key;j-=d)l.r[j+d]=l.r[j];l.r[j+d]=l.r[0];}d=d/2;}}根本思想：nd1作为第一个增量，把文件的全部记录分成d1个组。全部距离为dl的倍数的记录放在同一个组中。先在各组内进展直接插人排序；然后，取其次个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即全部记录放在同一组中进展直接插入排序为止。该方法实质上是一种分组插入方法voidquicksort(sqlist&l,intlow,inthigh){//快速排序if(low<high));//r[low..high]进展一次快速排序{i=low;j=high;l.r[0]=l.r[i];do{while(i<j&&l.r[j].key>l.r[0].key)--j;if(i<j){l.r[i]=l.r[j];++i;}while(i<j&&l.r[i].key<=l.r[0].key)++i;if(i<j){l.r[j]=l.r[i];--j;}}while(i!=j);l.r[i]=l.r[0];quicksort(l,low,i-1);r[low..i-1]进展快速排序quicksort(l,i+1,high);r[I+1.high]进展快速排序}}根本思想设当前待排序的无序区为r[low..high]，利用分治法可将快速排序的根本思想描述为：①分解：在r[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间 r[low..pivotpos-1]和r[pivotpos+1..high]，并使左边子区间中全部记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中全部记录的关键字均大于等于pivot.ke而基准记录pivot则位于正确的位置(pivotpos上它无须参与后续的排序。留意：划分的关键是要求出基准记录所在的位置pivotpos 。划分的结果可以简单地表示为( 注pivot=r[pivotpos])r[low..pivotpos-1].keys≤r[pivotpos].key≤r[pivotpos+1..high].keys其中low≤pivotpos≤high。②求解：通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和r[pivotpos+1..high]快速排序③组合由于当“求解“步骤中的两个递归调用完毕时，其左、右两个子区间已有序。对快速排序而言，“组合“步骤无须做什么，可看作是空操作。voidheapadjust(sqlist&l,ints,intm){///筛选法调整堆，使其成为大顶堆rc=l.r[s].key;for(j=2*s;j<=m;j*=2){if(j<m&&l.r[j].key<l.r[j+1].key)j++;if(rc>l.r[j].key)break;l.r[s].key=l.r[j].key;s=j;}l.r[s].key=rc;}voidheapsort(sqlist&l){//建堆的过程for(i=l.length/2;i>0;i--)heapadjust(l,i,l.length);for(i=l.length;i>1;i--){t=l.r[1].key,l.r[1].key=l.r[i].key,l.r[i].key=t;heapadjust(l,1,i-1);}}根本思想：堆排序利用了大根堆堆顶记录的关键字最大这一特征，使得在当前无序区中选取最大关键字的记录变得简洁。先将初始文件R[1..n]建成一个大根R[1](即堆顶)和无序区r[n]r[1..n-1]r[n]，且满足r[1..n-1].keys≤r[n].key。由于交换后的根R[1]可能违反堆性质，故应将当前无序区r[1..n-1]r[1..n-1]中关键字最大的记录r[1]和该区间的最终一个记录R[n-1]交换，由此得到的无序区r[1..n-2]和有序区r[n-1..n]，且仍满足关系r[1..n-2].keys≤r[n-1..n].keys，同r[1..n-2]调整为堆。直到无序区只有一个元素为止。voidoesort(sqlist&l,intn){//奇偶交换排序change=1;标志变量，假设其为零，即两次更替的交换中都没有交换数据，即排序完毕while(change){change=0;for(i=1;i<n;i+=2)//堆奇数进展一趟排序if(l.r[i].key>l.r[i+1].key){t=l.r[i].key,l.r[i].key=l.r[i+1].key,l.r[i+1].key=t;change=1;}for(i=2;i<n;i+=2)//堆偶数进展一趟排序if(l.r[i].key>l.r[i+1].key){t=l.r[i].key,l.r[i].key=l.r[i+1].key,l.r[i+1].key=t;change=1;}}}算法过程：i扫描，②其次趟对序列中的全部偶数项iri]>r[i+1]，则交换它们。③第三趟有对全部的奇数项，第四趟对全部的偶数项，……④如此反复，直到整个序列全部排好序为止。五．源程序：#include“stdio.h“#include“malloc.h“#include“conio.h“#definemaxsize5typedefstruct{intkey;}redtype;typedefstruct{redtype*r;intlength;}sqlist;voidshellsort(sqlistl,intd){inti,j;d=l.length/2;while(d>0){for(i=d+1;i<=l.length;++i)if(l.r[i].key<l.r[i-d].key){l.r[0]=l.r[i];for(j=i-d;j>0&&l.r[0].key<l.r[j].key;j-=d)l.r[j+d]=l.r[j];l.r[j+d]=l.r[0];}d=d/2;}}voidquicksort(sqlistl,intlow,inthigh){inti,j;if(low<high){i=low;j=high;l.r[0]=l.r[i];do{while(i<j&&l.r[j].key>l.r[0].key)--j;if(i<j){l.r[i]=l.r[j];++i;}while(i<j&&l.r[i].key<=l.r[0].key)++i;if(i<j){l.r[j]=l.r[i];--j;}}while(i!=j);l.r[i]=l.r[0];quicksort(l,low,i-1);quicksort(l,i+1,high);}}voidheapadjust(sqlistl,ints,intm){intrc,j;rc=l.r[s].key;for(j=2*s;j<=m;j*=2){if(j<m&&l.r[j].key<l.r[j+1].key)j++;if(rc>l.r[j].key)break;l.r[s].key=l.r[j].key;s=j;}l.r[s].key=rc;};voidheapsort(sqlistl){inti,t;for(i=l.length/2;i>0;i--)heapadjust(l,i,l.length);for(i=l.length;i>1;i--){t=l.r[1].key,l.r[1].key=l.r[i].key,l.r[i].key=t;heapadjust(l,1,i-1);}}voidoesort(sqlistl,intn){intt,i,change;change=1;while(change){change=0;for(i=1;i<n;i+=2)if(l.r[i].key>l.r[i+1].key){t=l.r[i].key,l.r[i].key=l.r[i+1].key,l.r[i+1].key=t;change=1;}for(i=2;i<n;i+=2)if(l.r[i].key>l.r[i+1].key){t=l.r[i].key,l.r[i].key=l.r[i+1].key,l.r[i+1].key=t;change=1;}}}main{inti,j,low,high,a[maxsize+1];charch;sqlistl;clrscr;if(!l.r)printf(“overflow“);l.length=0;printf(“\n\npleaseinputfiveelements:\n\n“);for(i=1;i<maxsize+1;i++){scanf(“%d“,&a[i]);l.length++;}getchar;do{for(j=1,i=1;j<maxsize+1;i++,j++)l.r[i].key=a[j];printf(“\n\nusePanWeiFeng”sKeChenSheJi\n\n“);printf(“s:shellsort\tq:quicksort\n\n“);printf(“h:heapsort\te:oesort\n\n“);printf(“o:quit\n\n“);printf(“pleaseinputtheway:“);ch=getchar;clrscr;printf(“\n\ntheorignalarray:“);for(i=1;i<maxsize+1;i++)printf(“%d“,l.r[i].key);printf(“\n\n“);/*printf(“pleaseinputtheway:“);ch=getchar;*/getchar;switch(ch){case”s”:shellsort(l,l.length);printf(“\n\nthe odered arry:“);for(i=1;i<maxsize+1;i++)printf(“%d“,l.r[i].key);printf(“\n\n“);break;case”q”:low=1;high=l.length;quicksort(l,low,high);printf(“\n\nthe odered arry:“);for(i=1;i<maxsize+1;i++)printf(“%d“,l.r[i].key);printf(“\n\n“);break;case”h”:heapsort(l);printf(“\n\nthe odered arry:“);for(i=1;i<maxsize+1;i++)printf(“%d“,l.r[i].key);printf(“\n\n“);break;case”e”:oesort(l,l.length);printf(“\n\nthe odered arry:“);for(i=1;i<maxsize+1;i++)printf(“%d“,l.r[i].key);printf(“\n\n“);break;case”o”:exit(0);default:printf(“\n\nerror!writeagain!\n“);}}while(1);}六． 程序运行结果：当你编译连接通过后，运行。pleaseinputfiveelements:64583回车后消灭大括号内的局部{usePanWeiFeng”sKeChenSheJis:shellsort q:quicksorth:heapsort e:oesorto:quitpleaseinputtheway:}s输入s回车后消灭大括号内的局部{theorignalarray:64583the oderedarray:34568usePanWeiFeng”sKeChenSheJis:shellsort q:quicksorth:heapsort e:oesorto:quitpleaseinputtheway:}q输入q回车后消灭大括号内的局部{theorignalarray: