B-树课程设计0001

1、课程设计成果学院 : 计算机工程学院 班 级 : 学生姓名 : 学 号: 设计地点（单位）设计题目 : B- 树完成日期： 年 月 日指导教师评语 :成绩（五级记分制 ）: 教师签名 :目录1 需求分析 11.1 系统目标 11.2 主体功能 11.3 开发环境 12 概要设计 12.1 功能模块划分 12.2 系统流程图 23 详细设计 33.1 数据结构 33.2 模块设计 44 测试 74.1 测试数据 74.2 测试结果 75 总结 10参考文献 11附录 源程序代码 121 需求分析1.1 系统目标完成 B-树的创建、查找、插入和删除。1. 2 主体功能B-Trees 是一类满足特殊

2、条件的 M路查找树，它满足如下两个条件的 M路查找树：1. 所有叶节点的高度相同。2. 除根之外的所有节点都是半满的，即该节点包含 M/2或更多的值。3. 树中每个节点都至多有 M棵树。4. 所有的叶子节点都出现在同一层，并且不带信息。5. 所有的非终端节点中包含下列信息： (n,A0,K1,A1,K2,A2K3,A3 .Kn,An)其中： Ki 为关键字，且 Ki<Ki+1;Ai 为指向自树的指针，且 Ai-1 所指子树中 所有的节点的关键字均小于 Ki,An 所指子树中所有节点的关键字均大于 Kn ，n 为关键 字的个数。1. 设计并实现 B-Trees 数据结构，包含其上的基本操作

3、，如节点的插入和删除等。2. 实现在 B-trees 树上的查找操作。3. 设计良好的运行界面，能够实现重复的操作。1.3 开发环境开发系统： Windows 系统，处理器要求最低奔腾处理器，内存 32m，建议在 i5 处理器， 128m内存配置下调试。编译集成软件： Devc+开发软件。Devc+是一个强大的 C/C+软件开发工具，操作简单，使用非常广泛， 称为很多程序员 的首选开发工具。2 概要设计2.1 功能模块划分主函数即 main() 函数，主要实现 B-Trees 的建立，建立一棵满足要求的 4 节 B-Trres 树。菜单介绍函数即 meau()函数，主要包括介绍各个功能的实现途

4、径，并给操作者提供 个操作界面。插入元素函数即 insertbtree(b) 函数，主要有用户通过界面输入要插入的元素，首先 判断要插入的元素是否已在 B-Trees 中，若不在则插入之。删除函数即 deletetree(b) 函数，首先判断要删除的元素是否在 B-Trees 中若在该B-Trees 中则删除查找函数即 searchbtree(b) 函数，由用户通过界面输入一个元素，查找该元素是否在 该 B-Trees 中，若在就输出它在节点的位置。图 2.1 主函数流程图2. 2 系统流程图B- 树的主程序流程如图 2.2 所示B- 树的主程序流程如图 2.3 所示3 详细设计3.1 数据结

5、构B-树的数据类型：typedef struct BTNodeint keynum; / 结点中关键字的个数，即结点的大小 struct BTNode *parent; / 指向双亲指针int keym+1; / 关键字向量struct BTNode *ptrm+1; / 子树指针向量BTNode3.2 模块设计 B-树插入新元素模块如图 3.2 所示树插入元素函数流程图B-树删除元素模块如图 3.3 所示图 3.3 B- 树删除元素函数流程图B-树查找模块如图 3.4 所示B-树查找模块如图 3.4 所示图 3.5 B- 树查找元素模块流程图4 测试4.1 测试数据图表 4-1序号数据内容说

6、明显示截图13查找，要查元素在 B- 树中图 4.225查找，要查元素不在 B- 树中图 4.3332插入，插入元素不在 B 树中图 4.4442插入，插入元素在 B- 树中图 4.5561删除，删除元素在 B-树中图 4.6651删除，删除元素不在 B- 树中图 4.74.2 测试结果界面主菜单运行结果如图 4.1 所示图 4.1 主界面运行查询 B-树中元素运行结果分两种可能一是要查元素在 B-树中，另一种是不在要查元素在 B-树中的运行结果如图 4.2 所示图 4.2 查找 B- 树已有元素要查不在元素在 B- 树中的运行结果如图 4.3 所示图 4.3 查找 B- 树中没有元素插入 B

