完整版數(shù)據(jù)結(jié)構(gòu)排序試驗(yàn)報(bào)告文檔良心出品

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

3、)、對(duì)存儲(chǔ)數(shù)字的遍歷函數(shù)Visit ().(8)、初始化函數(shù) InitSqList ().(9)、主函數(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 =

4、L.r0;二、希爾排序void ShellSort(SqList &L)(int i, j;int dk = 1;/ 增量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.r

5、0.key;)三、冒泡排序void BubbleSort(SqList &L)(int i,j;for(i=0;i<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è)無(wú)交換說(shuō)明已經(jīng)有序if(flag=1)break;)四、快速排序int Partition(SqList &L,int low,int

6、high)(/分割區(qū)域函數(shù)L.r0 = L.rlow;int pivotkey = L.rlow.key;/ 一般將順序表第一個(gè)元素作為支點(diǎn) 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 &

7、;L,int low,int high)(/每張子表的快速排序if(low<high)(int pivotloc = Partition(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

8、.ri.key;for (int k = i; k < L.length; k+)/在Ri.n-1中選擇最小的記錄if (L.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*=

9、2)(/沿著結(jié)點(diǎn)記錄較小的向下篩選if(j<m && H.rj.key<H.rj+1.key) +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;HeapAdju

10、st(H,1,i-1);(2)遍歷函數(shù)與初始化void Visit(SqList L)(for(int i=1; i<=L.length; i+)cout<<L.ri.key<<""cout<<endl;)void InitSqList(SqList &L,int a口)(for(int i=1;i<=L.length;i+)L.ri.key = ai;)五、測(cè)試結(jié)果以下是各種界面的測(cè)試結(jié)果：任:最后的:湊程設(shè)計(jì) De b u 口以E序exu'(1)輸入的界面一照那么史照刖也弓knrJ'KnB 酉glT

11、?亭竽庠舁人人入人入入2 8 6 315 7 2面 界 作 操 序 三 ' E：羈峰程倒nDebugGE序點(diǎn)xH序二|E L: L; iH 二.速擇 晚選真希日展選蓑 一 * | , , 12 3 4 5 6 7請(qǐng)輸入你需要的操作(3)各種排序的結(jié)果:非序后數(shù)字序列攵字序列' E 最后的侯亨設(shè)討Dc b ugaE序e xe ,非序前數(shù)字序列：.2 58 76 23 46序后數(shù)字序列工.2 23 46 S8 76一意鍵繼續(xù)！領(lǐng)A你需要的操侶2 二洋箭數(shù)字序司：.2 58 76 23 46*序后數(shù)字序列;.2 23 46 58 76:意鍵繼續(xù)！輸入你籥要取操作：3 列 46F序后數(shù)字序列 46,2 23 46 58 76一意鍵維續(xù)就疆即512 58 76 23 46排序后數(shù)字序列：23 46 SB 76 46任意鍵繼續(xù)！醯密置鬻操作,6排序刖記錄序列：12 58 76 23 46排序后記錄序列：l2 23 46 58 76六、設(shè)計(jì)缺乏以及存在問(wèn)題本