西文圖書管理系統(tǒng)(編輯修改稿)
2025-05-05 03:49 本頁面
【文章內(nèi)容簡介】 /則tag=1,指針pt所指結(jié)點(diǎn)中第i個關(guān)鍵字等于k；否則tag=0,等于k的 //關(guān)鍵字應(yīng)插入在指針Pt所指結(jié)點(diǎn)中第i和第i+1個關(guān)鍵字之間BTNode *p=t,*q=NULL。 /*初始化,t為待查樹,p指向待查結(jié)點(diǎn),q指向p的雙親*/int found=0,i=0。//found為標(biāo)志位Result r。//創(chuàng)建查找結(jié)果類型結(jié)構(gòu)體rwhile (p!=NULL amp。amp。 found==0){ i=Search(p,k)。 /*在pkey[1..keynum]中查找i,使得pkey[i]=kpkey[i+1]*/ if (i0 amp。amp。 pkey[i]==k) /*找到待查關(guān)鍵字*/ found=1。 else { q=p。//雙親結(jié)點(diǎn)q指向p p=pptr[i]。//p變成它原來的孩子結(jié)點(diǎn) }}=i。//關(guān)鍵字序號iif (found==1) /*查找成功*/{ =p。=1。//pt指向找到的結(jié)點(diǎn)p,tag置為1}else /*查找不成功,返回K的插入位置信息*/{ =q。=0。//pt指向q,tag置為0}return r。 /*返回k的位置(或插入位置)*/}void Insert(BTNode *amp。q,int i,KeyType x,BTNode *amp。ap){ //若有位置,將x插入到qkey[i+1],ap插到qptr[i+1]中int j。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++。}void Split(BTNode *amp。q,BTNode *amp。ap){ //,前一半保留,后一半移入新生結(jié)點(diǎn)apint i,s=(m+1)/2。//分裂的位置ap=(BTNode *)malloc(sizeof(BTNode))。 /*生成新結(jié)點(diǎn)*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é)點(diǎn)的指針*/if (apptr[i]!=NULL) apptr[i]parent = ap。qkeynum=s1。 /*q的前一半保留,修改keynum*/}void NewRoot(BTNode *amp。t,BTNode *p,KeyType x,BTNode *ap)//生成含信息(T,x,ap)的新的根結(jié)點(diǎn)*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。}void InsertBTree(BTNode *amp。t, KeyType k, BTNode *amp。q, int i) { /**q的key[i]與key[i+1]之間插入關(guān)鍵字k。若引起 結(jié)點(diǎn)過大,則沿雙親鏈進(jìn)行必要的結(jié)點(diǎn)分裂調(diào)整,使t仍是m階t樹。*/BTNode *ap。int finished,needNewRoot,s。KeyType x。if (q==NULL) /*t是空樹(參數(shù)q初值為NULL)*/ NewRoot(t,NULL,k,NULL)。 //生成僅含關(guān)鍵字k的根結(jié)點(diǎn)*telse { x=k。ap=NULL。finished=needNewRoot=0。 while (needNewRoot==0 amp。amp。 finished==0) { Insert(q,i,x,ap)。 /*將x和ap分別插入到qkey[i+1]和qptr[i+1]*/ if (qkeynum=Max) finished=1。 /*無須分裂,插入完成*/ else { /*分裂結(jié)點(diǎn)*q,將qkey[s+1..m],qptr[s..m]和qrecptr[s+1..m]移入新結(jié)點(diǎn)*ap*/ s=(m+1)/2。 Split(q,ap)。 x=qkey[s]。 if (qparent) /*在雙親結(jié)點(diǎn)*q中查找x的插入位置*/ { q=qparent。 i=Search(q, x)。 } else needNewRoot=1。 } } if (needNewRoot==1) /*根結(jié)點(diǎn)已分裂為結(jié)點(diǎn)*q和*ap*/ NewRoot(t,q,x,ap)。 /*生成新根結(jié)點(diǎn)*t,q和ap為子樹指針*/}}void Remove(BTNode *p,int i)/*從*p結(jié)點(diǎn)刪除key[i]和它的孩子指針ptr[i]*/{int j。for (j=i+1。j=pkeynum。j++) /*前移刪除key[i]和ptr[i]*/{ pkey[j1]=pkey[j]。 pptr[j1]=pptr[j]。}pkeynum。}void Successor(BTNode *p,int i)/*查找被刪關(guān)鍵字pkey[i](在非葉子結(jié)點(diǎn)中)的替代葉子結(jié)點(diǎn)*/{BTNode *q。for (q=pptr[i]。qptr[0]!=NULL。q=qptr[0])。p
公司管理相關(guān)推薦
鄂ICP備17016276號-1