第八章堆積-wenkub
2022-10-22 12:12:13 本頁(yè)面
【正文】 *1+2=4 個(gè)位置，其值為 13。 ? struct heapTag *heap。若 size 成員值已達(dá) 0 值則傳回 0 值。 ? } 從堆積移除節(jié)點(diǎn) ? 從堆積 heap 裡移除資料 *dataptr 所指的節(jié)點(diǎn)，該指標(biāo)為資料陣列第零個(gè)元素的位址，即 heapdata[0]，它是堆積裡最大值者，然後將最後的元素移到陣列第零個(gè)元素的位址，進(jìn)行 ReheapDown() 再堆下作業(yè)，使?jié)M足堆積的要求。 ? (heaplast)。 ? } ? } ? return。 ? if (heappare(data[child],data[parent])0) ? { ? temp=data[parent]。 ? } 插入堆積 ? void ReheapUp(struct heapTag *heap, int child) ? { ? int parent。 ? ++(heapsize)。 ? heapdata[heaplast] = dataptr。 ? } 建立堆積結(jié)構(gòu) 建立堆積結(jié)構(gòu) ? 需要提供兩個(gè)引數(shù)， 第一個(gè)是最大容量之元素個(gè)數(shù) maxsize， 第二個(gè)是比較的函式名稱 pare。 ? heappare = pare。 ? heap = malloc(sizeof(struct heapTag))。 ? }。 ? int last。 ? 2. 9 的註標(biāo)為 4（從 0算起），其父母節(jié)點(diǎn) 57 的註標(biāo) 為 (41)/2 整數(shù)部份為 1。 ? 右子女節(jié)點(diǎn)註標(biāo)為 k，左子女節(jié)點(diǎn)註標(biāo)為 k1。舉例如下圖。 26 比它的父母節(jié)點(diǎn) 13 還大，違反堆積的規(guī)定，必須互換，因此就往上移動(dòng)，如下圖所示。 再堆上作業(yè) ? 假想我們有一個(gè) N 個(gè)元素的接近完整二元樹，其前面的 N1 個(gè)元素均已滿足堆積的要求，但最後一個(gè)元素 N 卻不滿足堆積，換句話說(shuō)只要第 N 個(gè)元素滿足堆積的要求，整個(gè)結(jié)構(gòu)就是一個(gè)堆積了。注意上圖（ c）是一棵接近完整的二元樹，第二層次是從左而右填滿的，這也是堆積的要求。 ? 2. 每一節(jié)點(diǎn)的鍵值大於或等於其子樹節(jié)點(diǎn)鍵值。 ? 若父母節(jié)點(diǎn)的 註標(biāo) i 從 0 開始 計(jì)數(shù)時(shí)，則左子樹節(jié)點(diǎn)的註標(biāo)為 2*i+1，右子樹節(jié)點(diǎn)的註標(biāo)為 2*i+2。這中堆績(jī)稱為最大堆績(jī)。第八章 堆 積 ? 堆積 （ heap）是樹結(jié)構(gòu)的第三種型態(tài)。堆積的子樹可擺在左邊當(dāng)左子樹，也可擺在右邊當(dāng)右子樹，因此左右子樹俱有相同的性質(zhì)。 ? 若父母節(jié)點(diǎn)的 註標(biāo) i 從 1 開始 計(jì)數(shù)時(shí)，則左子樹節(jié)點(diǎn)的註標(biāo)為 2*i，右子樹節(jié)點(diǎn)的註標(biāo)為 2*i+1。 ? 一棵完整的二元樹是每一層次（ level）都佔(zhàn)滿，一棵接近完整的二元樹指其葉節(jié)點(diǎn)相差在一個(gè)層次以內(nèi)。 堆積有兩個(gè)基本的操作 ? 對(duì)於堆積有兩個(gè)基本的操作： 插入一個(gè)節(jié)點(diǎn) 以及 移除一個(gè)節(jié)點(diǎn) 。再堆上作業(yè)將第 N 個(gè)元素往上堆，定位於正確的位置，使整個(gè)結(jié)構(gòu)成為一個(gè)堆積。 26再往上移動(dòng) ? 26 比
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1