B树课程设计汇本报告

1、课程设计报告课程设计名称：数据构造课程设计课程设计题目：B-树算法的应用院系：专业：计算机科学与技术班级：学号：姓名：指导教师：I / 361需求分析11.1课程设计的容11.2 B-树的描述12概要设计22.1总体设计思想22.2局部模块设想2查找关键字2将关键字插入结点，分裂结点，建立新的结点，建立B-树2搜索指定结点，新建文件23详细设计43.1主函数设计4设计思想4主流程图53.2函数设计53.3存储构造63.4函数流程图74运行调试174.1调试过程中遇到的问题及解决方法174.2运行结果174.3结论分析18参考文献19附录关键局部程序清单201需求分析1.1课程设计的容编写算法能

2、将学生信息保存到文件中，能够为学生信息建立 B-树索 引，并能够利用B-树索引查找到指定学生的信息。建立B-树索引使用学号 为关键字。B-树中只含有学号和该记录在文件中的位置信息要求：1. 1.B-树的阶可以选择，要求给出一个完整班的学生信息2. 参考相应资料，独立完成课程设计任务。3. 3 交规课程设计报告和软件代码。1.2 B-树的描述B-树是一种平衡的多路查找树，它在文件系统中很有用。在此先介绍树的 构造。一棵m阶的B-树，或为空树，或为满足以下特性的 m叉树：(1) 树中每个结点至多有 m棵子树；(2) 假设根结点不是叶子结点，那么至少有两棵子树；(3) 除根之外的所有非终端结点至少有

3、m/2棵子树；4所有非终端结点中包含以下信息数据n,A0，K1,A1,K2,A2,Kn,An 其中：Ki(i=1,n)为关键字，且 Ki<Ki+1(i=1,n-1);Ai(i=0,n)为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均 小于Ki(i=1,n),An 所指子树中所有结点的关键字均大于 Kn,n(m/2-1<=n<=m-1)为关键字的个数或 n+1为子树个数。5所有的叶子结点都出现在同一层次上，并且不带信息可以看作是外部 结点或查找失败的结点实际上这些结点根本不存在，指向这些结点的指 针为空。2概要设计2.1 总体设计思想首先将学生信息从键盘键入存

4、到指定的文件中，在此每当输入一个学生的信 息，对应学生信息的学号将作为B-树的关键字，连同一起的该记录在文件中的信 息这两局部作为结点插入到 B-树中，插入的过程也就是建立B-树的过程，其中B-树的阶m在开场的时候已经确定了，当结点中的关键字的个数大于m-1时就开场分裂，并生成新的结点，按此规律即能建立好 B-树，程序运行时只须输入任意 学生的学号，然后屏幕上将显示此学号对应的学生的全部信息，由此即完成课程 设计要求。2.2 局部模块设想221查找关键字分别从结点中，B-树中查找关键字K,因为要想建树，就要插入结点，插入 结点要先检验一下此时树中有没有次结点，int SearchNode(BT

5、ree p,int k)函数 和 Result SearchBTree(BTree t,int k)函数实现了查找功能。将关键字插入结点，分裂结点，建立新的结点，建立 B-树在将关键字插入结点时，由于阶树m经决定了，当结点中的关键字个数大于m-1时就要分裂此结点，第m/2个结点被提升到上一结点，与此同时原结点中关 键字前面的关键字还继续在此结点中，关键字之后的关键字需要存储到新生成的 结点中，这样逐个结点才能顺利插入到B-树中。即此时的B-树已经建立好了。搜索指定结点，新建文件B-树索引过程就是搜索指定关键字的过程，从根结点开场，向子树结点中的 关键字查找，当查找时即返回此时文件指针fp当前位

6、置，假设查找失败，就继续 查找，直到找到根结点为止，倘假设还没查找到就返回没有找到。我们需要把学 生的相关信息从键盘输入到指定文件中，其中包括学生的，学号和家庭地址等信 息，在利用文件中的fseek函数，使文件指针指向学生的相应信息位置，定义为 整型，与结点中学生信息在文件中的位置信息相对应，运行时只需要输入学生学 号，屏幕上会显示相应的学生完整信息，此时索引过程完成。36 / 363详细设计3.1 主函数设计设计思想B-树算法的实现，首先应该建立一个m阶的B-树在本算法中m设为5在 建立B-树过程中，首先输入一个关键字学生学号序列为方便起见本算法使用整数序列，关键字个数设定为10，将这个整数

