【文章內(nèi)容簡介】 字個數(shù) struct BTNode *parent。 //父親指針 KeyType key[m+1]。 //關(guān)鍵字?jǐn)?shù)組， 0 號單元未用 struct BTNode *ptr[m+1]。 //子數(shù)指針 Record *rec[m+1]。 //記錄指針， 0 號單元未用 }BTNode,*BTree。 //B 樹節(jié)點類型和 B 樹類型 typedef struct { BTNode *pt。 //指向找到的結(jié)點或應(yīng)該插入的結(jié)點 int i。 //關(guān)鍵字序號 int tag。 //1 表示查找成功， 0 表示查找失敗 }Result。 //B 樹查找結(jié)果類型 B 樹基本操作 ： Reselt SearchBTree(BTree T,KeyType k) //在 m 階 B 樹上查找關(guān)鍵字 k，返回結(jié)果（ 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)鍵字之間。 Status InsertBTree(BTree amp。T, KeyType k, BTree q, int i,Record *rec) //在 m 階 B 樹 T 上結(jié)點 *q 的 key[i]與 key[i+1]之間插入關(guān)鍵字 k，和記錄 rec //若引起結(jié)點過大，則沿著雙親鏈進(jìn)行必要的結(jié)點分裂調(diào)整，使 T 仍是 m 階 B 樹 Status DeleteBTree(BTree amp。T,KeyType k) //在 m 階 B 樹 T 上刪除關(guān)鍵字 k 及其對應(yīng)記錄，并返回 OK //如 T 上不存在關(guān)鍵字 k，則返回 ERROR void BTreeTraverse(BTree T,void (*Visi)t(BTree p)) //遍歷 B 樹 T，對每個結(jié)點調(diào)用 Visit 函數(shù) void ShowBTree(BTree T,short x = 8) //遞歸以凹入表形式顯示 B 樹 T,每層的縮進(jìn)量為 x，初始縮進(jìn)量為 x=8 B 樹的 基本 操作偽代碼： Result SearchBTree(BTree T, KeyType k) //在 m 階 B 樹上查找關(guān)鍵字 k，返回結(jié)果（ 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)鍵字之間。 { p = T, q = NULL。 //初始化， p 指向待查結(jié)點， q 指向 p 的雙親 found = FALSE。 3681bd1c2b9ef87aa40ba80437378615 第 9 頁 共 31 頁 while(p amp。amp。 !found) { i = Search(p, k)。 //查找 k 的位置使 pkey[i]=kpkey[i+1] if(i 0 amp。amp。 k == pkey[i]) found = TRUE。 else{ //未找到，則查找下一層 q = p。 p = pptr[i]。 } } if(found) return {p, i, 1}。 //查找成功 else return {q, i, 0}。 //查找不成功，返回 k 的插入位置信息 } Status InsertBTree(BTree amp。T, KeyType k, BTree q, int i,Record *rec) //在 m 階 B 樹 T 上結(jié)點 *q 的 key[i]與 key[i+1]之間插入關(guān)鍵字 k，和記錄 rec //若引起結(jié)點過大，則沿著雙親鏈進(jìn)行必要的結(jié)點分裂調(diào)整，使 T 仍是 m 階 B 樹 { ap = NULL。 finished = FALSE。 if (!q) NewRoot(T, NULL, k, NULL,rec)。 //T 是空樹，生成僅含關(guān)鍵字 K 的根結(jié)點 *T else{ while (!finished) { Insert(q, i, k, ap,rec)。 //將 k 和 ap 分別插入到 qkey[i+1]和 qptr[i+1] if (qkeynum m) finished = TRUE。 //插入完成 else{ Split(q, (m+1)/2, ap)。 //分裂結(jié)點 Q k = qkey[(m+1)/2]。 rec = qrec[(m+1)/2]。 if (qparent) { // 在雙親結(jié)點 *q 中查找 k 的插入位置 q = qparent。 i = Search(q, k)。 } else finished = OVERFLOW。 //根節(jié)點已分裂為 *q 和 *ap 兩個結(jié)點 } } if (finished == OVERFLOW) //根結(jié)點已分裂為結(jié)點 *q 和 *ap NewRoot(T, q, k, ap,rec)。 //需生成新根結(jié)點 *T,q 和 ap 為子樹指針 } return OK。 } StatusDeleteBTree(BTree amp。T,KeyType k) //在 m 階 B 樹 T 上刪除關(guān)鍵字 k 及其對應(yīng)記錄，并返回 OK //如 T 上不存在關(guān)鍵字 k，則返回 ERROR { 3681bd1c2b9ef87aa40ba80437378615 第 10 頁 共 31 頁 q,b = NULL。 finished = FALSE,i = 1。 Result res = SearchBTree(T,k)。 //在 T 中查找關(guān)鍵字 k if( == 0 ) return ERROR。 //未搜索到 else { q = 。 //q 指向待刪結(jié)點 i = 。 if(qptr[0]) TakePlace(q, i)。 //若 q 的子樹不空， (非底層結(jié)點 ) //則以其后繼代之，且令 q 指向后繼所在結(jié)點 Del(q,i)。 //刪除 q 所指向結(jié)點中第 i個關(guān)鍵字及記錄 if(qkeynum=(m1)/2||!qparent) //若刪除后關(guān)鍵字個數(shù)不小于 (m1)/2 或 q 是根節(jié)點 { finished = TRUE。 //刪除完成 if(qkeynum == 0 ) T = NULL。 //若 q 的關(guān)鍵字個數(shù)為 0 ，則為空樹 } while(!finished) { if(Borrow(q)) finished = TRUE。 //若 q 的相鄰兄弟結(jié)點關(guān)鍵字大于 (m1)/2,則從該 //兄弟結(jié)點上移一個最大（或最小）關(guān)鍵字到 //父節(jié)點，從父節(jié)點借一關(guān)鍵字到 q else{ //若 q 相鄰兄弟關(guān)鍵字個數(shù)均等于┌ m /2┑ 1 Combine(q)。 //將 q 中的剩余部分和雙親中的相關(guān)關(guān)鍵字合并至 q 的一個兄弟中 q = qparent。 //檢查雙親 if(q == T amp。amp。 Tkeynum ==0 ) //若被刪結(jié)點的父節(jié)點是根 T 且 T 的關(guān)鍵字個數(shù)為 0 { T = Tptr[0]。 //新根 Tparent = NULL。 free(q)。 //刪除原雙親結(jié)點 finished = TRUE。 } else if(qkeynum = m/2) finished = TRUE。 } //合并后雙親關(guān)鍵字個數(shù)不少于 (m1)/2，完成 } } return OK 。 } void BTreeTraverse(BTree T,void ( *Visit)(BTree p)) //遍歷 B 樹 T，對每個結(jié)點調(diào)用 Visit 函數(shù) { if(!T) return 。 Visit(T)。 for(i = 0 。i = Tkeynum。 i++) //遞歸遍歷子樹結(jié)點 if(Tptr[i]) BTreeTraverse(Tptr[i],Visit)。 } 3681bd1c2b9ef87aa40ba80437378615 第 11 頁 共 31 頁 void ShowBTree(BTree T,short x = 8) //遞歸以凹入表形式顯示 B 樹 T,每層的縮進(jìn)量為 x，初始縮進(jìn)量為 x=8 { if(!T) return 。 for(i = 0。i=x。i++) putchar(39。 39。)。 //縮進(jìn) x for(i = 1 。i = Tkeynum。i++) printf(%d,Tkey[i])。 for(i = 0 。i = Tkeynum。i++) //遞歸顯示子樹結(jié)點關(guān)鍵字 ShowBTree(Tptr[i],x+7)。 } 4. 主函數(shù)和其他函數(shù)的偽碼算法 int main() { RecordLogs(0)。 //記錄日志 進(jìn)入系統(tǒng) 顯示歡迎界面 InitLibrary(L)。 //初始化書庫 L while(1) { 顯示菜單； 1 新書入庫， 2 清除庫存， 3 圖書出借 4 圖書歸還 5 圖書預(yù)約， 6 列出著者著作 7 查看圖書狀態(tài) 8 遍歷書庫， 9 退出系統(tǒng) cmd = getch()。