算法與數(shù)據(jù)結(jié)構(gòu)程設(shè)計報告

1、算法與數(shù)據(jù)結(jié)構(gòu)程設(shè)計報告一 設(shè)計題目： 堆排序的算法二運(yùn)行環(huán)境：1、 硬件：計算機(jī)2、 軟件：microsoft visual c+6.0三目的和意義：目的：創(chuàng)建一個大堆，按從大到小順序輸出堆元素，實(shí)現(xiàn)堆排序。意義：利用堆排序，即使在最壞情況下的時間復(fù)雜度也是o(nlog2n)，相對于快速排序來說，時間復(fù)雜度小，這是堆排序的最大優(yōu)點(diǎn)，可用于對若干元素進(jìn)行排序，加快排序速度。四算法設(shè)計的基本思想：堆排序算法設(shè)計基本思想：堆排序利用了大根堆堆頂記錄的關(guān)鍵字最大這一特征，使得在當(dāng)前無序區(qū)中選取最大關(guān)鍵字的記錄變得簡單。先將初始文件r1.n建成一個大根堆，此堆為初始的無序區(qū)。再將關(guān)鍵字最大的記錄r1(

2、即堆頂)和無序區(qū)的最后一個記錄rn交換，由此得到新的無序區(qū)r1.n-1和有序區(qū)rn，且滿足r1.n-1.keysrn.key。由于交換后新的根r1可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)r1.n-1調(diào)整為堆。然后再次將r1.n-1中關(guān)鍵字最大的記錄r1和該區(qū)間的最后一個記錄rn-1交換，由此得到新的無序區(qū)r1.n-2和有序區(qū)rn-1.n，且仍滿足關(guān)系r1.n-2.keysrn-1.n.keys，同樣要將r1.n-2調(diào)整為堆。直到無序區(qū)只有一個元素為止.五 程序流程圖： 流程圖1 輸入數(shù)組長度len的值 ilen i=0輸入aii+temp=1;sum=0;sum+tem=0i=sum-1調(diào)用建堆函數(shù)b

3、uild()i-ilen-1i=0tmp=a0;a0=alen-1-i;alen-1-i=tmp; 調(diào)用建堆函數(shù)build()調(diào)用打印隊(duì)函數(shù)prnthp() 調(diào)用打印已排序數(shù)組函數(shù)prntar()printf(“-“); printf(n 排序結(jié)果：n) 調(diào)用調(diào)用打印數(shù)組函數(shù)prnt()printf(n=nn)調(diào)用getch(). k=i; j=2*k+1 jn yjn & aj=ajtmp=ak 返回主調(diào)函數(shù)ak=ajaj=tmp 流程圖2：建堆函數(shù)build()流程圖3：打印數(shù)組函數(shù)print() printf(n) in i=0printf(%3d,ai)i+printf(n)h=0,s

4、um=0,item=1; size=b2-b1+1;ysum=sizen sum+=itemh+item*=2 item=1;cnt=0;start=b1;tmp=1;printf(n-n)；printf( 堆：n)真 y n ih i=0jh-i j=0 打印空格 ji+1 j=0 打印空格 jsize-1輸出acnt+ j+ j+ j+ printf(n)tmp*=2 i+流程圖4：打印堆函數(shù)prnthp()六 算法設(shè)計分析：性能分析：堆排序的時間主要由建立初始堆和不斷重復(fù)建堆這兩部分的時間開銷構(gòu)成,它們均是通過調(diào)用heapify實(shí)現(xiàn)的。其中：建立初始堆時，總共需進(jìn)行的關(guān)鍵字比較次數(shù) 4n

5、 =o(n) ;排序過程中進(jìn)行n-1次重建堆所進(jìn)行的總比較次數(shù)不超過下式： 2*( log2(n-1) + log2(n-2) + log22 ) 2n log2n =o(n log2n)因此堆排序總的時間復(fù)雜度是 o(n+ n log2n)= o(n log2n)。堆排序在最壞情況下的時間復(fù)雜度也是o(nlog2n)，相對于快速排序來說，這是堆排序的最大優(yōu)點(diǎn)。另外，堆排序僅需一個記錄大小供交換用的輔助空間。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄較少的文件，但對n較大的文件還是很有效的。堆排序是就地排序，輔助空間為o(1)，它是不穩(wěn)定的排序方法。堆的描述：堆排序(heapsor

6、t)是一樹形選擇排序。堆是對基于數(shù)組的樹的重要應(yīng)用場合之一。它是節(jié)點(diǎn)間具有層次次序關(guān)系的完全二叉樹。其中，父節(jié)點(diǎn)值大于或等于其孩子節(jié)點(diǎn)值的，叫“最大堆（maximum heap）”;父節(jié)點(diǎn)值小于或等于孩子節(jié)點(diǎn)值的，叫“最小堆（minimum heap）”.在最大堆中，根中的元素值最大；在最小堆中，根中的元素值最小。堆排序的特點(diǎn)是：在排序過程中，將rl.n看成是一棵完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大(或最小)的記錄。從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最后一個元素交換位置。所以堆排序有兩個函數(shù)組成。一