7、序列存入数组中，然后从空树开场， 依次将关键字插入B-树中，建立一个m阶的B-树。在输入学生信息的同时只是 将学生学号作为关键字存入文件中建树过程中，每插入一个关键字，首先应该 判断出这个关键字在B-树中应该插入的位置，需要调用SearchBTree()和SearchNode()两个函数共同配合完成；然后调用 InsertBTree() 和Insert() 函数 进展插入，插入完成后，应该看该节点中关键字个数是否小于B-树的阶数m,当节点中插入的关键字个数不符合要求时，应该考虑节点分裂的情况根节点和子 树节点的情况都应该考虑到，如果有节点分裂的情况，应该进展节点分裂，可以 建立一个split(

8、)函数来实现这个功能；如果需要建立新的根节点，需要建立一 个NewRoot()函数来完成这个功能。B-树建立成功后，返回指向该 B-树根节点的 指针。该算法要求具有查找任一指定学生信息的功能，可以输入任意一个学生的学 号，在B-树中查找该关键字，看该关键字是否存在在该 B-树，如果存在，那么返 回该关键字对应的学生完整信息，否那么查找不成功，那么该学号所对应的关键 字不在该B-树中，以上即完成B-树索引过程。主流程图图3-1主函数流程图3.2函数设计在该算法中，设计了一个 main()主函数和10个子函数，通过主函数调用子 函数、子函数相互调用，完成设计要求的B-树的建立、在B-树中查找指定节

9、点该 算法中查找具体的关键字位置、B-树的遍历以及输出遍历序列等功能。3.2.1 函数在该算法中涉及到的各个函数的中文和英文名称分别为：主函数main()、节点查找函数SearchNode()、B-树查找函数SearchBTree()、节点插入函数Inset()、 节点分裂函数split()、节点建立函数NewRoot()、B-树插入函数InsertBTree()、 查找函数found()、中序遍历输出函数 PrintBTree()、文件写函数savestud、 文件读取函数readstud。322函数调用关系图321函数调用关系说明主函数里面包含四个函数，即主函数中需调用四个函数分别为Sea

10、rchBTree()、InsertBTree() 、found()、PrintBTree();执行 SearchBTree() 函数时需调用 SearchNode()函数；执行InsertBTree()函数时，需要调用SearchNode()、NewRoot()、Insert() 以及 split() 函数；执行 found()函数时， 要用到递归调用found()函数；执行 PrintBTree()函数时，也要用到递归调用 Prin tBTree()函数。3.3存储构造在该设计的算法中，定义B-树中节点类型、B-树类型以及查找结果类型如下:#defi ne m 3B-树的阶，暂定为3type

11、def struct BTNodeint keynum;/节点中关键字个数struct BTNode *pare nt;/指向双亲节点int keym+1;/关键字向量，0号单元未用struct BTNode *ptrm+1; /子树指针向量BTNode,*BTree; typedef structBTNode *pt;B-树节点和B-树的类型/指向找到的节点int i;/在节点中的关键字序号int tag;1:查找成功，0:查找失败Result;B-树的查找结果类型3.4函数流程图在这局部中，将每个函数分别用流程图表示出来，并且将每个函数的功能以 及实现过程详细的表述出来，使得能够更加清晰、

12、有条理表达出该算法。341函数调用关系说明函数名：mai n()函数功能：输入关键字序列，调用 B-树建立函数、查找函数、遍历输出函数 实现过程：如图所示，输入一个关键字序列，存储到数组中。对于数 组中每个学号关键字，首先调用函数SearchBTree()，找出该关键字应该插入的位置，然后调用函数InsertBTree(),将关键字依次插入B-树中，插入完成后，返 回指向B-树的根节点指针。然后按照要求输入要查找的学号关键字，调用found() 函数进展查找，返回查找结果可进展循环输入查找。并将查找的学号所对应的 学生完整信息输出在屏幕上。完成索引过程。开始图3-3主函数流程图342节点查找函

