关于实验的报告

　　数据结构设计性实验报告

　　课程名称数据结构实验

　　题目名称B树（难度1.4）

　　学生学院 计算机学院

　　专业班级

　　学 号

　　姓名 指导教师黄

　　20xx年 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（1pt, p->i, m);

　　初始条件：树T存在，p->pt指向T中某个结点

　　操作结果：在B树T上结点p->pt的key[i]和key[i+1]之间插入关键字k DeleteBTree(p->pt, p->i, m, T);

　　初始条件：树T存在，p->pt指向T中某个结点

　　操作结果：删除B树T上结点p->pt的关键字k

　　PrintBTree(T);

　　初始条件：树T存在

　　操作结果：中序遍历B树

　　DestroyBTree(T)

　　初始条件：树T存在

　　操作结果：销毁B树

　　}ADTBTree

　　三、存储结构定义

　　#include

　　#include

　　#include

　　#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,*resu< // 在B树的查找结果类型

　　四、关键算法设计流程图

　　主函数：MAIN;

　　功能：确定B树阶数与初始结点数，提供基本的菜单功能选择

　　函数名：intSearchNode(BTree p, int k);

　　功能：在节点中查找关键字，返回该关键字在节点中的位置。