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

1、數(shù)據(jù)結(jié)構(gòu)?課程設(shè)計(jì)報(bào)告實(shí)驗(yàn)五 排序一、需求分析：本演示程序用 C+6.0 編寫，完成各種排序的實(shí)現(xiàn)，對(duì)輸入的一組數(shù)字實(shí)現(xiàn)不同的排序 方法，對(duì)其由小到大順序輸出。1分別對(duì)直接插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序算法 進(jìn)行編寫。 2、對(duì)存儲(chǔ)的函數(shù)即輸入的數(shù)字進(jìn)行遍歷。3、初始化函數(shù)對(duì)輸入的數(shù)字進(jìn)行保存。4、主函數(shù)實(shí)現(xiàn)使用者操作界面的編寫，對(duì)輸入、選擇、保存、輸出的各種實(shí)現(xiàn)。 這當(dāng)中還包括了各個(gè)函數(shù)的調(diào)用的實(shí)現(xiàn)。5、程序所能到達(dá)的功能：完成對(duì)輸入的數(shù)字的生成，并通過對(duì)各排序的選擇實(shí)現(xiàn)數(shù)字從小到大的輸出。二、程序主要功能以及根本要求：1、設(shè)計(jì)一個(gè)菜單，格式如下：1、直接插入排序2、

2、希爾排序3、冒泡排序4、快速排序5、選擇排序6、堆排序7、退出2、選擇不同的菜單但進(jìn)行相應(yīng)的排序，并給出排序的關(guān)鍵字序列。三、系統(tǒng)框架圖：本程序包含了 9個(gè)函數(shù)，它們分別是：1、直接插入排序的算法函數(shù)InsertSort 。各對(duì)輸操作個(gè)入的界面排數(shù)組的設(shè)序進(jìn)行計(jì)，函算遍歷數(shù)的法初始調(diào)用。函化數(shù)主函數(shù)2、希爾排序的算法函數(shù)ShellSort。3、冒泡排序算法函數(shù)BubbleSort 。4、快速排序的算法函數(shù)Partition 。5、選擇排序算法函數(shù)SelectSort。6、堆排序算法函數(shù) HeapAdjust 。7、對(duì)存儲(chǔ)數(shù)字的遍歷函數(shù)Visit。8、初始化函數(shù) InitSqList 。9、主函

3、數(shù) main。四、詳細(xì)設(shè)計(jì)實(shí)現(xiàn)各個(gè)算法的主要內(nèi)容，下面是各個(gè)函數(shù)的主要信息:1各個(gè)排序函數(shù)的算法：一、直接插入排序void InsertSort(SqList &L)int i,j;for( i=2; i<=L.length;i+)if(L.ri.key < L.ri-1.key)L.r0 = L.ri;L.ri = L.ri-1;for( j=i-2; (L.r0.key < L.rj.key); j-)L.rj+1 = L.rj;L.rj+1 = L.r0;二、希爾排序void ShellSort(SqList &L)int i, j;int dk = 1

4、;/ 增量while(dk <=L.length/3)dk = 3*dk+1;/ 增大增量while(dk>0)dk /= 3;/ 減小增量for (i = dk; i <=L.length; i+)L.r0.key = L.ri.key;j = i;while (j >= dk) && (L.rj-dk.key > L.r0.key)L.rj.key = L.rj-dk.key;j -= dk;L.rj.key = L.r0.key;三、冒泡排序void BubbleSort(SqList &L)int i,j;for(i=0;i<

5、L.length-2;i+)int flag = 1;for(j=0;j<L.length-i-2;j+)if(L.rj.key > L.rj+1.key)flag = 0;int temp;temp = L.rj.key;L.rj.key = L.rj+1.key;L.rj+1.key = temp;/假設(shè)無交換說明已經(jīng)有序if(flag=1)break;四、快速排序int Partition(SqList &L,int low,int high)/分割區(qū)域函數(shù)個(gè)元素作為支點(diǎn)L.r0 = L.rlow;int pivotkey = L.rlow.key;/ 一般將順序表第

6、一 while(low < high)while(low<high && L.rhigh.key>=pivotkey) high-;L.rlow = L.rhigh;while(low<high && L.rlow.key<=pivotkey)low+;L.rhigh = L.rlow;L.rlow = L.r0;/ 返回樞軸位置return low;void QSort(SqList &L,int low,int high)/每張子表的快速排序if(low<high)int pivotloc = Partition(

7、L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);void QuickSort(SqList &L)QSort(L,1,L.length);五、簡(jiǎn)單項(xiàng)選擇擇排序void SelectSort(SqList &L)int min;int j;for (int i = 0; i <L.length; i+) / 選擇第 i 小的記錄，并交換j = i;min = L.ri.key;for (int k = i; k < L.length; k+) / 在 Ri.n-1 中選擇最小的記錄 if (L.

8、rk.key < min)min = L.rk.key ;j = k;if (i != j) / 與第 i 個(gè)記錄交換 int temp = L.ri.key; L.ri.key = L.rj.key; L.rj.key = temp;六、堆排序void HeapAdjust(HeapType &H,int s,int m)/堆調(diào)整，將記錄調(diào)整為小頂堆int j;RedType rc = H.rs;/ 暫時(shí)存儲(chǔ)根結(jié)點(diǎn)for(j=2*s; j<=m; j*=2)/沿著結(jié)點(diǎn)記錄較小的向下篩選if(j<m && H.rj.key<H.rj+1.key)

9、+j;if(rc.key>= H.rj.key)break;H.rs = H.rj;s = j;H.rs = rc;void HeapSort(HeapType &H)int i;RedType temp;for(i = H.length; i>0; -i)HeapAdjust(H,i,H.length);for(i=H.length; i>1; -i)temp = H.r1;H.r1 = H.ri;H.ri = temp;HeapAdjust(H,1,i-1);2遍歷函數(shù)與初始化void Visit(SqList L)for(i nt i=1; i<=Len

10、gth; i+) cout<<L.ri.key<<""cout<<e ndl;void InitSqList(SqList &L,int a)for(i nt i=1;i<=Len gth;i+) L.ri.key = ai;五、測(cè)試結(jié)果以下是各種界面的測(cè)試結(jié)果:1輸入的界面"E:石門序理資Debu gV? E予e氓'RH 2 s S 3 6S 7 2 4 熱姝 ? 1 2 3 4 5 AAAAAA -一 - _扌丄1牛七1扌孑 請(qǐng)請(qǐng)諳請(qǐng)請(qǐng)排序操作界面骯量脣的儼直設(shè)計(jì)9訪ug瞬序尼“'WSS 9.1

11、選直希曰屆選亠-n1234567游界面排序iM耳 N X 3*X W 耳 N X 3*X W 耳？請(qǐng)輸入你需要的操作:3各種排序的結(jié)果:菲序后敎字序列2 23 4£ 鬧 76轍操作23 46坯丿予刖炎Eft排序后數(shù)字序列；12 23 46 59 76 任菖撻繼績(jī)1 請(qǐng)希人你需要的操作IE序前裁字序列=2 58 76 23 46菲序后數(shù)字序列I攏詁52 S8 76 23 46非序后數(shù)字序列：3 4& 58 76 46盍匾入禰需要的罠作：6 距岸前記錄序列；2 58 7B 23 怖 豐序后i酥序列=2 23 4G GS ?fcF序后數(shù)字序列七i翱姑諜輕設(shè)計(jì)、。出四也時(shí)，晞六、設(shè)計(jì)缺乏以及存在問題本程序是基于