7、-树中元素运行结果分两种可能一是要查元素在 B-树中，另一种是不在 要插入的元素在 B- 树中的运行结果如图 4.4 所示。图 4.4 插入 B- 树已有元素要插入的元素不在 B-树中的运行结果如图 4.5 所示。图 4.5 插入 B- 树中没有元素插入 B-树中元素运行结果分两种可能一是要查元素在 B-树中，另一种是不在 要删除的元素在 B- 树中的运行结果如图 4.6 所示。要删除的元素不在图 4.6 删除 B- 树中已有元素退出 B-树中元素的运行结果如图 4.8 所示。图 4.8 退出运行主界面5 总结 历时两周的课程设计终于结束了，对于课程设计： 首先，关于程序方面，我发现即使对设计

8、思路有了眉目，知道了所要用到的B-树的一些知识，但是要把这些写成函数代码，其实还是一件非常不容易的事情。再加上要完善设 计思路，构造整个程序框架在内，都是一件工作量非常大的工作。幸好，有很多资料可以在网路上搜到。所以课程设计的第一天，我们搜集了很多关于 B-树的资料，包括几种不同思路的程序代码，以及程序流程。然后我们的工作就变成：尽量看懂并整理这些代码，然后再其基础上筛选需要的功能，按照自己的意愿来修改与完善在操作界面的人性化上，我倒尽可能的做得很完善，无论从美观角度还是方便清楚操 作，都实行了非常人性化的方式。因为通常清楚程序的人，知道怎么操作以及该输入什么， 而不清楚的人却有很大可能在细节

9、方面输入错误导致程序运行失败，或是根本不知道应该 怎么输入。所以，尽可能的人性化的设计是非常有必要的，让不懂程序的人也可以正确的 操作运行。在调试程序的过程中，遇到了许多常识性的问题，通过不断的调试、改进，最终使程 序能够运行，并且得到正确的运行结果。在这个过程中，能够不断地发现问题，并且自己 独立的去解决多遇到的问题，这是课程设计过程中所不可缺少的精神。最后，做再次一下总结。程序方面仍有为解决的问题，希望即便课设之后也可以努力 将问题解决掉。然后 B-树的算法中，有些知道怎么做却很难清楚回答出来的问题，希望可 以再好好的查找一下相关资料，将知识系统化、理论化、规范化。参考文献1 顾泽元，刘文

10、强编 . 数据结构. 北京：北京航空航天大学出版社， 2011年.2 李素若，陈万华，游明坤编 .数据结构（ C语言描述），中国水利水电出版社， 2014 年.3 李素若，陈万华，游明坤编 . 数据结构习题解答及上机指导，中国水利水电出版社， 2014年.4 谭浩强编 .C 语言设计 . 清华大学出版社， 2011 年.附录 源程序代码#include<stdio.h> #include<malloc.h>#include<stdlib.h>#define m 4 /B- 树的阶，设定为 4#define max 32767typedef struct BT

11、Nodeint keynum; / 结点中关键字的个数，即结点的大小struct BTNode *parent;/ 指向双亲指针int keym+1; / 关键字向量struct BTNode *ptrm+1;/ 子树指针向量BTNode,*BTree;/ 定义 B- 树的节点结构int data20=3,24,45,27,53,90,50,61,70,100,12,37,85,105,108,113,121,124,138,135; BTree T,R,R1;int rag;BTree searchtree(int k) / 查找建树时要插入元素的位置int j;BTree p1,q1;p1

