快速排序和堆排序 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：102012指導(dǎo)教師評定：簽實(shí)驗(yàn)名稱：實(shí)驗(yàn)十內(nèi)部排序?qū)W生姓名：學(xué)號：名：題目：編程分別實(shí)現(xiàn)快速排序算法、堆排序算法。一、需求分析用戶可以根據(jù)自己的需求輸入一個(gè)順序表。通過利用快速排序法按非遞減排序已有的順序表。通過利用堆排序按非遞減排序已有的順序表。程序執(zhí)行的命令包括：(1)創(chuàng)建順序表(2)輸出順序表(3快速排序算法排序(4)堆排序算法排序二、概要設(shè)計(jì)為實(shí)現(xiàn)上述算法，需要順序表的抽象數(shù)據(jù)類型：ADTsqlist數(shù)據(jù)對彖D：D是具有相同特征的數(shù)據(jù)元素的集合。各數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)識數(shù)據(jù)元素的關(guān)鍵字。數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個(gè)集合?；静僮鱌：Creatsql

2、ist(&1)操作結(jié)果：構(gòu)造一個(gè)具有n個(gè)數(shù)據(jù)元素的順序表loListLength(L)初始條件：線性表L已經(jīng)存在操作結(jié)果：返回L中數(shù)據(jù)元素的個(gè)數(shù)。destroylist(&1)初始條件：順序表1存在。操作結(jié)果：銷毀順序表1。displaylist(1)初始條件：順序表1存在。操作結(jié)果：顯示順序表1。quicksort(&1)初始條件：順序表1存在。操作結(jié)果：通過快速排序得到一個(gè)有序的順序表loheapsort(&1)初始條件：順序表1存在。操作結(jié)果：通過堆排序得到一個(gè)有序的順序表loheapadjust(&1,sm)初始條件：順序表1存在。操作結(jié)果：調(diào)整h-rs的關(guān)鍵字，使h-rs成為一個(gè)大頂

3、堆partion（&1,&1ow,high）初始條件：順序表1存在。操作結(jié)果：交換順序表中子表rlow.high的記錄，使樞軸記錄到位，并返回其所在的位置。ADTsqlist本程序有三個(gè)模塊：（1）主程序模塊mainO初始化：接受命令:顯示結(jié)果;（2）創(chuàng)建順序表的模塊：主要建立一個(gè)順序表;快速排序模塊：得到一個(gè)有序的順序表：（4）輸出順序表模塊：顯示已創(chuàng)建順序表；（5）堆排序模塊：得到一個(gè)有序的順序表。三、詳細(xì)設(shè)計(jì)1元素類型，結(jié)點(diǎn)類型typedefstructintkey;keytype;typedefstructkeytyper100:int2ngth;sqlist;對抽彖數(shù)據(jù)類型中的部分基

4、本操作的偽碼算法如下:/*創(chuàng)建順序表*/voidcreat(sqlist*1)intprintf(pleaseintputitslength:);scanf&1-length);printf(z，nnpleaseintput%ddatan，z,llength);for(i=l;ilength;i+)scanf(“%&key);l-rikey=key;/*交換順序表中子表rlow.high的記錄，使樞軸記錄到位，并返回其所在的位置*/intpartion(sqlist*1,intlow,inthigh)intpivotkey;l-r0l-rlow;pivotkey=lrlowkey;while(

5、lowhigh)while(lowrhigh_key=pivotkey)high;l-rlow=l-rhigh;while(lowrlowkeyrhigh=l-rlow;l-rlowl-r0;returnlow;/*快速排序*/voidQsort(sqlist*1,intlow,inthigh)intpivotloc;if(lowlength);/*顯示順序表*/voiddisplay(sqlist*1)inti;for(i=l;ilength;i+)printf(，z%4.2d,i);printfCXn);for(i=l;ilength;i+)printfC3；printfCn)；for(i

6、=l;ilength;i+)printf2d,1-工ikey);/*調(diào)整h-rs的關(guān)鍵字，使h-rs成為一個(gè)人頂堆*/voidheapadjust(sqlist*h,ints,intm)keytyperc;intj；rc=h-rs;for(j=2*s;jrj+1key)+j;if(rckey=hrjkey)break:h-rs=h-rj;s二j；h-rs=rc;/*對順序表h進(jìn)行堆排序*/voidheapsort(sqlist*h)keytyperc;inti;for(i=h-length/2;i0;i)heapadjust(h,i,hlength);for(i=h-length;il;i)r

