数据结构_图书馆管理系统实验报告.doc

实验报告题目：图书管理一， 需求分析1.每种书的信息包括了书号书名，作者显存量和总库存等。2.要实现的主要操作有，在B-树上的插入删除操作，并且在这些B-树的操作的基础上的图书馆借阅归还入库清除等操作。3.每插入或删除一个关键字后就要显示B-树的状态。也可以显示图书的相关借阅的信息。4.借阅的信息链接在相应的那种数的记录之后。2.两种抽象数据类型：Btree和Library。3. 测试数据 入库书号：35，16，18，70，5，50，22，60，13，17，12，45，25，42，15然后清除：45， 50，22，42，90二概要设计ADT BTree数据对象：D=ai |ai E BTNode,I=2,3,n,n=0数据关系：R1=|ai-1,ai E D, I=2,3N基本操作：void InitBTree(BTree &T);int Search(BTree p,int k);Result SearchBTree(BTree T,int k);void split(BTree &q,int s,BTree &ap);void Insert(BTree &q,int i,KeyType x,BTree ap);void NewRoot(BTree &T,BTree q,KeyType x,BTree ap);Status InsertBTree(BTree &T,KeyType k,BTree q,int i);void FindSmallest(BTree p,BTree &q);int Parent(BTree p);void RightBrother(BTree p,BTree &right);void LeftBrother(BTree p,BTree &left);void LeftMove(BTree &p,int loc);Status DeleteBTree(BTree &T,int k);void PrintBTree(BTree T);ADT Library数据对象：D=ai |ai E RecordI=2,3,n,n=0数据关系：R1=|ai-1,ai E D, I=2,3N基本操作：void GetInformation(Record &book);void PrintBookInfomation(Record *book);void Procurement(BTree &T);void DeleteBook(BTree &T,int k);void Lending(BTree &T,int k,char librarynum10,char data10);void Return(BTree &T,int k,char *librarynum);3 程序的几个模块1）主程序模块void main（）接受命令初始化处理命令2）B-树模块-实现B树的抽象数据类型3）图书馆模块-实现图书馆的抽象数据类型调用关系如下：主程序模块B树模块图书馆模块-三详细设计（在源代码上通过注释的方式来 说明）1、基本结构typedef structint booknum;char name20;char writer20;int total;int current;char librarynumMAXMAX;char returndateMAXMAX;Record;typedef structint k;Record *recptr;KeyType;typedef struct BTNodeint keynum;struct BTNode *parent;KeyType *keyM+1;struct BTNode *ptrM+1;BTNode,*BTree;typedef structBTNode *pt;int i;int tag;Result;2、源代码1）主函数#include head.h#include head.hvoid main()BTree T;int order=0,booknum;char returndate10,librarynum10;Result result;InitBTree(T);printf(n*n);printf(Welcome to the library system!n);while(order!=6)printf(n*n);printf(请选择服务： 1.采编入库 2.清除库存 3.借阅 4.归还 5.显示 6.退出.n);scanf(%d,&order);switch(order)case 1:Procurement(T);PrintBTree(T);break;case 2:printf(请输入要删除的书的编号。n);scanf(%d,&booknum);DeleteBook(T,booknum);PrintBTree(T);break;case 3:printf(请输入要借阅的书的编号：n);scanf(%d,&booknum);printf(请输入借书证号：n);getchar();gets(librarynum);printf(请输入归还日期：n);gets(returndate);Lending(T,booknum,librarynum,returndate);break;case 4:printf(请输入要归还的书的编号：n);scanf(%d,&booknum);printf(请输入借书证号：n);getchar();gets(librarynum);Return(T,booknum,librarynum);break;case 5:printf(输入要查找的书的编号:n);scanf(%d,&booknum);result=SearchBTree(T,booknum);if(result.tag=0)printf(cant find this book!n);else PrintBookInfomation(result.pt-keyresult.i-recptr);break;case 6:printf(bye!n);2）B树的操作#include head.hvoid InitBTree(BTree &T)T=(BTree)malloc(sizeof(BTNode);T-keynum=0;T-parent=NULL;T-ptr0=NULL;int Search(BTree p,int k)int i=0;while(ikeynum)if(p-keyi+1-kk)return i;else if(p-keyi+1-k=k)return i+1;else i+;return i;Result SearchBTree(BTree T,int k)BTree p,q;Result r;int found=FALSE,i=0;q=NULL;p=T;while(p!=NULL&!found)i=Search(p,k);if(i0 & p-keyi-k=k) found=TRUE;elseq=p;if(p-ptri)p-ptri-parent=p;p=p-ptri;if(found)r.pt=p;r.i=i;r.tag=1;elseif(T=NULL)r.pt=T;elser.pt=q;r.i=i;r.tag=0;return r;void split(BTree &q,int s,BTree &ap)int i;ap=(BTree)malloc(sizeof(BTNode);ap-keynum=q-keynum-s;for(i=1;ikeynum;i+)ap-keyi=(KeyType *)malloc(sizeof(KeyType);ap-keyi-k=q-keyi+s-k;ap-keyi-recptr=q-keyi+s-recptr;ap-ptri=q-ptrs+i;ap-ptr0=q-ptrs;ap-parent=q-parent;q-keynum=s-1;void Insert(BTree &q,int i,KeyType x,BTree ap)int j,t;q-keynum+;q-keyq-keynum=(KeyType *)malloc(sizeof(KeyType);for(j=q-keynum;ji+1;j-)q-keyj-k=q-keyj-1-k; /？如果直接写成q-keyj=q-keyj-1就会有错q-keyj-recptr=q-keyj-1-recptr;q-ptrj=q-ptrj-1;q-keyi+1-k=x.k;q-keyi+1-recptr=x.recptr ;q-ptri+1=ap;if(ap!=NULL)ap-parent=q;void NewRoot(BTree &T,BTree q,KeyType x,BTree ap)BTree temp;temp=T;/*temp=(BTree)malloc(sizeof(BTNode);temp-keynum=1;temp-parent=NULL; /T-key1=x; 不能直接赋值，而要分别对其中的元素赋值temp-key1=(KeyType *)malloc(sizeof(KeyType);temp-key1-k=x.k;temp-key1-recptr=x.recptr;temp-ptr0=T;T-ptr1=ap;T=temp;*/T=(BTree)malloc(sizeof(BTNode);T-keynum=1;T-parent=NULL; temp-parent=T; ap-parent=T;T-key1=(KeyType *)malloc(sizeof(KeyType);T-key1-k=x.k;T-key1-recptr=x.recptr;T-ptr0=temp;T-ptr1=ap;Status InsertBTree(BTree &T,KeyType k,BTree q,int i)int s,j;KeyType x;BTree ap,parent=T;int finished=FALSE;x=k;ap=NULL;if(T!=NULL &q!=T)for(j=0;jkeynum;j+)if(q=T-ptrj)q-parent=T;break;while(q!=NULL &!finished)Insert(q,i,x,ap);if(q-keynumkeys-k;x.recptr=q-keys-recptr;q=q-parent;if(q!=NULL) i=Search(q,x.k);if(!finished)NewRoot(T,q,x,ap);return OK;void FindSmallest(BTree p,BTree &q)q=p;while(q-ptr0!=NULL)q=q-ptr0;int Parent(BTree p) /返回p的父结点中指向p的编号BTree q;int i;q=p-parent;if(q!=NULL)for(i=0;ikeynum;i+)if(q-ptri=p)return i;return -1;void RightBrother(BTree p,BTree &right)int i;if(p-parent=NULL)right=NULL;i=Parent(p);if(i+1)parent-keynum)right=p-parent-ptri+1;if(right)right-parent=p-parent;elseright=NULL;void LeftBrother(BTree p,BTree &left)int i;if(p-parent=NULL)left=NULL;i=Parent(p);if(i-1)=0)left=p-parent-ptri-1;left-parent=p-parent;elseleft=NULL;void LeftMove(BTree &p,int loc)int i;for(i=loc;ikeynum;i+)p-keyi-k=p-keyi+1-k;p-keyi-recptr=p-keyi+1-recptr;p-ptri=p-ptri+1;Status DeleteBTree(BTree &T,int k)int i,loc,key;BTree p,q,right,left;Result location;int finished=FALSE;location=SearchBTree(T,k);if(!location.tag)printf(cant find the node with keyword %d.n,k);return ERROR;p=location.pt; /要删除的结点的位置loc=location.i;if(p-ptr0!=NULL) /删除结点为非终端结点时FindSmallest(p-ptrloc,q); /q记录p-ptr所指子树中的最小关键字key=q-key1-k;DeleteBTree(T,key);p-keyloc-k=key;elseif(p-keynum=M/2+1) /关键字数目不小于m/2时for(i=loc;ikeynum;i+)p-keyi-k=p-keyi+1-k;p-keyi-recptr=p-keyi+1-recptr;p-keynum-;finished=TRUE;elseif(p-keynum=M/2)i=Parent(p);RightBrother(p,right);if(right & right-keynumM/2)p-keyM/2-k=p-parent-keyi+1-k;p-keyM/2-recptr=p-parent-keyi+1-recptr;p-parent-keyi+1-k=right-key1-k;p-parent-keyi+1-recptr=right-key1-recptr;right-key1-k=right-key2-k;right-key1-recptr=right-key2-recptr;right-keynum-;finished=TRUE;elseLeftBrother(p,left);if(left & left-keynumM/2)p-key1-k=p-parent-keyi-k;p-key1-recptr=p-key1-recptr;p-parent-keyi-k=left-keyleft-keynum-k;p-parent-keyi-recptr=left-keyleft-keynum-recptr;left-keynum-;finished=TRUE;else /相邻兄弟结点中关键字数目均等于m/2-1while(p-parent & !finished)if(right)i=Parent(right);right-keynum+;right-key2=(KeyType *)malloc(sizeof(KeyType);/dont forget!right-key2-k=right-key1-k;right-key2-recptr=right-key1-recptr;right-ptr2=right-ptr1;right-ptr1=right-ptr0;p-keynum-;right-key1-k=p-parent-keyi-k;right-key1-recptr=p-parent-keyi-recptr;p-parent-keynum-;if(p-ptr0 & p-ptr0-keynum!=0)right-ptr0=p-ptr0;elseright-ptr0=p-ptr1;if(p-parent-keynum=M/2 &p-parent-keynumparent-key1-k=p-parent-key2-k;p-parent-key1-recptr=p-parent-key2-recptr; p-parent-ptr0=p-parent-ptr1;p-parent-ptr1=p-parent-ptr2;elsep-parent-ptr1=right;finished=TRUE;else if(left)i=Parent(left);left-keynum+;left-key2=(KeyType *)malloc(sizeof(KeyType);left-key2-k=p-parent-keyi+1-k;left-key2-recptr=p-parent-keyi+1-recptr;p-parent-keynum-;p-parent-ptri+1=NULL;if(p-ptr1)left-ptr2=p-ptr1;elseleft-ptr2=p-ptr0;if(p-parent-keynum=M/2)LeftMove(p-parent,i);/p-parent-key1=p-parent-key2;/p-parent-ptr0=right-ptr1;/p-parent-ptr1=right-ptr2;finished=TRUE;if(!finished)/*if(p-parent-parent & p-parent-keynum=0)if(right)i=Parent(p-parent);p-parent-ptri=right;finished=TRUE;elseif(left)i=Parent(p-parent);p-parent-ptri=left;else */if(!p-parent-parent & p-parent-keynum=0)if(right)T=right;elseif(left)T=left;T-parent=NULL;finished=TRUE;elsep=p-parent;if(p)RightBrother(p,right);LeftBrother(p,left); /while return OK;void PrintBTree(BTree T)int i;if(T=NULL) return;/printf(NULLn);return;if(T-parent!=NULL)if(T-parent-parent=NULL)printf();else if(T-parent-parent-parent=NULL)printf();else if(T-parent-parent-parent-parent=NULL)printf();for(i=1;ikeynum;i+)printf(%d ,T-keyi-k);printf(n);for(i=0;ikeynum;i+)/printf(*%d*,i);PrintBTree(T-ptri);3图书馆#include head.hvoid GetInformation(Record &book)/*printf(enter the name of the book:n);getchar();gets();printf(enter the number of the book:n);scanf(%d,&book.booknum);printf(enter the writer of the book:n);getchar();gets(book.writer);printf(enter the total storage of the book:n);scanf(%d,&book.total);book.current=book.total;*/strcpy(,happy);strcpy(book.writer,sunny);book.total=5;book.current=book.total;printf(enter the number of the book:n);scanf(%d,&book.booknum);void PrintBookInfomation(Record *book)int i;printf(the booknum:%dn,book-booknum);printf(name:%sn,book-name);printf(writer:%sn,book-writer);printf(total storage:%d,current storage:%d,book-total,book-current);for(i=0;itotal-book-current;i+)printf(nNO.:%d LIBRARYNUM:%s RETURNDATE:%s,i+1,book-librarynumi,book-returndatei);void CopyBook(KeyType &k,Record book)int i;k.k=book.booknum;k.recptr=(Record *)malloc(sizeof(Record);k.recptr-booknum=book.booknum;k.recptr-current=book.current;k.recptr-total=book.total;strcpy(k.recptr-name,);strcpy(k.recptr-writer,book.writer);for(i=0;ilibrarynumi,book.librarynumi);strcpy(k.recptr-returndatei,book.returndatei);void Procurement(BTree &T)Record book;Result result;KeyType k;GetInformation(book);result=SearchBTree(T,book.booknum);if(result.tag=0)CopyBook(k,book);InsertBTree( T,k,result.pt,result.i);elseresult.pt-keyresult.i-recptr-total+;void DeleteBook(BTree &T,int k)DeleteBTree(T,k);void Lending(BTree &T,int k,char librarynum10,char returndate10)Result result;BTree p;int i,j;result=SearchBTree(T