第八章堆積-資料下載頁(yè)
【導(dǎo)讀】堆積是樹(shù)結(jié)構(gòu)的第三種型態(tài)。其左右子樹(shù)節(jié)點(diǎn)的值均較其父母節(jié)點(diǎn)的值小。值保證是該樹(shù)最大值。這中堆績(jī)稱(chēng)為最大堆績(jī)。樹(shù)俱有相同的性質(zhì)。堆積還有一個(gè)有趣的特性，就是以陣列實(shí)作較以連結(jié)串列實(shí)。當(dāng)以陣列實(shí)作堆積時(shí)，已知父母節(jié)點(diǎn)的註標(biāo)。為2*i+1，右子樹(shù)節(jié)點(diǎn)的註標(biāo)為2*i+2。一棵堆積是一棵二元樹(shù)，俱備下列的特性：。完整的二元樹(shù)指其葉節(jié)點(diǎn)相差在一個(gè)層次以?xún)?nèi)。在上圖的兄弟節(jié)點(diǎn)裡，左節(jié)點(diǎn)有大於右節(jié)點(diǎn)者，節(jié)說(shuō)明過(guò)的二元搜尋樹(shù)是不允許的。對(duì)於堆積有兩個(gè)基本的操作：插入一個(gè)節(jié)。點(diǎn)以及移除一個(gè)節(jié)點(diǎn)。假想我們有一個(gè)N個(gè)元素的接近完整二元樹(shù)，其。位置，使整個(gè)結(jié)構(gòu)成為一個(gè)堆積。上圖新元素26插入原來(lái)已成堆積的樹(shù)。元素規(guī)定要擺在最右邊的。雖然堆積可以透過(guò)動(dòng)態(tài)樹(shù)結(jié)構(gòu)建立起來(lái)，但最常見(jiàn)的還是。以陣列實(shí)作為宜。右子女節(jié)點(diǎn)註標(biāo)為k，左子女節(jié)點(diǎn)註標(biāo)為k-1。這種結(jié)構(gòu)就命名為heapTag結(jié)構(gòu)。需要提供兩個(gè)引數(shù)，第一個(gè)是最大容量之元
【正文】 ? struct custNodeTag ? { ? int id。 ? int priority。 ? int serial。 ? }。 ? 其中 id 成員為人員識(shí)別碼， priority 為優(yōu)先碼，serial 為序號(hào)。所建立的堆積如下圖所示。 登機(jī)人員所建立的堆積 登機(jī)人員所建立的 heap 堆積 ? 登機(jī)人員所建立的 heap 堆積，在根節(jié)點(diǎn)序號(hào) 4997 是堆積裡頭最大的，他的優(yōu)先碼為 4，屬於最優(yōu)先的一群。移除 4997 節(jié)點(diǎn)後，4996 次大值變成新的根節(jié)點(diǎn)，接著移除，第三大值的 4991 變成新的根節(jié)點(diǎn)，如此循序移除，直到?jīng)]有節(jié)點(diǎn)為止，移除的節(jié)點(diǎn)資料除了顯示在螢?zāi)恢猓€輸出至 本文檔。 登機(jī)人員所建立的 heap 堆積輸出如下 ? id priority serial ? 104 4 4997 ? 204 4 4996 ? 304 4 4991 ? 103 3 3998 ? 203 3 3994 ? 303 3 3989 ? 202 2 2995 ? 302 2 2990 ? 101 1 1999 ? 201 1 1993 ? 301 1 1992 最小堆積 ? 前面所處理的堆積為內(nèi)定的最大堆積，若要建立最小堆積又如何？只要修改再堆上 ReheapUp() 及再堆下 ReheapDown() 這兩個(gè)函式就行，修改如下： ? void ReheapUp(struct heapTag *heap, int child) ? { ? int parent。 ? void **data, *temp。 ? if (child != 0) ? { ? data = heapdata。 ? parent = (child 1)/ 2。 ? if (heappare(data[child],data[parent])0) ? { ? temp=data[parent]。 data[parent]=data[child]。 ? data[child]=temp。 ReheapUp (heap, parent)。 ? } ? } ? return。 ? } /*exchange*/ /*when child*/ /* parent*/ 最小堆積 ? 修改成子女節(jié)點(diǎn)之較小者，比父母節(jié)點(diǎn)小時(shí)，互換其值，小者往上升或往下降。 ? 修改 後的檔案改名為 表頭檔備用。 ? 下列程式 用於測(cè)試 是否正確。執(zhí)行時(shí)依序從整數(shù) k[] 陣列取得下列資料建立 heap 最小堆積，輸入資料如下： ? 9 24 45 13 21 53 15 19 ? 所建立的堆積如下圖所示。 最小堆積 ? 執(zhí)行時(shí)依序從整數(shù) k[] 陣列取得下列資料建立 heap 最小堆積，輸入資料如下： ? 9 24 45 13 21 53 15 19
鄂ICP備17016276號(hào)-1