数据结构课程设计(c语言)

1、算法与数据结构课程设计 内部排序算法比较 第一章问题描述_1- 第二章系统分析-1- 第三章系统设计2- 第四章系统实现-2- 第五章系统测试-11 第六章总结一14一 参考文献-15- 教师评语和成绩 -15- 第一章问题描述 对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快 速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次 数和移动 次数（交换计为3次）估算每种算法的时间消耗。分析其特点，并进行比 较。 排序表的数据应该是多种不同的情况，如可以随机产生数据、极端的 数据如已是正序或逆序数据。比较的结果用直方图表示。 第二章系统分析 内部排序算法比较系统的功能如下: 1

2、.用直接插入排序，简单选择排序，冒泡排序，堆排序，快 速排 序对多组数据进行正序排列。 2. 对每种算法的比较次数和移动次数进行统计 3. 把各种算法的比较次数和移动次数进行比较。 4. 用直方图来对比各种算法比较次数和移动次数的差别。 5. 用随机数据，逆序数据，正序数据进行排列对比各种算法 的差 别。 界面需求： 通过选择可以进入不同类型的数据进行各种排序。 通过选择可以查看不同数据的比较和移动的直方图。 第三章系统设计 1.随机数据排序 2 随机数据排序结果的直方图 3. 逆序数据排序 4. 逆序数据排序结果的直方图 5. 正序数据排序 6. 正序数据排序结果的直方图 0 退出 请选择要

3、进行的操作输入相关代码 开始 主函数 int main (void) int n; while (1) system(cls);/system(COLOR fO); 内部排序算法比t*nn); prin tf(*t ttn*)* prin tf(*t ttn*)* printf Ct*tl 随机数据排序t*n); printf(*t*t2 随机数据排序结果的直方图 t*rT); printf Ct*t3. 逆序数据排序t*)； printf (*t*t4 逆序数据排序结果的直方图 t*n*); printf Ct*t5. 正序数据排序t*)； printf(*t*t6 正序数据排序结果的直方图

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是记录个数*/ 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是记录个数灯 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与其左右孩子之间可能不满足堆特性*/ /#进行调整使以Rs为根的子树成为大顶堆*/ datatype rc; /*缓冲变量 */ rc=Rs; int

8、 i=s; mt j； for(j=2*i; j=t; j=2*j) /*沿关键码较大的孩子结点向下筛选 */ if (jt break; / mn3+;i=j; 准备继续向下调整柠 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); /* 将重新调整为堆*/ 快速排序 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 比较次数tt移动次数十）; 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) ; 随机数据的排序 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; 逆序数据的排序 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 ; 正序数据的排序 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 (” 比较次数的直方图如下: 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(* 移动次数的直方图如下巧； 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 ; 第五章系统测试 随机数据 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 入择序序 比较次数

22、 移动次数 43 52 18 24 8 12 45 2S 52 (24 匕较次数的直方图如下， II（rccrcccrccC 21 q 广 接曇 直5101 图 ILF 【( L L 102 4” 堆摊序：( LL( ( ( 40 5-快逋排丿Y la 51 8e序 入库亠予亠予 比较次数 54 25 8 10 40 移动次数 &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, 譚雪甫星汕佃丄込驱 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, 比较次数的直方图如下: 直接插入：L L ( L ( L IL ( L ( L L 54 : 2-简单选择25 : 人冒泡排序！( S : 氣堆排序；【10 : 5. Ifc