【正文】 維數(shù)組 books 數(shù)組中。 //現(xiàn)存量大于 0，不可出借 GetDate(Rbespeakdate)。 //無人預約則登記預約者 信息 else{ for( pre = r = Bbespeaker。 pre = r, r = rnextb) if(rcardnum == Rcardnum) return ERROR。 //否則登記預約信息 } return OK。 //搜索 booknum if(!) return ERROR。 SortBorrower(B)。 //對預約者鏈表按日期遲到早排序 PrintBook(B)。 //顯示借閱名單 PrintBespeaker(B)。 } void PrintAll(BTree p) //顯示 B 樹結(jié)點 p 所有記錄 { for(i = 1 。i++) PrintD(prec[i])。 //遍歷 B 樹，顯示所有圖書信息 PrintT()。 //記錄指針為圖書結(jié)點類型 typedef int KeyType。 //每個結(jié)點關(guān)鍵字個數(shù) struct BTNode *parent。 //關(guān)鍵字數(shù)組， 0 號單元未用 struct BTNode *ptr[m+1]。 //記錄指針， 0 號單元未用 }BTNode,*BTree。 //指向找到的結(jié)點或應該插入的結(jié)點 int i。 //1 表示查找成功， 0 表示查找失敗 }Result。若查找成功，則特征值 tag=1，指針 pt //所指結(jié)點中第 i個關(guān)鍵字等于 k；否則返回特征值 tag=0，等于 k 的關(guān)鍵字應插入在 pt 所指結(jié)點 //中第 i和第 i+1 個關(guān)鍵字之間。T, KeyType k, BTree q, int i,Record *rec) //在 m 階 B 樹 T 上結(jié)點 *q 的 key[i]與 key[i+1]之間插入關(guān)鍵字 k，和記錄 rec //若引起結(jié)點過大，則沿著雙親鏈進行必要的結(jié)點分裂調(diào)整，使 T 仍是 m 階 B 樹 Status DeleteBTree(BTree amp。若查找成功，則特征值 tag=1，指針 pt //所指結(jié)點中第 i個關(guān)鍵字等于 k；否則返回特征值 tag=0，等于 k 的關(guān)鍵字應插入在 pt 所指結(jié)點 //中第 i和第 i+1 個關(guān)鍵字之間。 //初始化， p 指向待查結(jié)點， q 指向 p 的雙親 found = FALSE。amp。 //查找 k 的位置使 pkey[i]=kpkey[i+1] if(i 0 amp。 k == pkey[i]) found = TRUE。 p = pptr[i]。 //查找成功 else return {q, i, 0}。T, KeyType k, BTree q, int i,Record *rec) //在 m 階 B 樹 T 上結(jié)點 *q 的 key[i]與 key[i+1]之間插入關(guān)鍵字 k，和記錄 rec //若引起結(jié)點過大，則沿著雙親鏈進行必要的結(jié)點分裂調(diào)整，使 T 仍是 m 階 B 樹 { ap = NULL。 if (!q) NewRoot(T, NULL, k, NULL,rec)。 //將 k 和 ap 分別插入到 qkey[i+1]和 qptr[i+1] if (qkeynum m) finished = TRUE。 //分裂結(jié)點 Q k = qkey[(m+1)/2]。 if (qparent) { // 在雙親結(jié)點 *q 中查找 k 的插入位置 q = qparent。 } else finished = OVERFLOW。 //需生成新根結(jié)點 *T,q 和 ap 為子樹指針 } return OK。T,KeyType k) //在 m 階 B 樹 T 上刪除關(guān)鍵字 k 及其對應記錄，并返回 OK //如 T 上不存在關(guān)鍵字 k，則返回 ERROR { 3681bd1c2b9ef87aa40ba80437378615 第 10 頁 共 31 頁 q,b = NULL。 Result res = SearchBTree(T,k)。 //未搜索到 else { q = 。 if(qptr[0]) TakePlace(q, i)。 //刪除 q 所指向結(jié)點中第 i個關(guān)鍵字及記錄 if(qkeynum=(m1)/2||!qparent) //若刪除后關(guān)鍵字個數(shù)不小于 (m1)/2 或 q 是根節(jié)點 { finished = TRUE。 //若 q 的關(guān)鍵字個數(shù)為 0 ，則為空樹 } while(!finished) { if(Borrow(q)) finished = TRUE。 //將 q 中的剩余部分和雙親中的相關(guān)關(guān)鍵字合并至 q 的一個兄弟中 q = qparent。amp。 //新根 Tparent = NULL。 //刪除原雙親結(jié)點 finished = TRUE。 } //合并后雙親關(guān)鍵字個數(shù)不少于 (m1)/2，完成 } } return OK 。 Visit(T)。i = Tkeynum。 } 3681bd1c2b9ef87aa40ba80437378615 第 11 頁 共 31 頁 void ShowBTree(BTree T,short x = 8) //遞歸以凹入表形式顯示 B 樹 T,每層的縮進量為 x，初始縮進量為 x=8 { if(!T) return 。i=x。 39。 //縮進 x for(i = 1 。i++) printf(%d,Tkey[i])。i = Tkeynum。 } 4. 主函數(shù)和其他函數(shù)的偽碼算法 int main() { RecordLogs(0)。 //初始化書庫 L while(1) { 顯示菜單； 1 新書入庫， 2 清除庫存， 3 圖書出借 4 圖書歸還 5 圖書預約， 6 列出著者著作 7 查看圖書狀態(tài) 8 遍歷書庫， 9 退出系統(tǒng) cmd = getch()。Bbooknum,amp。Bwriter,amp。Bpublishyear, amp。 res = SearchBTree(L,Bbooknum)。 記錄日志； case 2: scanf(amp。 DeleteBook(L,booknum)。booknum)。R)。 記錄日志； case 4: scanf(amp。cardnum)。 記錄日志； case 5: scanf(amp。 3681bd1c2b9ef87aa40ba80437378615 第 12 頁 共 31 頁 if(能夠預約 ) scanf(amp。//讀入借閱者信息 case 6: scanf(amp。 ListAuthor(L)。booknum)。ShowBookinfo(L,booknum)。 //顯示所有圖書基本信息 case 9: 提示是否確認退出， 確認則 exit(0)。 } } void AddDate(tm amp。 = ( + (day / 30)) % 12。 } StatusEarlier(tm date1,tm date2) //比較 data1 與 date2 日期的遲與早，如果 date1 早于或等于 date2 則返回 TRUE，否則返回 FALSE。 if( ) return ERROR。 if( ) return ERROR。 return ERROR。 secc 為 1 代表操作成功，為 0 代表操作失敗 //根據(jù) op 不同的操作，把操作記錄到日志文件 logfile 中 { char s[][6] = {失敗 ,成功 }。 //操作名字符串 logfp = fopen(logfile,a+))) //打開日志文件 GetDate(date)。 //記錄當前時間 switch(op) 3681bd1c2b9ef87aa40ba80437378615 第 13 頁 共 31 頁 { //fprintf(logfp,”%s,%s”,opera[op],s[succ])。 //關(guān)閉日志文件 } 5. 函數(shù)調(diào)用關(guān)系圖 四、 調(diào)試分析 1. 調(diào)試過程中遇到的問題以及對設計與實現(xiàn)的回顧討論和分析 本次設計比較難的部分是 B樹的操作，雖然書中給出查找和插入偽代碼，但編碼過程仍出現(xiàn) 不少問題。 (2) 刪除關(guān)鍵字時，要把對應的記錄刪除，但本次設計只是覆蓋記錄指針，未釋放對應記錄的空間，有 待改進。應該每次 父 節(jié)點改變后 刷新一次。 (5) 本次設計的預約功能寫的不是很完善，只能登記預約信息，判斷預約是否無效等。 而且入庫、借書前，還要先搜索 B 樹。 2． 算法的時空分析 和改進設想 設 B 樹的階為 m， （書號） 關(guān)鍵字個數(shù)為 N (1) SearchBTree 最好情況為 O(1),最壞時 比較的結(jié)點數(shù)不超過 log[m/2]((N+1)/2)+1； 3681bd1c2b9ef87aa40ba80437378615 第 14 頁 共 31 頁 (2) 因為 B 樹總是在最后一層插入，因此 InsertBTree 操作比較的結(jié)點數(shù)也不超過 log[m/2]((N+1)/2)+1， (3) DeleteBTree 最好情況為被刪關(guān)鍵字在最下層結(jié)點而且刪除后該結(jié)點關(guān)鍵字個數(shù)不小于 m/2， 時間復 雜度 O(1)； 最壞情況 為刪除后 需要合并 父節(jié)點直到 到根節(jié)點，需比較 2 *（ log[m/2