數(shù)據(jù)結(jié)構(gòu)b樹的圖書管理系統(tǒng)(編輯修改稿)
2024-10-14 02:43 本頁面
【文章內(nèi)容簡介】 pt, i, tag // 若查找成功，則特征值 tag = 1，指針 pt 所指結(jié)點中第 i個關(guān)鍵字等于 K； // 否則特征值 tag = 0，等于 K 的關(guān)鍵字應(yīng)插入在指針 pt 所指結(jié)點中第 i和 // 第 i+1 個關(guān)鍵字之間 //順序查找 // 在結(jié)點 pkey[1..keynum]中查找 ,返回 i： pkey[i] = key pkey[i+1] int Search(BTree amp。p, KeyType key) { for (int i = 1。 i = pkeynum。 i++) { if (pkey[i] key) return i1。 } // for_i return pkeynum。 } // Search Result SearchBTree (BTree T, KeyType key) { BTree p = T, q = NULL。 bool flag = false。 int i = 0。 while (p amp。amp。 !flag) { i = Search (p, key)。 if (i 0 amp。amp。 pkey[i] == key) flag = true。 else { q = p。 p = pptr[i]。 } } // while return Result(flag ? p:q, i, flag)。 } // SearchBTree //2 B樹插入操作 // 關(guān)鍵字插入的位置必定在最下層的非葉結(jié)點，有下列幾種情況： // 1）插入后，該結(jié)點的關(guān)鍵字個數(shù) nm，不修改指針 。 // 2）插入后，該結(jié)點的關(guān)鍵字個數(shù) n=m， 則需進行結(jié)點分裂， // 令 s = m+1/2，在原結(jié)點中保留 ( A0, K1, …… , Ks1, As1 )； // (備注：這里的 (m+1)/2 = (m+1) 1 和 m+1 除以 2 上取整同值可證 ) // 新建結(jié)點 (As,Ks+1,…… , Kn, An ).將 ( Ks, p ) 插入雙親結(jié)點。 // 3）若雙親為空，則建新的根結(jié)點。 // 在 m 階 B樹 T 上結(jié)點 *q 的 key[i]與 key[i+1]之間插入關(guān)鍵字 K // 若因起節(jié)點過大，則眼雙親鏈進行必要的節(jié)點分裂調(diào)整 ,保持 T 的特性 //插入操作 // 將 x和 ap 分別插入到 qkey[i+1]和 qptr[i+1] // 這里涉及到數(shù)組元素的移 動的問題，因為這里也是順序結(jié)構(gòu)表示鍵值。 // 要插入到 pkey[i+1]我們必須對 i+1 之后的數(shù)進行后移，這也是采用 // 順序結(jié)構(gòu)的弊端 ,但是由于順序表很短，所以反而更高效。 void insert (BTree amp。p, int i, KeyType x, BTree ap) { 華東交通大學(xué) 08 級軟件工程（ 1）班 —— 張志福 6 for (int k = pkeynum + 1。 k i + 1。 k) { pkey[k] = pkey[k 1]。 pptr[k] = pptr[k 1]。 } // for_k pkey[i + 1] = x。 pptr[i + 1] = ap。 if (ap) apparent = p。 pkeynum++。 } // insert //分裂操作 // 將結(jié)點 p 分為兩個部分 [1..s1]和 [s..m].同時更新每部分 // 這里我們要考慮兩種情況， 2. 插入到父節(jié)點 void split (BTree amp。p, int s, BTree amp。ap) { ap = NULL。 ap = (BTNode *) malloc( sizeof(BTNode) )。 for (int i = s + 1, k = 0。 i = pkeynum。 i++) { apkey[++k] = pkey[i]。 apptr[k] = pptr[i]。 } // for_i apptr[0] = pptr[s]。 apkeynum = pkeynum s。 pkeynum = s 1。 apparent = pparent。 } // split //生成新根節(jié)點 // 這里要考慮兩種情況： // T 是空樹（參數(shù) q 初值為 NULL) 或者 根節(jié)點已分配為節(jié)點 *q 和 *ap // 生成含有信息（ T,x, ap)的新的根節(jié)點 *T, 原 T 和 ap 為子樹指針 void NewRoot (BTree amp。T, BTree amp。q, KeyType x, BTree amp。ap) { T = NULL。 T = (BTNode *) malloc ( sizeof(BTNode) )。 for (int i = 0。 i = m。 i++) Tptr[i] = NULL。 Tkey[1] = x。 Tkeynum = 1。 Tparent = NULL。 Tptr[0] = q。 Tptr[1] = ap。 if (q != NULL) qparent = T。 if (ap != NULL) { apparent = T。 for (int j = 0。 j = apkeynum。 j++) { if (apptr[j]) apptr[j]parent = ap。 } // for_j } // if } // NewRoot void InsertBTree (BTree amp。T, KeyType key, BTree q, int i) { KeyType x = key。 bool flag = false。 BTree ap = NULL, p = NULL。 while (q amp。amp。 !flag) { insert (q, i, x, ap)。 if (qkeynum m) flag = true。 else { int s = (m + 1) 1。 split(q, s, ap)。 x = qkey[s]。 p = q。 q = qparent。 if (q) i = Search(q, x)。 } //else } // while if (!flag) NewRoot(T, p, x, ap)。 } // InserBTree 華東交通大學(xué) 08 級軟件工程（ 1）班 —— 張志福 7 //B樹的刪除操作 /假若我們刪除關(guān)鍵字為非終端節(jié)點中的 Ki,則可以指針 Ai 所指子樹中的最小關(guān)鍵字 Y 代替 // Ki,然后在相應(yīng)的結(jié)點中刪去 Y. 下面我們討論刪除最下層非終端節(jié)點中的關(guān)鍵字的： // 1. 被刪除的關(guān)鍵字所在節(jié)點中的關(guān)鍵字的數(shù)目不小于 (m+1)/ // 該關(guān)鍵字和相應(yīng)的指針 Ai，樹的其它部分不變 // 2. 被刪除關(guān)鍵字所在節(jié)點中的關(guān)鍵字?jǐn)?shù)目等于 (m+1)/21,而該節(jié)點相 鄰的有兄弟 // 或左兄弟節(jié)點中的關(guān)鍵字的個數(shù)大于（ m+1)/2 1,則只需將其兄弟節(jié)點中最?。ɑ蜃畲螅? // 的關(guān)鍵字上移至雙親節(jié)點中，而將雙親節(jié)點中小于（或大于）且緊靠上移關(guān)鍵字的關(guān)鍵字 // 下移至被刪除關(guān)鍵字所在的節(jié)點中。 // 3. 被刪除關(guān)鍵字所在節(jié)點和其相鄰的兄弟節(jié)點中的關(guān)鍵字?jǐn)?shù)目均等與（ m+1)/ /設(shè)該節(jié)點有右兄弟，且其右兄弟節(jié)點地址有雙親節(jié)點中的指針 Ai
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1