第八章堆積(文件)
【正文】 它的父母節(jié)點 43 還小，就不必再移動，已經(jīng)定到正確的位置了。 堆積實作 ? 雖然堆積可以透過動態(tài)樹結(jié)構(gòu)建立起來，但最常見的還是以陣列實作為宜。 ? 4. 設(shè)完整堆積元素數(shù)為 n，第一個葉節(jié)點為 (n/2) 之整數(shù)部份。 ? 3. 總共有 7 個元素（ n=7），第一個葉節(jié)點為 7/2 整數(shù)部份為 3。 ? int size。 data指標(biāo)變數(shù)的含意 ? 這種結(jié)構(gòu)就命名為 heapTag 結(jié)構(gòu)。 ? if (heap == NULL) ? return NULL。 ? heapmaxsize = (int)pow(2,ceil(log2(maxsize)))1。首先取得一塊 heapTag 結(jié)構(gòu)的 heap 記憶體，設(shè)定 heaplast 為 1， heapsize 為 0， heapmazsize 最大容量為 2 的 log10(maxsize)/log10(2) 次方值再減一，例如 mazsize 引數(shù)值為 16，那麼 heapmaxsize 的值為 2 的 4 次方再減一，為 7。 ? return 1。 ? heapdata[heaplast] = dataptr。 ? void **data, **temp。 data[parent]=data[child]。 ? } 從堆積移除節(jié)點 ? int heapRemove(struct heapTag *heap, void **dataptr) ? { ? if (heapsize == 0) ? return 0。 ? (heapsize)。ReheapDown() 再堆下函式屬於遞迴函式，一層一層往下堆積，直到最後一個元素那一層時才停止。 測試程式 ? 上面說明的堆積結(jié)構(gòu)宣告以及相關(guān)的函式存入 表頭檔備用。 ? heap = heapCreate(16,pareInt)。 節(jié)點 45 在第 2 個位置，左子樹在第 2*2+1=5 個位置，其值為 24，右子樹在第 2*2+2=6 個位置，其值為 15。設(shè)機組員的優(yōu)先碼為 4，貴賓優(yōu)先碼為 3，孕婦優(yōu)先碼為 2，一般乘客優(yōu)先碼為 1。每一類別人員建立一個如下的資料結(jié)構(gòu)custNodeTag。 ? int priority。所建立的堆積如下圖所示。 ? void **data, *temp。 data[parent]=data[child]。 ? } /*exchange*/ /*when child*/ /* parent*/ 最小堆積 ? 修改成子女節(jié)點之較小者，比父母節(jié)點小時，互換其值，小者往上升或往下降。 最小堆積 ? 執(zhí)行時依序從整數(shù) k[] 陣列取得下列資料建立 heap 最小堆積，輸入資料如下： ? 9 24 45 13 21 53 15 19 。 ? 下列程式 用於測試 是否正確。 ReheapUp (heap, parent)。 ? parent = (child 1)/ 2。移除 4997 節(jié)點後，4996 次大值變成新的根節(jié)點，接著移除，第三大值的 4991 變成新的根節(jié)點，如此循序移除，直到?jīng)]有節(jié)點為止，移除的節(jié)點資料除了顯示在螢?zāi)恢?，還輸出至 本文檔。 ? }。每一類別人員建立一個如下的資料結(jié)構(gòu) custNodeTag。 優(yōu)先佇列 ? 我們使用電腦來模擬，若每一個人有一個識別碼
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1