B树课程设计报告[沐风书苑]

1、教学 f 课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目：B-树算法的应用 院（系）： 专 业：计算机科学与技术 班 级： 学 号： 姓 名： 指导教师： 教学 f 目目 录录 1 需求分析需求分析.1 1.1 课程设计的内容.1 1.2 B-树的描述.1 2 概要设计概要设计.2 2.1 总体设计思想 .2 2.2 局部模块构想 .2 2.2.1 查找关键字.2 2.2.2 将关键字插入结点，分裂结点，建立新的结点，建立 B-树.2 2.2.3 搜索指定结点，新建文件.2 3 详细设计详细设计.4 3.1 主函数设计 .4 3.1.1 设计思

2、想.4 3.1.2 主流程图.5 3.2 函数设计.5 3.3 存储结构.6 3.4 函数流程图.7 4 运行调试运行调试.17 4.1 调试过程中遇到的问题及解决办法.17 4.2 运行结果 .17 4.3 结论分析 .18 参考文献参考文献.19 附附 录（关键部分程序清单）录（关键部分程序清单）.20 教学 f 1 需求分析 1.1 课程设计的内容课程设计的内容 编写算法能将学生信息保存到文件中，能够为学生信息建立 B-树索引， 并能够利用 B-树索引查找到指定学生的信息。建立 B-树索引使用学号为关 键字。 （ B-树中只含有学号和该记录在文件中的位置信息） 要求： 1.1.B-树的阶

3、可以选择，要求给出一个完整班的学生信息。 2.参考相应资料，独立完成课程设计任务。 3.3交规范课程设计报告和软件代码。 1.2 B-树的描述树的描述 B-树是一种平衡的多路查找树，它在文件系统中很有用。在此先介绍树的 结构。一棵 m 阶的 B-树，或为空树，或为满足下列特性的 m 叉树： （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

