B-树课程设计

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总结 .9参考文献.11附录 源程序代码 .121 需求分析1.1系统目标完成 B-树的创建、查找、插入和删除。1. 2 主体功能B-Trees 是一类满足特殊条件的M路查

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

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

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

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

6、元素在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.7 所示。图 4.7删除 B- 树中没有元素退出 B-树中元素的运行结果如图4.8 所示。图 4.8退出运行主界面5 总结历时两周的课程设计终于结束了，对于课程设计：首先，关于程序方面，我发现即使对设计思

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

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

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

11、;/ 指向双亲指针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=T;while(p1)for(j=1;jkeyjk)break;q1=p1;p1=p1-ptrj-1;rag=j-

12、1;return q1;void search(BTree p2,int a)int j;for(j=1;jkeyja)break;rag=j-1;void zimeau()/ 介绍菜单printf(ttn);printf(tt菜单简介n);printf(ttn);printf(tt1.printf(tt2.printf(tt3.printf(tt4.查询结点信息插入新的结点删除结点 n);退出 n);n);n);printf(ttn);int searchbtree(int k)/ 查询要查元素在树中，若树中有该元素则打印否则打印说明无int i,found=0;BTree p;p=T;wh

13、ile(!found)&(p-ptr0!=NULL)for(i=1;im;i+)if(kkeyi)break;if(p-keyi=k)found=1;elsep=p-ptri-1;if(p-ptr0=NULL)for(i=1;im;i+)if(kkeyi)break;if(p-keyi=k)found=1;if(found=0)printf(tt此元素不在该B-树中 n);elseprintf(ttprintf(tt此元素元素在该B-树中 n);该元素是B- 树中结点的第%d元素 n,i);return found;void insertbtree(int x)/ 插入元素函数int j,fi

14、nished,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)/ 当要插入的元素所在结点是中间的结点xfor(j=3;jrag;j-)q-keyj+1=q-keyj;q-ptrj+1=q-ptrj;q-ptrj+1=R;R-pare

15、nt=q;q-keyj+1=x;q-keynum+;else/ 当插入的元素所在结点是最下层的结点时for(j=3;jrag;j-)q-keyj+1=q-keyj;q-keyj+1=x;q-keynum+;finished=0;if(q-keynumkeys;q-keys=max;q-keynum=s-1;R=(BTNode*)malloc(sizeof(BTNode);/ 新申请一个结点来存放分裂的另一部分数据R-key1=q-keys+1;for(j=2;jkeyj=max;R-ptrj=NULL;R-ptr0=q-ptrs;R-ptr1=q-ptrs+1;R-keynum=1;q-key

16、s+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;jkeyj=max;for(j=0;jptrj=NULL;elsesearch(q,x);/ 在一个结点中查找要插入元素的位置void deletetree1(BTree q,int j)/ 当要删除的节点是终端结点,j是要删除元素是节点的地几个元素int i,h;BTree p,q0,q1;p=q-parent;for(h=0;hptrh=q)break;if(h=0)q1=p-ptrh

17、+1;elseq0=p-ptrh-1;q1=p-ptrh+1;if(q-keynum=m/2)/当节点的数目不小于for(i=j;ikeyi=q-keyi+1;m/2elseif(q-keynumkeynum=2|q1-keynum=2)/ 当结点的数目少于m/2但其左兄弟或右兄弟的结点数目大于时if(q1-keynum=m/2) /右兄弟时q-keyj=p-keyh;p-keyh=q1-key0;for(i=0;ikeyi=q1-keyi+1;q1-keynum-;else/ 左兄弟时q-keyj=p-keyh;p-keyh=q0-keyq0-keynum; q0-keyq0-keynum=

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

19、 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;p=T;while(!found)&(p-ptr0!=NULL)/ 找到要插入节点的位置for(i=1;im;i+)if(kkeyi)break;if(p-keyi=k)found=1;elsep=p-ptri-1;

20、if(p-ptr0=NULL)for(i=1;im;i+)if(kkeyi)/ 找到要插入节点的位置break;if(p-ptr0=NULL)deletetree1(p,i);/ 当要删除元素是终端结点elsedeletetree2(p,i);/当插入节点不是终端结点int searchbtree1(int k)/ 查询要删除元素是否在树中int i,found=0;BTree p;p=T;while(!found)&(p-ptr0!=NULL)for(i=1;im;i+)if(kkeyi)break;if(p-keyi=k)found=1;elsep=p-ptri-1;if(p-ptr0=N

21、ULL)for(i=1;im;i+)if(kkeyi)break;if(p-keyi=k)found=1;/ 返回值， 1 代表该元素在B-树中可以删除否则无法删除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,

22、3,3,3,3,3,3,3,3,3,3);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,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3);a=rumeau();/ 子菜单switch(a)case 1:system(cls);printf(tt请输入要查找的元素:);scanf(%d,&b);rate=searchbtree(b);/ 在 B-树中查找元素函数break;case 2:system(cls);printf(tt请

23、输入要插入的元素:);scanf(%d,&b);rate=searchbtree(b);/ 查询要插入的元素是否在该if(rate=0)B- 树中printf(ttinsertbtree(b);该元素不在此B- 树中，故可插入之 / 插入新元素函数);elseprintf(tt 该元素已在 B- 树中，不需要再插入 n); break;case 3:system(cls);printf(tt请输入要删除的元素:);scanf(%d,&b);rate=searchbtree1(b);if(rate=0)printf(tt由于该元素不在此B- 树中，故无法删除n);elseprintf(ttdeletetree(b);该元素在此B- 树中，可删除n);/ 删除 B-树中的元素调用函数break;while(a!=4);void main()int x,i,finished,s,j;BTree q,p;system(color 1B);/ 背景颜色显示函数T=(BTNode*)malloc(sizeof(BTNode);T-keynum=0;for(i=0;ikeyi+1=datai;T-keynum+;T-key4=max;for(i=0;iptri=NULL;T-parent=NULL