B树专业课程设计专业资料.doc

课程设计成果 学院： 计算机工程学院 班 级： 学生姓名： 学 号： 设计地点（单位） 设计题目： 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是一类满足特殊条件M路查找树，它满足如下两个条件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-trees树上查找操作。3.设计良好运营界面，可以实现重复操作。 1.3 开发环境开发系统：Windows 系统，解决器规定最低奔腾解决器，内存32m，建议在i5解决器，128m内存配备下调试。编译集成软件：Devc+开发软件。Devc+是一种强大C/C+软件开发工具，操作简朴，使用非常广泛，称为诸多程序员首选开发工具。2概要设计 2.1 功能模块划分主函数即main()函数，重要实现B-Trees建立，建立一棵满足规定4节B-Trres树。菜单简介函数即meau（）函数，重要涉及简介各个功能实现途径，并给操作者提供个操作界面。插入元素函数即insertbtree(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 BTNode int keynum；/结点中核心字个数，即结点大小 struct BTNode *parent；/指向双亲指针int keym+1；/核心字向量struct BTNode *ptrm+1；/子树指针向量BTNode 3.2 模块设计B-树插入新元素模块如图3.2所示。图3.2 B-树插入元素函数流程图B-树删除元素模块如图3.3所示。图3.3 B-树删除元素函数流程图B-树查找模块如图3.4所示。图3.4 B-树查找元素模块流程图B-树查找模块如图3.4所示。图3.5 B-树查找元素模块流程图4 测试4.1测试数据图表 4-1序号数据内容阐明显示截图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-树中元素运营成果分两种也许一是要查元素在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 总结历时两周课程设计终于结束了，对于课程设计：一方面，关于程序方面，我发现虽然对设计思路有了眉目，懂得了所要用到B-树某些知识，但是要把这些写成函数代码，其实还是一件非常不容易事情。再加上要完善设计思路，构造整个程序框架在内，都是一件工作量非常大工作。幸好，有诸多资料可以在网路上搜到。因此课程设计第一天，咱们收集了诸多关于B-树资料，涉及几种不同思路程序代码，以及程序流程。然后咱们工作就变成：尽量看懂并整顿这些代码，然后再其基本上筛选需要功能，按照自己意愿来修改与完善。在操作界面人性化上，我倒尽量做得很完善，无论从美观角度还是以便清晰操作，都实行了非常人性化方式。由于普通清晰程序人，懂得怎么操作以及该输入什么，而不清晰人却有很大也许在细节方面输入错误导致程序运营失败，或是主线不懂得应当怎么输入。因此，尽量人性化设计是非常有必要，让不懂程序人也可以对的操作运营。在调试程序过程中，遇到了许多常识性问题，通过不断调试、改进，最后使程序可以运营，并且得到对的运营成果。在这个过程中，可以不断地发现问题，并且自己独立去解决多遇到问题，这是课程设计过程中所不可缺少精神。 最后，做再次一下总结。程序方面仍有为解决问题，但愿即便课设之后也可以努力将问题解决掉。然后B-树算法中，有些懂得怎么做却很难清晰回答出来问题，但愿可以再好好查找一下有关资料，将知识系统化、理论化、规范化。参照文献1顾泽元，刘文强编.数据构造.北京：北京航空航天大学出版社，. 2李素若，陈万华，游明坤编.数据构造（C语言描述），中华人民共和国水利水电出版社，.3李素若，陈万华，游明坤编.数据构造习题解答及上机指引，中华人民共和国水利水电出版社，.4谭浩强编.C语言设计.清华大学出版社，. 附录 源程序代码#include #include #include #define m 4 /B-树阶，设定为4 #define max 32767 typedef struct BTNode int 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=T； while(p1) for(j=1;jkeyjk) break；q1=p1;p1=p1-ptrj-1； rag=j-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.查询结点信息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;im;i+) if(kkeyi) break；if(p-keyi=k) found=1；else p=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); else printf(tt此元素元素在该B-树中n)； printf(tt该元素是B-树中结点第%d元素n,i)； return found； void insertbtree(int 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)/当要插入元素所在结点是中间结点x for(j=3;jrag;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;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-keys+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； else search(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+1；else q0=p-ptrh-1;q1=p-ptrh+1；if(q-keynum=m/2) /当节点数目不不大于m/2 for(i=j;ikeyi=q-keyi+1；else if(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=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 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；else p=p-ptri-1； if(p-ptr0=NULL) for(i=1;im;i+) if(kkeyi) /找到要插入节点位置break；if(p-ptr0=NULL) deletetree1(p,i)；/当要删除元素是终端结点else deletetree2(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；else p=p-ptri-1； if(p-ptr0=NULL) 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,3,3,3,3,3,3,3,3,3,3)；do zimeau()；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请输入要插入元素:)；scanf(%d,&b)；rate=searchbtree(b)；/查询要插入元素与否在该B-树中if(rate=0) printf(tt该元素不在此B-树中，故可插入之)；insertbtree(b)；/插入新元素函数 else printf(tt该元素已在B-树中，不需要再插入n)； break；case 3:system(cls)；printf(tt请输入要删除元素:)；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=(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；for(i=3;ikeynum=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) /当要插入元素所在结点是中间结点x for(j=3;jrag;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;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；if(R-ptr0!=NULL) R-ptr0-parent=R;R-ptr1-parent=R; q-ptrs=NULL;q-ptrs+1=NULL;R-keynum=1；q-keys+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；else search(q,x)；/在一种结点中查找要插入元素位置 meau()；/主菜单