13、数函数名：SearchNode()功能：在节点中查找关键字，返回该关键字在节点中的位置幵始赋初值:=1返回-1加1结束图3-4 SearchNode()函数流程图实现过程：如图所示，SearchNode()函数代入的参数是指向关键字 可能所在节点的指针p和关键字k,从该节点的第一个关键字找起，依次将要查 找的关键字与节点中的关键字比拟，返回结果是所给关键字应该在节点中的位置。3.4.3 B-树查找函数函数名称：SearchBTree()功能：从B-树的根节点开场查找，查找所给关键字在该B-树中的节点位置以 及在所在节点中的位置，该函数返回结果为Result类型，result 表示关键字 在节点

14、中应该插入的位置，result.pt 表示关键字应该所在的节点， result.tag 表示是否能够在B-树中查找到该关键字。实现过程：如图所示，代入B-树的根节点指针和要查找的关键字， 从根节点开场，对每个节点使用 SearchNode()函数，查找所给关键字所在的节点 以及在该节点中的位置，如果该关键字已经存在于B-树中，那么返回关键字所在节点、以及所在序号以及查找到的标志；如果不存在，那么返回应该插入的节点 指针、在节点中的序号以及没有找到的标志。3.4.4 节点插入函数函数名：In sert()函数功能：将所给关键字插入到正确节点的正确位置函数流程图实现过程：如图所示，代入指向所给关键

15、字应该插入节点的指针、 所给关键字、关键字应该插入的位置，然后再将该关键字插入到节点的正确位置 上，节点关键字个数加1，返回指向该节点的指针q。3.4.5 节点分裂函数函数名：split()函数功能：当节点中关键字个数不符合要求时，进展节点分裂幵始图3-7 split()函数流程图实现过程：如图所示，该函数带入的参数是指向要产生分裂的节点 的指针q、节点最小子树个数s以及空指针ap，首先给ap分配BTree类型的空间， 然后再将q中序号大于s的关键字插入到ap节点中，同时纸箱子树的指针也插入 到ap中，然后再分别计算q和ap中的关键字个数，对q和ap进展处理。最后返 回ap指针。3.4.6 节

16、点建立函数函数名：NewRoot()函数功能：建立新的节点，并且返回指向该节点的指针开始图3-8NewRoot()函数流程图实现过程：如图所示，该函数的代入参数是根节点 T、指向子树的 指针p和ap以及关键字x，创立这个新节点，需要将关键字插入到该节点序号 1 的位置上，0号和1号的子树指针分别指向空。如果 p和ap不为空，那么它们的 父节点指向T节点。该函数最后返回的是指针 To347 B-树建立函数函数名：In sertBTree()函数功能：从空树开场建立 B-树，返回的是B-树的根指针实现过程：如图所示，该函数代入参数是根节点T、要插入到的节点q、要插入的关键字可以及在节点中应该插入的

17、位置序号i。该函数从根节点开场建立B-树，当根节点为空时，需要建立新的根节点并且插入关键字；如果根节 点不为空，那么直接插入即可，但是插入完成后，要考虑是否有节点分裂的情况函数分裂节点根节点分函数最后返回指向B-产生，入伏哦需要进展节点分裂，那么要调用split()裂以及子树节点分裂的情况都考虑到重新进展分裂插入 树根节点的指针To348 查找函数函数名：found()开始图3-10fo un d()函数流程图函数功能：查找指指定关键字，查找成功那么返回在所在节点的序号，否那 么返回-1。实现过程：如图所示，该函数代入参数是B-树根节点指针t以及关 键字k，从根节点开场查找，如果查找到返回i值

18、否那么返回-1，在查找过程中 低轨调用函数found()进展查找。文件随机读写输出函数函数名：fseek()功能：将位置指针按需要移动到任意位置，实现随即读写功能。图3-11 fseek() 函数流程图实现过程：需要查找学生相关信息时，只需输入对应的学生学号，利用fseek() 函数，将文件指针指到相应存处，将所有该学生信息全部显示出来，完成索引过 程。4运行调试4.1 调试过程中遇到的问题及解决方法在调试程序的过程中，遇到的问题有多种，但是集中表现为语句错误、逻辑 错误、参数未定义等方面。针对该算法中的这些问题，进展了具体分析，找到了 正确的解决方法。语句错误问题：missing befor

