數(shù)據(jù)結(jié)構(gòu)課程設計(c語言)

1、算法與數(shù)據(jù)結(jié)構(gòu)課程設計 內(nèi)部排序算法比較 第一章問題描述_1- 第二章系統(tǒng)分析-1- 第三章系統(tǒng)設計2- 第四章系統(tǒng)實現(xiàn)-2- 第五章系統(tǒng)測試-11 第六章總結(jié)一14一 參考文獻-15- 教師評語和成績 -15- 第一章問題描述 對各種內(nèi)部排序算法如直接插入排序，冒泡排序，簡單選擇排序，快 速排序，希爾排序，堆排序、二路歸并排序等，以關鍵碼的比較次 數(shù)和移動 次數(shù)（交換計為3次）估算每種算法的時間消耗。分析其特點，并進行比 較。 排序表的數(shù)據(jù)應該是多種不同的情況，如可以隨機產(chǎn)生數(shù)據(jù)、極端的 數(shù)據(jù)如已是正序或逆序數(shù)據(jù)。比較的結(jié)果用直方圖表示。 第二章系統(tǒng)分析 內(nèi)部排序算法比較系統(tǒng)的功能如下: 1

2、.用直接插入排序，簡單選擇排序，冒泡排序，堆排序，快 速排 序?qū)Χ嘟M數(shù)據(jù)進行正序排列。 2. 對每種算法的比較次數(shù)和移動次數(shù)進行統(tǒng)計 3. 把各種算法的比較次數(shù)和移動次數(shù)進行比較。 4. 用直方圖來對比各種算法比較次數(shù)和移動次數(shù)的差別。 5. 用隨機數(shù)據(jù)，逆序數(shù)據(jù)，正序數(shù)據(jù)進行排列對比各種算法 的差 別。 界面需求： 通過選擇可以進入不同類型的數(shù)據(jù)進行各種排序。 通過選擇可以查看不同數(shù)據(jù)的比較和移動的直方圖。 第三章系統(tǒng)設計 1.隨機數(shù)據(jù)排序 2 隨機數(shù)據(jù)排序結(jié)果的直方圖 3. 逆序數(shù)據(jù)排序 4. 逆序數(shù)據(jù)排序結(jié)果的直方圖 5. 正序數(shù)據(jù)排序 6. 正序數(shù)據(jù)排序結(jié)果的直方圖 0 退出 請選擇要

3、進行的操作輸入相關代碼 開始 主函數(shù) int main (void) int n; while (1) system(cls);/system(COLOR fO); 內(nèi)部排序算法比t*nn); prin tf(*t ttn*)* prin tf(*t ttn*)* printf Ct*tl 隨機數(shù)據(jù)排序t*n); printf(*t*t2 隨機數(shù)據(jù)排序結(jié)果的直方圖 t*rT); printf Ct*t3. 逆序數(shù)據(jù)排序t*)； printf (*t*t4 逆序數(shù)據(jù)排序結(jié)果的直方圖 t*n*); printf Ct*t5. 正序數(shù)據(jù)排序t*)； printf(*t*t6 正序數(shù)據(jù)排序結(jié)果的直方圖

4、 t*rT); printf(t*tO 退出徉5); printf (t* printf Cttnn 請選擇要進行的操作輸入相關代碼： tn); scanf switch(n) case 1： system(clszx) ; sui jishuO ; break; case 2：system(cls);zhifangtu(l, 2, 3, 4, 5):break; case 3:systemCcls*) ;nixu() ;break; case 4：system(cls);zhifangtu(6, 7, 8, 9, 10); break; case SisystemCcls*) ;zhengx

5、u();break; case 6:system(cls);zhifangtu(ll, 12, 13,14, 15);break; case 0：exit(0); 直接插入排序 void D_lnsertSort(datatype R , mt n) int i, j； for(i=2; i=n; i 卄) cn0+; if (Ri keyRil. key) mnO卄; RO=Ri： for(j=i-l;R0.keyRj. key; j_) Rj+l=Rj： mn 0十+; cnlOj-H； Rj+1=RO ;mn0+; /簡單選擇排序 void Select_Sort(datatype R

6、int n) /*對排序表R.Rn進行簡單選擇排序，n是記錄個數(shù)*/ int i, j,k; for(i=l;in;i+)/* 作 n-1 趟選取 / k=i;/*在i開始的n-i+1 個記錄中選關鍵碼最小的記錄 for (j=i+l; jv=n; j+) if(RjJ. keyR：k key) cnl卄；k 巧; /* k中存放關鍵碼最小記錄的下標*/ if (i!=k) /*關鍵碼最小的記錄與第i個記錄交換*/ mnl=mn：l+3; RO=Rk; Rk=Rtil； Ri=RO; /冒泡排序 void Bubble_Sort(datatype R int n) /*對排序表RRn 進行冒泡

7、排序，n是記錄個數(shù)燈 int i, j； int swap; /*父換標志變量*/ for(i=l; in-l; i+) swap=0;cn2+; for(j=l; jRjl key) mn 2=mn23; RO=Rj+l; Rj+l=Rj; Rj=RO; swap=l: /*置交換標志材 if(swap=0) break; /堆排序 void HeapAdjust(datatype R1 , int s, int t) 以Rs為根的子樹只有Rs與其左右孩子之間可能不滿足堆特性*/ /#進行調(diào)整使以Rs為根的子樹成為大頂堆*/ datatype rc; /*緩沖變量 */ rc=Rs; int

