数据结构课程设计
实习报告
题 目： 学 号：姓 名：年 级：学 院：专 业：完成日期：授课教师：
B树的建立，插入与
删除 1110685 李建男 大二
信息技术科学学院 计算机科学与技术专业
2013.5.12 辛运帷
数据结构第二次作业实习报告 1110685
1. 题目
2. B树的表示及基本操作的实现。 3. 1．掌握B树的存贮结构。
4. 2．实现B树中关键字值的插入及删除操作。 5. 3．练习屏幕图形化的显示。
2.要求
a) 参考书中的示例代码，以整数表示每个记录的关键字。为简单起见，每个记录可以只包含一个
关键字（即其他的字段可以不定义）。
b) 从空树开始，依次输入各关键字，建立相应的B树。 c) 并实现B树中关键字的插入及删除。
d) 同时将树型显示在屏幕上。全部关键字插入完毕时显示树型，之后每完成一次插入或删除操作
后也显示当前的树型。
e) 假设B树中不存在重复的关键字。 f)
程序运行时，当要输入数据时必须在屏幕上给出输入的格式要求（中英文均可）。当有输出显示时，也需要将输出的内容做必要的解释。
3.程序实现
3.1程序运行及编译环境
VisualStudio2012
3.2程序描述
该程序支持用户进行以下三种操作：
1、 新建B树：从键盘输入新建B树的阶数和关键字个数，新建B树。
2、 插入关键字：既支持单个关键字的插入，也支持多个关键字的插入。（重复插入时给出信息提示） 3、 删除关键字：既支持单个关键字的删除，也支持多个关键字的删除。（树中没有该关键字时给出
信息提示）
特别说明：程序编写时参考了《算法导论》中的内容，对B树的规定与老师课上所讲略有出入，采用了如下规则： 对m阶B树：
关键字个数：Least：m-1；Most：2*m-1
1
数据结构第二次作业实习报告 1110685
孩子个数：Least：m；Most：2*m
3.3实现功能
介绍该程序应具有的功能，可采用IPO图（即输入一处理一输出图）的形式。 说明：如果该程序只有单一功能时可以直接描述其输入项、输出项等等各个部分，否则按照各个子功能模块分别介绍。
3.3.1子功能模块1——新建B树&插入关键字
说明：因新建和插入用到的算法相同，故合并为一个模块
根据用户输入的B树阶数，关键字个数及关键字，新建B树。
用户： 输入B树阶数degree，待输入关键字个数key_num。 2
数据结构第二次作业实习报告 1110685
3.3.1.1 输入项
输入项一：B树阶数degree和带插入关键字个数key_num 名称：B树阶数 标识：degree 数据类型：int 有效范围：整型变量 输入方式：用户从键盘输入
名称：待插入关键字个数 标识：key_num 数据类型：int 有效范围：整型变量
3
根据degree，初始化B树： MyBTreeBTree（degree）； 用户：依次输入关键字 （超出关键字个数的忽略掉） 调用Insert函数，将输入的关键字依次插入到B树中，完成B树的创建。 数据结构第二次作业实习报告 1110685
输入方式：用户从键盘输入 输入项二： 名称：关键字 标识：key 数据类型：int 有效范围：整型变量
存储方式：动态数组new int[key_num] 输入方式：用户从键盘输入
3.3.1.2输出项
输出为B树树形，采用两种输出方式：屏幕图形化输出（采用MFC实现）；层遍历输出所有关键字、 具体输出方式同子模块1，不再赘述。
3.3.1.3数据结构的定义
3.3.1全局数据结构
函数bool* erase(intkey)——用来实现B树关键字的插入
3.3.2 局部数据结构
函数voidsplite_child(node* pnode, inti)——用来实现当结点满时结点的分裂
3.3.1.4算法及程序说明
采取的算法： 1、 树的创建：
B树类class b_trees。包含两个私有数据变量：结点类node* root，和表示树阶数的变量int degree。 node类包含三个成员变量——关键字队列deque
explicitb_trees(intdeg=10):root(newnode),degree(deg){};
4