《B树课程设计报告【沐风书苑】》由会员分享，可在线阅读，更多相关《B树课程设计报告【沐风书苑】（40页珍藏版）》请在金锄头文库上搜索。
1、课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目：B-树算法的应用院（系）：专 业：计算机科学与技术班 级： 学 号： 姓 名：指导教师： 教学f目 录1 需求分析11.1课程设计的内容11.2 B-树的描述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 调试过程中遇到的问题及解决办法174.2
2、 运行结果174.3 结论分析18参考文献19附 录（关键部分程序清单）20教学f 1 需求分析 1.1课程设计的内容编写算法能将学生信息保存到文件中，能够为学生信息建立B-树索引，并能够利用B-树索引查找到指定学生的信息。建立B-树索引使用学号为关键字。（ B-树中只含有学号和该记录在文件中的位置信息）要求：1. 1.B-树的阶可以选择，要求给出一个完整班的学生信息。2. 参考相应资料，独立完成课程设计任务。3. 3交规范课程设计报告和软件代码。1.2 B-树的描述B-树是一种平衡的多路查找树，它在文件系统中很有用。在此先介绍树的结构。一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：（
3、1） 树中每个结点至多有m棵子树；（2） 若根结点不是叶子结点，则至少有两棵子树；（3） 除根之外的所有非终端结点至少有m/2棵子树；（4） 所有非终端结点中包含下列信息数据（n,A0，K1,A1,K2,A2,Kn,An）其中：Ki(i=1,n)为关键字，且KiKi+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） 所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点实际
4、上这些结点根本不存在，指向这些结点的指针为空）。2 概要设计2.1 总体设计思想首先将学生信息从键盘键入存到指定的文件中，在此每当输入一个学生的信息，对应学生信息的学号将作为B-树的关键字，连同一起的该记录在文件中的信息这两部分作为结点插入到B-树中，插入的过程也就是建立B-树的过程，其中B-树的阶m在开始的时候已经确定了，当结点中的关键字的个数大于m-1时就开始分裂，并生成新的结点，按此规律即能建立好B-树，程序运行时只须输入任意学生的学号，然后屏幕上将显示此学号对应的学生的全部信息，由此即完成课程设计要求。2.2 局部模块构想2.2.1查找关键字分别从结点中，B-树中查找关键字K，因为要想
5、建树，就要插入结点，插入结点要先检验一下此时树中有没有次结点，int SearchNode(BTree p,int k)函数和Result SearchBTree(BTree t,int k)函数实现了查找功能。2.2.2 将关键字插入结点，分裂结点，建立新的结点，建立B-树在将关键字插入结点时，由于阶树m经决定了，当结点中的关键字个数大于m-1时就要分裂此结点，第m/2个结点被提升到上一结点，与此同时原结点中关键字前面的关键字还继续在此结点中，关键字之后的关键字需要存储到新生成的结点中，这样逐个结点才能顺利插入到B-树中。即此时的B-树已经建立好了。2.2.3 搜索指定结点，新建文件B-树索
6、引过程就是搜索指定关键字的过程，从根结点开始，向子树结点中的关键字查找，当查找时即返回此时文件指针fp当前位置，假如查找失败，就继续查找，直到找到根结点为止，倘若还没查找到就返回没有找到。我们需要把学生的相关信息从键盘输入到指定文件中，其中包括学生的姓名，学号和家庭地址等信息，在利用文件中的fseek函数，使文件指针指向学生的相应信息位置，定义为整型，与结点中学生信息在文件中的位置信息相对应，运行时只需要输入学生学号，屏幕上会显示相应的学生完整信息，此时索引过程完成。 3 详细设计3.1 主函数设计3.1.1 设计思想B-树算法的实现，首先应该建立一个m阶的B-树（在本算法中m设为5）。在建立
7、B-树过程中，首先输入一个关键字学生学号序列（为方便起见本算法使用整数序列，关键字个数设定为10），将这个整数序列存入数组中，然后从空树开始，依次将关键字插入B-树中，建立一个m阶的B-树。（在输入学生信息的同时只是将学生学号作为关键字存入文件中）建树过程中，每插入一个关键字，首先应该判断出这个关键字在B-树中应该插入的位置，需要调用SearchBTree()和SearchNode()两个函数共同配合完成；然后调用InsertBTree()和Insert()函数进行插入，插入完成后，应该看该节点中关键字个数是否小于B-树的阶数m，当节点中插入的关键字个数不符合要求时，应该考虑节点分裂的情况（根
8、节点和子树节点的情况都应该考虑到，如果有节点分裂的情况，应该进行节点分裂，可以建立一个split()函数来实现这个功能；如果需要建立新的根节点，需要建立一个NewRoot()函数来完成这个功能。B-树建立成功后，返回指向该B-树根节点的指针。该算法要求具有查找任一指定学生信息的功能，可以输入任意一个学生的学号，在B-树中查找该关键字，看该关键字是否存在在该B-树，如果存在，则返回该关键字对应的学生完整信息，否则查找不成功，则该学号所对应的关键字不在该B-树中，以上即完成B-树索引过程。3.1.2 主流程图图3-1 主函数流程图3.2函数设计在该算法中，设计了一个main()主函数和10个子函数
9、，通过主函数调用子函数、子函数相互调用，完成设计要求的B-树的建立、在B-树中查找指定节点（该算法中查找具体的关键字位置）、B-树的遍历以及输出遍历序列等功能。3.2.1 函数在该算法中涉及到的各个函数的中文和英文名称分别为：主函数main()、节点查找函数SearchNode()、B-树查找函数SearchBTree()、节点插入函数Inset()、节点分裂函数split()、节点建立函数NewRoot()、B-树插入函数InsertBTree()、查找函数found()、中序遍历输出函数PrintBTree()、文件写函数savestud（）、文件读取函数readstud（）。3.2.2
10、函数调用关系图Readstud()函数Savestud()函数 图3-2 函数调用模块图3.2.1 函数调用关系说明主函数里面包含四个函数，即主函数中需调用四个函数分别为SearchBTree()、InsertBTree()、found()、PrintBTree()；执行SearchBTree()函数时需调用SearchNode()函数；执行InsertBTree()函数时，需要调用SearchNode()、NewRoot()、Insert()以及split()函数；执行found()函数时，要用到递归调用found()函数；执行PrintBTree()函数时，也要用到递归调用PrintBTr
11、ee()函数。3.3存储结构在该设计的算法中，定义B-树中节点类型、B-树类型以及查找结果类型如下：#define m 3 /B-树的阶，暂定为3typedef struct BTNode int keynum; /节点中关键字个数 struct BTNode *parent; /指向双亲节点 int keym+1; /关键字向量，0号单元未用 struct BTNode *ptrm+1; /子树指针向量BTNode,*BTree; /B-树节点和B-树的类型typedef struct BTNode *pt; /指向找到的节点 int i; /在节点中的关键字序号 int tag; /1：查
12、找成功，0：查找失败Result; /B-树的查找结果类型3.4函数流程图在这部分中，将每个函数分别用流程图表示出来，并且将每个函数的功能以及实现过程详细的表述出来，使得能够更加清晰、有条理体现出该算法。3.4.1 函数调用关系说明函数名：main()函数功能：输入关键字序列，调用B-树建立函数、查找函数、遍历输出函数实现过程：如图2.1.1所示，输入一个关键字序列，存储到数组中。对于数组中每个学号关键字，首先调用函数SearchBTree()，找出该关键字应该插入的位置，然后调用函数InsertBTree(),将关键字依次插入B-树中，插入完成后，返回指向B-树的根节点指针。然后按照要求输入
13、要查找的学号关键字，调用found()函数进行查找，返回查找结果（可进行循环输入查找）。并将查找的学号所对应的学生完整信息输出在屏幕上。完成索引过程。 图3-3 主函数流程图3.4.2 节点查找函数函数名：SearchNode()功能：在节点中查找关键字，返回该关键字在节点中的位置 图3-4 SearchNode()函数流程图实现过程：如图2.1.2(a)所示，SearchNode()函数代入的参数是指向关键字可能所在节点的指针p和关键字k，从该节点的第一个关键字找起，依次将要查找的关键字与节点中的关键字比较，返回结果是所给关键字应该在节点中的位置。3.4.3 B-树查找函数函数名称：Sear
14、chBTree()功能：从B-树的根节点开始查找，查找所给关键字在该B-树中的节点位置以及在所在节点中的位置，该函数返回结果为Result类型，result.i表示关键字在节点中应该插入的位置，result.pt 表示关键字应该所在的节点，result.tag表示是否能够在B-树中查找到该关键字。 图 3-5 SearchBTree()函数流程图实现过程：如图 2.1.2(b)所示，代入B-树的根节点指针和要查找的关键字，从根节点开始，对每个节点使用SearchNode()函数，查找所给关键字所在的节点以及在该节点中的位置，如果该关键字已经存在于B-树中，则返回关键字所在节点、以及所在序号以及查找到的标志；如果不存在，则返回应该插入的节点指针、在节点中的序号以及没有找到的标志。3.4.4 节点插入函数函数名：Insert()函数功能：将所给关键字插入到正确节点的正确位置 图3-6 Insert
