资源描述：
《广工数据结构实验设计报告btree》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构设计性实验报告课程名称数据结构实验题目名称B树（难度1.4）学生学院计算机学院专业班级学号姓名指导教师黄剑锋2015年06月25日33B树抽象数据类型实现一、设计简介本次设计在AnyviewCL自由编程平台上实现了B树的6种基本操作，并根据这个基本操作设计了友好的交际界面，操作简单易懂，并在AnyviewCL自由编程平台上可视化测试B树各个基本操作，保证了各基本的操作算法的正确性。经在AnyviewCL自由编程平台严格测试后，将本设计移植到VisualC++6.0平台生成可运行程序，并进行各个基本操作的测试，保证了程序运行的稳定性。其中数据来源为一组在0~1000内的
2、int型随机数，但数据由typedefintKeyType定义，若需要改变数据类型，只需要将int替换成所需的数据类型即可。二、抽象数据类型定义及各种基本操作的描述ADTBTree{数据对象：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）指向子
3、树的根结点，Ai-1指向子树中所有结点的关键字均小于Ki，且大于Ki-1；3）关键字的个数n必须满足：┌m/2┐-1<=n<=m-1。（5）所有的叶子节点都在同一层，子叶结点不包含任何信息。基本操作P：CreatBTree(&T,n,m);初始条件：初始化关键字个数n大于等于0，B树的阶数m大于3小于等于20。操作结果：构建一棵阶数为m，含有n个关键字的B树。SearchBTree(T,k,&p);33初始条件：树T存在。操作结果：在m阶B树t上查找关键字k，返回(pt,i,tag)。InsertBTree(&T,k,p->pt,p->i,m);初始条件：树T存在，p->pt
4、指向T中某个结点操作结果：在B树T上结点p->pt的key[i]和key[i+1]之间插入关键字kDeleteBTree(p->pt,p->i,m,T);初始条件：树T存在，p->pt指向T中某个结点操作结果：删除B树T上结点p->pt的关键字kPrintBTree(T);初始条件：树T存在操作结果：中序遍历B树DestroyBTree(T)初始条件：树T存在操作结果：销毁B树}ADTBTree三、存储结构定义#include#include#include#defineTRUE1#defineFALSE0#defineO
5、VERFLOW-2#defineOK1#defineERROR0typedefintKeyType;typedefintStatus;33typedefstruct{KeyTypekey;chardata;}Record;typedefstructBTNode{intkeynum;//结点中关键字个数，即结点的大小structBTNode*parent;//指向双亲结点KeyTypekey[21];//关键字向量，0号单元未用structBTNode*ptr[21];//子树指针向量Record*recptr[21];//记录指针向量，0号单元未用}BTNode,*BTree
6、;//B树结点和B树的类型typedefstruct{BTNode*pt;//指向找到的结点inti;//1..m，在结点中的关键字序号inttag;//1:查找成功，0:查找失败}restype,*result;//在B树的查找结果类型四、关键算法设计流程图主函数：MAIN();功能：确定B树阶数与初始结点数，提供基本的菜单功能选择33函数名：intSearchNode(BTreep,intk);功能：在节点中查找关键字，返回该关键字在节点中的位置。33函数名：voidSearchBTree(BTreet,intk,result&SearchBTree);功能：在m阶B树t
7、上查找关键码k，返回(pt,i,tag)。函数名：voidsplit(BTree&q,ints,BTree&ap);功能：将结点q分裂成两个结点，前一半保留，后一半移入新生结点ap。33函数名：voidnewroot(BTree&t,BTreep,intx,BTreeap);功能：生成新的根结点。33函数名：voidInsert(BTree&q,inti,intx,BTreeap);功能：将关键字ap分别插入到q->key[i+1]和q->ptr[i+1]中。函数名：voidInsertBTree(BT
