数据结构课程设计-b-树算法的应用

《数据结构课程设计-b-树算法的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、课程设计报告课程设计名称：数据结构课程设计课程设计题目：B-树算法的应用院（系）：专业：计算机科学与技术班级：学号：姓名：指导教师：目录1需求分析11.1课程设计的内容11.2B-树的描述12概要设计22.1总体设计思想22.2局部模块构想22.2.1查找关键字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调试过程中遇到的问题

2、及解决办法174.2运行结果174.3结论分析18参考文献19附录（关键部分程序清单）20341需求分析1.1课程设计的内容编写算法能将学生信息保存到文件中，能够为学生信息建立B-树索引，并能够利用B-树索引查找到指定学生的信息。建立B-树索引使用学号为关键字。（B-树中只含有学号和该记录在文件中的位置信息）要求：1.1.B-树的阶可以选择，要求给出一个完整班的学生信息。2.参考相应资料，独立完成课程设计任务。3.3．交规范课程设计报告和软件代码。1.2B-树的描述B-树是一种平衡的多路查找树，它在文件系统中很有用。

3、在此先介绍树的结构。一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：（1）树中每个结点至多有m棵子树；（2）若根结点不是叶子结点，则至少有两棵子树；（3）除根之外的所有非终端结点至少有[m/2]棵子树；（4）所有非终端结点中包含下列信息数据（n,A0，K1,A1,K2,A2,…,Kn,An）其中：Ki(i=1,…,n)为关键字，且Ki

4、均大于Kn,n([m/2]-1<=n<=m-1)为关键字的个数（或n+1为子树个数）。（5）所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点实际上这些结点根本不存在，指向这些结点的指针为空）。342概要设计2.1总体设计思想首先将学生信息从键盘键入存到指定的文件中，在此每当输入一个学生的信息，对应学生信息的学号将作为B-树的关键字，连同一起的该记录在文件中的信息这两部分作为结点插入到B-树中，插入的过程也就是建立B-树的过程，其中B-树的阶m在开始的时候已经确定了，当结点中的关键字的

5、个数大于m-1时就开始分裂，并生成新的结点，按此规律即能建立好B-树，程序运行时只须输入任意学生的学号，然后屏幕上将显示此学号对应的学生的全部信息，由此即完成课程设计要求。2.2局部模块构想2.2.1查找关键字分别从结点中，B-树中查找关键字K，因为要想建树，就要插入结点，插入结点要先检验一下此时树中有没有次结点，intSearchNode(BTreep,intk)函数和ResultSearchBTree(BTreet,intk)函数实现了查找功能。2.2.2将关键字插入结点，分裂结点，建立新的结点，建立B-树在将关

6、键字插入结点时，由于阶树m经决定了，当结点中的关键字个数大于m-1时就要分裂此结点，第[m/2]个结点被提升到上一结点，与此同时原结点中关键字前面的关键字还继续在此结点中，关键字之后的关键字需要存储到新生成的结点中，这样逐个结点才能顺利插入到B-树中。即此时的B-树已经建立好了。2.2.3搜索指定结点，新建文件B-树索引34过程就是搜索指定关键字的过程，从根结点开始，向子树结点中的关键字查找，当查找时即返回此时文件指针fp当前位置，假如查找失败，就继续查找，直到找到根结点为止，倘若还没查找到就返回没有找到。我们需要把

7、学生的相关信息从键盘输入到指定文件中，其中包括学生的姓名，学号和家庭地址等信息，在利用文件中的fseek函数，使文件指针指向学生的相应信息位置，定义为整型，与结点中学生信息在文件中的位置信息相对应，运行时只需要输入学生学号，屏幕上会显示相应的学生完整信息，此时索引过程完成。343详细设计3.1主函数设计3.1.1设计思想B-树算法的实现，首先应该建立一个m阶的B-树（在本算法中m设为5）。在建立B-树过程中，首先输入一个关键字学生学号序列（为方便起见本算法使用整数序列，关键字个数设定为10），将这个整数序列存入数组中

8、，然后从空树开始，依次将关键字插入B-树中，建立一个m阶的B-树。（在输入学生信息的同时只是将学生学号作为关键字存入文件中）建树过程中，每插入一个关键字，首先应该判断出这个关键字在B-树中应该插入的位置，需要调用SearchBTree()和SearchNode()两个函数共同配合完成；然后调用InsertBTree()和Insert()函数进行