支付数据结构实验实例.doc

目录一、实验题目-1二、实验目的-1三、实验内容-1四、实验要求-1五、实验环境-1六、实验过程-1七、实验结果-9一、实验题目排序算法验证二、实验目的1掌握常用排序方法的基本思想及其实现技术2了解各种排序方法的优缺点和适用范围三、实验内容实现冒泡排序、直接插入排序、选择排序和快速排序，并比较各种排序算法的运行速度。四、实验要求1采用顺序表存放排序的记录，设关键字类型为典型。2设计一个菜单，以菜单方式选择上述排序方法。3程序执行时，能按趟输出排序的结果。4对每种基本排序方法改进算法，再给出改进算法前后的实验结果：（1）随机生成10个随机数进行排序的结果；（2）分别给出升序和降序的随机数排序的结果。5对上述四种算法给出结论性意见，说明改进算法后的效果明显或不明显的原因。五、实验环境软件需求：C语言硬件需求：微型计算机六、实验过程1实验步骤（1）理解顺序表排序的基本实验原理；（2）仔细分析实验内容，给出其算法和流程图；（3）用C语言实现该算法；（4）给出测试数据，并分析其结果；（5）在实验报告册上写出实验过程。2算法步骤（1）文件的类型说明typedef struct keytype key; infotype otherinfo; rectype; typedef rectype seqlistn+1; （2）主函数调用void main() 生成需要排序的关键字，选择调用各排序的算法；（3）算法调用void insertsort(); 插入排序算法，输入趟数，按趟输出排序的结果；void rubblesort(); 起泡排序算法，输入趟数，按趟输出排序的结果；void quicksort(int low,int high); 快速排序算法，调用int partition(int i,int j)函数对Rlow到Rhigh做划分，输入趟数，按趟输出排序的结果；void selectsort(); 选择排序算法，输入趟数，按趟输出排序的结果；（4）返回主函数3算法修改随机生成10个随机数进行升序和降序的随机数排序的程序如下：#include stdio.h#include stdlib.h1#define n 10 #define FALSE 0 #define TRUE 1 #define Maxsize 100typedef int keytype;typedef char infotype;typedef struct keytype key; infotype otherinfo; rectype; typedef rectype seqlistn+1;typedef rectype temlistn+1;int VMaxsizen+1;int m,num; int a=1,b=1;seqlist R;temlist T;void insertsort(); void rubblesort(); void quicksort(); void quicksort2();void selectsort(); int partition(int i,int j); int partition2(int i,int j);void main() seqlist s; temlist u; int i; char ch1,ch2; for(i=1;i=n;i+) si.key=rand()%1000; for(i=1;i=n;i+) ui.key=si.key; printf(Have generated randomly 10 sort numbers:n); for(i=1;i=n;i+)printf(%5d,si.key);printf(n); ch1=y; while(ch1=y|ch1=Y) printf(*Menu*n); printf(Please select option:n); printf( 1-Updata data-n); printf( 2-Insert sort-n); printf( 3-Rubble sort-n); printf( 4-Quick sort-n); printf( 5-Select sort-n); printf( 6-Quit sort-n); 2 printf(Please select operating type:); scanf(n%c,&ch2); switch(ch2) case1: for(i=1;i=n;i+) si.key=rand()%1000; printf(Have again generated randomly 10 sort numbers:n); for(i=1;i=n;i+) printf(%5d,si.key); printf(n); for(i=1;i=n;i+) ui.key=si.key; break; case2: printf(Please enter number of times for result:); scanf(%d,&m); for(i=1;i=n;i+) Ri.key=si.key; Ti.key=ui.key; insertsort(); break; case3: printf(Please enter number of times for result:); scanf(%d,&m); for(i=1;i=n;i+) Ri.key=si.key; Ti.key=ui.key; rubblesort(); break; case4: printf(Please enter number of times for result:); scanf(%d,&m); for(i=1;i=n;i+) Ri.key=si.key; Ti.key=ui.key; num=0; quicksort(1,n); quicksort2(1,n); break; case5: printf(Please enter number of times for result:); scanf(%d,&m); for(i=1;i=n;i+) Ri.key=si.key; 3 Ti.key=ui.key; selectsort(); break; case6: ch1=n; break; default: ch1=n; void insertsort() int i,j,k;for(i=2;i=n;i+) if(Ri.keyRi-1.key) R0=Ri; j=i-1; while(R0.keyTi-1.key) T0=Ti; j=i-1; while(T0.keyTj.key) Tj+1=Tj; j-; Tj+1=T0; if(i-1=m) printf(The ascending result is:%dn,m); for(k=1;k=n;k+) printf(%5d,Rk.key); printf(n); printf(The descending result is:%dn,m); for(k=1;k=n;k+) printf(%5d,Tk.key); printf(n); printf(Continue? Exit to press 0:n); scanf(%d,&m); 4 if(m!=0) printf(The ascending sort result is:n); for(k=1;k=n;k+) printf(%5d,Rk.key); printf(n); printf(The descending sort result is:n); for(k=1;k=n;k+) printf(%5d,Tk.key); printf(n); void rubblesort()int i,j,k;int exchange,exchange2;for(i=1;i=i;j-)if(Rj+1.keyTj.key)T0=Tj+1;Tj+1=Tj;Tj=T0;exchange2=TRUE;if(i=m)printf(The ascending result is:%dn,m);for(k=1;k=n;k+) printf(%5d,Rk.key);printf(n);printf(The descending result is:%dn,m);for(k=1;k=n;k+) printf(%5d,Tk.key);printf(n);printf(Continue? Exit to press 0:n);scanf(%5d,&m);if(!exchange)&(!exchange2)|(m=0)5break;if(m!=0)printf(The ascending sort result is:n);for(k=1;k=n;k+) printf(%5d,Rk.key);printf(n);printf(The descending sort result is:n);for(k=1;k=n;k+) printf(%5d,Tk.key);printf(n);int partition(int i,int j)int c=1;rectype pivot=Ri;while(ij)while(i=pivot.key)j-;if(ij)Ri+=Rj;while(ij&Ri.key=pivot.key)i+;if(ij)Rj-=Ri;Ri=pivot;for(b=1;b=n;b+) Vab=Rc.key;c+;a+;return i;void quicksort(int low,int high)int pivotpos;if(lowhigh)pivotpos=partition(low,high);quicksort(low,pivotpos-1);quicksort(pivotpos+1,high);int partition2(int i,int j)rectype pivot=Ti;while(ij)6while(ij&Tj.key=pivot.key)j-;if(ij)Ti+=Tj;while(i=pivot.key)i+;if(ij)Tj-=Ti;Ti=pivot;return i;void quicksort2(int low,int high)int pivotpos,k;if(lowhigh)pivotpos=partition2(low,high);num+;if(num=m)printf(The ascending sort result is:%dn,m);for(k=1;k=n;k+)while(Vmk=0) m-;printf(%5d,Vmk);printf(n);printf(The descending sort result is:%dn,m);for(k=1;k=n;k+)printf(%5d,Tk.key);printf(n);printf(Continue? Exit to press 0:n);scanf(%5d,&m);quicksort2(low,pivotpos-1);quicksort2(pivotpos+1,high); if(m!=0&Vmk=0)if(low=1&high=n) printf(The ascending sort result is:n);for(k=1;k=n;k+)while(Vmk=0) m-;printf(%5d,Vmk);printf(n);printf(The descending sort result is:n);for(k=1;k=n;k+)printf(%5d,Tk);7printf(n); while(m!=0&Vmk!=0) printf(The ascending sort result is:n);for(k=1;k=n;k+)printf(%5d,Vmk);printf(n); printf(The descending sort result is:n);for(k=1;k=n;k+)printf(%5d,Tk);printf(n);printf(Continue? Exit to press 0:n);scanf(%5d,&m); void selectsort()int i,j,k,h;for(i=1;in;i+)h=i;for(j=i+1;j=n;j+)if(Rj.keyRh.key)h=j;if(h!=i)R0=Ri;Ri=Rh;Rh=R0;for(j=i+1;jTh.key)h=j;if(h!=i)T0=Ti;Ti=Th;Th=T0;if(i=m)printf(The ascending result is:%dn,m);for(k=1;k=n;k+) printf(%5d,Rk.key);printf(n);printf(The descending result is:%dn,m);for(k=1;k=n;k+)8 printf(%5d,Tk.key);printf(n);printf(Continue? Exit to press 0:n);scanf(%5d,&m);if(m!=0)printf(The ascending sort result is:n);for(k=1;k=n;k+)printf(%5d,Rk.key);printf(n);printf(The descending sort result is:n);for(k=1;k=n;k+)printf(%5d,Tk.key);printf(n);七、实验结果1排序思想：（1）插入排序（Insertion Sort）的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的文件中的适当位置，直到全部记录插入完成为止。（2）起泡排序（Rubble Sort）的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。 3）快速排序（Quick Sort）又称划分交换排序。其基本思想是：在当前无序区R1到Rh中任取一个记录作为比较的“基准”（不妨记为temp），用此基准将当前的无序区划分为左右两个较小的无序子区：R1到Ri-1和Ri+1到Rh,且左边的无序子区中记录关键字均小于或等于基准temp的关键字，右边的无序子区中记录的关键字均大于或等于基准temp的关键字，而基准temp则位于最终排序的位置上，即： R1到Ri-1中关键字=temp.key=Ri+1到Rh的关键字（1=i=h） 当R1到Ri-1和Ri+1到Rh均非空时，分别对它们进行上述的划分过程，直到所有的无序子区中记录均已排好序为止。（4）选择排序（Selection Sort）的基本方法是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在排好序的子文件的最后，直到全部记录排序完毕。2运行结果：（1）第一次生成随机数排序结果：Have generated randomly 10 sort numbers: 41 845 460 67 568 60 709 967 529 968*Menu*Please select option: 1-Updata data- 2-Insert sort- 3-Rubble sort- 4-Quick sort- 5-Select sort-6-Quit sort-9Please select operating type:210The ascending sort result is: 41 60 67 460 529 568 709 845 967 968The descending sort result is: 968 967 845 709 568 529 460 67 60 41*Menu*Please select option: 1-Updata data- 2-Insert sort- 3-Rubble sort- 4-Quick sort- 5-Select sort- 6-Quit sort-Please select operating type:310The ascending sort result is: 41 60 67 460 529 568 709 845 967 968The descending sort result is: 968 967 845 709 568 529 460 67 60 41*Menu*Please select option: 1-Updata data- 2-Insert sort- 3-Rubble sort- 4-Quick sort- 5-Select sort- 6-Quit sort-Please select operating type:48The ascending sort result is: 41 60 67 460 529 568 709 845 967 968The descending sort result is: 968 967 845 709 568 529 460 67 60 41*Menu*Please select option:1-Updata data- 2-Insert sort- 3-Rubble sort- 4-Quick sort- 5-Select sort- 6-Quit sort-Please select operating type:510The ascending sort result is:10 41 60 67 460 529 568 709 845 967 968The descending sort result is:968 967 845 709 529 568 460 60 67 41（2）第二次生成随机数排序结果：*Menu*Please select option: 1-Updata data- 2-Insert sort- 3-Rubble sort- 4-Quick sort- 5-Select sort- 6-Quit sort-Please select operating type:1Have again generated randomly 10 sort numbers: 735 313 419 923 21 491 13 14 851 466*Menu*Please select option: 1-Updata data- 2-Insert sort- 3-Rubble sort- 4-Quick sort- 5-Select sort- 6-Quit sort-Please select operating type:210The ascending sort result is: 13 14 21 313 419 466 491 735 851 923The descending sort result is: 923 851 735 491 466 419 313 21 14 13*Menu*Please select option: 1-Updata data- 2-Insert sort- 3-Rubble sort- 4-Quick sort-5-Select sort- 6-Quit sort-Please select operating type:39The ascending sort result is: 13 14 21 313 419 466 491 735 851 923The descending sort result is:923 851 735 491 466 419 313 21 14 13*Menu*Please select option:11 1-Updata data- 2-Insert sort- 3-Rubble sort- 4-Quick sort- 5-Select sort- 6-Quit sort-Please select operating type:48The ascending sort result is: 466 313 4