广工数据结构实验设计报告-B树（难度1.4）.docx

数据结构设计性实验报告 课程名称 数据结构实验 题目名称 B树（难度1.4） 学生学院 计算机学院 专业班级 学 号 姓 名 指导教师 黄剑锋 2015年 06 月25日B树抽象数据类型实现一、设计简介本次设计在AnyviewCL自由编程平台上实现了B树的6种基本操作，并根据这个基本操作设计了友好的交际界面，操作简单易懂，并在AnyviewCL自由编程平台上可视化测试B树各个基本操作，保证了各基本的操作算法的正确性。经在AnyviewCL自由编程平台严格测试后，将本设计移植到Visual C+ 6.0平台生成可运行程序，并进行各个基本操作的测试，保证了程序运行的稳定性。其中数据来源为一组在01000内的int型随机数，但数据由typedef int KeyType定义，若需要改变数据类型，只需要将int替换成所需的数据类型即可。二、抽象数据类型定义及各种基本操作的描述ADT BTree数据对象：D是具有相同特征的数据元素集合。数据关系：若D为空集，则称为空树；（1）树中每个结点最多含有m棵子树；（2）若根结点不是叶子结点，则至少有2个子树；（3）除根结点之外的所有非终端结点至少有m/2棵子树；（4）每个非终端结点中包含信息：（n，A0，K1，A1，K2，A2，Kn，An）。其中：1）Ki（1=i=n）为关键字，且关键字按升序排序；2）指针Ai（0=i=n）指向子树的根结点，Ai-1指向子树中所有结点的关键字均小于Ki，且大于Ki-1；3）关键字的个数n必须满足：m/2-1=n pt, p - i, m);初始条件：树T存在，p - pt指向T中某个结点操作结果：在B树T上结点p - pt的keyi和keyi+1之间插入关键字k DeleteBTree(p - pt, p - i, m, T);初始条件：树T存在，p - pt指向T中某个结点操作结果：删除B树T上结点p - pt的关键字kPrintBTree(T);初始条件：树T存在操作结果：中序遍历B树DestroyBTree(T)初始条件：树T存在操作结果：销毁B树ADT BTree三、存储结构定义#include#include#include #define TRUE 1#define FALSE 0#define OVERFLOW -2#define OK 1#define ERROR 0typedef int KeyType;typedef int Status;typedef struct KeyType key; char data;Record;typedef struct BTNode int keynum; / 结点中关键字个数，即结点的大小 struct BTNode *parent; / 指向双亲结点 KeyType key21; / 关键字向量，0号单元未用 struct BTNode *ptr21; / 子树指针向量 Record *recptr21; / 记录指针向量，0号单元未用BTNode, *BTree; / B树结点和B树的类型typedef struct BTNode *pt; / 指向找到的结点 int i; / 1.m，在结点中的关键字序号 int tag; / 1:查找成功，0:查找失败restype,*result; / 在B树的查找结果类型四、关键算法设计流程图主函数：MAIN();功能：确定B树阶数与初始结点数，提供基本的菜单功能选择 函数名：int SearchNode(BTree p, int k);功能：在节点中查找关键字，返回该关键字在节点中的位置。函数名：void SearchBTree(BTree t, int k, result &SearchBTree);功能：在m阶B树t上查找关键码k，返回(pt,i,tag)。函数名：void split(BTree &q, int s, BTree &ap);功能：将结点q分裂成两个结点，前一半保留，后一半移入新生结点ap。函数名：void newroot(BTree &t, BTree p, int x, BTree ap);功能：生成新的根结点。函数名：void Insert(BTree &q, int i, int x, BTree ap);功能：将关键字ap分别插入到q-keyi+1和q-ptri+1中。函数名：void InsertBTree(BTree &t, int k, BTree q, int i, int m);功能：在B树t上结点*q的keyi和keyi+1之间插入关键字k。函数名：void Successor(BTree &p, int i);功能：由后继最下层非终端结点的最小关键字代替结点中关键字keyi。函数名：void Remove(BTree &p, int i);功能：从结点p中删除keyi。函数名：void Restore(BTree &p, int i, int m, BTree &T);功能：调整B树。函数名：void DeleteBTree(BTree p, int i, int m, BTree &T);功能：删除B树T上结点p的关键字k。五、 程序测试1、AnyviewCL自由编程平台上测试结果1）3阶B树的测试：此时B树的结构为：进行查找操作： 进行插入操作：插入后B树的结构为：进行删除操作（直接删除关键字）：删除关键字618后B树的结构为：此时对B树进行打印操作：继续进行删除操作：（删后结点与左兄弟合并）删除关键字798后B树的结构为：继续进行删除操作：（直接删除关键字）删除关键字796后B树的结构为：继续进行删除操作：（删后结点与右兄弟合并、父节点与左兄弟合并）删除关键字580后B树的结构为：继续进行删除操作：（删后结点与左兄弟合并、父节点与右兄弟合并，树的高度减1）删除关键字281后B树的结构为：进行B树的销毁：此时AnyviewCL的演示区情况为：2）5阶B树的测试：初始化B树的结构后，B树的结构为： 进行插入操作：插入关键字580后B树的结构为：进行删除操作：（删后结点与右兄弟合并）删除关键字21后B树的结构为：继续进行删除操作：（寻找后继结点并与之交换，删后向左兄弟借关键字）删除关键字596后B树的结构为： 进行打印B树操作：2、在Visual C+ 6.0平台测试： B树设置界面：进行B树初始话操作：进行打印B树操作：进行查找操作：进行插入操作： 插入关键字588后的B树结构为：进行删除操作：删除关键字532后的B树结构为：进行销毁B树操作：销毁后B树为空，无法打印：退出程序操作：六、思考与小结1、B树的高度：若N=1，则对任意一棵包含N个关键字、高度为h、阶数为m的B树：1）因为B树中每个结点最多有m棵子树，m-1个关键字，所以在一棵高度为h的m阶B树中的关键字个数应满足：N=logm(N+1);2）若让每个结点中的关键字个数达到最少，则容纳同样多关键字的B树的高度可达到最大，此时有hkey1.keynum找p-keyi=kkeyi+1，并返回i int i = 1; while(i keynum & k p-keyi) i+; return i;void SearchBTree(BTree t, int k, result &SearchBTree)/ 在m阶B树t上查找关键码k，返回(pt,i,tag)。/ 若查找成功，则特征值tag=1，指针pt所指结点中第i个关键码等于k；否则，/ 特征值tag=0,等于k的关键码记录应插入在指针pt所指结点中第i个和第i+1个关键码间 int i = 0, found = 0; BTree p = t, q = NULL; / 初始，p指向待查结点，q指向p的双亲 while(p != NULL & 0 = found) i = SearchNode(p, k); / 在p-key1.keynum找p-keyi=kkeyi+1 if(i0 & p-keyi = k) found = 1; / 找到待查关键字 else q = p; p = p-ptri-1; if(1 = found) / 查找成功 SearchBTree - pt = p; SearchBTree - i = i; SearchBTree - tag = 1; else / 查找不成功，返回key的插入位置i SearchBTree - pt = q; SearchBTree - i = i; SearchBTree - tag = 0; void split(BTree &q, int s, BTree &ap)/ 将结点q分裂成两个结点，前一半保留，后一半移入新生结点ap int i, j, n = q - keynum; ap = (BTNode*)malloc(sizeof(BTNode); / 生成新结点ap ap - ptr0 = q - ptrs; for(i = s + 1, j = 1; i keyj = q - keyi; ap - ptrj = q - ptri; ap - keynum = n - s; ap - parent = q - parent; for(i = 0; i ptri) ap - ptri - parent = ap; q - keynum = s - 1; / q的前一半保留，修改keynumvoid newroot(BTree &t, BTree p, int x, BTree ap)/ 生成新的根结点 t = (BTNode*)malloc(sizeof(BTNode); t - keynum = 1; t - ptr0 = p; t - ptr1 = ap; t - key1 = x; if(p!=NULL) p - parent = t; if(ap!=NULL) ap - parent = t; t - parent = NULL; / 新根的双亲是空指针void Insert(BTree &q, int i, int x, BTree ap) int j,n = q - keynum; for(j = n; j = i; j-) q - keyj+1 = q - keyj; q - ptrj+1 = q - ptrj; q - keyi = x; q - ptri = ap; if(ap!=NULL) ap - parent = q; q - keynum+;void InsertBTree(BTree &t, int k, BTree q, int i, int m)/ 在B树t上结点*q的keyi和keyi+1之间插入关键字k/ 若引起结点过大，则沿双亲链进行必要的结点分裂调整，使T仍是m阶的B树 int x, s; BTree ap; int finished = 0, neednewroot = 0; if(NULL=q) newroot(t, NULL, k, NULL); else x = k; ap = NULL; while(0 = neednewroot & 0 = finished) Insert(q, i, x, ap); / key和ap分别插到q-keyi+1和q-ptri+1 if(q-keynum keys; if(q - parent) q = q - parent; i = SearchNode(q, x); / 在双亲结点*q中查找x的插入位置 else neednewroot = 1; if(1 = neednewroot) / t是空树或者根结点已分裂为结点q和ap newroot(t, q, x, ap); / 生成含信息(t,x,ap)的新的根结点root void Successor(BTree &p, int i)/由后继最下层非终端结点的最小关键字代替结点中关键字keyi BTNode *u; u = p - ptri; while(NULL != u - ptr0) /找出关键字的后继 u = u - ptr0; p - keyi = u - key1; p = u;void Remove(BTree &p, int i)/从结点p中删除keyi int j,n = p - keynum; for(j = i; j keyj = p - keyj+1; p - ptrj = p - ptrj+1; /free(p - ptrn); /p - ptrn = NULL; p - keynum - ;void Restore(BTree &p, int i, int m, BTree &T)/调整B树 int j; BTree ap = p - parent; BTree lc, rc, pr; int finished = 0, r = 0; while(0 = finished) r = 0; while(ap - ptrr != p) /确定p在ap子树的位置 r+; if(r = 0) r+; lc = NULL; rc = ap - ptrr; else if(r = ap - keynum) rc = NULL; lc = ap - ptrr-1; else lc = ap - ptrr-1; rc = ap - ptrr+1; if(r 0 & lc != NULL & (lc - keynum (m - 1) / 2) /向左兄弟借关键字 p - keynum +; for(j = p - keynum; j 1; j-) /结点关键字右移 p - keyj = p - keyj-1; p - ptrj = p - ptrj-1; p - key1 = ap - keyr; /父亲插入到结点 p - ptr1 = p - ptr0; p - ptr0 = lc - ptrlc - keynum; if(NULL != p - ptr0) /修改p中的子女的父结点为p p - ptr0 - parent = p; ap - keyr = lc - keylc - keynum; /左兄弟上移到父亲位置 lc - keynum -; finished = 1; break; else if(ap - keynum r & rc != NULL & (rc - keynum (m - 1) / 2) /向右兄弟借关键字 p - keynum +; p - keyp - keynum = ap - keyr; /父亲插入到结点 p - ptrp - keynum = rc - ptr0; if(NULL != p - ptrp - keynum) /修改p中的子女的父结点为p p - ptrp - keynum - parent = p; ap - keyr = rc - key1; /右兄弟上移到父亲位置 rc - ptr0 = rc - ptr1; for(j = 1; j keynum; j+) /右兄弟结点关键字左移 rc - keyj = rc - keyj+1; rc - ptrj = rc - ptrj+1; rc - keynum -; finished = 1; break; r = 0; while(ap - ptrr != p) /重新确定p在ap子树的位置 r+; if(r 0 & (ap - ptrr-1 - keynum ptrr - 1; p - keynum +; for(j = p - keynum; j 1; j- ) /将p结点关键字和指针右移1位 p - keyj = p - keyj-1; p - ptrj = p - ptrj-1; p - key1 = ap - keyr; /父结点的关键字与p合并 p - ptr1 = p - ptr0; /从左兄弟右移一个指针 ap - ptrr+1 = lc; for(j = 1; j keynum + p - keynum; j+) /将结点p中关键字和指针移到p左兄弟中 lc-keylc - keynum + j = p - keyj; lc-ptrlc - keynum + j = p - ptrj; if(p - ptr0) /修改p中的子女的父结点为lc for(j = 1; j keynum; j+) p - ptrp - keynum + j - parent = lc; lc - keynum = lc - keynum + p - keynum; /合并后关键字的个数 ap - keynum-; pr = p; free(pr); /释放p结点空间 pr = NULL; p = lc; else /与右兄弟合并 rc = ap - ptrr + 1; if(r = 0) r +; p - keynum +; p - keyp - keynum = ap - keyr; /父结点的关键字与p合并 p - ptrp - keynum = rc - ptr0; /从右兄弟左移一个指针 rc - keynum = p - keynum + rc - keynum; /合并后关键字的个数 ap - ptrr-1 = rc; for(j = 1; j keynum - p - keynum); j+) /将p右兄弟关键字和指针右移 rc-keyp - keynum + j = rc - keyj; rc-ptrp - keynum + j = rc - ptrj; for(j = 1; j keynum; j+) /将结点p中关键字和指针移到p右兄弟中 rc-keyj = p - keyj; rc-ptrj = p - ptrj; rc-ptr0 = p - ptr0; if(p - ptr0) /修改p中的子女的父结点为rc for(j = 1; j keynum; j+) p - ptrp - keynum + j - parent = rc; for(j = r; j keynum; j+) /将父结点中关键字和指针左移 ap - keyj = ap - keyj + 1; ap - ptrj = ap - ptrj + 1; ap - keynum-; /父结点的关键字个数减1 pr = p; free(pr); /释放p结点空间 pr = NULL; p = rc; ap = ap - parent; if(p - parent - keynum = (m-1)/2 | (NULL = ap & p - parent - keynum 0) finished = 1; else if(NULL = ap) /若调整后出现空的根结点，则删除该根结点，树高减1 pr = T; T = p; /根结点下移 free(pr); pr = NULL; finished = 1; p = p - parent; void DeleteBTree(BTree p, int i, int m, BTree &T)/ 删除B树T上结点p的关键字k if(p-ptri-1!=NULL) / 若不是最下层非终端结点 Successor(p, i); / 由后继最下层非终端结点的最小关键字代替它 DeleteBTree(p, 1, m, T); / 变成删除最下层非终端结点中的最小关键字 else / 若是最下层非终端结点 Remove(p, i); / 从结点p中删除keyi if(p-keynum (m-1)/2) / 删除后关键字个数小于（m-1）/2 Restore(p, i, m, T); / 调整B