19、e ''括号匹配不正确分析：这种问题在编译时最容易表达出来，因为如果出现这种错误，系统会 进展提示。产生这种问题的原因是输入代码时疏忽，或是代入参数的类型与定义 类型布匹配。女口：定义BTree类型的指针p,引用的是&p,那么会出现 、 ' 匹配有误，解决该问题，根据提示找到该符号的地方，进展改正即可。逻辑错误问题：函数不能调用或赋值语句不能分析：这种问题在执行程序时出现，表现为执行到一半会出错。通常这种问 题是由于编写算法算判断语句不完善造成的，通常解决方法是单步调试，找到出 错的地方，即算法执行停顿的地方，修改错误的逻辑语句。4.2 运行结果该设计最终要现B

20、-树算法，根据该算法设定的参数，输入事先指定好的学生 信息，按先后顺序从键盘输入到文件中，此时 B-树已经建立好了，索引时只需输 入任意一个学生的学号，就可以得到该学生完整信息的运行结果： 学生信息包括学生的，学号，成绩等。例如：输入的是：Zhao 1 78Qia n 2 56Sun 3 87Li 4 34Zhou 567Wu 6 64Zheng 7 39Wang 8 79Feng 9 68Chen 10 86程序会自动以学号为关键字建立好 B-树，请输入要查找的学生信息的学号： 例如：输入5；那么输出：Zhou 5 67当输入0的时候停顿索引，过程完毕！4.3 结论分析在该算法中，实现了建立

21、一个m阶的B-树，返回指向建好的B-树根节点的指 针，并且能够查找指定的学号关键字，假设查找成功，那么返回该关键字所在学 生的相关信息，否那么查找不成。在调试程序的过程中，遇到了许多常识性的问题，通过不断的调试、改良， 最终使程序能够运行，并且得到正确的运行结果。在这个过程中，能够不断地发 现问题，并且自己独立的去解决多遇到的问题，这是课程设计过程中所不可缺少 的精神。参考文献1 .?数据构造？用面向对象方法与C+苗述，殷人昆等，清华大学。2 .?算法与数据构造习题精解和实验指导？，宁正元等，清华大学。3 .?数据构造课程实验？徐孝凯 编著，清华大学。4 严蔚敏，吴伟民.数据构造（C语言版）M

22、 .:清华大学，2006. 吕国英.算法设计与分析M .:清华大学，2006 徐宝文，志.C程序设计语言M .:机械工业，2004.7 夏克俭.数据构造+算法】M .:国防工业，2001.8 春葆，曾慧，植民.数据构造程序设计题典】M .:清华大学，2002.附 录关键局部程序清单/B-树算法的应用#i nclude "stdio.h"#i nclude "math.h"#i nclude "malloc.h"#i nclude "stdlib.h"#include "fstream.h"#de

23、fi ne m 5#defi ne n 10typedef struct BTNodeint keynum;struct BTNode *pare nt;int keym+1;struct BTNode *ptrm+1;in t locati on m+1;BTNode,*BTree;typedef structBTNode *pt;int i;int tag;Result;struct stude nt int num;char n ame10;int score;std n;in t an ,b n;/在结点中查找关键字int SearchNode(BTree p,int k)int i=

24、1;while(i<=p->ke ynum)if(k<p->keyi)return i-1;else if(k=p->keyi) return -1;else i+;return i-1;/在B树中查找关键字k为B树根节点Result SearchBTree(BTree t,i nt k)/tBTree p=t,q=NULL;int foun d=0;int i=0;Result result;while(p&&!fou nd)i=SearchNode(p,k);if(i=-1)result.pt=p;result.i=i;result.tag=1

25、;return result;while(p->ptri) p=p->ptri; i=SearchNode(p,k);if(i>0&&p->keyi=k)foun d=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=O;return result;/将关键字插入节点BTree In sert(BTree q,i nt i,i nt x,BTree ap,i nt I)/ insert the