4、(i=0,n) 为指向子树根结点的指针，且指针 Ai-1 所指子树中所有结点的关键字均 小于 Ki(i=1,n),An 所指子树中所有结点的关键字均大于 Kn,n(m/2 -1=nnum 否 开始 是 否 返回i-1 k小于p-keyi i加1 结束 是 图 3-4 SearchNode()函数流程图 实现过程：如图 2.1.2(a)所示，SearchNode()函数代入的参数是指向关键字可 能所在节点的指针 p 和关键字 k，从该节点的第一个关键字找起，依次将要查找 的关键字与节点中的关键字比较，返回结果是所给关键字应该在节点中的位置。 3.4.3 B-树查找函数树查找函数 函数名称：Sea

5、rchBTree() 功能：从 B-树的根节点开始查找，查找所给关键字在该 B-树中的节点位置 以及在所在节点中的位置，该函数返回结果为 Result 类型，result.i表示关键字 在节点中应该插入的位置，result.pt 表示关键字应该所在的节点，result.tag表 示是否能够在 B-树中查找到该关键字。 教学 f 赋初值：found=0；i=1 p不为空且found=0 否 开始 是 调用函数SearchNode，查找应 该插入的节点p以及插入位置i 否 赋值：result.pt=p; result.i=i;result.tag=1; found=1 赋值：result.pt=q

6、; result.i=i;result.tag=0; 结束 是 图 3-5 SearchBTree()函数流程图 实现过程：如图 2.1.2(b)所示，代入 B-树的根节点指针和要查找的关键字， 从根节点开始，对每个节点使用 SearchNode()函数，查找所给关键字所在的节点 以及在该节点中的位置，如果该关键字已经存在于 B-树中，则返回关键字所在节 点、以及所在序号以及查找到的标志；如果不存在，则返回应该插入的节点指针、 在节点中的序号以及没有找到的标志。 3.4.4 节点插入函数节点插入函数 函数名：Insert() 教学 f 函数功能：将所给关键字插入到正确节点的正确位置 j减1 结

7、束 j大于i 赋初值：j=q-keynum 否 开始 q-keyj后移，q-ptrj后移 是 ap=NULL 否 否 赋值：ap-parent=q 赋值q-keyi+1=x;q-ptri+1=ap; q-num加1 图 3-6 Insert()函数流程图 实现过程：如图 2.1.2(c)所示，代入指向所给关键字应该插入节点的指针、所 给关键字、关键字应该插入的位置，然后再将该关键字插入到节点的正确位置上， 节点关键字个数加 1，返回指向该节点的指针 q。 3.4.5 节点分裂函数节点分裂函数 教学 f 函数名：split() 函数功能：当节点中关键字个数不符合要求时，进行节点分裂 赋初值：ap

8、-ptr0=q-ptrs; 结束 将q节点中序号大于s的关键 字和指针插入到新建节点ap 开始 赋值：ap-keynum=q-keynum-s; ap-parent=q-parent; 赋值：q-keyq-keynum=0;q-keynum=s-1; 返回ap 将ap中子树指针父节点指向ap 图 3-7 split()函数流程图 实现过程：如图 2.1.2(d)所示，该函数带入的参数是指向要产生分裂的节点的 指针 q、节点最小子树个数 s 以及空指针 ap，首先给 ap 分配 BTree 类型的空间， 然后再将 q 中序号大于 s 的关键字插入到 ap 节点中，同时纸箱子树的指针也插入 到 a

9、p 中，然后再分别计算 q 和 ap 中的关键字个数，对 q 和 ap 进行处理。最后返 教学 f 回 ap 指针。 3.4.6 节点建立函数节点建立函数 函数名：NewRoot() 函数功能：建立新的节点，并且返回指向该节点的指针。 结束 是 给T分配空间 开始 返回T 是 赋值：p-parent=T 赋值：T-parent=NULL p！=NULL 否 否 赋值：T-keynum=1; T-ptr0=p; T-ptr1=ap; T-key1=x; ap！=NULL 赋值：ap-parent=T 图 3-8 NewRoot()函数流程图 实现过程：如图 2.1.2(e)所示，该函数的代入参数

10、是根节点 T、指向子树的指 针 p 和 ap 以及关键字 x，创建这个新节点，需要将关键字插入到该节点序号 1 的 教学 f 位置上，0 号和 1 号的子树指针分别指向空。如果 p 和 ap 不为空，则它们的父节 点指向 T 节点。该函数最后返回的是指针 T。 3.4.7 B-树建立函数树建立函数 函数名：InsertBTree() 函数功能：从空树开始建立 B-树，返回的是 B-树的根指针。 赋值：x=K; ap=NULL; finished=needNewRoot=0; 调用函数Insert，将返回值赋给q 结束 是 是 否 否 q为空 开始 返回T Finshed=0且 needNewR

11、oot=0 是 q-numptri-1; ikeynum 是 是 kptri-1！=NULL 否 赋值：p=p-ptri-1; 调用函数found，将返回值赋给i p-ptri-1！=NULL 否 图 3-10 found()函数流程图 函数功能：查找指指定关键字，查找成功则返回在所在节点的序号，否则返 回-1。 实现过程：如图 2.1.2(g)所示，该函数代入参数是 B-树根节点指针 t 以及关 键字 k，从根节点开始查找，如果查找到返回 i 值否则返回-1，在查找过程中低轨 教学 f 调用函数 found()进行查找。 3.4.9 文件随机读写输出函数文件随机读写输出函数 函数名：fsee

12、k() 功能：将位置指针按需要移动到任意位置，实现随即读写功能。 结束 是 开始 否 索引过程是否结束 fseek(fp,i*sizeof( struct student),0)_函数 输出相应学生信 息 输入待查找学生 信息对应的学号 图 3-11 fseek()函数流程图 实现过程: 需要查找学生相关信息时，只需输入对应的学生学号，利用 fseek()函数，将文件指针指到相应内存处，将所有该学生信息全部显示出来，完 成索引过程。 教学 f 4 运行调试 4.1 调试过程中遇到的问题及解决办法调试过程中遇到的问题及解决办法 在调试程序的过程中，遇到的问题有多种，但是集中表现为语句错误、逻辑

13、错误、参数未定义等方面。针对该算法中的这些问题，进行了具体分析，找到了 正确的解决办法。 4.1.1 语句错误语句错误 问题：missing ; before ；括号匹配不正确 分析：这种问题在编译时最容易体现出来，因为如果出现这种错误，系统会 进行提示。产生这种问题的原因是输入代码时疏忽，或是代入参数的类型与定义 类型布匹配。如：定义 BTree 类型的指针 p，引用的是 struct BTNode *parent; int keym+1; struct BTNode *ptrm+1; int locationm+1; BTNode,*BTree; typedef struct BTNode

14、 *pt; 教学 f int i; int tag; Result; struct student int num; char name10; int score; stdn; int an,bn; /在结点中查找关键字 int SearchNode(BTree p,int k) int i=1; while(ikeynum) if(kkeyi) return i-1; else if(k=p-keyi) return -1; else i+; 教学 f return i-1; /在 B 树中查找关键字 k Result SearchBTree(BTree t,int k)/t 为 B 树根节

15、点 BTree p=t,q=NULL; int found=0; int i=0; Result result; while(p if(i=-1) result.pt=p; result.i=i; result.tag=1; return result; while(p-ptri) 教学 f p=p-ptri; i=SearchNode(p,k); if(i0 else q=p; p=p-ptri; if(found) result.pt=p; result.i=i; result.tag=1; else result.pt=q; 教学 f result.i=i; result.tag=0;

16、return result; /将关键字插入节点 BTree Insert(BTree q,int i,int x,BTree ap,int l) / insert the key X between the keyi and keyi+1 / at the pointer node q int j; for(j=q-keynum;ji;j-) q-keyj+1=q-keyj; q- location j+1=q- location j; q-ptrj+1=q-ptrj; q-keyi+1=x; q-ptri+1=ap; q- location i+1=l; if(ap) 教学 f ap-pa

17、rent=q; q-keynum+; return q; /分裂节点 BTree split(BTree q,int s,BTree ap) /move keys+1.m,p-ptrs.m int the new pointer *ap int i,j; ap=(BTree)malloc(sizeof(BTNode); ap-ptr0=q-ptrs; for(i=s+1,j=1;ikeynum;i+,j+) ap-keyj=q-keyi; ap-ptrj=q-ptri; ap- location j=q- location i; ap-keynum=q-keynum-s; ap-parent=

18、q-parent; for(i=0;ikeynum-s;i+) if(ap-ptri) 教学 f ap-ptri-parent=ap; q-keyq-keynum=0; q- location q-keynum=0; q-keynum=s-1; return ap; /建立新的节点 BTree NewRoot(BTree T,BTree p,int x,BTree ap,int z) T=(BTree)malloc(sizeof(BTNode); T-keynum=1; T-ptr0=p; T-ptr1=ap; T-key1=x; T- location 1=z; if(p) p-parent

19、=T; if(ap) ap-parent=T; T-parent=NULL; return T; 教学 f /建立 B-树 BTree InsertBTree(BTree T,int K,BTree q,int i,int l) / 在 m 阶 B 树 T 上结点*q 的 keyi与 keyi+1之间插入关键字 K。 / 若引起结点过大，则沿双亲链进行必要的结点分裂调整，使 T 仍是 m 阶 B 树。 BTree ap; int finished, needNewRoot, s; int x; if(!q) / T 是空树(参数 q 初值为 NULL) T=NewRoot(T,NULL,K,N

20、ULL,l); / 生成仅含关键字 K 的根结点*T else x=K; ap=NULL; finished=needNewRoot=0; while(!needNewRoot / 将 x 和 ap 分别插入到 q-keyi+1和 q- ptri+1 if(q-keynumkeys+1.m, q-ptrs.m和 / q- location s+1.m移入新结点*ap s=(m+1)/2; ap=split(q,s,ap); x=q-keys; l=q- location s; q-locations=0; q-keys=0; if(q-parent) / 在双亲结点*q 中查找 x 的插入位置

21、 q=q-parent; i=SearchNode(q, x); else needNewRoot=1; / else / while if(needNewRoot) / 根结点已分裂为结点*q 和*ap T=NewRoot(T,q,x,ap,l); / 生成新根结点*T,q 和 ap 为子树指针 return T; 教学 f / InsertBTree int found(BTree MT,int k) /查找关键字对应记录的存储位置 int i; BTree p=MT; while(p!=NULL) i=1; while(kp-keyi if(k=p-keyi) return p- loc

22、ation i; else if(kp-keyi) p=p-ptri; else if(kkeyi) p=p-ptri-1; return -1; 教学 f void savestud(FILE *fout) /存 储信息 int i; if (fout=fopen(E:xuesheng.txt,wb)=NULL) printf(can not open filen); exit(0); for(i=0;in;i+) scanf(%d%s%d, ai=stdi.num; bi=i; fwrite( fclose(fout); void readstud(FILE *fin,int j) /读取

23、 信息的 int i; 教学 f fin=fopen(E:xuesheng.txt,rb); fseek(fin,sizeof(struct student),0); fseek(fin,-sizeof(struct student),1); for(i=1;i=j;i+) fseek(fin,sizeof(struct student),1); fread( printf(学号 姓名 成绩n); printf(%-6d%-10s%6dn,std0.num,,std0.score); fclose(fin); /中序遍历 B 树 void PrintBTree(BTree t

24、) if(t) int i=1; while(ikeynum) PrintBTree(t-ptri-1); 教学 f printf(%dn,t-keyi); i+; PrintBTree(t-ptri-1); void main() FILE *f1; BTree root=NULL; Result result; int i,x,arrayn; int en,h; printf(输入学生信息n); savestud(f1); for(i=0;in;i+) arrayi=ai; ei=bi; for(i=0;in;i+) 教学 f result=SearchBTree(root,arrayi); /寻找关键字在 B 树中应该 插入的位置 root=InsertBTree(root,arrayi,resul