北理工數(shù)據(jù)結(jié)構(gòu)實驗報告4

1、數(shù)據(jù)結(jié)構(gòu)與算法統(tǒng)計實驗報告實驗四學院:班級:學號:姓名:、實驗目的1、熟悉VC環(huán)境，學會使用 C語言利用順序表解決實際問題。2、通過上機、編程調(diào)試，加強對線性表的理解和運用的能力。3、鍛煉動手編程，獨立思考的能力。二、實驗內(nèi)容從鍵盤輸入10個數(shù)，編程實現(xiàn)分別用插入排序、交換排序、選擇排序算法進行排序, 輸出排序后的序列。三、程序設計1 、概要設計為了實現(xiàn)排序的功能，需要將輸入的數(shù)字放入線性表中，進行進一步的排序操作。 (1)抽象數(shù)據(jù)類型：ADT SqList數(shù)據(jù)對象：d= ai |ai ElemSet,i1,2,K,n, n 0數(shù)據(jù)關(guān)系：R1= ai 1,aiD,i1,2,K ,n基本操作：I

2、nput(Sqlist & L)操作結(jié)果：構(gòu)造一個線性表L。output(SqList L)初始條件：線性表 L已存在。操作結(jié)果：按順序在屏幕上輸出L的數(shù)據(jù)元素。BiI nsertio nsort (Sqlist L)初始條件：線性表 L已存在。操作結(jié)果：對L的數(shù)據(jù)元素進行折半插入排序。Quicksort (Sqlist L)初始條件：線性表 L已存在。操作結(jié)果：對L的數(shù)據(jù)元素進行交換排序。SelectSort(SqList &L)初始條件：線性表 L已存在。操作結(jié)果：對L的數(shù)據(jù)元素進行選擇排序。ADT SqList宏定義#defi ne KeyType int#define

3、MAXSIZE 10#define ok 1#defi ne error 0主程序流程由主程序首先調(diào)用In put(L)函數(shù)創(chuàng)建順序表，先調(diào)用BiInsertionsort(L)函數(shù)進行折半插入排序，調(diào)用output(L)函數(shù)顯示排序結(jié)果。再調(diào)用QuickSort (L)函數(shù)進行交換排序，調(diào)用output (L)函數(shù)顯示排序結(jié)果。函數(shù)顯示排序結(jié)果。最后調(diào)用SelectSort(L)函數(shù)進行選擇排序，調(diào)用output(L)模塊調(diào)用關(guān)系由主函數(shù)模塊調(diào)用創(chuàng)建順序表模塊，排序模塊與顯示輸出模塊。(5)流程圖開始輸入待排數(shù)字創(chuàng)建線性表進行插入排序輸出排序結(jié)果進行交換排序輸出排序結(jié)果進行選擇排序輸出排序結(jié)

