完整版數(shù)據(jù)結(jié)構(gòu)試驗(yàn)9排序子系統(tǒng)

1、實(shí)驗(yàn)9 :排序子系統(tǒng)1.實(shí)驗(yàn)?zāi)康?1)掌握常用排序方法的根本思想.(2)通過(guò)實(shí)驗(yàn)加深理解各種排序算法.(3)通過(guò)實(shí)驗(yàn)掌握各種排序方法的時(shí)間復(fù)雜度分析.(4) 了解各種排序方法的優(yōu)缺點(diǎn)及適用范圍.2 .實(shí)驗(yàn)內(nèi)容(1)編寫直接插入排序程序.(2)編寫希爾排序程序.(3)編寫冒泡排序程序.(4)編寫快速排序程序.(5)編寫選擇排序程序.(6)編寫歸并排序程序.(7)編寫堆排序程序.(8)程序執(zhí)行時(shí),要求能顯示每一趟的排序結(jié)果.(9)設(shè)計(jì)一個(gè)選擇式菜單,以菜單方式選擇上述排序程序.排序子系統(tǒng)更新排序數(shù)據(jù)*直接插入排序1*3希爾排序*4冒泡排序*5快速排序*6選擇排序*7歸并排序*8堆排序*0返回*2*

2、請(qǐng)選擇菜單號(hào)(0-8 ):3 .實(shí)驗(yàn)程序#include #include #include#define L 8#define FALSE 0#define TURE 1 typedef struct int key;char otherinfo;RecType;typedef RecType SeqlistL+1;int num;Seqlist R;void Insertsort();void Bubblesort();void QuickSort(int low,int high);void Shellsort();void Selectsort();void Mergesort();i

3、nt Partition(int i,int j);void Heap();void main()Seqlist S;int i,k;char ch1,ch2,q;printf(nt 請(qǐng)輸入d個(gè)待排序數(shù)據(jù)(按【Enter 鍵分隔)：nt,L); for(i=1;i=L;i+)scanf(%d,&Si.key);getchar();printf(t);printf(nt排序數(shù)據(jù)已經(jīng)輸入完畢！)；ch1=y;while(ch1=y|ch1=Y)printf(n);printf(ntt排序子系統(tǒng));printf(ntt* *);printf(ntt* 1 更新排序數(shù)據(jù)*);printf(ntt*2

4、直接插入排序*);printf(ntt*3 希爾排序*);printf(ntt*4 冒泡排序*);printf(ntt*5 快速排序printf(ntt* 6 選擇 排序*)；printf(ntt* 7 歸并 排序 *);printf(ntt* 8 堆 排 序*)；printf(ntt* 0 返回*)；printf(ntt* *);printf(ntt 請(qǐng)選擇菜單號(hào)(0-8 ):);scanf(%c,&ch2);getchar();for(i=1;i=L;i+)Ri.key=Si.key;switch(ch2) case 1:nt,L););printf(nt 請(qǐng)輸入d個(gè)待排序數(shù)據(jù)(按【Ent

5、er】鍵分隔)for(i=1;i=L;i+)scanf(%d,&Si.key);getchar();printf(t);printf(nt排序數(shù)據(jù)已經(jīng)輸入完畢！)；break;case 2:Insertsort();break;case 3:Shellsort();break;case 4:Bubblesort();break;case 5:printf(nt原始數(shù)據(jù)為(按【Enter 鍵開始排序)for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);num=0;QuickSort(1,L);printf(nt排序的最終結(jié)果是：);for(

6、k=1;k=L;k+)printf(%5d,Rk.key);printf(n);break;case 6:Selectsort();break;case 7:Mergesort();break;case 8:Heap();break;case 0:ch1=n;break;default:printf(nt輸入出錯(cuò)！);)if(ch2!=0)(if(ch2=2|ch2=3|ch2=4|ch2=5|ch2=6|ch2=711ch2=8) printf(nt 排序輸出完畢！)；printf(nnt按回車鍵返回.);q=getchar();if(q!=xA) (getchar();ch1=n;)voi

7、d Insertsort()(int i,j,k,m=0;printf(nt原始數(shù)據(jù)為(按【Enter 鍵開始排序)：);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);for(i=2;i=L;i+)(if(Ri.keyRi-1.key)(R0=Ri;j=i-1;while(R0.keyRj.key) (Rj+1=Rj;j-;)Rj+1=R0;)m+;,m);printf(t第趟排序結(jié)果為(按【Enter 鍵繼續(xù))for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);)；print