12、=T;while(p1)for(j=1;j<m;j+) if(p1->keyj>k) break;q1=p1; p1=p1->ptrj-1;rag=j-1;return q1;void search(BTree p2,int a)int j;for(j=1;j<m;j+) if(p2->keyj>a)break;rag=j-1;void zimeau() / 介绍菜单printf("ttn");printf("tt 菜单简介 n");printf("ttn");printf("tt1

13、.查询结点信息n");printf("tt2.插入新的结点n");printf("tt3.删除结点 n");printf("tt4.退出 n");printf("ttn");int searchbtree(int k)/ 查询要查元素在树中，若树中有该元素则打印否则打印说明无int i,found=0;BTree p;p=T;while(!found)&&(p->ptr0!=NULL)for(i=1;i<m;i+) if(k<=p->keyi) break;if(p

14、->keyi=k)found=1;elsep=p->ptri-1;if(p->ptr0=NULL) for(i=1;i<m;i+) if(k<=p->keyi) break;if(p->keyi=k)found=1;if(found=0)printf("tt 此元素不在该 B- 树中 n");elseprintf("tt 此元素元素在该 B- 树中 n");printf("tt 该元素是 B- 树中结点的第 %d元素 n",i);return found;void insertbtree(in

15、t x) / 插入元素函数int j,finished,s;BTree q,p;finished=0;q=searchtree(x); / 查找要插入元素在 B- 树中的位置 while(!finished)if(q->keynum=0) / 当要插入的元素所在结点是根节点 , 且为新申请的根结点q->ptr0=p;q->ptr1=R;q->key1=x; q->keynum+;p->parent=q;R->parent=q;else if(q->keynum!=0)&&(q->ptr0!=NULL) / 当要插入的元素所在

16、结点是中间的结点 x for(j=3;j>rag;j-) q->keyj+1=q->keyj;q->ptrj+1=q->ptrj; q->ptrj+1=R;R->parent=q;q->keyj+1=x;q->keynum+;else / 当插入的元素所在结点是最下层的结点时for(j=3;j>rag;j-) q->keyj+1=q->keyj;q->keyj+1=x;q->keynum+;finished=0;if(q->keynum<m)/ 当插入节点后，结点的关键字数小于 m时, 插入新的元素

