第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
数据结构实验报告10-查找-B-树基本操作的实现-实验内容与要求.docx
数据结构实验报告
评分
学号：xxxxxxxxxxx
知识范畴：查找
姓名：xxxxxx
专业：计算机科学与技术
完成日期：2019 年 06 月 03 日
满分——10 分
实验题目：B-树基本操作的实现
实验内容及要求：定义 B-树存储结构（要求 m3；为方便操作，结点中增加双亲结点指针域，
最底层的 Fail 结点用 NULL 指针表示并且所有结点均存储于内存）。定义 B-树插入关键字函数、
删除关键字函数、查找关键字函数以及按层次遍历输出 B-树所有结点的函数。主函数定义菜
单(1.插入关键字 2.删除关键字 3. 查找关键字 4.层次遍历输出 B-树所有结点 5.结束程序)。
1. 插入关键字功能的输入为一个关键字，输出为新插入关键字所在结点的信息。
要求结点信息输出格式如下所示:
(R102, n, K1, K2, …, Kn)
R102 表示结点位置，R 表示根结点指针；第一个数字 1 表示根结点的 A[1]指针，第二个数
字 0 表求 R->A[1]所指结点的 A[0]指针，第三个数字 2 表示 R->A[1]->A[0]所指结点的 A[2]
指针，即该结点指针为: R->A[1]->A[0]->A[2](该结点在第 4 层上)。n 为该结点的关键字数
目，K1, K2, …, Kn 为该结点中 n 个非递减有序的关键字。
2. 删除关键字功能的输入为一个关键字，输出为删除成功与失败的信息。
3. 查找关键字功能的输入为一个关键字，输出为查找成功与失败的信息，查找成功时，应输
出关键字所在结点信息（结点信息输出方法同 1.）。
4. 按层次遍历输出 B-树所有结点功能的输入为一个字符文件名，输出为该字符文件，字符文
件中，一个结点的信息输出一行（结点信息输出方法同 1.），结点输出次序为按层次号由小
到大并且同层结点从左向右。
提示：B-树的初态为空树，通过反复执行功能 1. (插入结点)可以建立 B-树存储结构。
实验目的：掌握 B-树插入关键字、删除关键字以及查找算法。
数据结构设计简要描述：
// B-树数据类型定义
typedef struct node
{
int n; // 节点中关键字的个数
KeyTp K[M+1];
// 关键字向量，0 号元素没有使用
struct node *A[M+1]; // 子树指针向量
struct node *parent; // 双亲节点指针
}BSubTNode, *BSubT;
// 层次遍历以及输出节点位置信息辅助数据结构
typedef struct output
1 / 16
{
BSubT bt; // 节点指针
std::vector infor; // 节点位置信息容器
}Output;
// 查找节点信息辅助数据结构
std::vector infor;
算法设计简要描述：
B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则
结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经
是叶子结点；因此，B-Tree 的查找过程是一个顺指针查找结点和在结点的关键字中进行查找
的交叉进行的过程。
B-树是从空树起，逐个插入关键码而生成的。在 B-树，每个非失败结点的关键码个数都
在[ m/2 -1, m-1]之间。插入在某个叶结点开始。如果在关键码插入后结点中的关键码个数超
出了上界 m-1，则结点需要“分裂”，否则可以直接插入。实现结点“分裂”的原则是：设结
点 A 中已经有 m-1 个关键码，当再插入一个关键码后结点中的状态为( m, A0, K1, A1, K2,
A2, ……, Km, Am)其中 Ki < Ki+1, 1 =< m，这时必须把结点 p 分裂成两个结点 p 和 q，
它们包含的信息分别为：
结点 p：( m/2 -1, A0, K1, A1, ……, Km/2 -1, Am/2 -1)
结点 q：(m - m/2, Am/2, Km/2+1, Am/2+1, ……, Km, Am)
位于中间的关键码 Km/2 与指向新结点 q 的指针形成一个二元组 ( Km/2, q )，插入到
这两个结点的双亲结点中去。
输入/输出设计简要描述：
从文件输入一些不重复的关键字，建立 B-树；查找和插入的时候输出(R102, n, K1, K2, …,
Kn)，R102 表示结点位置，R 表示根结点指针；第一个数字 1 表示根结点的 A[1]指针，第二个
数字 0 表求 R->A[1]所指结点的 A[0]指针，第三个数字 2 表示 R->A[1]->A[0]所指结点的 A[2]
指针，即该结点指针为: R->A[1]->A[0]->A[2](该结点在第 4 层上)。n 为该结点的关键字数目，
K1, K2, …, Kn 为该结点中 n 个非递减有序的关键字。层次遍历的时候输出格式与上面一样，但
是数据保存在文本文件。
编程语言说明：
使用 Visual C++编程。主要代码采用 C 语言实现 ；动态存储分配采用 C++的 new 和 delete
操作符实现；输入与输出采用 C++的 cin 和 cout 流；程序注释采用 C/C++规范。
主要函数说明：
void Mgr() // 控制程序函数， 减少 main 函数负担
2 / 16
BSubT BSubTCreate() //根据文件创建 b 树
int BTNodeDelete(BSubTNode *p,int k) //在结点 p 中查找并删除关键字 k
int FindBTNode(BSubTNode *p,int k,int &i)
//反映是否在结点 p 中是否查找到关键字 k
void Substitution(BSubTNode *p,int i) //寻找替代值（右子树中最小的关键字）
void AdjustBTree(BSubTNode *p,int i)
// 调整 B-树，使之平衡
void MoveRight(BSubTNode *p,int i) //将左结点 aq 中的最后一个关键字移入双亲结点 p 中
void MoveLeft(BSubTNode *p,int i) //将右结点 q 中的第一个关键字移入双亲结点 p 中
void Combine(BSubTNode *p,int i) // 双亲结点 p、右结点 q 合并入左结点 aq，并调整双亲
// 结点 p 中的剩余关键字的位置
BSubT BSubTInsert(BSubT t,int key) //插入结点
void Layorder(BSubT bt) // 层次遍历输出 B-树的所有节点信息
void Menu() // 显示菜单
void BSubTSearch(BSubT t, KeyTp key) // B-树查找节点算
int Search(BSubT p, KeyTp key) // 节点内查找 key,满足返回下标
void Sort(BSubT p,int key) //排序函数
程序测试简要报告：
1. 菜单
2. 插入关键字
3. 删除关键字
4. 查询关键字
1 查询失败
2 查询成功
3 / 16
5. 遍历 B-树
源程序代码：
// Predefine.h
#ifndef PREDEFINE_H_
#define PREDEFINE_H_
#include
#include
#define M 3 // m 为 4 的 B 树
#define Min ((M-1)/2) // 节点最小关键字数
typedef int KeyTp; // 定义关键字类型为整数类型
// B-树数据类型定义
typedef struct node
{
}BSubTNode, *BSubT;
int n; // 节点中关键字的个数
KeyTp K[M+1];
struct node *A[M+1]; // 子树指针向量
struct node *parent; // 双亲节点指针
// 关键字向量，0 号元素没有使用
/* // 节点查找返回值数据类型
* typedef struct
* {
*
*
*
BSubT bt; // 查找成功返回成功节点，失败返回上一次查找的节点
int i; // 节点指针
int flag; // 查找结果标志变量
4 / 16
* }Result;
*/
#endif // PREDEFINE_H_
// mgr.cpp
#include
#include
#include
#include "Predefine.h"
extern void Menu();
extern void BSubTSearch(BSubT t, KeyTp key);
extern void Layorder(BSubT bt);
extern BSubT BSubTCreate();//根据文件创建 b 树
extern BSubT BSubTInsert(BSubT t,int key);
extern int BTNodeDelete(BSubTNode *p,int k);
// 控制程序函数， 减少 main 函数负担
void Mgr()
{
BSubT bt;
bt = BSubTCreate();
char select; // 选择的操作
int key; // 要删除或者插入或者查找的关键字
while(select!='5')
{
Menu();
std::cin >> select;
switch(select)
{
case '1':
{
}
case '2':
{
}
std::cout << "Please enter keywords:";
std::cin >> key;
bt = BSubTInsert(bt, key);
BSubTSearch(bt,key);
std::cout << std::endl << std::endl;
break;
std::cout << "Please enter keywords:";
std::cin >> key;
if(BTNodeDelete(bt,key))
std::cout << "Delete success!" << std::endl << std::endl;
break;
5 / 16
case '3':
{
}
case '4':
{
}
std::cout << "Please enter keywords:";
std::cin >> key;
BSubTSearch(bt,key);
std::cout << std::endl << std::endl;
break;
Layorder(bt);
std::cout << std::endl << std::endl;
break;
}
}
}
// main.cpp
#include
#include
std::vector infor; // 查找节点信息
extern void Mgr();
int main()
{
Mgr();
std::cout << "End of Procedure!" << std::endl;
return 0;
}
// sort.cpp
#include "Predefine.h"
//排序函数
void Sort(BSubT p,int key)
{
int i,j;
p->n++;
for(i=1;in;i++)
if(keyK[i]){
for(j=p->n;j>i;j--)
p->K[j]=p->K[j-1];
p->K[i]=key;
break;
}
if(i==p->n) p->K[i]=key;
6 / 16
}
// create_b_tree.cpp
#include
#include "Predefine.h"
extern BSubT BSubTInsert(BSubT t,int key);
//根据文件创建 b 树
BSubT BSubTCreate()
{
int key,i;
BSubT t = new BSubTNode;//建立头结点并初始化
t->parent = NULL;
t->n = 0;
for(i=0;i<=M;i++)
t->A[i] = NULL;
std::ifstream infile("input.txt");
infile >> key;
t->K[1] = key;
t->n++;
while(!infile.eof())
{
infile >> key;
t = BSubTInsert(t,key);
}
std::cout << "Create Success!" << std::endl;
infile.close();
return t;
}
// delete.cpp
#include "Predefine.h"
int FindBTNode(BSubTNode *p,int k,int &i);
void Substitution(BSubTNode *p,int i);
void Remove(BSubTNode *p,int i);
void AdjustBTree(BSubTNode *p,int i);
void MoveLeft(BSubTNode *p,int i);
void Combine(BSubTNode *p,int i);
void MoveRight(BSubTNode *p,int i);
//在结点 p 中查找并删除关键字 k
int BTNodeDelete(BSubTNode *p,int k)
{
int i;
int find_flag; //查找标志
if(p==NULL)
7 / 16
//返回查找结果
find_flag=FindBTNode(p,k,i);
if(find_flag==1) //查找成功
{
if(p->A[i-1]!=NULL)
{ //删除的是非叶子结点
Substitution(p,i);
BTNodeDelete(p->A[i],p->K[i]);
//寻找相邻关键字 （右子树中最小的关键字）
Remove(p,i); //从结点 p 中位置 i 处删除关键字
find_flag=BTNodeDelete(p->A[i],k); //沿孩子结点递归查找并删除关键字 k
if(p->A[i]!=NULL)
if(p->A[i]->nK[1])
{
i=0;
return 0;
}
//在 p 结点中查找
else{
i=p->n;
while(kK[i]&&i>1)
i--;
//结点 p 中查找关键字 k 成功
if(k==p->K[i])
return 1;
}
}
//寻找替代值（右子树中最小的关键字）
void Substitution(BSubTNode *p,int i)
{
8 / 16
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
