数据结构课程设计实验报告

《数据结构课程设计实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京理工大学珠海学院计算机学院课程设计2012—2013学年第一学期实践教学课程名称：数据结构课程实践指导教师：钱峰专业班级：2011级软件工程4班教学部门：计算机学院29北京理工大学珠海学院计算机学院课程设计北京理工大学珠海学院课程设计说明书2012—2013学年第一学期题目:B树与B+树及其操作学院：计算机学院专业班级：软工四班学号：110202041028学生姓名：宁琳琳指导教师：钱峰　成绩：　　时间：　　2012年10月16日29北京理工大学珠海学院计算机学院课程设计课程设计成绩评定表姓名

2、成绩评定权重总分总成绩（五分制）平时成绩20报告成绩50答辩成绩3029北京理工大学珠海学院计算机学院课程设计B树与B+树及其操作摘要通过学习B树的相关知识了解B树的性质以及B树的构建、查找、插入、删除等操作，能用C或C++语言写出相关代码，并编译演示成功。关键词：B树的构建、查找、插入、删除　结点分裂　29北京理工大学珠海学院计算机学院课程设计目录摘要……………………………………………………………4概要设计………………………………………………………61.数据结构设计………………………………………

3、……62.算法设计…………………………………………………73.ADT描述…………………………………………………74.功能模块分析……………………………………………7详细设计………………………………………………………91.主要算法流程图………………………………………92.数据存储结构设计……………………………………123.界面设计………………………………………………13参考文献………………………………………………………14心得体会………………………………………………………15教师评语……………………

4、…………………………………16计算机学院课程设计答辩记录表……………………………17附录……………………………………………………………1829北京理工大学珠海学院计算机学院课程设计概要设计1.数据结构设计B树又称为多路平衡查找树。一棵度为m的B树称为m阶B树。一个结点有k个孩子时，必有k-1个关键字才能将子树中所有关键字划分为k个子集。B树中所有结点的孩子结点最大值称为B树的阶，通常用m表示。从查找效率考虑，一般要求m≥3。一棵m阶的B树或者是一棵空树，或者是满足下列要求的m叉树：（1）根结点或者

5、为叶子，或者至少有两棵子树，至多有m棵子树。（2）除根结点外，所有非终端结点至少有ceil(m/2)棵子树，至多有m棵子树。（3）所有叶子结点都在树的同一层上。（4）每个结点的结构为：（n，A0，K1，A1，K2，A2，…，Kn，An）其中，Ki(1≤i≤n)为关键字，且Ki

6、一般来说B树的结构如下所示：29北京理工大学珠海学院计算机学院课程设计2.算法设计先定义一颗空树，题目给出的数据是{53,75,139,49,145,36,101}，然后不断地调用插入算法来插入数据，完成构建。查找时，调用SearchBTree()函数来查找关键字；插入时，调用InsertBTree()函数来插入关键字，若插入后结点中关键字个数不符合要求，需用split()函数来调整。3.ADT描述ADTList{数据对象：D：{ai

7、ai∈ElemSet,i=1,2,3,……,n,n≥0}数据关

8、系：R1={

9、ai-1,ai∈D,i=2,……,n}基本操作：CreatBTree(&T);//构建一颗B树TInsertBTree(T,K,q,i);//在B树T上结点*q的key[i]和key[i+1]之间插入关键字KSearchBTree(T,K);//在B树T上查找关键字K}ADTList;4.功能模块分析1、SearchBTree()函数：B树的查找过程：根据给定值查找结点和在结点的关键字中进行查找交叉进行。首先从根结点开始重复如下过程：若比结点的第一个关键字小，则查找

10、在该结点第一个指针指向的结点进行；若等于结点中某个关键字，则查找成功；若在两个关键字之间，则查找在它们之间的指针指向的结点进行；若比该结点所有关键字大，则查找在该结点最后一个指针指向的结点进行；若查找已经到达某个叶结点，则说明给定值对应的数据记录不存在，查找失败。2、Insert()函数：将所给关键字插入到正确节点的正确位置。代入指向所给关键字应该插入节点的指针、所给关键字、关键字应该插入的位置，然后再将该关键字插入到节点的正确位置上，节点关键字个数加1，返回指向该节点的指针q。3