17、完成finished=1;else/ 当插入新的结点后，结点的关键字数不小于 m时将结点分裂s=m/2+1;x=q->keys;q->keys=max;q->keynum=s-1;R=(BTNode*)malloc(sizeof(BTNode); / 新申请一个结点来存放分裂的另一部分数据 R->key1=q->keys+1;for(j=2;j<=m;j+) R->keyj=max;R->ptrj=NULL; R->ptr0=q->ptrs;R->ptr1=q->ptrs+1;R->keynum=1;q->ke

18、ys+1=max;p=q;q=q->parent;if(!q)R1=(BTNode*)malloc(sizeof(BTNode); / 新申请一个节点作为根节点 T=q=R1; q->keynum=0;q->parent=NULL;for(j=1;j<=m;j+) q->keyj=max;for(j=0;j<=m;j+)q->ptrj=NULL; elsesearch(q,x); / 在一个结点中查找要插入元素的位置void deletetree1(BTree q,int j) / 当要删除的节点是终端结点 ,j 是要删除元素 是节点的地几个元素int

19、 i,h;BTree p,q0,q1; p=q->parent;for(h=0;h<m;h+)if(p->ptrh=q)break;if(h=0)q1=p->ptrh+1;elseq0=p->ptrh-1;q1=p->ptrh+1;if(q->keynum>=m/2) / 当节点的数目不小于 m/2for(i=j;i<m;i+) q->keyi=q->keyi+1;elseif(q->keynum<m/2)&&(q0->keynum>=2|q1->keynum>=2) / 当结

20、点的数目少于 m/2 但其左兄弟或右兄弟的结点数目大于时if(q1->keynum>=m/2) / 右兄弟时 q->keyj=p->keyh;p->keyh=q1->key0; for(i=0;i<m;i+)q1->keyi=q1->keyi+1;q1->keynum-;else / 左兄弟时q->keyj=p->keyh;p->keyh=q0->keyq0->keynum; q0->keyq0->keynum=q0->keyq0->keynum+1;q0->keynum-;

21、else / 当结点的数目少于 m/2 且其左兄弟和右兄弟的结点数目小于时if(h=0) / 当该节点只有有兄弟时q->key1=p->key1;q->key2=q1->key1;q->keynum=2;free(q1); for(i=1;i<m;i+)p->keyi=p->keyi+1;p->keyi=p->keyi+1;p->keynum-;else / 当该节点有左兄弟时 q->key1=p->keyh;q->key2=q0->key1;q->keynum=2;free(q0); for(i=

22、1;i<m;i+)p->keyi=p->keyi+1;p->ptri=p->ptri+1;p->keynum-;void deletetree2(BTree q,int j) / 要插入节点是非终端结点BTree p;p=q;while(q->ptr0) / 找终端结点q=q->ptrj;if(q->ptr0!=NULL)q=q->ptr0;q=q->parent;p->keyj=q->key1;deletetree1(q,1);void deletetree(int k)int i,found=0;BTree p;

23、p=T;while(!found)&&(p->ptr0!=NULL) / 找到要插入节点的位置for(i=1;i<m;i+)if(k<=p->keyi)break;if(p->keyi=k)found=1;elsep=p->ptri-1;if(p->ptr0=NULL)/ 找到要插入节点的位置/ 当要删除元素是终端结点/ 当插入节点不是终端结点/ 查询要删除元素是否在树中for(i=1;i<m;i+) if(k<=p->keyi) break;if(p->ptr0=NULL)deletetree1(p,i);el

24、sedeletetree2(p,i);int searchbtree1(int k)int i,found=0;BTree p;p=T;while(!found)&&(p->ptr0!=NULL) for(i=1;i<m;i+) if(k<=p->keyi) break;if(p->keyi=k)found=1;elsep=p->ptri-1; if(p->ptr0=NULL)for(i=1;i<m;i+)if(k<=p->keyi)break;if(p->keyi=k)B-树中可以删除否则found=1; /

25、返回值， 1 代表该元素在 无法删除 return found;int rumeau() / 提供给读者自己的选择int c; printf("tttt 请输入您的选择： "); scanf("%d",&c);return c;void meau() / 菜单选项函数int a,b,rate;printf("tt%c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %cn",3 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3);

26、dozimeau();printf("tt%c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %cn",3a=rumeau(); / 子菜单 switch(a)case 1:system("cls");printf("tt 请输入要查找的元素 :"); scanf("%d",&b);rate=searchbtree(b); / 在 B- 树中查找元素函数 break;case 2:system("cls");pri

27、ntf("tt 请输入要插入的元素 :");scanf("%d",&b);rate=searchbtree(b); / 查询要插入的元素是否在该 B- 树中 if(rate=0)printf("tt 该元素不在此 B- 树中，故可插入之 "); insertbtree(b); / 插入新元素函数elseprintf("tt 该元素已在 B- 树中，不需要再插入 n"); break;case 3:system("cls"); printf("tt 请输入要删除的元素 :&quo

28、t;); scanf("%d",&b); rate=searchbtree1(b);if(rate=0)printf("tt 由于该元素不在此 B- 树中，故无法删除 n"); else printf("tt 该元素在此 B- 树中，可删除 n"); deletetree(b); / 删除 B- 树中的元素调用函数break;while(a!=4);void main()int x,i,finished,s,j;BTree q,p;system("color 1B"); / 背景颜色显示函数T=(BTNod

29、e*)malloc(sizeof(BTNode);T->keynum=0;for(i=0;i<3;i+)T->keyi+1=datai;T->keynum+;T->key4=max;for(i=0;i<5;i+)T->ptri=NULL;T->parent=NULL;for(i=3;i<20;i+)x=datai;finished=0;q=searchtree(x); / 查找要插入元素在 B- 树中的位置 while(!finished)if(q->keynum=0) / 当要插入的元素所在结点是根节点 , 且为新申请的根结点q->ptr0=p;q->ptr1=R;q->key1=x;q->keynum+;p->parent=q;R->parent=q;elseif(q->keynum!=0)&&(q->ptr0!=