第八章堆積(參考版)
2024-10-15 12:12本頁面
【正文】 最小堆積 ? 執(zhí)行時依序從整數 k[] 陣列取得下列資料建立 heap 最小堆積，輸入資料如下： ? 9 24 45 13 21 53 15 19 。 ? 下列程式 用於測試 是否正確。 ? } /*exchange*/ /*when child*/ /* parent*/ 最小堆積 ? 修改成子女節(jié)點之較小者，比父母節(jié)點小時，互換其值，小者往上升或往下降。 ReheapUp (heap, parent)。 data[parent]=data[child]。 ? parent = (child 1)/ 2。 ? void **data, *temp。移除 4997 節(jié)點後，4996 次大值變成新的根節(jié)點，接著移除，第三大值的 4991 變成新的根節(jié)點，如此循序移除，直到沒有節(jié)點為止，移除的節(jié)點資料除了顯示在螢幕之外，還輸出至 本文檔。所建立的堆積如下圖所示。 ? }。 ? int priority。每一類別人員建立一個如下的資料結構 custNodeTag。每一類別人員建立一個如下的資料結構custNodeTag。 優(yōu)先佇列 ? 我們使用電腦來模擬，若每一個人有一個識別碼，一般是護照號碼或身份證字號，還有一個優(yōu)先碼，這四類的人有先來後到的，若輸入檔案的內容如下： 101 1 103 3 104 4 204 4 202 2 203 3 201 1 301 1 304 4 302 2 303 3 第一個欄位為識別碼，為了簡單起見識別碼採用三位數字，第二欄為優(yōu)先碼，一位數字 1～ 4，優(yōu)先碼 4 最優(yōu)先。設機組員的優(yōu)先碼為 4，貴賓優(yōu)先碼為 3，孕婦優(yōu)先碼為 2，一般乘客優(yōu)先碼為 1。 優(yōu)先佇列 ? 許多出國旅遊的人在機場登機時，?？吹綑C組員最先登機，然後持有貴賓卡的人登機，然後孕婦或帶嬰兒的人登機，最後才是一般乘客登機，很顯然因為身份的不同，處理的方式也不同，某些人要優(yōu)先處理。 節(jié)點 45 在第 2 個位置，左子樹在第 2*2+1=5 個位置，其值為 24，右子樹在第 2*2+2=6 個位置，其值為 15。 ? 9 24 45 13 21 53 15 19 依序插入 9,24,45,13,21時之堆積 依序插入 53,15時之堆積 依序插入 19時之堆積及陣列 根節(jié)點 為第 0 個元素，其值為 53 最大，它的左子樹在第 1 個位置，其值為 21，它的右子樹在第 2 個位置，其值為 45。 ? heap = heapCreate(16,pareInt)。首先建立一個 heap 堆積，最大元素個數為 16，資料比較函式名稱為 pareInt。 測試程式 ? 上面說明的堆積結構宣告以及相關的函式存入 表頭檔備用。傳回 1 值。ReheapDown() 再堆下函式屬於遞迴函式，一層一層往下堆積，直到最後一個元素那一層時才停止。 ? return 1。 ? (heapsize)。 ? heapdata[0] = heapdata[heaplast]。 ? } 從堆積移除節(jié)點 ? int heapRemove(struct heapTag *heap, void **dataptr) ? { ? if (heapsize == 0) ? return 0。 ReheapUp (heap, parent)。 data[parent]=data[child]。 ?
教學課件相關推薦
鄂ICP備17016276號-1