btree实验报告.doc

btree实验报告 篇一：广工数据结构实验设计报告BTree 数据结构设计性实验报告 课程名称数据结构实验 题目名称B树（难度1.4） 学生学院 计算机学院 专业班级 学 号 姓名 指导教师黄剑锋 2015年 06月25日 B树抽象数据类型实现 一、设计简介 本次设计在AnyviewCL自由编程平台上实现了B树的6种基本操作，并根据这个基本操作设计了友好的交际界面，操作简单易懂，并在AnyviewCL自由编程平台上可视化测试B树各个基本操作，保证了各基本的操作算法的正确性。 经在AnyviewCL自由编程平台严格测试后，将本设计移植到Visual C++ 6.0平台生成可运行程序，并进行各个基本操作的测试，保证了程序运行的稳定性。 其中数据来源为一组在0~1000内的int型随机数，但数据由typedefintKeyType定义，若需要改变数据类型，只需要将int替换成所需的数据类型即可。 二、抽象数据类型定义及各种基本操作的描述 ADT BTree{ 数据对象：D是具有相同特征的数据元素集合。 数据关系： 若D为空集，则称为空树； （1）树中每个结点最多含有m棵子树； （2）若根结点不是叶子结点，则至少有2个子树； （3）除根结点之外的所有非终端结点至少有┌m/2┐棵子树； （4）每个非终端结点中包含信息：（n，A0，K1，A1，K2，A2，…，Kn，An）。其中： 1）Ki（1lt;=ilt;=n）为关键字，且关键字按升序排序； 2）指针Ai（0lt;=ilt;=n）指向子树的根结点，Ai-1指向子树中所有结点的关键字均小于Ki，且大于Ki-1； 3）关键字的个数n必须满足：┌m/2┐-1lt;=nlt;=m-1。 （5）所有的叶子节点都在同一层，子叶结点不包含任何信息。 基本操作P： CreatBTree(amp;T, n, m); 初始条件：初始化关键字个数n大于等于0，B树的阶数m大于3小于等于20。 操作结果：构建一棵阶数为m，含有n个关键字的B树。 SearchBTree(T, k, amp;p); 初始条件：树T存在。 操作结果：在m阶B树t上查找关键字k，返回(pt,i,tag) 。 InsertBTree(amp;T, k, p-gt;pt, p-gt;i, m); 初始条件：树T存在，p-gt;pt指向T中某个结点 操作结果：在B树T上结点p-gt;pt的key[i]和key[i+1]之间插入关键字k DeleteBTree(p-gt;pt, p-gt;i, m, T); 初始条件：树T存在，p-gt;pt指向T中某个结点 操作结果：删除B树T上结点p-gt;pt的关键字k PrintBTree(T); 初始条件：树T存在 操作结果：中序遍历B树 DestroyBTree(T) 初始条件：树T存在 操作结果：销毁B树 }ADTBTree 三、存储结构定义 #includelt;stdio.hgt; #includelt;stdlib.hgt; #include lt;time.hgt; #define TRUE 1 #define FALSE 0 #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedefintKeyType; typedefint Status; typedefstruct { KeyType key; char data; }Record; typedefstructBTNode { intkeynum;// 结点中关键字个数，即结点的大小 structBTNode*parent; // 指向双亲结点 KeyTypekey[21]; // 关键字向量，0号单元未用 structBTNode*ptr[21];// 子树指针向量 Record *recptr[21];// 记录指针向量，0号单元未用 }BTNode, *BTree;// B树结点和B树的类型 typedefstruct { BTNode*pt;// 指向找到的结点 inti; // 1..m，在结点中的关键字序号 inttag; // 1:查找成功，0:查找失败 }restype,*result; // 在B树的查找结果类型 四、关键算法设计流程图 主函数：MAIN(); 功能：确定B树阶数与初始结点数，提供基本的菜单功能选择 函数名：intSearchNode(BTree p, int k); 功能：在节点中查找关键字，返回该关键字在节点中的位置。 篇二：数据结构实验报告 实验目的