7、是建堆的滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實(shí)現(xiàn)排序的函數(shù)。 堆的存儲特點(diǎn) ：在這里，討論作為順序表存儲的堆。它是按某種次序?qū)⒁幌盗袛?shù)據(jù)以完全二叉樹形式存放的一種表。它要求堆中的節(jié)點(diǎn)的值都大于或等于其孩子節(jié)點(diǎn)的值。 按照這種存儲方式，可知第i個元素的左右兒子分別是第2i和第2i+1個元素，而它的父親節(jié)點(diǎn)是第i/2個元素。由于父親節(jié)點(diǎn)和兒子節(jié)點(diǎn)具有這樣的順序關(guān)系，所以可以方便地由父親節(jié)點(diǎn)找到兒子節(jié)點(diǎn)，反之亦然?？梢?，這種存儲方式大大節(jié)省了存儲空間，高效快速。 堆的相關(guān)操作 ：作為抽象表結(jié)構(gòu)，堆允許增加和刪除表項(xiàng)。插入過程不用假定新表項(xiàng)占有一個特定的位置而只需維持堆順序。但是刪除操作總是刪去表中的最大項(xiàng)

8、 （根）。 堆可以用于那些客戶程序想直接訪問最大（?。┰氐膱龊?。作為表，堆并不提供find操作，而對表的直接訪問是只讀的。所有的堆處理算法都有責(zé)任更新樹和維持堆順序。 1.建堆：數(shù)組具有對應(yīng)的樹表示形式。一般情況下，樹并不滿足堆的條件。通過重新排列元素，可以建立一棵“堆化”的樹。 2.插入一個元素：新元素被加入到表中，隨后樹被更新以恢復(fù)堆次序。例如，下面的步驟將15加入到表中。 3.刪除一個元素：刪除總是發(fā)生在根節(jié)點(diǎn)處。用表中的最后一個元素來填補(bǔ)空缺位置，結(jié)果樹被更新以恢復(fù)堆條件。 在堆實(shí)現(xiàn)時我們是采用數(shù)組來存儲堆的完全二叉樹表示，并且用一種有效的算法來保證對堆的所有操作不破壞堆的性質(zhì)。這種

9、表示的主要問題在于數(shù)組的大小需要事先確定，這使得對堆的大小有了一個初始的限定。在堆中數(shù)據(jù)增長到超過這個界限時雖然可以通過復(fù)制的方法建立更大的向量來存放堆，但整個向量的復(fù)制是不可避免的，這大大降低了操作效率。為避免這個問題，可把二叉樹的順序存儲改為二叉樹的鏈表存儲 . 根據(jù)算法復(fù)雜性分析的結(jié)果。williams&floyd在1964年提出的堆排序算法在最壞情況的時間復(fù)雜性為2nlogn+o(n)。但在判定樹的模型下，為n個數(shù)排序的算法時間復(fù)雜性的下界為nlogn+o(n)?？梢?，williams&floyd的算法或許可以改進(jìn)。其中在進(jìn)入實(shí)質(zhì)性排序的第i步，在把第i大元素（在堆頂）與當(dāng)時處在第i大

10、的目標(biāo)位置的元素對調(diào)之后，總是讓堆頂元素往下沉，可能直到葉子才完成局部（重新）堆化。如果當(dāng)時處在第i大的目標(biāo)位置元素很小，則下沉過程中要做很多次的比較。如果能把這個次數(shù)降下來，或許能對williams&floyd的算法作出效率上的顯著改進(jìn)。顧訓(xùn)穰，諸宇章就是這樣循著發(fā)現(xiàn)問題、提出問題、分析問題和解決問題的線索，通過讓空缺結(jié)點(diǎn)一下下沉h/2達(dá)到改進(jìn)的目的，于1994年在軟件學(xué)報上發(fā)表他們的成果。改進(jìn)后的堆排序算法在最壞情況下的時間復(fù)雜性為nlogn+nloglogn+o(n)主項(xiàng)系數(shù)由2降為1，與下界的主項(xiàng)系數(shù)同。 進(jìn)一步，王曉東、傅清祥等還是沿著發(fā)現(xiàn)問題、提出問題、分析問題和解決問題的思路，發(fā)

