北理工數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告4

1、數(shù)據(jù)結(jié)構(gòu)與算法統(tǒng)計(jì)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)四學(xué)院:班級(jí):學(xué)號(hào):姓名:、實(shí)驗(yàn)?zāi)康?、熟悉VC環(huán)境，學(xué)會(huì)使用 C語(yǔ)言利用順序表解決實(shí)際問(wèn)題。2、通過(guò)上機(jī)、編程調(diào)試，加強(qiáng)對(duì)線性表的理解和運(yùn)用的能力。3、鍛煉動(dòng)手編程，獨(dú)立思考的能力。二、實(shí)驗(yàn)內(nèi)容從鍵盤輸入10個(gè)數(shù)，編程實(shí)現(xiàn)分別用插入排序、交換排序、選擇排序算法進(jìn)行排序, 輸出排序后的序列。三、程序設(shè)計(jì)1 、概要設(shè)計(jì)為了實(shí)現(xiàn)排序的功能，需要將輸入的數(shù)字放入線性表中，進(jìn)行進(jìn)一步的排序操作。 (1)抽象數(shù)據(jù)類型：ADT SqList數(shù)據(jù)對(duì)象：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)造一個(gè)線性表L。output(SqList L)初始條件：線性表 L已存在。操作結(jié)果：按順序在屏幕上輸出L的數(shù)據(jù)元素。BiI nsertio nsort (Sqlist L)初始條件：線性表 L已存在。操作結(jié)果：對(duì)L的數(shù)據(jù)元素進(jìn)行折半插入排序。Quicksort (Sqlist L)初始條件：線性表 L已存在。操作結(jié)果：對(duì)L的數(shù)據(jù)元素進(jìn)行交換排序。SelectSort(SqList &L)初始條件：線性表 L已存在。操作結(jié)果：對(duì)L的數(shù)據(jù)元素進(jìn)行選擇排序。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ù)進(jìn)行折半插入排序，調(diào)用output(L)函數(shù)顯示排序結(jié)果。再調(diào)用QuickSort (L)函數(shù)進(jìn)行交換排序，調(diào)用output (L)函數(shù)顯示排序結(jié)果。函數(shù)顯示排序結(jié)果。最后調(diào)用SelectSort(L)函數(shù)進(jìn)行選擇排序，調(diào)用output(L)模塊調(diào)用關(guān)系由主函數(shù)模塊調(diào)用創(chuàng)建順序表模塊，排序模塊與顯示輸出模塊。(5)流程圖開(kāi)始輸入待排數(shù)字創(chuàng)建線性表進(jìn)行插入排序輸出排序結(jié)果進(jìn)行交換排序輸出排序結(jié)果進(jìn)行選擇排序輸出排序結(jié)

4、果結(jié)束2、詳細(xì)設(shè)計(jì)(1)數(shù)據(jù)類型設(shè)計(jì)/*順序存儲(chǔ)結(jié)構(gòu)*/typedef structKeyType Key; / 關(guān)鍵字項(xiàng) RedType;typedef structRedType rMAXSIZE+1;int len gth;/ =MAXSIZE; Sqlist;/(2)操作算法設(shè)計(jì)/*輸入數(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);定義順序表類型把要插入的當(dāng)成哨兵 折半法找到要插入的位置high=m-1;插入位置后的袁術(shù)后移一位插入元素/BiI nserti on sort/*快速交換排序法*/int Partition(Sqlist &L,int low,int high)int pivotkey;L.r0.Key=L.rlow.Key; /用子表的第一個(gè)記錄作樞軸記錄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)/長(zhǎng)度大于 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)對(duì)低子表遞歸排序，pivotloc 對(duì)高子表遞歸排序?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ù)設(shè)計(jì)int mai n()Sql

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

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

12、是比較后就直接交換的，后來(lái)看書(shū)上是記住數(shù)組的下標(biāo)全部比較后進(jìn)行一次交換就可以了，少了不少的交換次數(shù)，效率提高了不少，讓我看到了優(yōu)化程序的重要性，在實(shí)現(xiàn)的基礎(chǔ)上不斷地去優(yōu)化程序，讓程序變得更好。五、用戶使用說(shuō)明1、本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：排序.exe。2、進(jìn)入程序后，輸入所需排序的十個(gè)整數(shù)，回車運(yùn)行程序。3、程序運(yùn)行后即在屏幕上輸出計(jì)算結(jié)果。六、程序運(yùn)行結(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 /*順序存儲(chǔ)結(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; /把要插入的當(dāng)成哨兵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;用子表的第一個(gè)記錄作樞軸記錄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)/長(zhǎng)度大于 1分為二是樞軸位置pivotloc=Partitio n(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);將 L.rlow high-對(duì)低子表遞歸排序，pivotloc 對(duì)高子表遞歸排序?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