數(shù)據(jù)結(jié)構(gòu)內(nèi)排序?qū)嶒?yàn)報(bào)告

1、一、 實(shí)驗(yàn)?zāi)康?、 了解內(nèi)排序都是在內(nèi)存中進(jìn)行的。2、 為了提高數(shù)據(jù)的查找速度，需要對(duì)數(shù)據(jù)進(jìn)行排序。3、 掌握內(nèi)排序的方法。二、 實(shí)驗(yàn)內(nèi)容1、 設(shè)計(jì)一個(gè)程序exp101.cpp實(shí)現(xiàn)直接插入排序算法，并輸出9,8,7,6,5,4,3,2,1,0的排序過程。（1） 源程序如下所示：/文件名:exp10-1.cpp#include <stdio.h>#define MAXE 20/線性表中最多元素個(gè)數(shù)typedef int KeyType;typedef char InfoType10;typedef struct /記錄類型KeyType key; /關(guān)鍵字項(xiàng)InfoType data

2、; /其他數(shù)據(jù)項(xiàng),類型為InfoType RecType;void InsertSort(RecType R,int n) /對(duì)R0.n-1按遞增有序進(jìn)行直接插入排序int i,j,k;RecType temp;for (i=1;i<n;i+) temp=Ri;j=i-1; /從右向左在有序區(qū)R0.i-1中找Ri的插入位置while (j>=0 && temp.key<Rj.key) Rj+1=Rj;/將關(guān)鍵字大于Ri.key的記錄后移j-; Rj+1=temp;/在j+1處插入Riprintf("i=%d,",i);/輸出每一趟的排序結(jié)果

3、printf("插入%d,結(jié)果為: ",temp);for (k=0;k<n;k+)printf("%3d",Rk.key);printf("n");void main()int i,k,n=10;KeyType a=9,8,7,6,5,4,3,2,1,0;RecType RMAXE;for (i=0;i<n;i+)Ri.key=ai;printf("初始關(guān)鍵字: ");/輸出初始關(guān)鍵字序列for (k=0;k<n;k+)printf("%3d",Rk.key);printf(

4、"n");InsertSort(R,n);printf("最后結(jié)果: ");/輸出初始關(guān)鍵字序列for (k=0;k<n;k+)printf("%3d",Rk.key);printf("n");（2） 運(yùn)行的結(jié)果如下圖所示：2、 設(shè)計(jì)一個(gè)程序exp102.cpp實(shí)現(xiàn)希爾插入排序算法，并輸出9,8,7,6,5,4,3,2,1,0的排序過程。（1） 源程序如下所示：/文件名:exp10-2.cpp#include <stdio.h>#define MAXE 20/線性表中最多元素個(gè)數(shù)typedef i

5、nt KeyType;typedef char InfoType10;typedef struct /記錄類型KeyType key;/關(guān)鍵字項(xiàng)InfoType data;/其他數(shù)據(jù)項(xiàng),類型為InfoType RecType;void ShellSort(RecType R,int n)/希爾排序算法int i,j,d,k;RecType temp;d=n/2;/d取初值n/2while (d>0) for (i=d;i<n;i+)/將Rd.n-1分別插入各組當(dāng)前有序區(qū)中j=i-d;while (j>=0 && Rj.key>Rj+d.key) temp

6、=Rj; /Rj與Rj+d交換Rj=Rj+d;Rj+d=temp;j=j-d;printf("d=%d: ",d);/輸出每一趟的排序結(jié)果for (k=0;k<n;k+)printf("%3d",Rk.key);printf("n"); d=d/2; /遞減增量dvoid main()int i,k,n=10;KeyType a=9,8,7,6,5,4,3,2,1,0;RecType RMAXE;for (i=0;i<n;i+)Ri.key=ai;printf("初始關(guān)鍵字: ");/輸出初始關(guān)鍵字序列

7、for (k=0;k<n;k+)printf("%3d",Rk.key);printf("n");ShellSort(R,n);printf("最后結(jié)果: ");/輸出初始關(guān)鍵字序列for (k=0;k<n;k+)printf("%3d",Rk.key);printf("nn");（2） 結(jié)果如下圖所示：3、 設(shè)計(jì)一個(gè)程序exp103.cpp實(shí)現(xiàn)冒泡排序算法，并輸出9,8,7,6,5,4,3,2,1,0的排序過程。（1） 源程序如下所示：/文件名:exp10-3.cpp#includ

8、e <stdio.h>#define MAXE 20/線性表中最多元素個(gè)數(shù)typedef int KeyType;typedef char InfoType10;typedef struct /記錄類型KeyType key; /關(guān)鍵字項(xiàng) InfoType data; /其他數(shù)據(jù)項(xiàng),類型為InfoType RecType;void BubbleSort(RecType R,int n)/冒泡排序算法int i,j,k;RecType temp;for (i=0;i<n-1;i+) for (j=n-1;j>i;j-)/比較,找出本趟最小關(guān)鍵字的記錄if (Rj.key&

9、lt;Rj-1.key) temp=Rj; /Rj與Rj-1進(jìn)行交換,將最小關(guān)鍵字記錄前移Rj=Rj-1;Rj-1=temp;printf("i=%d,冒出的最小關(guān)鍵字:%d,結(jié)果為: ",i,Ri.key);/輸出每一趟的排序結(jié)果for (k=0;k<n;k+)printf("%2d",Rk.key);printf("n"); void main()int i,k,n=10;KeyType a=9,8,7,6,5,4,3,2,1,0;RecType RMAXE;for (i=0;i<n;i+)Ri.key=ai;printf("初始關(guān)鍵字: ");/輸出初始關(guān)鍵字序列for (k=0;k<n;k+)printf("%2d",Rk.key);printf("