4、果結(jié)束2、詳細設計(1)數(shù)據(jù)類型設計/*順序存儲結(jié)構(gòu)*/typedef structKeyType Key; / 關(guān)鍵字項 RedType;typedef structRedType rMAXSIZE+1;int len gth;/ =MAXSIZE; Sqlist;/(2)操作算法設計/*輸入數(shù)據(jù)*/int In put(Sqlist & L)for(int i=1;i<=MAXSIZE;i+)sea nf("%d",&L.ri.Key);L.le ngth=MAXSIZE;return ok;/*輸出排好的數(shù)字*/in t output(Sqlis

5、t L)for(i nt i=1;i<=MAXSIZE;i+)prin tf("%-4d",L.ri.Key);prin tf("n ”); return ok;/*折半插入排序法*/void BiI nserti on sort (Sqlist L)int i,j,low,high,m; for(i=2;i<=Len gth;i+)L.rO.Key=L.ri.Key; / low=1; high=i-1;while(low<=high) / m=(low+high)/2; if(L.rO.Key<L.rm.Key) else low=m+

6、1; for(j=i-1;j>=high+1;j-) /.rj+1=L.rj;L.rhigh+1=L.rO; II /lowprintf("折半插入排序:n");output(L);定義順序表類型把要插入的當成哨兵 折半法找到要插入的位置high=m-1;插入位置后的袁術(shù)后移一位插入元素/BiI nserti on sort/*快速交換排序法*/int Partition(Sqlist &L,int low,int high)int pivotkey;L.r0.Key=L.rlow.Key; /用子表的第一個記錄作樞軸記錄pivotkey=L.rlow.Key

7、; /樞軸記錄關(guān)鍵字while(low<high) / 從表的兩端交替地向中間掃描while(low<high&&L.rhigh.Key>=pivotkey)-high;/ 將比樞軸記錄小的記錄移到低端/whileL.rlow.Key=L.rhigh.Key; while(low<high&&L.rlow.Key<=pivotkey) +low;將比樞軸記錄大的記錄移到高端/whileL.rhigh.Key=L.rlow.Key;/whileL.rlow.Key=L.r0.Key;樞軸記錄到位return low;/返回樞軸位置/P

8、artiti onvoid QSort(Sqlist & L,i nt low,i nt high)int pivotloc;if(low<high)/長度大于 1pivotloc=Partition(L,low,high);將 L.rlow highQSort(L,low,pivotloc-1);/QSort(L,pivotloc+1,high);/ /if/QSortvoid QuickSort(Sqlist &L)/QSort(L,1,L.le ngth); printf("交換排序:n”); output(L);/QuickSort/*選擇排序法*/vo

9、id SelectSort(Sqlist L)對低子表遞歸排序，pivotloc 對高子表遞歸排序?qū)樞虮鞮做快速排序分為二是樞軸位置for(i=1;i<=Len gth;i+) k=i;/要確定排序元素的位置for(j=i+1;j<=Len gth;j+)if(L.rk.Key>L.rj.Key) k=j; /temp=L.ri.Key; 輸出線性表 L L.ri.Key=L.rk.Key;L.rk.Key=temp;/forprintf("選擇排序:n”);output(L);/SelectSort若后面有更小的記錄下其位置主函數(shù)設計int mai n()Sql

10、ist L;In put(L);/BiI nserti on sort(L); /BubbleSort(L); /輸入要排的數(shù)字，創(chuàng)建線性表L對L進行插入排序，輸出線性表L 對L進行交換排序，輸出線性表LSelectSort(L); /對L進行選擇排序，輸出線性表Lreturn ok;四、程序調(diào)試分析1 、由于本次實驗中存儲數(shù)據(jù)的線性表是在In put函數(shù)中進行的，所以開始時忘了將l.length 初始化，出現(xiàn)報錯，開始我直接在定義線性表的結(jié)構(gòu)中賦值為MAXSIZE還是有問題，原來是定義結(jié)構(gòu)時不能直接在內(nèi)部賦初值！通過這次錯誤讓我對數(shù)組的用法有了一個更 深的了解，實踐后記得更深。2、對于快速排

11、序一直都不太理解，編譯時出現(xiàn)了各種報錯提示，后來我又回頭仔仔細細的看了書上的內(nèi)容， 重新理解快排的算法思想，先設置樞軸，進行一趟簡單的分大小， 再進行遞歸調(diào)用，直到排序結(jié)束，重新寫了一遍程序，調(diào)試了幾次就成功了，對于快排有了一個 較深的把握與理解。3、一直對于快排的交換環(huán)節(jié)存有疑慮，當出現(xiàn)第一個比樞軸小的關(guān)鍵字時就進行這句L.rlow.Key=L.rhigh.Key;原以為這樣后low空間里的關(guān)鍵字被換成了 high的了，那low里的關(guān)鍵字就缺失了，但是調(diào)試卻沒有問題，經(jīng)過單步運行后，發(fā)現(xiàn)原來low里的為樞軸量，放在了首單元地址里，后來又換回來了，所以沒有缺失。4、在選擇排序中，剛開始我的程序

12、是比較后就直接交換的，后來看書上是記住數(shù)組的下標全部比較后進行一次交換就可以了，少了不少的交換次數(shù)，效率提高了不少，讓我看到了優(yōu)化程序的重要性，在實現(xiàn)的基礎上不斷地去優(yōu)化程序，讓程序變得更好。五、用戶使用說明1、本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：排序.exe。2、進入程序后，輸入所需排序的十個整數(shù)，回車運行程序。3、程序運行后即在屏幕上輸出計算結(jié)果。六、程序運行結(jié)果叵 *D：Program Files (x86)Vni<rosoft visual c+ + MSDc-v98MyProjcct1cpp4 1010073473 4475773344757733447577395

13、10096 1009S 10012 34 57 99 21折半插入排序:41012 Z1交換排序，1 IQ 1221孫擇舟£序=41012 Z1Press anyto conti_n ue'D:Pragram File (xfiSmicnQSQFt visual c+MSDev5SMyProj21 3 34 1 54 3 67 54 10U 45 卅半插入排序二133213445545467100交按排序：1332124455454詵擇排序：13321344554546?1QQFress on歲 k&y to continue七、程序清單#i nclude"

14、stdio.h"/*宏定義*/#defi ne KeyType int#defi ne MAXSIZE 10#defi ne ok 1#defi ne error 0 /*順序存儲結(jié)構(gòu)*/typedef structKeyType Key; RedType;typedef structRedType rMAXSIZE+1;in t le ngth;/ =MAXSIZE; Sqlist;/*輸入數(shù)據(jù)*/in tin put(Sqlist & L)for(int i=1;i<=MAXSIZE;i+)scan f("%d",&L.ri.Key);L

15、.le ngth=MAXSIZE;return ok;/*輸出排好的數(shù)字*/in t output(Sqlist L)for(int i=1;i<=MAXSIZE;i+)prin tf("%-4d",L.ri.Key);prin tf("n");return ok;/*折半插入排序法*/void Bii nserti on sort (Sqlist L)int i,j,low,high,m;for(i=2;i<=Len gth;i+)L.rO.Key=L.ri.Key; /把要插入的當成哨兵low=1; high=i-1;while(low&

16、lt;=high)II折半法找到要插入的位置m=(low+high)I2;if(L.rO.Key<L.rm.Key) high=m-1;else low=m+1;for(j=i-1;j>=high+1;j-) II插入位置后的袁術(shù)后移一位L.rj+1=L.rj;L.rhigh+1=L.rO; II插入元素IIlowprintf("折半插入排序:n");output(L);IIBii nserti on sortI*快速交換排序法*Iint Partition(Sqlist &L,int low,int high)int pivotkey;L.r0.Key

17、=L.rlow.Key;用子表的第一個記錄作樞軸記錄pivotkey=L.rlow.Key;樞軸記錄關(guān)鍵字while(low<high)從表的兩端交替地向中間掃描while(low<high&&L.rhigh.Key>=pivotkey)-high;/將比樞軸記錄小的記錄移到低端/whileL.rlow.Key=L.rhigh.Key;while(low<high&&L.rlow.Key<=pivotkey)+low;將比樞軸記錄大的記錄移到高端/whileL.rhigh.Key=L.rlow.Key;/whileL.rlow.Ke

18、y=L.r0.Key;樞軸記錄到位return low;/ 返回樞軸位置/Partitio n void QSort(Sqlist &L,int low,int high) int pivotloc;if(low<high)/長度大于 1分為二是樞軸位置pivotloc=Partitio n(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);將 L.rlow high-對低子表遞歸排序，pivotloc 對高子表遞歸排序?qū)樞虮鞮做快速排序要確定排序元素的位置/if/QSortvoid QuickSort(Sqlist &L)/QSort(L,1, L.le ngth); printf("交換排序:n");output(L);/QuickSort/*選擇排序法*/void SelectSort(Sqlist L)int i,j,k,temp;for(i