26、key X between the keyi and keyi+1/ at the poin ter node qint j;for(j=q->ke ynu m;j>i;j-)q->keyj+1=q->keyj;q-> location j+1=q-> location j;q->ptrj+1=q->ptrj;q->keyi+1=x;q->ptri+1=ap;q-> locati on i+1=l;if(ap)ap->pare nt=q;q->ke ynu m+;return q;/分裂节点BTree split(B

27、Tree q,i nt s,BTree ap)/move keys+1.m,p->ptrs.m int the new poin ter *ap int i,j;ap=(BTree)malloc(sizeof(BTNode);ap->ptrO=q->ptrs;for(i=s+1,j=1;i<=q->ke ynu m;i+,j+)ap->keyj=q->keyi;ap->ptrj=q->ptri;ap-> location j=q-> location i;ap->ke ynum=q->ke ynu m-s;ap-&g

28、t;pare nt=q->pare nt;for(i=0;i<=q->ke ynu m-s;i+)if(ap->ptri)ap->ptri->pare nt=ap;q->keyq->ke ynu m=0;q-> locatio n q->ke ynum=0;q->ke ynum=s-1;return ap;/建立新的节点BTree NewRoot(BTree T,BTree p,i nt x,BTree ap,i nt z)T=(BTree)malloc(sizeof(BTNode);T->ke ynum=1;T->

29、ptr0=p;T->ptr1=ap;T->key1=x;T-> locati on 1=z;if(p)p->pare nt=T;if(ap)ap->pare nt=T;T->pare nt=NULL;return T;/建立B-树BTree In sertBTree(BTree T,i nt K,BTree q,i nt i,i nt I)/ 在m阶B树T上结点*q的keyi与keyi+1之间插入关键字K。/假设引起结点过大，那么沿双亲链进展必要的结点分裂调整，使T仍是m阶B树。BTree ap;int fini shed, n eedNewRoot, s;

30、int x;if(!q)/ T是空树(参数q初值为NULL)T=NewRoot(T,NULL,K,NULL,l); /生成仅含关键字 K的根结点*Telsex=K; ap=NULL; fini shed=n eedNewRoot=0;while(! needNewRoot&&!fin ished)/将x和ap分别插入到q->keyi+1和插入完成q=I nsert(q,i,x,ap,l);q->ptri+1if(q->ke ynumv m)fini shed = 1; /else /分裂结点*q/将 q->keys+1.m, q->ptrs.m/

31、q-> locati on s+1.ms=(m+1)/2;ap=split(q,s,ap); x=q->keys; l=q-> location s;移入新结点*apq->locati on s=0;q->keys=0;if(q->pare nt) /在双亲结点*q中查找x的插入位置q=q->pare nt;i=SearchNode(q, x);else n eedNewRoot=1; / else / whileif(n eedNewRoot)/T=NewRoot(T,q,x,ap,l); /return T; / In sertBTree根结点已分

32、裂为结点*q和*ap生成新根结点*T,q和ap为子树指针/存储int found(BTree MT,int k)查找关键字对应记录的存储位置int i;BTree p=MT;while(p!=NULL)i=1;while(k>p->keyi&&i<p->ke ynum)i+;if(k=p->keyi)return p-> location i;else if(k>p->keyi)p=p->ptri;else if(k<p->keyi)p=p->ptri-1;return -1;void savestud(F

33、ILE *fout)/信息int i;if (fout=fope n("E:xueshe ng.txt","wb")=NULL)prin tf("ca n not ope n filen");exit(0);for(i=0;i <n ;i+)sca nf("%d%s%d",&stdi. nu m,stdi. name,&stdi.score);ai=stdi. num;bi=i;fwrite(&stdi,sizeof(struct stude nt),1,fout);fclose(fo

34、ut);读取void readstud(FILE *fin ,i nt j)/信息的 int i;fin=fope n("E:xueshe ng.txt","rb");fseek(fin,sizeof(struct student),0);fseek(fin,-sizeof(struct student),1);for(i=1;i<=j;i+)fseek(fi n,sizeof(struct stude nt),1);fread(&std0,sizeof(struct stude nt),1,fi n);printf("学号成绩 n");prin tf("%-6d%-10s%6dn",std0. nu m,std0. name,std0.score); fclose(fi n);/中序遍历B树void Prin tBTree(BTree t)if(t)int i=1;while(i<=t->ke ynum)Prin tBTree(t->ptri-1);prin tf("%dn",t->k