东北大学数据结构B树算法的应用实验报告docx.docx
- 文档编号:1250702
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:37
- 大小:403.32KB
东北大学数据结构B树算法的应用实验报告docx.docx
《东北大学数据结构B树算法的应用实验报告docx.docx》由会员分享,可在线阅读,更多相关《东北大学数据结构B树算法的应用实验报告docx.docx(37页珍藏版)》请在冰点文库上搜索。
东北大学数据结构B树算法的应用实验报告docx
课程设计报告
课程设计名称:
数据结构课程设计
课程设计题目:
B-树算法的应用
1需求分析
1.1课程设计的内容
编写算法能将学生信息保存到文件中,能够为学生信息建立B-树索引,并能够利用B-树索引查找到指定学生的信息。
建立B-树索引使用学号为关键字。
(B-树中只含有学号和该记录在文件中的位置信息)
要求:
1.1.B-树的阶可以选择,要求给出一个完整班的学生信息。
2.参考相应资料,独立完成课程设计任务。
3.3.交规范课程设计报告和软件代码。
1.2B-树的描述
B-树是一种平衡的多路查找树,它在文件系统中很有用。
在此先介绍树的结构。
一棵m阶的B-树,或为空树,或为满足下列特性的m叉树:
(1)树中每个结点至多有m棵子树;
(2)若根结点不是叶子结点,则至少有两棵子树;
(3)除根之外的所有非终端结点至少有[m/2]棵子树;
(4)所有非终端结点中包含下列信息数据
(n,A0,K1,A1,K2,A2,…,Kn,An)
其中:
Ki(i=1,…,n)为关键字,且Ki (5)所有的叶子结点都出现在同一层次上,并且不带信息(可以看作是外部结点或查找失败的结点实际上这些结点根本不存在,指向这些结点的指针为空)。 2概要设计 2.1总体设计思想 首先将学生信息从键盘键入存到指定的文件中,在此每当输入一个学生的信息,对应学生信息的学号将作为B-树的关键字,连同一起的该记录在文件中的信息这两部分作为结点插入到B-树中,插入的过程也就是建立B-树的过程,其中B-树的阶m在开始的时候已经确定了,当结点中的关键字的个数大于m-1时就开始分裂,并生成新的结点,按此规律即能建立好B-树,程序运行时只须输入任意学生的学号,然后屏幕上将显示此学号对应的学生的全部信息,由此即完成课程设计要求。 2.2局部模块构想 2.2.1查找关键字 分别从结点中,B-树中查找关键字K,因为要想建树,就要插入结点,插入结点要先检验一下此时树中有没有次结点,intSearchNode(BTreep,intk)函数和ResultSearchBTree(BTreet,intk)函数实现了查找功能。 2.2.2将关键字插入结点,分裂结点,建立新的结点,建立B-树 在将关键字插入结点时,由于阶树m经决定了,当结点中的关键字个数大于m-1时就要分裂此结点,第[m/2]个结点被提升到上一结点,与此同时原结点中关键字前面的关键字还继续在此结点中,关键字之后的关键字需要存储到新生成的结点中,这样逐个结点才能顺利插入到B-树中。 即此时的B-树已经建立好了。 2.2.3搜索指定结点,新建文件 B-树索引过程就是搜索指定关键字的过程,从根结点开始,向子树结点中的关键字查找,当查找时即返回此时文件指针fp当前位置,假如查找失败,就继续查找,直到找到根结点为止,倘若还没查找到就返回没有找到。 我们需要把学生的相关信息从键盘输入到指定文件中,其中包括学生的姓名,学号和家庭地址等信息,在利用文件中的fseek函数,使文件指针指向学生的相应信息位置,定义为整型,与结点中学生信息在文件中的位置信息相对应,运行时只需要输入学生学号,屏幕上会显示相应的学生完整信息,此时索引过程完成。 3详细设计 3.1主函数设计 3.1.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.2主流程图 图3-1主函数流程图 3.2函数设计 在该算法中,设计了一个main()主函数和10个子函数,通过主函数调用子函数、子函数相互调用,完成设计要求的B-树的建立、在B-树中查找指定节点(该算法中查找具体的关键字位置)、B-树的遍历以及输出遍历序列等功能。 3.2.1函数 在该算法中涉及到的各个函数的中文和英文名称分别为: 主函数main()、节点查找函数SearchNode()、B-树查找函数SearchBTree()、节点插入函数Inset()、节点分裂函数split()、节点建立函数NewRoot()、B-树插入函数InsertBTree()、查找函数found()、中序遍历输出函数PrintBTree()、文件写函数savestud()、文件读取函数readstud()。 3.2.2函数调用关系图 图3-2函数调用模块图 3.2.1函数调用关系说明 主函数里面包含四个函数,即主函数中需调用四个函数分别为SearchBTree()、InsertBTree()、found()、PrintBTree();执行SearchBTree()函数时需调用SearchNode()函数;执行InsertBTree()函数时,需要调用SearchNode()、NewRoot()、Insert()以及split()函数;执行found()函数时,要用到递归调用found()函数;执行PrintBTree()函数时,也要用到递归调用PrintBTree()函数。 3.3存储结构 在该设计的算法中,定义B-树中节点类型、B-树类型以及查找结果类型如下: #definem3//B-树的阶,暂定为3 typedefstructBTNode { 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函数流程图 在这部分中,将每个函数分别用流程图表示出来,并且将每个函数的功能以及实现过程详细的表述出来,使得能够更加清晰、有条理体现出该算法。 3.4.1函数调用关系说明 函数名: main() 函数功能: 输入关键字序列,调用B-树建立函数、查找函数、遍历输出函数 实现过程: 如图2.1.1所示,输入一个关键字序列,存储到数组中。 对于数组中每个学号关键字,首先调用函数SearchBTree(),找出该关键字应该插入的位置,然后调用函数InsertBTree(),将关键字依次插入B-树中,插入完成后,返回指向B-树的根节点指针。 然后按照要求输入要查找的学号关键字,调用found()函数进行查找,返回查找结果(可进行循环输入查找)。 并将查找的学号所对应的学生完整信息输出在屏幕上。 完成索引过程。 图3-3主函数流程图 3.4.2节点查找函数 函数名: SearchNode() 功能: 在节点中查找关键字,返回该关键字在节点中的位置 图3-4SearchNode()函数流程图 实现过程: 如图2.1.2(a)所示,SearchNode()函数代入的参数是指向关键字可能所在节点的指针p和关键字k,从该节点的第一个关键字找起,依次将要查找的关键字与节点中的关键字比较,返回结果是所给关键字应该在节点中的位置。 3.4.3B-树查找函数 函数名称: SearchBTree() 功能: 从B-树的根节点开始查找,查找所给关键字在该B-树中的节点位置以及在所在节点中的位置,该函数返回结果为Result类型,result.i表示关键字在节点中应该插入的位置,result.pt表示关键字应该所在的节点,result.tag表示是否能够在B-树中查找到该关键字。 图3-5SearchBTree()函数流程图 实现过程: 如图2.1.2(b)所示,代入B-树的根节点指针和要查找的关键字,从根节点开始,对每个节点使用SearchNode()函数,查找所给关键字所在的节点以及在该节点中的位置,如果该关键字已经存在于B-树中,则返回关键字所在节点、以及所在序号以及查找到的标志;如果不存在,则返回应该插入的节点指针、在节点中的序号以及没有找到的标志。 3.4.4节点插入函数 函数名: Insert() 函数功能: 将所给关键字插入到正确节点的正确位置 图3-6Insert()函数流程图 实现过程: 如图2.1.2(c)所示,代入指向所给关键字应该插入节点的指针、所给关键字、关键字应该插入的位置,然后再将该关键字插入到节点的正确位置上,节点关键字个数加1,返回指向该节点的指针q。 3.4.5节点分裂函数 函数名: split() 函数功能: 当节点中关键字个数不符合要求时,进行节点分裂 图3-7split()函数流程图 实现过程: 如图2.1.2(d)所示,该函数带入的参数是指向要产生分裂的节点的指针q、节点最小子树个数s以及空指针ap,首先给ap分配BTree类型的空间,然后再将q中序号大于s的关键字插入到ap节点中,同时纸箱子树的指针也插入到ap中,然后再分别计算q和ap中的关键字个数,对q和ap进行处理。 最后返回ap指针。 3.4.6节点建立函数 函数名: NewRoot() 函数功能: 建立新的节点,并且返回指向该节点的指针。 图3-8NewRoot()函数流程图 实现过程: 如图2.1.2(e)所示,该函数的代入参数是根节点T、指向子树的指针p和ap以及关键字x,创建这个新节点,需要将关键字插入到该节点序号1的位置上,0号和1号的子树指针分别指向空。 如果p和ap不为空,则它们的父节点指向T节点。 该函数最后返回的是指针T。 3.4.7B-树建立函数 函数名: InsertBTree() 函数功能: 从空树开始建立B-树,返回的是B-树的根指针。 图3-9InsertBTree()函数流程图 实现过程: 如图2.1.2(f)所示,该函数代入参数是根节点T、要插入到的节点q、要插入的关键字可以及在节点中应该插入的位置序号i。 该函数从根节点开始建立B-树,当根节点为空时,需要建立新的根节点并且插入关键字;如果根节点不为空,则直接插入即可,但是插入完成后,要考虑是否有节点分裂的情况产生,入伏哦需要进行节点分裂,则要调用split()函数分裂节点(根节点分裂以及子树节点分裂的情况都考虑到)重新进行分裂插入。 函数最后返回指向B-树根节点的指针T。 3.4.8查找函数 函数名: found() 图3-10found()函数流程图 函数功能: 查找指指定关键字,查找成功则返回在所在节点的序号,否则返回-1。 实现过程: 如图2.1.2(g)所示,该函数代入参数是B-树根节点指针t以及关键字k,从根节点开始查找,如果查找到返回i值否则返回-1,在查找过程中低轨调用函数found()进行查找。 3.4.9文件随机读写输出函数 函数名: fseek() 功能: 将位置指针按需要移动到任意位置,实现随即读写功能。 图3-11fseek()函数流程图 实现过程: 需要查找学生相关信息时,只需输入对应的学生学号,利用fseek()函数,将文件指针指到相应内存处,将所有该学生信息全部显示出来,完成索引过程。 4运行调试 4.1调试过程中遇到的问题及解决办法 在调试程序的过程中,遇到的问题有多种,但是集中表现为语句错误、逻辑错误、参数未定义等方面。 针对该算法中的这些问题,进行了具体分析,找到了正确的解决办法。 4.1.1语句错误 问题: missing';'before'}';括号匹配不正确 分析: 这种问题在编译时最容易体现出来,因为如果出现这种错误,系统会进行提示。 产生这种问题的原因是输入代码时疏忽,或是代入参数的类型与定义类型布匹配。 如: 定义BTree类型的指针p,引用的是&p,则会出现’{‘、’}’匹配有误,解决该问题,根据提示找到该符号的地方,进行改正即可。 4.1.2逻辑错误 问题: 函数不能调用或赋值语句不能 分析: 这种问题在执行程序时出现,表现为执行到一半会出错。 通常这种问题是由于编写算法算判断语句不完善造成的,通常解决办法是单步调试,找到出错的地方,即算法执行停止的地方,修改错误的逻辑语句。 4.2运行结果 该设计最终要求实现B-树算法,根据该算法设定的参数,输入事先指定好的学生信息,按先后顺序从键盘输入到文件中,此时B-树已经建立好了,索引时只需输入任意一个学生的学号,就可以得到该学生完整信息的运行结果: 学生信息包括学生的姓名,学号,成绩等。 例如: 输入的是: Zhao178 Qian256 Sun387 Li434 Zhou567 Wu664 Zheng739 Wang879 Feng968 Chen1086 程序会自动以学号为关键字建立好B-树,请输入要查找的学生信息的学号: 例如: 输入5; 则输出: Zhou567 当输入0的时候停止索引,过程结束! 4.3结论分析 在该算法中,实现了建立一个m阶的B-树,返回指向建好的B-树根节点的指针,并且能够查找指定的学号关键字,若查找成功,则返回该关键字所在学生的相关信息,否则查找不成。 在调试程序的过程中,遇到了许多常识性的问题,通过不断的调试、改进,最终使程序能够运行,并且得到正确的运行结果。 在这个过程中,能够不断地发现问题,并且自己独立的去解决多遇到的问题,这是课程设计过程中所不可缺少的精神。 参考文献 [1].《数据结构》(用面向对象方法与C++描述),殷人昆等,清华大学出版社。 [2].《算法与数据结构习题精解和实验指导》,宁正元等,清华大学出版社。 [3].《数据结构课程实验》徐孝凯编著,清华大学出版社。 [4]严蔚敏,吴伟民.数据结构(C语言版)[M].北京: 清华大学出版社,2006. [5]吕国英.算法设计与分析[M].北京: 清华大学出版社,2006. [6]徐宝文,李志.C程序设计语言[M].北京: 机械工业出版社,2004. [7]夏克俭.数据结构+算法[M].北京: 国防工业出版社,2001. [8]李春葆,曾慧,张植民.数据结构程序设计题典[M].北京: 清华大学出版社,2002. 附录(关键部分程序清单) //B-树算法的应用 #include"stdio.h" #include"math.h" #include"malloc.h" #include"stdlib.h" #include"fstream.h" #definem5 #definen10 typedefstructBTNode { 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 returni-1; else if(k==p->key[i]) return-1; elsei++; } returni-1; } //在B树中查找关键字k ResultSearchBTree(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,intx,BTreeap,intl) { //insertthekeyXbetweenthekey[i]andkey[i+1] //atthepointernodeq intj; 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]=x; 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*ap inti,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,intx,BTreeap,intz) { T=(BTree)malloc(sizeof(BTNode)); T->keynum=1; T->ptr[0]=p; T->ptr[1]=ap; T->key[1]=x; 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; intx; if(! q)//T是空树(参数q初值为NULL) T=NewRoot(T,NULL,K,NULL,l);//生成仅含关键字K的根结点*T else { x=K;ap=NULL;finished=needNewRoot=0; while(! needNewRoot&&! finished) { q=Insert(q,i,x,ap,l);//将x和ap分别插入到q->key[i+1]和q->ptr[i+1] if(q->keynum finished=1;//插入完成 else {//分裂结点*q //将q->key[s+1..m],q->ptr[s..m]和 //q->location[s+1..m]移入新结点*ap s=(m+1)/2; ap=split(q,s,ap); x=q->key[s]; l=q->location[s]; q->location[s]=0; q->key[s]=0; if(q->parent) {//在双亲结点*q中查找x的插入位置 q=q->parent; i=SearchNode(q,x); } elseneedNewRoot=1; }//else }//while if(needNewRoot)//根结点已分裂为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 东北大学 数据结构 算法 应用 实验 报告 docx