西文圖書管理系統(tǒng)(編輯修改稿)
2025-05-05 03:32 本頁面
【文章內(nèi)容簡介】 階B樹,為全局變量*/intMax。 /*m階B樹中每個結(jié)點的至多關(guān)鍵字個數(shù),Max=m1*/intMin。 /*m階B樹中非葉子結(jié)點的至少關(guān)鍵字個數(shù),Min=(m1)/2*/Results。intSearch(BTNode*p,KeyTypek){//在pkey[1..keynum]中查找關(guān)鍵字序號i,使得pkey[i]=kpkey[i+1]inti。for(i=0。ipkeynumamp。amp。pkey[i+1]=k。i++)returni。}ResultSearchBTree(BTNode*amp。t,KeyTypek)//在m階t樹t上查找關(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)鍵字之間BTNode*p=t,*q=NULL。/*初始化,t為待查樹,p指向待查結(jié)點,q指向p的雙親*/intfound=0,i=0。//found為標(biāo)志位Resultr。//創(chuàng)建查找結(jié)果類型結(jié)構(gòu)體rwhile(p!=NULLamp。amp。found==0){i=Search(p,k)。 /*在pkey[1..keynum]中查找i,使得pkey[i]=kpkey[i+1]*/if(i0amp。amp。pkey[i]==k)/*找到待查關(guān)鍵字*/found=1。else{q=p。//雙親結(jié)點q指向pp=pptr[i]。//p變成它原來的孩子結(jié)點}}=i。//關(guān)鍵字序號iif(found==1) /*查找成功*/{=p。=1。//pt指向找到的結(jié)點p,tag置為1}else /*查找不成功,返回K的插入位置信息*/{=q。=0。//pt指向q,tag置為0}returnr。 /*返回k的位置(或插入位置)*/}voidInsert(BTNode*amp。q,inti,KeyTypex,BTNode*amp。ap){//若有位置,將x插入到qkey[i+1],ap插到qptr[i+1]中intj。for(j=qkeynum。ji。j)/*空出一個位置*/{qkey[j+1]=qkey[j]。qptr[j+1]=qptr[j]。}qkey[i+1]=x。qptr[i+1]=ap。if(ap!=NULL)apparent=q。qkeynum++。}voidSplit(BTNode*amp。q,BTNode*amp。ap){//q分裂成兩個結(jié)點,前一半保留,后一半移入新生結(jié)點apinti,s=(m+1)/2。//分裂的位置ap=(BTNode*)malloc(sizeof(BTNode))。/*生成新結(jié)點*ap*/apptr[0]=qptr[s]。 /*后一半移入ap*/for(i=s+1。i=m。i++){apkey[is]=qkey[i]。apptr[is]=qptr[i]。if(apptr[is]!=NULL)apptr[is]parent=ap。}apkeynum=qkeynums。apparent=qparent。for(i=0。i=qkeynums。i++)/*修改指向雙親結(jié)點的指針*/if(apptr[i]!=NULL)apptr[i]parent=ap。qkeynum=s1。 /*q的前一半保留,修改keynum*/}voidNewRoot(BTNode*amp。t,BTNode*p,KeyTypex,BTNode*ap)//生成含信息(T,x,ap)的新的根結(jié)點*t,//原t和ap為子樹指針{t=(BTNode*)malloc(sizeof(BTNode))。tkeynum=1。tptr[0]=p。tptr[1]=ap。tkey[1]=x。if(p!=NULL)pparent=t。if(ap!=NULL)apparent=t。tparent=NULL。}voidInsertBTree(BTNode*amp。t,KeyTypek,BTNode*amp。q,inti){/*m階t樹t上結(jié)點*q的key[i]與key[i+1]之間插入關(guān)鍵字k。若引起結(jié)點過大,則沿雙親鏈進(jìn)行必要的結(jié)點分裂調(diào)整,使t仍是m階t樹。*/BTNode*ap。intfinished,needNewRoot,s。KeyTypex。if(q==NULL) /*t是空樹(參數(shù)q初值為NULL)*/NewRoot(t,NULL,k,NULL)。 //生成僅含關(guān)鍵字k的根結(jié)點*telse{x=k。ap=NULL。finished=needNewRoot=0。while(needNewRoot==0amp。amp。finished==0){Insert(q,i,x,ap)。 /*將x和ap分別插入到qkey[i+1]和qptr[i+1]*/if(qkeynum=Max)finished=1。/*無須分裂,插入完成*/else{/*分裂結(jié)點*q,將qkey[s+1..m],qptr[s..m]和qrecptr[s+1..m]移入新結(jié)點*ap*/s=(m+1)/2。Split(q,ap)。x=qkey[s]。if(qparent) /*在雙親結(jié)點*q中查找x的插入位置*/{q=qparent
公司管理相關(guān)推薦
鄂ICP備17016276號-1