8、 i=s; mt j； for(j=2*i; j=t; j=2*j) /*沿關鍵碼較大的孩子結(jié)點向下篩選 */ if (jt break; / mn3+;i=j; 準備繼續(xù)向下調(diào)整檸 Ri=rc; /*插入*/ void HeapSort(datatype R , int n) / 將序列 Rl.Rn 按堆排序方法進行排序燈 mt i; for(i=n/2; i0; i) HeapAdjust(R, i, n):/* 將序列Rl.Rn建成初始堆檸 for(i=n; il; i) mn3：=mn3+3; RO=R1J;/* 堆頂R與堆底元素Ri交換*/ Rl=Ril; Ri=R0; HeapAd

9、just(R, 1, il); /* 將重新調(diào)整為堆*/ 快速排序 mt Partition (datatype R , int low, int high) /*以RloO為支點對Rlow. .R high進行劃分，返回支點記錄最終的位置 R0=Rlow; /*暫存支點記錄材 while(lowvhigh) /*從表的兩端交替地向中間掃描/ while(low=R0key) ( cn4+; high: if(lowhigh) RClow=Rhigh;十;mn4十+; .*將比支點小的交換到前面*/ while (lowhighIow-h-; if (lowhigh) R*high=Rllow

10、; high一;mn卄;/*將比支點大的交換到后面 Rlow=R0; ”支點記錄到位*/ return low; *返回支點記錄所在位置3 void Quick_Sort(datatype R , int s, mt t) /*對Rs.Rt進行快速排序*/ int i; if(st ) /*將表一分為二*/ 對支點前端子表遞歸排序*/ 對支點后端子表遞歸排序 i = Partition(R, s, t); Quick_Sort(R, s, il); /* Quick_Sort(R, i+l, t); /* void print(datatype R4) R datatype R11 , dat

11、atype R2 , datatype R3 匚, datatype int i; printf(n*); printf(*nl.直接插入排序:n); D_InsertSort(R, 10); pnntfC排序后的序列：”)； for(i=l; i=10; i+) printf (Wd, ”、Ri, key); printf rn); printf Cn2.簡單選擇排序:)； Select_Sort(Rl, 10); p“ntf(n排序后的序列：)： for(i=l;i=10; i+) printf C%d, ,Rli key); printf Cnn); printf (3.冒泡排序:”)；

12、 BubbleSort(R2, 10); printf (*n排序后的序列：)： for (i=l; i=10; i+) printf C%d. , R2i key); printf Cnn); printf(4.堆排序Q： HeapSort(R3, 10); printf （n排序后的丿孑列：*）: for (i=l; i=10; i+) printf(%d, R3i. key); printf(nn); 快速排序 printf C5 Quick_Sort(R4, 1,10); printf Cn 排序后的序列:）: for (i=l; i=10;i+) printf C%d, , R4i

13、key); printf (、*n); printf(tt 比較次數(shù)tt移動次數(shù)十）; printfC 直接插入 t%dttt%dn, cn0,mn0); printf( 簡單選擇 t%dttt%dn cnl, mnl); printfC 冒泡排序 t%dttt%dn, cn2,mn2); printfC 堆排序 t%dttt%dn, cnDJ.mnCS); printfC 快速排序 t%dttt%dn, cn4,mn4) ; 隨機數(shù)據(jù)的排序 void suijishuO int i; for(i=0;i5;i+) cni=0; mni=0; datatype R110 = (0: datat

14、ype Rl10=0; datatype R210=0; datatype R310=0; datatype R410=0; stand(time(NULL); for(i=l;i=10;i+) Ri key=l+(rand0%100); Rli. key=Ri. key; R2i key二Ri： key; R3ikey=Ri. key; Rli key=Ri. key; printf(”排序前的序列：)； for (i=l; i=10; i卄)printf (*%d, , Ri. key); print (R, Rl, R2, R3, R4); for(i=l;i6;i+) ctui=cni

15、l;mtui2=mnli-l; printf (n按任意鍵返回主菜單！ J； getchO; 逆序數(shù)據(jù)的排序 void nixuO int i: for(i=0;i0;mni0; datatype R = 0, 90, 80, 70, 60, 50,40, 30, 20, 10, 1; datatype Rl = 0,90, 80, 70, 60,50, 40, 30, 20,10,1; datatype R2 = 0,90, 80, 70, 60,50, 40, 30, 20,10,1); datatype R3 = 0,90, 80, 70, 60,50, 40, 30, 20,10,1;

16、 datatype R4=0,90, 80, 70, 60,50, 40, 30, 20,10,1; printf(排序前的序列：90, SO, 70, 60, 50,40, 30, 20, 10, lrT); print (R, Rl, R2, R3, R l); for (i=l;i6;i+) ctui+5=cnil: printf (n按任意鍵返回主菜單！)； getchO ; 正序數(shù)據(jù)的排序 void zhengxu() int i; for(i=0;i0;mni0; datatype R = Ot 8,10,15, 20, 50, 53, 60, 70, 85,89; datatyp

17、e Rl=0, 8, 10, 15, 20, 50, 53, 60, 70, 85, 89; datatype R2=0, 8,10,15, 20, 50, 53, 60, 70, 85, 89; datatype R3 = 0, 8, 10, 15, 20, 50, 53, 60, 70, 85, 89; datatype R4=0, 8,10,15, 20, 50, 53, 60, 70, 85, 89; printf(排序前的序歹J :8, 10, 15, 20, 50, 53, 60, 70, 85, 89n); print (R, Rl, R2, R3, R4); for(i=l;i

18、6;i+) ctui+10=cnil;mtui+10=mni-l; printf C4.堆排序I *) ;for(i=l; i=ctud printf (n 按任意鍵返回主菜單！ J ； getchO ; 打印直方圖 void zhifangtu(int a. int b, int c, int d, int e) int i; printf (” 比較次數(shù)的直方圖如下: n); printfC *n); printfC n); printfC n); printf (1 直 接 );for(i=l;i=ctua;i+) D;for(i=l;i=ctub;i+) r);for(i=l;i=ct

19、uc;i+) printfCDiprintfC %dctua):printfCn*); printfC |n); printf (*2簡單 printf CD ;printf C ctub) ;printf(*n*); printfC |n)； printf (3冒泡 printf CD ;printf Cctuc);printf (*n*); printfC |n): printf C *) ;printf (* %d*, ctud) ;printf (n); printf(” ! n); printf(5 D ；for(i=l;i0; printf(* 移動次數(shù)的直方圖如下巧； print

20、f(* n); printf(* 1n)； printfC !n)； printf Cl 直接 D ；for(i=l;i=mtua;i+) printf (/ ) :printf C nitua) ;printf Cn*); printf(2 ”):for(i=l;i=mtub;i+) printf C *) ;printfmtub) ;printf (n); printf(3 ”):for(i=l;i=mtuc;i+) printf():printfC %d,mtuc：);printf(*n); printfC4 ”):for(i=l;i=mtuld:i+) printf C *) ;pri

21、ntfmtud) ;printf C*n); printf (5 );for(i=l;i); printf Cn按任意鍵返回主菜單！ ”）； getchO ; 第五章系統(tǒng)測試 隨機數(shù)據(jù) 76, 1, 72, 71, 4, 2簡單選擇排序二 扌卡序肓的序列：1,4, 32, 70, 71, 72, 76, 77, 91, 93 聖序后 3謁辛列二 1. 4, 32. 70. 71, 72, 76, 77, 91, 93 i :4.32,70, 71, 72, 76, 77, 91, 93 J 序歹 J： 1, 4, 32- 70. 71, 72, 76, 77, 91, 93 入擇序序 比較次數(shù)

22、 移動次數(shù) 43 52 18 24 8 12 45 2S 52 (24 匕較次數(shù)的直方圖如下， II（rccrcccrccC 21 q 廣 接曇 直5101 圖 ILF 【( L L 102 4” 堆攤序：( LL( ( ( 40 5-快逋排丿Y la 51 8e序 入庫亠予亠予 比較次數(shù) 54 25 8 10 40 移動次數(shù) &3 15 132 直方圖 70, 60, 58, 40, 30, 20,10, 1 直錘入排和 序后的序列:1. 1020, 30, 40. 50, 60, 70, 80. 90, 簡單選擇排序， E 序肓的序列：1. 10,20, 30, 40, 50, 60, 70, 80, 90, 譚雪甫星汕佃丄込驅(qū) 40, SO, &0, 70, 80. 90, : 1. 10, 20, 30, 40, 50. 60, 70, 80. 90. :1, 10, 20, 30, 40, 50, &0, 70, 80, 90, 比較次數(shù)的直方圖如下: 直接插入：L L ( L ( L IL ( L ( L L 54 : 2-簡單選擇25 : 人冒泡排序！( S : 氣堆排序；【10 : 5. Ifc