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