8、f(nt排序的最終結(jié)果是:for(i=1;i=L;i+)printf(%5d,Ri.key);printf(n);void Shellsort()int i,j,gap,x,m=0,k;printf(nt 原始數(shù)據(jù)為(按【Enter 鍵開始排序)：);for(k=1;k0)for(i=gap+1;i0) if(Rj.keyRj+gap.key)x=Rj.key;Rj.key=Rj+gap.key;Rj+gap.key=x;j=j-gap;elsej=0;gap=gap,m);m+;printf(t第趟排序結(jié)果為(按【Enter 鍵繼續(xù))for(k=1;k=L;k+)printf(%5d,Rk.

9、key);getchar();printf(n);printf(nt排序的最終結(jié)果是：);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(n);void Bubblesort()(int i,j,k;int exchange;printf(nt 原始數(shù)據(jù)為(按【Enter 鍵開始排序)：)； for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);for(i=1;i=i+1;j-)if(Rj.keyRj-1.key)(R0.key=Rj.key;Rj.key=Rj-1.key;Rj-1.key=R0.key;

10、 exchange=TURE; if(exchange) (printf(t第趟排序結(jié)果為(按【Enter 鍵繼續(xù))：,i);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar(); printf(n);printf(nt排序的最終結(jié)果是：);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(n);int Partition(int i,int j)(RecType pirot=Ri;while(ij)(while(i=pirot.key)j-; if(ij)Ri+=Rj;while(ij&Rj.key=pirot.key)i+；

11、if(ij)Rj-=Ri； ) Ri=pirot;return i;)void QuickSort(int low,int high)(int pirotpos,k;if(lowhigh) (pirotpos=Partition(low,high);num+;printf(t第趟排序結(jié)果為(按【Enter 鍵繼續(xù))：,num);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);QuickSort(low,pirotpos-1);QuickSort(pirotpos+1,high);)void Selectsort()(int i,j,k

12、,h;printf(nt原始數(shù)據(jù)為(按【Enter 鍵開始排序)：)；for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);for(i=1;i=L;i+) (h=i;for(j=i+1;j=L;j+)if(Rj.keyRh.key) h=j;if(h!=j) (R0=Ri;Ri=Rh;Rh=R0;)printf(t 第趟排序結(jié)果為(按【Enter 鍵繼續(xù))：,i);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);printf(nt排序的最終結(jié)果是：);for(i=1;i=L;i+)

13、printf(%5d,Ri.key);printf(n);void Merge(int low,int mm,int high)int i=low,j=mm+1,p=0;RecType *R1;R1=(RecType *)malloc(high-low+1)*sizeof(RecType);if(!R1)printf(nt內(nèi)存容量不夠！);while(i=mm&j=high)R1p+=(Ri.key=Rj.key)?Ri+:Rj+;while(i=mm)R1p+=Ri+;while(i=high)R1p+=Rj+;for(p=0,i=low;i=high;p+,i+)Ri=R1p;void M

14、ergePass(int length)int i;for(i=1;i+2*length-1=L;i=i+2*length)Merge(i,i+length-1,i+2*length-1);if(i+length-1L)Merge(i,i+length-1,L);void Mergesort()int length,k,m=0;printf(nt原始數(shù)據(jù)為(按【Enter 鍵開始排序)：);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);for(length=1;lengthL;length*=2)MergePass(length);

15、m+;printf(t第趟排序結(jié)果為(按【Enter 鍵繼續(xù))：,m);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar(); printf(n);printf(nt排序的最終結(jié)果是：);for(k=1;k=L;k+)printf(%5d,Rk.key);printf(n);void CreateHeap(int root,int index)(int j,temp,finish;j=2*root;temp=Rroot.key;finish=0;while(j=index&finish=0)(if(jindex)if(Rj.key=Rj.key)finish=

16、1;else (Rj/2.key=Rj.key;j=j*2;Rj/2.key=temp;void HeapSort()(int i,j,temp,k;for(i=(L/2);i=1;i-)CreateHeap(i,L);for(i=L-1,k=1;i=1;i-,k+) (temp=Ri+1.key;Ri+1.key=R1.key;R1.key=temp;CreateHeap(1,i);printf(t第趟排序結(jié)果為(按【Enter 鍵繼續(xù))：,k);for(j=1;j=L;j+)printf(%5d,Rj.key);getchar();printf(n);void Heap()int i;pr

17、intf(nt原始數(shù)據(jù)為(按【Enter 鍵開始排序)：);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(nt);getchar();HeapSort();printf(nt排序的最終結(jié)果是：);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(n); 件文檔敕育學(xué)習(xí)數(shù)據(jù)幽孫驗(yàn)證性實(shí)噓 Debug供噓10 ：排序子基統(tǒng)a/口 回請(qǐng)輸入8個(gè)待排序數(shù)據(jù)按【血七】鍵分隔j ： 2258G孤71411S排序數(shù)據(jù)已經(jīng)輸入完畢！統(tǒng)系子序-rrrrr 莓開更直耆同選償返-12 3 4 56780,D：日件文檔款耳學(xué)習(xí)樓皮結(jié)構(gòu)驗(yàn)證性實(shí)蛉Deb

18、ug供蛉10 :排序子系院exb請(qǐng)選擇菜單號(hào).一8: 2151586原始數(shù)據(jù)為按Enter鍵開始排序：第1趟排序結(jié)果為第2趟排序結(jié)果為第3趟排序結(jié)果為第4趟排序結(jié)果為第5趟排序結(jié)果為第6趟排序結(jié)果為第7趟排序結(jié)果為25863614按Enter鍵繼續(xù)按tEnter鍵繼續(xù)按tEnter鍵繼續(xù)按Ent】鍵繼續(xù)按tEnterJ鍵繼續(xù)按LEnterJ鍵繼續(xù)按【Enter】鍵繼續(xù)排序的最終結(jié)果是:排序輸出完畢！按回車鍵返回.141586258636142536861425368614142536863614863612 3 4 5 6HrnrnrMrHhnpHI:節(jié)讓 D：整件文梭軟育學(xué)習(xí)樓或結(jié)構(gòu)蛉證性實(shí)

19、蛉Debug供蛉10 :排序子案短exe排序子系統(tǒng)*一一二-一 一 一 1 123456780更直希日展選根返二一二二二請(qǐng)選擇菜單號(hào)0-8： 4原始數(shù)據(jù)為按Entev鍵開始排序,86151515153686第1趟排序結(jié)果為第2趟排序結(jié)果為第3趟排序結(jié)果為第4趟排序結(jié)果為第5趟排序結(jié)果為按Enter鍵繼續(xù)按tEnter鍵繼續(xù)按tEnter鍵繼續(xù)按LEnter鍵繼續(xù)按Ent】鍵繼續(xù)排序的最終結(jié)果是,1 27排序輸出完畢！按回車鍵返回.143686141414867368625151514736862525D：d件文秘敕育學(xué)習(xí)擊況結(jié)構(gòu)臉證性實(shí)蛉Debug供蛉10 :排序子系院exe排序子系統(tǒng)排速擇并

20、 更直希日展選想返一 二二二二二一一二- 一 一 一 123456780*原始數(shù)據(jù)為按LEnter鍵開始排序,2258636714151515第1趟排序結(jié)果為第2趟排序結(jié)果為第3趟排序結(jié)果為第4趟排序結(jié)果為第5趟排序結(jié)果為第6趟排序結(jié)果為按LEnter鍵繼續(xù)按tEnter鍵繼續(xù)按tEnter鍵繼續(xù)按LEnter J鍵繼續(xù)按【Ent】鍵繼續(xù)按LEnter J鍵繼續(xù)251486868686863636363636368614142514141425Ei排序的取終結(jié)果是：17 36 86 14 252 15排序輸出完畢！按回車鍵返回.D：文件文秘蚊盲學(xué)習(xí)檄理結(jié)構(gòu)瞼證性實(shí)蛉Debug母蛉10 :排序子

21、系短exl1586868686123456780速擇并 子-更直希日展選根返請(qǐng)選擇菜單號(hào)0-8： 6原始數(shù)據(jù)為按Enter鍵開始排序：第1趟排序結(jié)果為第2趟排序結(jié)果為第3趟排序結(jié)果為第4趟排序結(jié)果為第5趟排序結(jié)果為第6趟排序結(jié)果為第7趟排序結(jié)果為第8趟排序結(jié)果為25863614按LEnter鍵繼續(xù)：按tEnterJ鍵繼續(xù)：按【Enter】鍵繼續(xù)：按【Enter】鍵繼續(xù)：按【Enter】鍵繼續(xù)：按tEnter鍵繼續(xù)：按EnterJ鍵繼續(xù)：按【Enter】鍵繼續(xù)：86361486361486148636361415251414127141525368615252333-D：汝件文極敷育學(xué)習(xí)樓百縛構(gòu)

22、驗(yàn)證性實(shí)蛉Debug母蛉10 :排序子系呢exb排序輸出完畢！按回車鍵返回.排序子系統(tǒng)158686868686868656780Lt 卻 速擇并 更直希日展選恨返請(qǐng)選擇菜單號(hào)0-8： 8原始數(shù)據(jù)為按rEnter鍵開始排序：第1趟排序結(jié)果為第2趟排序結(jié)果為第3趟排序結(jié)果為第4趟排序結(jié)果為第5趟排序結(jié)果為第G趟排序結(jié)果為第7趟排序結(jié)果為86按【Enter】鍵繼續(xù)：按【Enter】鍵繼續(xù)：按【Enter】鍵繼續(xù)：按tEnter鍵繼續(xù)：按EnterJ鍵繼續(xù)：按【Enter】鍵繼續(xù)：按【Ent】鍵繼續(xù)：25141414141414147?215151515133333 D;仁；叫齊二字EI教后?垂E田驗(yàn)

23、Debu睜蛤10 :排序茅W7WSSZ昌會(huì)排序的取終結(jié)果是：127 14 15 25 36 86排序輸出完畢！按回車鍵返回.排序子系統(tǒng)123456780Boon用人速:開罰 更直希日展選恨返*請(qǐng)選擇菜單號(hào)0-8： 1請(qǐng)輸入8個(gè)待排序數(shù)據(jù)按【Enter】鍵分隔：86_D：整件文極蚊育學(xué)習(xí)樓或縛構(gòu)驗(yàn)證性實(shí)蛉Debug供蛉10 :排序子系院exb79211415162排序數(shù)據(jù)已經(jīng)輸入完畢！按回車鍵返回.排序子系統(tǒng)123456780請(qǐng)選擇菜單號(hào)0-8： 2原始數(shù)據(jù)為按tEnter鍵開始排序：第1趟排序結(jié)果為第2趟排序結(jié)果為第3趟排序結(jié)果為第4趟排序結(jié)果為86921415按Enter】鍵繼續(xù)：按Ent】

24、鍵繼續(xù)：按rEnter鍵繼續(xù)：按Enter鍵繼續(xù)：第5趟排序結(jié)果為按Enter】鍵繼續(xù)：868692861492861414921517141586921611111 文件文梭效育學(xué)習(xí)檄振結(jié)構(gòu)q第6趟排序結(jié)果為按CEnterJ鍵繼續(xù) 22141516869第7趟排序結(jié)果為按【EnteQ鍵繼續(xù) 6921415168排序的最終結(jié)果是: 排序輸出完畢！ 按回車鍵返回.14158692kF123456780W更直希日展選房返一13Lt fl 速:開；十:整件文梭載育學(xué)習(xí)曲先縛構(gòu)驗(yàn)證性實(shí)蛉Debug供蛉10 :琲序子至短exb= zfp 日m j xAj/i 直接藉入排啟86?9215114第,趟排序結(jié)果為按【Enter】鍵繼續(xù)186?9221416第2趟排序結(jié)果為按Enter鍵繼續(xù)27921861