7、c=h-r1;h-rlh-ri;hrLi=rc;heapadjust(h,1,il);主函數(shù)和其他函數(shù)的偽碼算法/*主函數(shù)*/voidmainOsqlisti;creat(&t);Qsort(&t,1,tlength);printfCnn，z);printf(quicksortmeans：n);display(&t);heapsort(&t);printfCnz，);printf(/znheapsortmeans:nz，);display(&t);g己tch();4函數(shù)調(diào)用關(guān)系mainheapsortdisplaycreatQsortheapadjustpartion四、調(diào)試分析1開始的時(shí)候在

8、編寫快速排序算法的時(shí)候沒有設(shè)置用子表的第一個(gè)記錄作樞軸記錄導(dǎo)致沒有得到正確的結(jié)果。在l-rlow=l-rhigh;語句進(jìn)行交換時(shí),寫成lrlow.key=lrhigh.key,一直沒有找到錯(cuò)誤的地方，在看了參考資料后才發(fā)現(xiàn)是這里錯(cuò)了。算法的時(shí)空分析各操作的算法時(shí)間復(fù)雜度比較合理creat,partion,display為0(n)Qsort,heapadjustheapsort為O(nlogn)注：n為哈希表的長度。本次實(shí)驗(yàn)采用數(shù)據(jù)抽彖的程序設(shè)計(jì)方法，將程序化為三層次結(jié)構(gòu)，設(shè)計(jì)時(shí)思路清晰，使調(diào)試也較順利，各模塊有較好的可重用性。五、用戶手冊1-本程序的運(yùn)行環(huán)境為windowsxp操作系統(tǒng)，并且在

9、TC2.0中運(yùn)行，執(zhí)行文件為ExplO.c；2.進(jìn)入演示程序后，完成編譯，再點(diǎn)擊超級工具集里的中文DOS環(huán)境運(yùn)行選項(xiàng)，進(jìn)入DOS環(huán)境中，用戶根據(jù)需求鍵入相應(yīng)的數(shù)據(jù)，可以看到相應(yīng)的結(jié)果。六、測試結(jié)果在dos下輸入數(shù)據(jù)元素：98231056212301647434排序后的結(jié)果是：01102123233456647498則在dos界面輸入如圖所示：C:.DOCUME-1ADMINI-1面.paixu.exepleaseintputitslength=10pleaseintput10data&8231056212301647434o;uicksot*tmeans:pl02030405060?08091

10、00丄102123233456647498iea.psoitmeans:0102030405060708091001102123233456647498七、附錄：源程序#includestdio.htypedefstructintkey;keytype;typedefstructkeytyper100;int2ngth;sqlist;/*創(chuàng)建順序表*/voidcreat(sqlist*1)inti,“y;printf(pleaseintputitslength:);scanf&1-length);printf(z，nnpleaseintput%ddatan，z,llength);for(i=l

11、;ilength;i+)scanf(，z%d，z,&key);lrikey=key;/*交換順序表中子表rlow.high的記錄，使樞軸記錄到位，并返回其所在的位置*/intpartion(sqlist*1,intlow,inthigh)intpivotkey;l-r0l-rlow;pivotkey=lrlowkey;while(lowhigh)while(lowrhigh_key=pivotkey)high;lrlow=lrhigh;while(lowrlowkeyrhigh=l-rlow;l-rlowl-r0;returnlow;/*快速排序*/voidQsort(sqlist*1,int

12、low,inthigh)intpivotloc;if(lowhigh)pivotloc二partion(l,low,high);Qsort(1,low,pivotloc-1);Qsort(1,pivotloc+1,high);/*顯示順序表*/voiddisplay(sqlist*1)inti;for(i=l;ilength;i+)printf2d,i);printfCnz，);for(i=l;ilength;i+)printfC3；printfCnz，);for(i=l;ilength;i+)printf2d,1-工ikey);/*調(diào)整h-rs的關(guān)鍵字，使h-rs成為一個(gè)人頂堆*/voidheapadjust(sqlist*h,ints,intm)keytyperc;intj；rc=h-rs;for(j=2*s;jrj+1key)+j;if(rckey=hrjkey)break:h-rs=h-rj;s二j；h-rs=rc;/*對順序表h進(jìn)行堆排序*/voidheapsort(sqlist*h)keytyperc;inti;for(i=h-length/2;i0;i)heapadjust(h,i,hlength);for(i=h-length;il;i)rc=h-r1;h-rl二h-ri;hri=rc;