西文图书管理系统代码整合

#includestdio.h#includemalloc.h#includeiostream.h#includestring.h#includestdlib.htypedefstruct{intbooknum;charbookname[20];charwriter[20];inttotal;//书的库存intflag;//用以计算是否借出的标志}Book;typedefBookKeyType;#definem4///////////////////////////////////////////B-Tree模块////////////////////////////////////typedefstructBTNode{intkeynum;//结点中关键字的个数；structBTNode*parent;//结点的双亲结点；KeyTypekey[m+1];//结点中的关键字structBTNode*ptr[m+1];//孩子结点数组}BTNode,*BTree;//B_树结构体typedefstruct{BTNode*pt;//指向找到结点的指针inti;//在结点中的关键字序号inttag;//标志查找成功（=1）或失败（=0）}Result;//用以记录结果的结构体//设结点中的指针向量为空voidSetNull(BTree&p){inti=0;while(i=p-keynum){p-ptr[i]=NULL;i++;}}//在结点中查找关键字intsearchNode(BTreep,KeyType*k){inti=1;while(i=p-keynum){if(k-booknump-key[i].booknum)returni-1;i++;}returni-1;}//在B树中查找关键字ResultsearchBTree(BTreet,KeyType*k){BTreep=t,q=NULL;intfound=0;inti=0;Resultresult;while(p&&!found){i=searchNode(p,k);if(i0&&p-key[i].booknum==k-booknum)found=1;else{q=p;p=p-ptr[i];}}if(found){result.pt=p;result.i=i;result.tag=1;}else{result.pt=q;result.i=i;result.tag=0;}returnresult;}//赋值函数voidcpy(KeyType*p,KeyType*q){p-total=q-total;strcpy(p-writer,q-writer);p-booknum=q-booknum;strcpy(p-bookname,q-bookname);p-flag=q-flag;}//在结点中插入新的关键字k和指针ptvoidInsertInNode(BTree&q,inti,KeyType*k,BTreept){intj;for(j=q-keynum;ji;j--)cpy(&(q-key[j+1]),&(q-key[j]));cpy(&(q-key[j+1]),k);for(j=q-keynum;ji;j--)q-ptr[j+1]=q-ptr[j];q-ptr[j+1]=pt;if(pt){pt-parent=q;}q-keynum++;}voidInsert(BTNode*&q,inti,KeyTypex,BTNode*&ap)//将x和ap分别插入到q-key[i+1]和q-ptr[i+1]中{intj;for(j=q-keynum;ji;j--)//空出一个位置{q-key[j+1]=q-key[j];q-ptr[j+1]=q-ptr[j];}q-key[i+1]=x;q-ptr[i+1]=ap;if(ap!=NULL)ap-parent=q;q-keynum++;}//分裂结点pvoidSplit(BTreep,BTree&q){ints=m%2==0?m/2-1:m/2,i,j=0,t;p-keynum=s;q=(BTree)malloc(sizeof(BTNode));SetNull(q);for(i=s+2;i=m;i++){q-ptr[j]=p-ptr[i-1];cpy(&(q-key[++j]),&(p-key[i]));}q-ptr[j]=p-ptr[i-1];q-keynum=j;for(t=s+1;t=m;t++){if(p-ptr[t]!=NULL)p-ptr[t]-parent=q;}}voidNewRoot(BTNode*&t,BTNode*p,KeyTypex,BTNode*ap)//生成含信息(T,x,ap)的新的根结点*t,原t和ap为子树指针{t=(BTNode*)malloc(sizeof(BTNode));t-keynum=1;t-ptr[0]=p;t-ptr[1]=ap;t-key[1]=x;if(p!=NULL)p-parent=t;if(ap!=NULL)ap-parent=t;t-parent=NULL;}voidInsertBTree(BTNode*&t,KeyTypek,BTNode*&q,inti)//在m阶t树t上结点*q的key[i]与key[i+1]之间插入关键字k。若引起结点过大,则沿双亲链进行必要的结点分裂调整,使t仍是m阶t树。{BTNode*ap;intfinished,needNewRoot,s;KeyTypex;if(q==NULL)//t是空树(参数q初值为NULL)NewRoot(t,NULL,k,NULL);//生成仅含关键字k的根结点*telse{x=k;ap=NULL;finished=needNewRoot=0;while(needNewRoot==0&&finished==0){Insert(q,i,x,ap);//将x和ap分别插入到q-key[i+1]和q-ptr[i+1]if(q-keynum=m)finished=1;/*插入完成*/else{//分裂结点*q,将q-key[s+1..m],q-ptr[s..m]和q-recptr[s+1..m]移入新结点*aps=(m+1)/2;Split(q,ap);x=q-key[s];if(q-parent)//在双亲结点*q中查找x的插入位置{q=q-parent;//i=Search(q,x);}elseneedNewRoot=1;}}if(needNewRoot==1)//根结点已分裂为结点*q和*apNewRoot(t,q,x,ap);//生成新根结点*t,q和ap为子树指针}}voidSuccessor(BTNode*p,inti)//查找被删关键字p-key[i](在非叶子结点中)的替代叶子结点{BTNode*q;for(q=p-ptr[i];q-ptr[0]!=NULL;q=q-ptr[0]);p-key[i]=q-key[1];//复制关键字值}voidRemove(BTNode*p,inti)//查找被删关键字p-key[i]{BTNode*q;for(q=p-ptr[i];q-ptr[0]!=NULL;q=q-ptr[0]);}voidMoveRight(BTNode*p,inti)//把一个关键字移动到右兄弟中{intc;BTNode*t=p-ptr[i];for(c=t-keynum;c0;c--)//将右兄弟中所有关键字移动一位{t-key[c+1]=t-key[c];t-ptr[c+1]=t-ptr[c];}t-ptr[1]=t-ptr[0];//从双亲结点移动关键字到右兄弟中t-keynum++;t-key[1]=p-key[i];t=p-ptr[i-1];//将左兄弟中最后一个关键字移动到双亲结点中p-key[i]=t-key[t-keynum];p-ptr[i]-ptr[0]=t-ptr[t-keynum];t-keynum--;}voidMoveLeft(BTNode*p,inti)//把一个关键字移动到左兄弟中{intc;BTNode*t;t=p-ptr[i-1];//把双亲结点中的关键字移动到左兄弟中t-keynum++;t-key[t-keynum]=p-key[i];t-ptr[t-keynum]=p-ptr[i]-ptr[0];t=p-ptr[i];//把右兄弟中的关键字移动到双亲兄弟中p-key[i]=t-key[1];p-ptr[0]=t-ptr[1];t-keynum--;for(c=1;c=t-keynum;c++)//将右兄弟中所有关键字移动一位{t-key[c]=t-key[c+1];t-ptr[c]=t-ptr[c+1];}}voidCombine(BTNode*p,inti)//将三个结点合并到一个结点中{intc;BTNode*q=p-ptr[i];//指向右结点,它将被置空和删除BTNode*l=p-ptr[i-1];l-keynum++;//l指向左结点l-key[l-keynum]=p-key[i];l-ptr[l-keynum]=q-ptr[0];for(c=1;c=q-keynum;c++)//插入右结点中的所有关键字{l-keynum++;l-key[l-keynum]=q-key[c];l-ptr[l-keynum]=q-ptr[c];}for(c=i;cp-keynum;c++)//删除父结点所有的关键字{p-key[c]=p-key[c+1];p-ptr[c]=p-ptr[c+1];}p-keynum--;free(q);//释放空右结点的空间}voidRestore(BTNode*p,inti)//关键字删除后,调整B-树,找到一个关键字将其插入到p-ptr[i]中{if(i==0)//为最左边关键字的情况if(p-ptr[1]-keynum0)MoveLeft(p,1);elseCombine(p,1);elseif(i==p-keynum)//为最右边关键字的情况if(p-ptr[i-1]-keynum0)MoveRight(p,i);elseCombine(p,i);elseif(p-ptr[i-1]-keynum0)//为其他情况MoveRight(p,i);elseif(p-ptr[i+1]-keynum0)MoveLeft(p,i+1);elseCombine(p,i);}intSearchNode(KeyTypek,BTNode*p,int&i)//在结点p中找关键字为k的位置i,成功时返回1,否则返回0{if(k.booknump-key[1].booknum)//k小于*p结点的最小关键字时返回0{i=0;return0;}else//在*p结点中查找{i=p-keynum;while(k.booknump-key[i].booknum&&i1)i--;return(k.booknum==p-key[i].booknum);}}intRecDelete(KeyTypek,BTNode*p)//查找并删除关键字k{inti;intfound;if(p==NULL)return0;else{if((found=SearchNode(k,p,i))==1)//查找关键字k{if(p-ptr[i-1]!=NULL)//若为非叶子结点{Successor(p,i);//由其后继代替它RecDelete(p-key[i],p-ptr[i]);//p-key[i]在叶子结