《[计算机软件及应用]西文图书管理与野人过河.doc》由会员分享,可在线阅读,更多相关《[计算机软件及应用]西文图书管理与野人过河.doc(45页珍藏版)》请在三一文库上搜索。
1、 中国地质大学(武汉)本科生课程论文封面课程名称 :数据结构课程设计 指导老师 : 李桂玲 姓 名 : 张川川 学 号 : 20111002423 专 业 : 网络工程 学 院: 计算机学院 类 别 : 第三组(3、6) 日 期 : 2012-12-25 数据结构课程设计报告目 录一、西文图书管理系统 21.1问题描述2 1.2 设计2 1.2.1数据结构设计2 1.2.2各函数体详细设计31.3调试分析9 1.3.1调试过程中遇到的问题及解决办法9 1.3.2该程序时间分析91.4用户手册 101.5测试数据及测试结果101.6源程序清单 13二、修道士与野人问题312.1问题描述 312.
2、2设计312.2.1逻辑结构设计 312.2.2存储结构设计 32 2.2.3设计思想 33 2.2.4各函数体设计 332.3调试分析342.4用户手册342.5测试数据及测试结果 352.6源代码清单 36一、西文图书馆管理系统1.1问题描述图书管理基本业务活动包括:对一本书的采编入库、清除库存、借阅和归还等等。试设计一个图书管理系统,将上述业务活动借助于计算机系统完成。要求: (1)每种书的登记内容至少包括书号、书名、著者、现存量和总库存量等五项。 (2)作为演示系统,不必使用文件,全部数据可以都在内存存放。要用B-树(4阶树)对书号建立索引,以获得高效率。 (3)系统应有以下功能:采编
3、入库、清除库存、借阅、归还、显示(以凹入表的形式显示)等。1.2设计1.2.1 数据结构设计1) 逻辑结构设计由问题的描述可知,对一个图书管理系统来说,有管理员可支配界面和用户可查询界面,其中对于每本书的编号进行B-树存储方便查找,以树状结构表示为:图1.本系统组织结构及主要涉及函数调用图2) 存储结构设计对每本书进行结构体book定义如下:typedef structint booknum;char bookname20;char writer20;int now; /书的现存量int total; /书的总库存int flag; /用以计算是否借出的标志Book; /书的信息的结构体B_树
4、结构体:typedef struct BTNodeint keynum; /结点中关键字的个数;struct BTNode *parent; /结点的双亲结点;KeyType keym+1; /结点中的关键字 struct BTNode *ptrm+1; /孩子结点数组BTNode,*BTree; /B_树结构体Result结构体记录结果,其中标志位tag为判断查找失败与成功的标志:typedef struct BTNode *pt; /指向找到结点的指针int i; /在结点中的关键字序号int tag; /标志查找成功(=1)或失败(=0)Result; /用以记录结果的结构体1.2.2各
5、函数体详细设计1) B_树函数体1.B-树的查找B-树的查找过程:根据给定值查找结点和在结点的关键字中进行查找交叉进行。首先从根结点开始重复如下过程:若比结点的第一个关键字小,则查找在该结点第一个指针指向的结点进行;若等于结点中某个关键字,则查找成功;若在两个关键字之间,则查找在它们之间的指针指向的结点进行;若比该结点所有关键字大,则查找在该结点最后一个指针指向的结点进行;若查找已经到达某个叶结点,则说明给定值对应的数据记录不存在,查找失败。用C语言描述并返回结果如下:/在B-Tree中查找关键字Result searchBTree(BTree t, KeyType *k)BTree p=t,
6、q=NULL;int found=0;int i=0;Result result;while(p&!found)i=searchNode(p,k);if( i0 & p-keyi.booknum=k-booknum) found=1;elseq=p;p=p-ptri; if(found) result.pt=p; result.i=i; result.tag=1; elseresult.pt=q;result.i=i;result.tag=0;return result; 2. B-树的插入插入的过程分两步完成:(1)利用前述的B-树的查找算法查找关键字的插入位置。若找到,则说明该关键字已经存
7、在,直接返回。否则查找操作必失败于某个最低层的非终端结点上。(2)判断该结点是否还有空位置。即判断该结点的关键字总数是否满足nkeyi+1和q-ptri+1if(q-keynumkeys+1.m,q-ptrs.m和/q-recptrs+1.m移入新结点*aps=(m+1)/2;Split(q,ap);x=q-keys;if(q-parent) /在双亲结点*q中查找x的插入位/置q=q-parent;/i=Search(q, x);else needNewRoot=1;if(needNewRoot=1) /根结点已分裂为结点*q和*apNewRoot(t,q,x,ap); /生成新根结点*t,
8、q和ap为子树指针3.B-树的删除 在B-树上删除关键字k的过程分两步完成:(1)利用前述的B-树的查找算法找出该关键字所在的结点。然后根据 k所在结点是否为叶子结点有不同的处理方法。(2)若该结点为非叶结点,且被删关键字为该结点中第i个关键字keyi,则可从指针soni所指的子树中找出最小关键字Y,代替keyi的位置,然后在叶结点中删去Y。 因此,把在非叶结点删除关键字k的问题就变成了删除叶子结点中的关键字的问题了。在B-树叶结点上删除一个关键字的方法是 首先将要删除的关键字 k直接从该叶子结点中删除。然后根据不同情况分别作相应的处理,共有三种可能情况:(1)如果被删关键字所在结点的原关键字
9、个数n=ceil(m/2),说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单,只需从该结点中直接删去关键字即可。(2)如果被删关键字所在结点的关键字个数n等于ceil(m/2)-1,说明删去该关键字后该结点将不满足B-树的定义,需要调整。 调整过程为:如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右(左)兄弟结点中的关键字数目大于ceil(m/2)-1。则可将右(左)兄弟结点中最小(大)关键字上移至双亲结点。而将双亲结点中小(大)于该上移关键字的关键字下移至被删关键字所在结点中。(3)如果左右兄弟结点中没有“多余”的关键字,即与该结点相邻的右(左)兄弟结点中的关键字数目均
10、等于ceil(m/2)-1。这种情况比较复杂。需把要删除关键字的结点与其左(或右)兄弟结点以及双亲结点中分割二者的关键字合并成一个结点,即在删除关键字后,该结点中剩余的关键字加指针,加上双亲结点中的关键字Ki一起,合并到Ai(是双亲结点指向该删除关键字结点的左(右)兄弟结点的指针)所指的兄弟结点中去。如果因此使双亲结点中关键字个数小于ceil(m/2)-1,则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使整个树减少一层。总之,设所删关键字为非终端结点中的Ki,则可以指针Ai所指子树中的最小关键字Y代替Ki,然后在相应结点中删除Y。对任意关键字的删除都可以转化为对最下层关键字的删
11、除a、被删关键字Ki所在结点的关键字数目不小于ceil(m/2),则只需从结点中删除Ki和相应指针Ai,树的其它部分不变。b、被删关键字Ki所在结点的关键字数目等于ceil(m/2)-1,则需调整。调整过程如上面所述。c、被删关键字Ki所在结点和其相邻兄弟结点中的的关键字数目均等于ceil(m/2)-1,假设该结点有右兄弟,且其右兄弟结点地址由其双亲结点指针Ai所指。则在删除关键字之后,它所在结点的剩余关键字和指针,加上双亲结点中的关键字Ki一起,合并到Ai所指兄弟结点中(若无右兄弟,则合并到左兄弟结点中)。如果因此使双亲结点中的关键字数目少于ceil(m/2)-1,则依次类推。B_树中删除操
12、作用C语言描述为:int RecDelete(KeyType k,BTNode *p)/查找并删除关键字kint i;int found;if(p=NULL) return 0;elseif(found=SearchNode(k,p,i)=1) /查找关键字kif(p-ptri-1!=NULL) /若为非叶子结点Successor(p,i); /由其后继代替它RecDelete(p-keyi,p-ptri); /p-keyi在叶子结点中elseRemove(p,i); /从*p结点中位置i处删除关键字 else found=RecDelete(k,p-ptri); /沿孩子结点递归查找并删除关
13、键字k if(p-ptri!=NULL) if (p-ptri-keynum0) /删除后关键字个数小于MIN Restore(p,i); return found;2) Book函数体1. 采编入库函数定义Book型变量b,Result型变量re,输出要采编入库图书输入的信息标志,并用if语句控制输入图书数量,即b.booknum0时停止输入,输入成功则调用B_树查找searchBTree(*r,&b)函数,将结果赋给re,如果查询图书的标志位即re.tag=0,调用B_树插入InsertNode(*r,&b)函数,如果re.tag=1,使此时re指向关键字所指的现存量加上输入图书的现存量,
14、总量同现存量。最后输出“图书采编成功”,表示已采编入库成功。2. 清除库存函数定义KeyType型变量b,Result型变量result,提示输出并输入要清除库存的图书的书号,以b.booknum为关键字调用B_树查找函数(b.booknum0且re.tag=1,表示已找到该书,若该书flag(标志位)不等于零(flag=0则提示本书已清除库存,请采编),并且该书现存量大于等于需借出数量,则进行借书操作,并将该书原现存量减去借出数量即现现存量,若该书现存量小于需借出数量,则输出“该书现存不够”。4. 归还图书函书 定义Book型变量b,Result型变量re,整型变量k,提示输出并输入要归还的
15、书号和归还的本书,若该书书号b.booknum0,调用B_树查找函数并将结果赋给re,若re.tag!=0,且还书数量小于等于该书图书总量与现存量之差,则归还图书,并将原现存量加上归还本书即为现现存量,若还书数量大于两者之差,则说明还书错误,输出“还书大于总存量,输入错误!请重试!”。5. 显示所有图书由题意,需用凹入表法表示所有图书,类比在二叉树中用到的凹入表示知识,将书号作为节点,并递归调用原函数,若存在图书flag=0,则在其后输出“-此书已清除库存!”提示。3) 测试函数main() 测试函数中包含4个部分,分别为主登录界面,管理员使用状态界面,用户使用状态界面,退出界面。 1.3调试
16、分析1.3.1调试过程中遇到的问题及解决办法 1)对B_树理解不到位。 B_树的搜索查找是本题目的核心所在,但是我在做题目的时候却对B_树各函数体理解不到位,甚至连建立结构体、初始化、插入都搞不定,导致以后Book函数体根本没办法写,没办法,只有各种查资料,而且调用参数是否一致,参考课本及老师上课用的PPT建立B_树结构,看来是基本功没有打好。 2)各函数体的链接。 B_树各函数理解还不太熟练,参考课本及老师上课用的PPT建立B_树结构,写Book各函数时发现调用B_树时调用失败,经过查询资料问询其他同学终于有了点眉目,还有在输入变量时由于没有注意到头文件的规范导致部分程序根本没有运行到,经过
17、细致检查,一步步调,终于成功实现了要求的功能。 3)指针的使用。指针在学习的时候就没有完全理解,以致用到的时候捉襟见肘,总是弄不清什么是指针,什么是指针指向的对象,但是经过查询资料,终于较清楚的理解了。1.3.2该程序时间分析该程序时间复杂度主要在B_树的查找、插入及删除中,分别分析如下:1) 查找代价: B-Tree作为一个平衡多路查找树(4-叉)。B树的查找分成两种:一种是从一个结点查找另一结点的地址的时候,需要定位磁盘地址(查找地址),查找代价极高。另一种是将结点中的有序关键字序列放入内存,进行优化查找(可以用折半),相比查找代价极低。而B树的高度很小,因此在这一背景下,B树比任何二叉结
18、构查找树的效率都要高很多。 2)插入代价: B-Tree的插入会发生结点的分裂操作。当插入操作引起了s个节点的分裂时,磁盘访问的次数为h(读取搜索路径上的节点)2s(回写两个分裂出的新节点)1(回写新的根节点或插入后没有导致分裂的节点)。因此,所需要的磁盘访问次数是h+2s+1,最多可达到3h+1。因此插入的代价是很大的。 3)删除代价:B-Tree的删除会发生结点合并操作。最坏情况下磁盘访问次数是3h(找到包含被删除元素需要h次读访问)+(获取第2至h层的最相邻兄弟需要h-1次读访问)+(在第3至h层的合并需要h-2次写访问)+(对修改过的根节点和第2层的两个节点进行3次写访问)B-Tree
19、效率总结: 由于考虑磁盘储存结构,B树的查找、删除、插入的代价都远远要小于任何二叉结构树(读写磁盘次数的降低)。1.4用户手册本程序运行环境为VC +6.0,执行文件为“西文图书管理系统.exe”运行程序后进入系统首页,选择端口进入,因未使用文件存储数据,图书存储为空,所以必须首先以管理员身份进入系统并进行图书入库操作,此时便可进行所有操作,注:数据存储在磁盘。1.5测试数据及测试结果1)运行程序,显示如下对话框:2) 选择输入1,以管理员身份登录,显示如下界面(每完成一个操作,系统都会自动返回管理员登录界面,除非直接选择退出操作。):3) 选择1,进行图书入库操作,显示如下界面:将数据存放在
20、“西文图书管理系统.txt”中,用时复制粘贴即可。1 jdkjf jkj 30 502 jdkjf kdjf 20 203 kdfjk kjkj 34 404 kjfkdj kjkj 78 796 kjkljk jkjk 56 607 kjkj jkjk 43 45 8 lklk jkjk 76 80-1 jkkj kjkjk 89 90将数据成功输入后,显示如下界面:4) 输入5,查看入库图书信息(凹入法表示),显示如下界面:5) 输入2,进行清除库存操作,将书号为2的图书清除库存,显示如下界面:再次输入5,继续查看图书信息,显示如下界面:与清除前显示界面比较可以发现,书号为2的图书现存及总
21、库存改变为0,说明清除成功!6) 输入3,进行图书借阅操作,输入借阅图书3,借阅2本,显示如下界面:再次输入5,查看图书信息,显示如下界面:与借阅前界面比较可以发现,书号为3的图书现存量由34本变为32本,即表示图书3已被成功借出2本。7) 输入4,进行图书归还操作。输入归还图书3,归还1本:显示如下界面:再次输入5,查看图书信息,显示如下界面:与归还前图书信息比较,可以发现图书3现存量由32本变为33本,说明还书成功!8)输入0,返回管理员/普通借阅者登录选择界面,显示如下界面:9)输入2,进入普通借阅者登录界面,显示如下界面:10) 输入1,查看所有图书信息,显示如下界面:与最近管理员查看
22、图书信息一致,表明显示成功!11) 输入0,再输入3,退出本系统,显示如下界面:至此已完成题目所有要求功能,测试成功!1.6源程序清单#include #include #include #include#include#define m 4typedef structint booknum;char bookname20;char writer20;int now; /书的现存量int total; /书的总库存int flag; /用以计算是否借出的标志Book;/书的信息的结构体typedef Book KeyType;/B-Tree模块typedef struct BTNodeint
23、keynum; /结点中关键字的个数;struct BTNode *parent; /结点的双亲结点;KeyType keym+1; /结点中的关键字 struct BTNode *ptrm+1; /孩子结点数组BTNode,*BTree; /B_树结构体typedef struct BTNode *pt; /指向找到结点的指针int i; /在结点中的关键字序号int tag; /标志查找成功(=1)或失败(=0)Result; /用以记录结果的结构体/设结点中的指针向量为空void SetNull(BTree &p)int i=0;while(ikeynum)p-ptri=NULL;i+;
24、/在结点中查找关键字int searchNode(BTree p,KeyType *k)int i=1;while(ikeynum)if(k-booknumkeyi.booknum) return i-1;i+;return i-1;/在B-Tree中查找关键字Result searchBTree(BTree t, KeyType *k)BTree p=t,q=NULL;int found=0;int i=0;Result result;while(p&!found)i=searchNode(p,k);if( i0 & p-keyi.booknum=k-booknum) found=1;els
25、eq=p;p=p-ptri; if(found) result.pt=p; result.i=i; result.tag=1; elseresult.pt=q;result.i=i;result.tag=0;return result; /赋值函数void cpy(KeyType *p,KeyType *q) p-total=q-total;p-now=q-now; strcpy(p-writer,q-writer);p-booknum=q-booknum;strcpy(p-bookname,q-bookname);p-flag=q-flag;/在结点中插入新的关键字k和指针ptvoid In
26、sertInNode(BTree &q,int i,KeyType *k,BTree pt) int j;for(j=q-keynum;ji;j-)cpy(&(q-keyj+1),&(q-keyj);cpy(&(q-keyj+1),k);for(j=q-keynum;ji;j-)q-ptrj+1=q-ptrj;q-ptrj+1=pt;if(pt)pt-parent=q;q-keynum+;void Insert(BTNode *&q,int i,KeyType x,BTNode *&ap)/将x和ap分别插入到q-keyi+1和q-ptri+1中int j;for(j=q-keynum;ji;
27、j-) /空出一个位置q-keyj+1=q-keyj;q-ptrj+1=q-ptrj;q-keyi+1=x;q-ptri+1=ap;if(ap!=NULL)ap-parent=q;q-keynum+;void Split(BTree p,BTree &q)/分裂结点pint s=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;iptrj=p-ptri-1;cpy(&(q-key+j),&(p-keyi);q-ptrj=p-ptri-1;q-keynum=j;for(t=
28、s+1;tptrt!=NULL)p-ptrt-parent=q; void NewRoot(BTNode *&t,BTNode *p,KeyType x,BTNode *ap)/生成含信息(T,x,ap)的新的根结点*t,原t和ap为子树指针t=(BTNode *)malloc(sizeof(BTNode);t-keynum=1;t-ptr0=p;t-ptr1=ap;t-key1=x;if(p!=NULL) p-parent=t;if(ap!=NULL) ap-parent=t;t-parent=NULL;void InsertBTree(BTNode *&t, KeyType k, BTNo
29、de *&q, int i)/在m阶t树t上结点*q的keyi与keyi+1之间插入关键字k。若引起结点过大,则沿双亲链进行必要的结点分裂调整,使t仍是m阶t树。BTNode *ap;int finished,needNewRoot,s;KeyType x;if(q=NULL) /t是空树(参数q初值为NULL)NewRoot(t,NULL,k,NULL); /生成仅含关键字k的根结点*telsex=k;ap=NULL;finished=needNewRoot=0;while (needNewRoot=0 & finished=0)Insert(q,i,x,ap); /将x和ap分别插入到q-
30、keyi+1和q-ptri+1if(q-keynumkeys+1.m,q-ptrs.m和q-recptrs+1.m移入新结点*aps=(m+1)/2;Split(q,ap);x=q-keys;if(q-parent) /在双亲结点*q中查找x的插入位置q=q-parent;/i=Search(q, x);else needNewRoot=1;if(needNewRoot=1) /根结点已分裂为结点*q和*apNewRoot(t,q,x,ap); /生成新根结点*t,q和ap为子树指针void Successor(BTNode *p,int i)/查找被删关键字p-keyi(在非叶子结点中)的替
31、代叶子结点BTNode *q;for(q=p-ptri;q-ptr0!=NULL;q=q-ptr0);p-keyi=q-key1; /复制关键字值void Remove(BTNode *p,int i)/查找被删关键字p-keyiBTNode *q;for(q=p-ptri;q-ptr0!=NULL;q=q-ptr0);void MoveRight(BTNode *p,int i)/把一个关键字移动到右兄弟中int c;BTNode *t=p-ptri;for(c=t-keynum;c0;c-) /将右兄弟中所有关键字移动一位t-keyc+1=t-keyc;t-ptrc+1=t-ptrc;t-
32、ptr1=t-ptr0; /从双亲结点移动关键字到右兄弟中t-keynum+;t-key1=p-keyi;t=p-ptri-1; /将左兄弟中最后一个关键字移动到双亲结点中p-keyi=t-keyt-keynum;p-ptri-ptr0=t-ptrt-keynum;t-keynum-;void MoveLeft(BTNode *p,int i)/把一个关键字移动到左兄弟中int c;BTNode *t;t=p-ptri-1; /把双亲结点中的关键字移动到左兄弟中t-keynum+;t-keyt-keynum=p-keyi;t-ptrt-keynum=p-ptri-ptr0;t=p-ptri;
33、/把右兄弟中的关键字移动到双亲兄弟中p-keyi=t-key1;p-ptr0=t-ptr1;t-keynum-;for(c=1;ckeynum;c+) /将右兄弟中所有关键字移动一位t-keyc=t-keyc+1;t-ptrc=t-ptrc+1;void Combine(BTNode *p,int i)/将三个结点合并到一个结点中int c;BTNode *q=p-ptri; /指向右结点,它将被置空和删除BTNode *l=p-ptri-1;l-keynum+; /l指向左结点l-keyl-keynum=p-keyi;l-ptrl-keynum=q-ptr0;for(c=1;ckeynum;
34、c+) /插入右结点中的所有关键字l-keynum+;l-keyl-keynum=q-keyc;l-ptrl-keynum=q-ptrc;for (c=i;ckeynum;c+) /删除父结点所有的关键字p-keyc=p-keyc+1;p-ptrc=p-ptrc+1;p-keynum-;free(q); /释放空右结点的空间void Restore(BTNode *p,int i)/关键字删除后,调整B-树,找到一个关键字将其插入到p-ptri中if(i=0) /为最左边关键字的情况if(p-ptr1-keynum0)MoveLeft(p,1);elseCombine(p,1);else if
35、 (i=p-keynum) /为最右边关键字的情况if(p-ptri-1-keynum0)MoveRight(p,i);elseCombine(p,i);else if (p-ptri-1-keynum0) /为其他情况MoveRight(p,i);else if (p-ptri+1-keynum0)MoveLeft(p,i+1);elseCombine(p,i);int SearchNode(KeyType k,BTNode *p,int &i)/在结点p中找关键字为k的位置i,成功时返回1,否则返回0if(k.booknumkey1.booknum) /k小于*p结点的最小关键字时返回0i=0;return 0;else /在*p结点中查找i=p-keynum;while(k.booknumkeyi.booknum & i1) i-;return(k.booknum=p-keyi.booknum);int RecDelete(KeyType k,BTNode *p)/查找并删除关键字kint i;int found;if(p=NULL) return 0;elseif(found=SearchNode(k,p,i)=1) /查找关键字k
链接地址:https://www.31doc.com/p-1992086.html