【正文】 /*返回k的位置(或插入位置)*/}void Insert(BTNode *amp。 else { q=p。 /*初始化,t為待查樹,p指向待查結(jié)點(diǎn),q指向p的雙親*/int found=0,i=0。ipkeynum amp。 /*1..m,在結(jié)點(diǎn)中的關(guān)鍵字序號(hào)*/ int tag。typedef struct node //B樹結(jié)點(diǎn)定義{ int keynum。4．用戶手冊(cè)本程序在VC++，按照菜單提示的要求輸入即可。 顯示圖書狀態(tài)模塊 int i。q, int i)void Remove(BTNode *p,int i)void Successor(BTNode *p,int i)void MoveLeft(BTNode *p,int i)void MoveRight(BTNode *p,int i)void Combine(BTNode *p,int i)void Restore(BTNode *p,int i)int SearchNode(KeyType k,BTNode *p,int amp。主程序的流程圖如下：輸入i判斷i顯示圖書狀態(tài)刪除圖書記錄查找圖書借閱圖書讀取文件退出歸還圖書添加圖書作者總量現(xiàn)存量書號(hào)書名開始關(guān)閉 InsertBTreeInsert SplitNewRootSearchBTreeaddbookfindbookLendbookReturnbookBookcountexit menudelbookDeleteBTreeRecDeleteSearchNodeSuccessorRemoveRestoreMoveLeftCombineMoveRight 設(shè)計(jì)表示（1）函數(shù)調(diào)用關(guān)系圖（2）函數(shù)接口規(guī)格說明int Search(BTNode *p,KeyType k)Result SearchBTree(BTNode *amp。所以B樹的性能總是等價(jià)于二分查找（與M值無關(guān)），也就沒有B樹平衡的問題；因此，B樹是一種動(dòng)態(tài)查找效率較二叉排序樹更高的樹形結(jié)構(gòu)。要用B樹（4階樹）對(duì)書號(hào)建立索引，以獲得高效率。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。刪除圖書記錄：可根據(jù)提示輸入相應(yīng)的書號(hào)刪除圖書記錄。t, KeyType k, BTNode *amp。 刪除圖書記錄模塊 printf(請(qǐng)輸入書號(hào)) scanf(書號(hào)) if SearchBTree(書號(hào))=trueprintf(書的具體信息:書號(hào),書名,作者,現(xiàn)存量,總量) printf(輸入 1 刪除這本書) scanf() if(1) { 書號(hào)=0 printf(刪除成功!) } else printf(操作失敗!不存在這本書)return216。（2）算法的時(shí)間空間復(fù)雜度分析 由于B樹查找的時(shí)間復(fù)雜度為O（Log2N），而程序中多次用到了一重循環(huán)，其時(shí)間復(fù)雜度為O（n）,因此程序的時(shí)間復(fù)雜度為O（n），空間復(fù)雜度也為O（n）.（3）可改進(jìn)內(nèi)容：利用MFC做一個(gè)界面，使界面更加美觀；可嘗試用B+樹代替B_樹，更容易應(yīng)用于文件系統(tǒng)刪除圖書記錄的時(shí)候必須先收回所有的書，即要保證現(xiàn)存量和總量相等后方可刪除；采用文件的形式，可以保存圖書狀態(tài)。}。 /*指向找到的結(jié)點(diǎn)*/ int i。 for(i=0。若查找成功{ //則tag=1,指針pt所指結(jié)點(diǎn)中第i個(gè)關(guān)鍵字等于k；否則tag=0,等于k的 //關(guān)鍵字應(yīng)插入在指針Pt所指結(jié)點(diǎn)中第i和第i+1個(gè)關(guān)鍵字之間BTNode *p=t,*q=NULL。 pkey[i]==k) /*找到待查關(guān)鍵字*/ found=1。//pt指向q,tag置為0}return r。}qkey[i+1]=x。 /*生成新結(jié)點(diǎn)*ap*/apptr[0]=qptr[s]。 for (i=0。tptr[1]=ap。若引起 結(jié)點(diǎn)過大,則沿雙親鏈進(jìn)行必要的結(jié)點(diǎn)分裂調(diào)整,使t仍是m階t樹。 while (needNewRoot==0 amp。 i=Search(q, x)。}pkeynum。for (c=tkeynum。 /*將左兄弟中最后一個(gè)關(guān)鍵字移動(dòng)到雙親結(jié)點(diǎn)中*/pkey[i]=tkey[tkeynum]。tptr[tkeynum]=pptr[i]ptr[0]。 tptr[c]=tptr[c+1]。c=qkeynum。}pkeynum。else Combine(p,i)。 return(k==pkey[i])。 /*沿孩子結(jié)點(diǎn)遞歸查找并刪除關(guān)鍵字k*/ if (pptr[i]!=NULL) if (pptr[i]keynumMin) /*刪除后關(guān)鍵字個(gè)數(shù)小于MIN*/ Restore(p,i)。void addbook()//添加書{ int n=1,num。 scanf(%s,amp。 printf(\n總量:)。 if(booknumber==1) { printf(請(qǐng)輸入書號(hào):)。 } return。 } else printf(此書不存在.)。 printf(請(qǐng)輸入書號(hào):)。 return。 scanf(%d,amp。i1000。 switch(getch()) { case 39。 case 39。 case 39。 case 39。j10