第八章堆積-文庫吧資料
2024-10-19 12:12本頁面
【正文】 parent = (child 1)/ 2。 ? void **data, **temp。 ? return 1。 ? heapdata[heaplast] = dataptr。 ? ++(heaplast)。 ? return 1。 ? heaplast = 0。首先取得一塊 heapTag 結(jié)構(gòu)的 heap 記憶體，設(shè)定 heaplast 為 1， heapsize 為 0， heapmazsize 最大容量為 2 的 log10(maxsize)/log10(2) 次方值再減一，例如 mazsize 引數(shù)值為 16，那麼 heapmaxsize 的值為 2 的 4 次方再減一，為 7。 ? return heap。 ? heapmaxsize = (int)pow(2,ceil(log2(maxsize)))1。 ? heapsize = 0。 ? if (heap == NULL) ? return NULL。 ? struct heapTag *heapCreate(int maxsize, ? int (*pare) (void *arg1, void *arg2)) ? { ? struct heapTag *heap。 data指標(biāo)變數(shù)的含意 ? 這種結(jié)構(gòu)就命名為 heapTag 結(jié)構(gòu)。 ? int maxsize。 ? int size。 堆積結(jié)構(gòu) ? struct heapTag ? { ? void **data。 ? 3. 總共有 7 個(gè)元素（ n=7），第一個(gè)葉節(jié)點(diǎn)為 7/2 整數(shù)部份為 3。 堆積以樹及陣列表示 ? 1. 33 的註標(biāo)為 2（從 0算起），左子女節(jié)點(diǎn) 24 註標(biāo) 為 2*2+1=5，右子女節(jié)點(diǎn) 20 註標(biāo)為 2*2+2=6。 ? 4. 設(shè)完整堆積元素?cái)?shù)為 n，第一個(gè)葉節(jié)點(diǎn)為 (n/2) 之整數(shù)部份。 ? 3. 左子女節(jié)點(diǎn)註標(biāo)為 j，右子女節(jié)點(diǎn)註標(biāo)為 j+1。 堆積實(shí)作 ? 雖然堆積可以透過動(dòng)態(tài)樹結(jié)構(gòu)建立起來，但最常見的還是以陣列實(shí)作為宜。 再堆下作業(yè) ? 再堆下作業(yè)事實(shí)上是再堆上的相反操作。 26再往上移動(dòng) ? 26 比它的父母節(jié)點(diǎn) 43 還小，就不必再移動(dòng)，已經(jīng)定到正確的位置了。最後的元素規(guī)定要擺在最右邊的。再堆上作業(yè)將第 N 個(gè)元素往上堆，定位於正確的位置，使整個(gè)結(jié)構(gòu)成為一個(gè)堆積。要實(shí)作堆積的插入及移除節(jié)點(diǎn)操作，我們需要兩個(gè)演算法， 再堆上 （ reheap up）以及 再堆下 （ reheap down）。 堆積有兩個(gè)基本的操作 ? 對於堆積有兩個(gè)基本的操作： 插入一個(gè)節(jié)點(diǎn) 以及 移除一個(gè)節(jié)點(diǎn) 。 三種堆積舉例 ? 在上圖的兄弟節(jié)點(diǎn)裡，左節(jié)點(diǎn)有大於右節(jié)點(diǎn)者（ 139），左節(jié)點(diǎn)有小於右節(jié)點(diǎn)者（ 711， 1924），這對於前面章節(jié)說明過的二元搜尋樹是不允許的。 ? 一棵完整的二元樹是每一層次（ level）都佔(zhàn)滿，一棵接近完整的二元樹指其葉節(jié)點(diǎn)相差在一個(gè)層次以內(nèi)。 基本觀念 ? 一棵堆積是一棵二元樹，俱備下列的特性： ? 1. 這棵樹是一棵完整或接近完整的二元樹。 ? 若父母節(jié)點(diǎn)的 註標(biāo) i 從 1 開始 計(jì)數(shù)時(shí)，則左子樹節(jié)點(diǎn)的註標(biāo)為 2*i，右子樹節(jié)點(diǎn)的註標(biāo)為 2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1