（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（kkey[i]）
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->keynumfinished=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）//根结点已分裂为
升级会员 