B树课程设计报告

.z.课程设计报告课程设计名称：数据构造课程设计课程设计题目：B-树算法的应用院〔系〕：专业：计算机科学与技术班级：学号：姓名：指导教师：-.z.目录1需求分析11.1课程设计的内容11.2B-树的描述12概要设计22.1总体设计思想22.2局部模块设想2查找关键字22.2.2将关键字插入结点，分裂结点，建立新的结点，建立B-树22.2.3搜索指定结点，新建文件23详细设计43.1主函数设计43.1.1设计思想43.1.2主流程图53.2函数设计53.3存储构造63.4函数流程图74运行调试174.1调试过程中遇到的问题及解决方法174.2运行结果174.3结论分析18参考文献19附录〔关键局部程序清单〕20-.z.1需求分析1.1课程设计的内容编写算法能将学生信息保存到文件中，能够为学生信息建立B-树索引，并能够利用B-树索引查找到指定学生的信息。建立B-树索引使用**为关键字。〔B-树中只含有**和该记录在文件中的位置信息〕要求：1.B-树的阶可以选择，要求给出一个完整班的学生信息。参考相应资料，独立完成课程设计任务。3．交标准课程设计报告和软件代码。1.2B-树的描述B-树是一种平衡的多路查找树，它在文件系统中很有用。在此先介绍树的构造。一棵m阶的B-树，或为空树，或为满足以下特性的m叉树：树中每个结点至多有m棵子树；假设根结点不是叶子结点，则至少有两棵子树；除根之外的所有非终端结点至少有[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〕所有的叶子结点都出现在同一层次上，并且不带信息〔可以看作是外部结点或查找失败的结点实际上这些结点根本不存在，指向这些结点的指针为空〕。-.z.2概要设计2.1总体设计思想首先将学生信息从键盘键入存到指定的文件中，在此每当输入一个学生的信息，对应学生信息的**将作为B-树的关键字，连同一起的该记录在文件中的信息这两局部作为结点插入到B-树中，插入的过程也就是建立B-树的过程，其中B-树的阶m在开场的时候已经确定了，当结点中的关键字的个数大于m-1时就开场分裂，并生成新的结点，按此规律即能建立好B-树，程序运行时只须输入任意学生的**，然后屏幕上将显示此**对应的学生的全部信息，由此即完成课程设计要求。2.2局部模块设想2.2.分别从结点中，B-树中查找关键字K，因为要想建树，就要插入结点，插入结点要先检验一下此时树中有没有次结点，intSearchNode(BTreep,intk)函数和ResultSearchBTree(BTreet,intk)函数实现了查找功能。2.2.在将关键字插入结点时，由于阶树m经决定了，当结点中的关键字个数大于m-1时就要分裂此结点，第[m/2]个结点被提升到上一结点，与此同时原结点中关键字前面的关键字还继续在此结点中，关键字之后的关键字需要存储到新生成的结点中，这样逐个结点才能顺利插入到B-树中。即此时的B-树已经建立好了。搜索指定结点，新建文件B-树索引过程就是搜索指定关键字的过程，从根结点开场，向子树结点中的关键字查找，当查找时即返回此时文件指针fp当前位置，假设查找失败，就继续查找，直到找到根结点为止，倘假设还没查找到就返回没有找到。我们需要把学生的相关信息从键盘输入到指定文件中，其中包括学生的姓名，**和家庭地址等信息，在利用文件中的fseek函数，使文件指针指向学生的相应信息位置，定义为整型，与结点中学生信息在文件中的位置信息相对应，运行时只需要输入学生**，屏幕上会显示相应的学生完整信息，此时索引过程完成。-.z.3详细设计3.1主函数设计设计思想B-树算法的实现，首先应该建立一个m阶的B-树〔在本算法中m设为5〕。在建立B-树过程中，首先输入一个关键字学生**序列〔为方便起见本算法使用整数序列，关键字个数设定为10〕，将这个整数序列存入数组中，然后从空树开场，依次将关键字插入B-树中，建立一个m阶的B-树。〔在输入学生信息的同时只是将学生**作为关键字存入文件中〕建树过程中，每插入一个关键字，首先应该判断出这个关键字在B-树中应该插入的位置，需要调用SearchBTree()和SearchNode()两个函数共同配合完成；然后调用InsertBTree()和Insert()函数进展插入，插入完成后，应该看该节点中关键字个数是否小于B-树的阶数m，当节点中插入的关键字个数不符合要求时，应该考虑节点分裂的情况〔根节点和子树节点的情况都应该考虑到，如果有节点分裂的情况，应该进展节点分裂，可以建立一个split()函数来实现这个功能；如果需要建立新的根节点，需要建立一个NewRoot()函数来完成这个功能。B-树建立成功后，返回指向该B-树根节点的指针。该算法要求具有查找任一指定学生信息的功能，可以输入任意一个学生的**，在B-树中查找该关键字，看该关键字是否存在在该B-树，如果存在，则返回该关键字对应的学生完整信息，否则查找不成功，则该**所对应的关键字不在该B-树中，以上即完成B-树索引过程。主流程图图3-1主函数流程图3.2函数设计在该算法中，设计了一个main()主函数和10个子函数，通过主函数调用子函数、子函数相互调用，完成设计要求的B-树的建立、在B-树中查找指定节点〔该算法中查找具体的关键字位置〕、B-树的遍历以及输出遍历序列等功能。函数在该算法中涉及到的各个函数的中文和英文名称分别为：主函数main()、节点查找函数SearchNode()、B-树查找函数SearchBTree()、节点插入函数Inset()、节点分裂函数split()、节点建立函数NewRoot()、B-树插入函数InsertBTree()、查找函数found()、中序遍历输出函数PrintBTree()、文件写函数savestud〔〕、文件读取函数readstud〔〕。函数调用关系图Readstud()函数Savestud()函数图3-2函数调用模块图Readstud()函数Savestud()函数函数调用关系说明主函数里面包含四个函数，即主函数中需调用四个函数分别为SearchBTree()、InsertBTree()、found()、PrintBTree()；执行SearchBTree()函数时需调用SearchNode()函数；执行InsertBTree()函数时，需要调用SearchNode()、NewRoot()、Insert()以及split()函数；执行found()函数时，要用到递归调用found()函数；执行PrintBTree()函数时，也要用到递归调用PrintBTree()函数。3.3存储构造在该设计的算法中，定义B-树中节点类型、B-树类型以及查找结果类型如下：#definem3//B-树的阶，暂定为3typedefstructBTNode{intkeynum;//节点中关键字个数structBTNode*parent;//指向双亲节点intkey[m+1];//关键字向量，0号单元未用structBTNode*ptr[m+1];//子树指针向量}BTNode,*BTree;//B-树节点和B-树的类型typedefstruct{BTNode*pt;//指向找到的节点inti;//在节点中的关键字序号inttag;//1：查找成功，0：查找失败}Result;//B-树的查找结果类型3.4函数流程图在这局部中，将每个函数分别用流程图表示出来，并且将每个函数的功能以及实现过程详细的表述出来，使得能够更加清晰、有条理表达出该算法。函数调用关系说明函数名：main()函数功能：输入关键字序列，调用B-树建立函数、查找函数、遍历输出函数实现过程：如图所示，输入一个关键字序列，存储到数组中。对于数组中每个**关键字，首先调用函数SearchBTree()，找出该关键字应该插入的位置，然后调用函数InsertBTree(),将关键字依次插入B-树中，插入完成后，返回指向B-树的根节点指针。然后按照要求输入要查找的**关键字，调用found()函数进展查找，返回查找结果〔可进展循环输入查找〕。并将查找的**所对应的学生完整信息输出在屏幕上。完成索引过程。图3-3主函数流程图节点查找函数函数名：SearchNode()功能：在节点中查找关键字，返回该关键字在节点中的位置图3-4SearchNode()函数流程图实现过程：如图(a)所示，SearchNode()函数代入的参数是指向关键字可能所在节点的指针p和关键字k，从该节点的第一个关键字找起，依次将要查找的关键字与节点中的关键字比较，返回结果是所给关键字应该在节点中的位置。B-树查找函数函数名称：SearchBTree()功能：从B-树的根节点开场查找，查找所给关键字在该B-树中的节点位置以及在所在节点中的位置，该函数返回结果为Result类型，result.i表示关键字在节点中应该插入的位置，result.pt表示关键字应该所在的节点，result.tag表示是否能够在B-树中查找到该关键字。图3-5SearchBTree()函数流程图实现过程：如图(b)所示，代入B-树的根节点指针和要查找的关键字，从根节点开场，对每个节点使用SearchNode()函数，查找所给关键字所在的节点以及在该节点中的位置，如果该关键字已经存在于B-树中，则返回关键字所在节点、以及所在序号以及查找到的标志；如果不存在，则返回应该插入的节点指针、在节点中的序号以及没有找到的标志。节点插入函数函数名：Insert()函数功能：将所给关键字插入到正确节点的正确位置图3-6Insert()函数流程图实现过程：如图(c)所示，代入指向所给关键字应该插入节点的指针、所给关键字、关键字应该插入的位置，然后再将该关键字插入到节点的正确位置上，节点关键字个数加1，返回指向该节点的指针q。节点分裂函数函数名：split()函数功能：当节点中关键字个数不符合要求时，进展节点分裂图3-7split()函数流程图实现过程：如图(d)所示，该函数带入的参数是指向要产生分裂的节点的指针q、节点最小子树个数s以及空指针ap，首先给ap分配BTree类型的空间，然后再将q中序号大于s的关键字插入到ap节点中，同时纸箱子树的指针也插入到ap中，然后再分别计算q和ap中的关键字个数，对q和ap进展处理。最后返回ap指针。节点建立函数函数名：NewRoot()函数功能：建立新的节点，并且返回指向该节点的指针。图3-8NewRoot()函数流程图实现过程：如图(e)所示，该函数的代入参数是根节点T、指向子树的指针p和ap以及关键字*，创立这个新节点，需要将关键字插入到该节点序号1的位置上，0号和1号的子树指针分别指向空。如果p和ap不为空，则它们的父节点指向T节点。该函数最后返回的是指针T。B-树建立函数函数名：InsertBTree()函数功能：从空树开场建立B-树，返回的是B-树的根指针。图3-9InsertBTree()函数流程图实现过程：如图(f)所示，该函数代入参数是根节点T、要插入到的节点q、要插入的关键字可以及在节点中应该插入的位置序号i。该函数从根节点开场建立B-树，当根节点为空时，需要建立新的根节点并且插入关键字；如果根节点不为空，则直接插入即可，但是插入完成后，要考虑是否有节点分裂的情况产生，入伏哦需要进展节点分裂，则要调用split()函数分裂节点〔根节点分裂以及子树节点分裂的情况都考虑到〕重新进展分裂插入。函数最后返回指向B-树根节点的指针T。查找函数函数名：found()图3-10found()函数流程图函数功能：查找指指定关键字，查找成功则返回在所在节点的序号，否则返回-1。实现过程：如图(g)所示，该函数代入参数是B-树根节点指针t以及关键字k，从根节点开场查找，如果查找到返回i值否则返回-1，在查找过程中低轨调用函数found()进展查找。文件随机读写输出函数函数名：fseek()功能：将位置指针按需要移动到任意位置，实现随即读写功能。图3-11fseek()函数流程图实现过程:需要查找学生相关信息时，只需输入对应的学生**，利用fseek()函数，将文件指针指到相应内存处，将所有该学生信息全部显示出来，完成索引过程。4运行调试4.1调试过程中遇到的问题及解决方法在调试程序的过程中，遇到的问题有多种，但是集中表现为语句错误、逻辑错误、参数未定义等方面。针对该算法中的这些问题，进展了具体分析，找到了正确的解决方法。4.1.1问题：missing';'before'}'；括号匹配不正确分析：这种问题在编译时最容易表达出来，因为如果出现这种错误，系统会进展提示。产生这种问题的原因是输入代码时疏忽，或是代入参数的类型与定义类型布匹配。如：定义BTree类型的指针p，引用的是&p,则会出现’{‘、’}’匹配有误，解决该问题，根据提示找到该符号的地方，进展改正即可。4.1.2问题：函数不能调用或赋值语句不能分析：这种问题在执行程序时出现，表现为执行到一半会出错。通常这种问题是由于编写算法算判断语句不完善造成的，通常解决方法是单步调试，找到出错的地方，即算法执行停顿的地方，修改错误的逻辑语句。4.2运行结果该设计最终要求实现B-树算法，根据该算法设定的参数，输入事先指定好的学生信息，按先后顺序从键盘输入到文件中，此时B-树已经建立好了，索引时只需输入任意一个学生的**，就可以得到该学生完整信息的运行结果：学生信息包括学生的姓名，**，成绩等。例如：输入的是：Zhao178Qian256Sun387Li434Zhou567Wu664Zheng739Wang879Feng968Chen1086程序会自动以**为关键字建立好B-树，请输入要查找的学生信息的**：例如：输入5；则输出：Zhou567当输入0的时候停顿索引，过程完毕！4.3结论分析在该算法中，实现了建立一个m阶的B-树，返回指向建好的B-树根节点的指针，并且能够查找指定的**关键字，假设查找成功，则返回该关键字所在学生的相关信息，否则查找不成。在调试程序的过程中，遇到了许多常识性的问题，通过不断的调试、改进，最终使程序能够运行，并且得到正确的运行结果。在这个过程中，能够不断地发现问题，并且自己独立的去解决多遇到的问题，这是课程设计过程中所不可缺少的精神。-.z.参考文献[1]."数据构造"〔用面向对象方法与C++描述〕，殷人昆等，清华大学出版社。[2]."算法与数据构造习题精解和实验指导"，宁正元等，清华大学出版社。[3]."数据构造课程实验"徐孝凯编著，清华大学出版社。[4]严蔚敏，吴伟民.数据构造(C语言版)［M］.：清华大学出版社，2006.[5]吕国英.算法设计与分析［M］.：清华大学出版社，2006.[6]徐宝文，李志.C程序设计语言［M］.：机械工业出版社，2004.[7]夏克俭.数据构造+算法［M］.：国防工业出版社，2001.[8]李春葆，曾慧，张植民.数据构造程序设计题典［M］.：清华大学出版社，2002.-.z.附录〔关键局部程序清单〕//B-树算法的应用#include"stdio.h"#include"math.h"#include"malloc.h"#include"stdlib.h"#include"fstream.h"#definem5#definen10typedefstructBTNode{intkeynum;structBTNode*parent;intkey[m+1];structBTNode*ptr[m+1]; intlocation[m+1];}BTNode,*BTree;typedefstruct{BTNode*pt;inti;inttag;}Result;structstudent{intnum; charname[10]; intscore;}std[n];inta[n],b[n];//在结点中查找关键字intSearchNode(BTreep,intk){inti=1;while(i<=p->keynum){if(k<p->key[i])returni-1;else if(k==p->key[i]) return-1;elsei++;}returni-1;}//在B树中查找关键字kResultSearchBTree(BTreet,intk)//t为B树根节点{BTreep=t,q=NULL;intfound=0;inti=0;Resultresult;while(p&&!found){i=SearchNode(p,k); if(i==-1) { result.pt=p; result.i=i; result.tag=1; returnresult; } while(p->ptr[i]) { p=p->ptr[i]; i=SearchNode(p,k); }if(i>0&&p->key[i]==k)found=1;else{q=p;p=p->ptr[i];}}if(found){result.pt=p;result.i=i;result.tag=1;}else{result.pt=q;result.i=i;result.tag=0;}returnresult;}//将关键字插入节点BTreeInsert(BTreeq,inti,int*,BTreeap,intl){//insertthekey*betweenthekey[i]andkey[i+1]//atthepointernodeqintj;for(j=q->keynum;j>i;j--){q->key[j+1]=q->key[j];q->location[j+1]=q->location[j];q->ptr[j+1]=q->ptr[j];}q->key[i+1]=*;q->ptr[i+1]=ap;q->location[i+1]=l;if(ap) ap->parent=q;q->keynum++;returnq;}//分裂节点BTreesplit(BTreeq,ints,BTreeap){//movekey[s+1...m],p->ptr[s...m]intthenewpointer*apinti,j;ap=(BTree)malloc(sizeof(BTNode));ap->ptr[0]=q->ptr[s];for(i=s+1,j=1;i<=q->keynum;i++,j++){ap->key[j]=q->key[i];ap->ptr[j]=q->ptr[i];ap->location[j]=q->location[i];}ap->keynum=q->keynum-s;ap->parent=q->parent;for(i=0;i<=q->keynum-s;i++) if(ap->ptr[i]) ap->ptr[i]->parent=ap; q->key[q->keynum]=0; q->location[q->keynum]=0; q->keynum=s-1; returnap;}//建立新的节点BTreeNewRoot(BTreeT,BTreep,int*,BTreeap,intz){T=(BTree)malloc(sizeof(BTNode));T->keynum=1;T->ptr[0]=p;T->ptr[1]=ap;T->key[1]=*;T->location[1]=z;if(p) p->parent=T;if(ap)ap->parent=T;T->parent=NULL;returnT;}//建立B-树BTreeInsertBTree(BTreeT,intK,BTreeq,inti,intl){//在m阶B树T上结点*q的key[i]与key[i+1]之间插入关键字K。//假设引起结点过大，则沿双亲链进展必要的结点分裂调整，使T仍是m阶B树。BTreeap;intfinished,needNewRoot,s;int*;if(!q)//T是空树(参数q初值为NULL)T=NewRoot(T,NULL,K,NULL,l);//生成仅含关键字K的根结点*Telse{*=K;ap=NULL;finished=needNewRoot=0;while(!needNewRoot&&!finished) {q=Insert(q,i,*,ap,l);//将*和ap分别插入到q->key[i+1]和q->ptr[i+1]if(q->keynum<m) finished=1;//插入完成else {//分裂结点*q//将q->key[s+1..m],q->ptr[s..m]和//q->location[s+1..m]移入新结点*aps=(m+1)/2; ap=split(q,s,ap); *=q->key[s]; l=q->location[s]; q->location[s]=0; q->key[s]=0;if(q->parent) {//在双亲结点*q中查找*的插入位置q=q->parent; i=SearchNode(q,*); } elseneedNewRoot=1;}//else}//whileif(needNewRoot)//根结点已分裂为结点*q和*apT=NewRoot(T,q,*,ap,l);//生成新根结点*T,q和ap为子树指针}returnT;}//InsertBTreeintfound(BTreeMT,intk)//查找关键字对应记录的存储位置{ inti;BTreep=MT; while(p!=NULL) { i=1; while(k>p->key[i]&&i<p->keynum) i++; if(k==p->key[i]) returnp->location[i]; elseif(k>p->key[i]) p=p->ptr[i]; elseif(k<p->key[i]) p=p->ptr[i-1]; } return-1;}voidsavestud(FILE*fout)//存储信息{ inti; if((fout=fopen("E:\\*uesheng.t*t","wb"))==NULL) { printf("cannotopenfile\n"); e*it(0); } for(i=0;i<n;i++) { scanf("%d%s%d",&std[i].num,std[i].name,&std[i].score); a[i]=std[i].num; b[i]=i; fwrite(&std[i],sizeof(structstudent),1,fout); } fclose(fout);}voidreadstud(FILE*fin,intj)//读取信息的{inti; fin=fopen("E:\\*uesheng.t*t","rb"); fseek(fin,sizeof(structstudent),0); fseek(fin,-sizeof(structstudent),1); for(i=1;i<=j;i++) { fseek(fin,sizeof(structstudent),1); } fread(&std[0],sizeof(structstudent),1,fin); printf("**成绩\n"); printf("%-6d%-10s%6d\n",std[0].num,std[0].name,std[0].score); fclose(fin)