11、現(xiàn)顧訓(xùn)穰、諸宇章的算法可以通過讓空缺結(jié)點(diǎn)下沉f(h)=h-logh(不是h/2)改進(jìn)其時間復(fù)雜性的次項(xiàng)，于1996年在軟件學(xué)報上發(fā)表他們的成果。進(jìn)一步改進(jìn)后的堆排序算法在最最壞情況下的時間復(fù)雜性為nlogn+n3(n)+o(n)其中，函數(shù)x=3(y)是3階ackerman函數(shù)y=a(x，3)的逆函數(shù)。眾多的反映表明以上的設(shè)計是可取的。七 源代碼： 程序源代碼如下：/* name: heapsort2.c author: huangxing description: 堆排序算法的過程演示 date: 30/11/2005 copyright: */#include#define n 6int k

12、,j;/* 建堆函數(shù) */void build(int *a,int i,int n) int tmp; k=i; j=2*k+1; while(j=n) if(jn & aj=aj)break; tmp=ak; ak=aj; aj=tmp; k=j; j=2*j+1; /* 打印數(shù)組函數(shù) */void prnt(int *a,int n) int i; printf(n); for(i=0;in;i+) printf(%3d,ai); printf(n);/* 打印堆函數(shù) */void prnthp(int *a,int b1,int b2) int size; int h=0,sum=0,

13、item=1; int i,j,cnt,start,tmp; size=b2-b1+1; while(sum=size) sum+=item; h+; item*=2; item=1; cnt=0; start=b1; tmp=1; printf(n-n); printf( 堆：n); while(1) for(i=0;ih;i+) for(j=0;jh-i;j+) printf( ); for(j=0;ji+1;j+)printf( ); for(j=0;jsize-1)goto end; printf(%4d,acnt+); printf(n); tmp*=2; end: printf(n

14、); return; /* 打印已排序數(shù)組函數(shù) */void prntar(int *a,int b2,int len) int i; printf( 已排序：n); for(i=0;ib2;i+) printf( ); for(i=b2;i=len;i+) printf(%3d,ai); printf(n); main() /* int a=-1,2,5,1,0,-3,-2,8,6; */ int a50; int i; int tmp; int sum; int num; int len; printf( 堆排序n); printf(n=n); printf(n 請輸入待排序數(shù)組個數(shù),以回

15、車結(jié)束：n); scanf(%3d,&len); printf(n 請輸入待排序數(shù)組,以回車結(jié)束：n); for(i=0;ilen;i+) scanf(%3d,&ai); tmp=1;sum=0; while(sum+tmp=0;i-) build(a,i,len-1); prnthp(a,0,len-1); /* 改建堆 */ for(i=0;ilen-1;i+) tmp=a0; a0=alen-1-i; alen-1-i=tmp; build(a,0,len-2-i); prnthp(a,0,len-2-i); prntar(a,len-1-i,len-1); printf(n-n); p

16、rintf(n 排序結(jié)果：n); prnt(a,len); printf(n=nn); getch();八 程序調(diào)試過程分析： 程序剛開始運(yùn)行不了，錯誤達(dá)8處，于是本人就認(rèn)真檢查，居然發(fā)現(xiàn)有6處不是寫錯了符號就是少了括號，粗心之至。于是改過來，但還有2處錯誤怎么也改不好，也不知道錯在哪里。于是問同學(xué)，上網(wǎng)查資料，發(fā)帖子求助，終于搞明白，也改過來了，原來是調(diào)用函數(shù)時出的錯。現(xiàn)在程序改好，可以正常運(yùn)行了，以下就可以看到程序運(yùn)行結(jié)果。九 運(yùn)行結(jié)果及分析：經(jīng)過不斷調(diào)試，確保程序無誤后，輸入執(zhí)行程序，會得到以下程序結(jié)果：我們隨便舉一例，假若我們輸入8回車，會得到下面結(jié)果：我們再隨便輸入8個數(shù)，如果輸入的是以下8個數(shù)字：6 9 5 8 7 0 -3 8再回車就能看到程序最后執(zhí)行的結(jié)果，如下： 十、小結(jié)： 經(jīng)過幾天的不斷努力，課程設(shè)計終于完成了，但肯定還存在許多不足，在這里有一點(diǎn)心得，堆就是一個關(guān)鍵字序列，對于堆排序，歸結(jié)起來，有兩個步驟：（1）建堆；（2）反復(fù)調(diào)整堆。對于給定的序列，用堆排序的過程主要是通過畫完全二叉樹來演示。通過這個課題，復(fù)習(xí)了許多沒搞懂的地方，也通過這比較了與別的排序法的區(qū)別，例如堆排序與直接插入排序的區(qū)別：直接選擇排序中，為了從r1.n中選出關(guān)鍵字最小的記錄，必須進(jìn)行n-1次比較，然后在r2.n中選出關(guān)鍵字最小的記錄，又需要做n-2次比較。事實(shí)上，后面的n-2次