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

时间:2024.3.27

20##—20##学年第一学期

实践教学

课程名称:数据结构课程实践

指导教师:钱峰

专业班级:20##级 软件工程4班

教学部门:计算机学院


北京理工大学珠海学院

课程设计说明书

20##—2013 学年第一学期

题    目:    B树与B+树及其操作

学    院:     计算机学院       

专业班级:       软工四班       

学    号:        110202041028      

学生姓名:       宁 琳 琳       

指导教师:       钱    峰      

成    绩:                    

时    间:                    

                      

20##年 10 月 16 日

课程设计成绩评定表

B树与B+树及其操作

摘  要

通过学习B树的相关知识了解B树的性质以及B树的构建、查找、插入、删除等操作,能用C或C++语言写出相关代码,并编译演示成功。

关键词:B树的构建、查找、插入、删除 结点分裂 

目  录

摘要……………………………………………………………4

概要设计………………………………………………………6

1.数据结构设计……………………………………………6

2.算法设计…………………………………………………7

3.ADT描述…………………………………………………7

4.功能模块分析……………………………………………7

详细设计………………………………………………………9

1.  主要算法流程图………………………………………9

2.  数据存储结构设计……………………………………12

3.  界面设计………………………………………………13

参考文献………………………………………………………14

心得体会………………………………………………………15

教师评语………………………………………………………16

计算机学院课程设计答辩记录表……………………………17

附录……………………………………………………………18

 

 

 

 

 

 

 

 

概要设计

1.数据结构设计

  B树又称为多路平衡查找树。

一棵度为m的B树称为m阶B树。一个结点有k个孩子时,必有k-1个关键字才能将子树中所有关键字划分为k个子集。B树中所有结点的孩子结点最大值称为B树的阶,通常用m表示。从查找效率考虑,一般要求m≥3。一棵m阶的B树或者是一棵空树,或者是满足下列要求的m叉树:

(1)根结点或者为叶子,或者至少有两棵子树,至多有m棵子树。

(2)除根结点外,所有非终端结点至少有ceil(m/2)棵子树,至多有m棵子树。

(3)所有叶子结点都在树的同一层上。

(4)每个结点的结构为:

(n,A0,K1,A1,K2,A2,…,Kn,An)

其中,Ki(1≤i≤n)为关键字,且Ki<Ki+1(1≤i≤n-1)。

Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1。An所指子树中所有结点的关键字均大于Kn。

n为结点中关键字的个数,满足ceil(m/2)-1≤n≤m-1。

一般来说B树的结构如下所示:

2.算法设计

先定义一颗空树,题目给出的数据是{53,75,139,49,145,36,101},然后不断地调用插入算法来插入数据,完成构建。查找时,调用SearchBTree()函数来查找关键字;插入时,调用InsertBTree()函数来插入关键字,若插入后结点中关键字个数不符合要求,需用split()函数来调整。

3.ADT描述

  ADT List{

       数据对象:D:{ai|ai∈ElemSet,i=1,2,3, ……,n,n≥0}

       数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2, ……,n}

       基本操作:

           CreatBTree(&T);

           //构建一颗B树T

           InsertBTree(T,K,q,i);

           //在B树T上结点*q的key[i]和key[i+1]之间插入关键字K

           SearchBTree(T,K);

           //在B树T上查找关键字K

}ADT List;

4.功能模块分析

  1、SearchBTree()函数:B树的查找过程:根据给定值查找结点和在结点的关键字中进行查找交叉进行。首先从根结点开始重复如下过程:

 若比结点的第一个关键字小,则查找在该结点第一个指针指向的结点进行;若等于结点中某个关键字,则查找成功;若在两个关键字之间,则查找在它们之间的指针指向的结点进行;若比该结点所有关键字大,则查找在该结点最后一个指针指向的结点进行;若查找已经到达某个叶结点,则说明给定值对应的数据记录不存在,查找失败。

  2、Insert()函数:将所给关键字插入到正确节点的正确位置。代入指向所给关键字应该插入节点的指针、所给关键字、关键字应该插入的位置,然后再将该关键字插入到节点的正确位置上,节点关键字个数加1,返回指向该节点的指针q。

3、InsertBTree()函数:插入的过程分两步完成:

(1)利用前述的B-树的查找算法查找关键字的插入位置。若找到,则说明该关键字已经存在,直接返回。否则查找操作必失败于某个最低层的非终端结点上。

(2)判断该结点是否还有空位置。即判断该结点的关键字总数是否满足n<=m-1。若满足,则说明该结点还有空位置,直接把关键字k插入到该结点的合适位置上。若不满足,说明该结点己没有空位置,需要把结点分裂成两个。

分裂的方法是:生成一新结点。把原结点上的关键字和k按升序排序后,从中间位置把关键字(不包括中间位置的关键字)分成两部分。左部分所含关键字放在旧结点中,右部分所含关键字放在新结点中,中间位置的关键字连同新结点的存储位置插入到父结点中。如果父结点的关键字个数也超过(m-1),则要再分裂,再往上插。直至这个过程传到根结点为止。

详细设计

1.主要算法流程图

SearchBTree()函数:

Insert()函数:

InsertBTree()函数:

2.数据存储设计

  B树是一种平衡的多路查找树,存储结构可定义为:

3.界面设计

参考文献

 [1]严蔚敏:《数据结构(C语言版)》[M],清华大学出版社20##年版,第238页。

[2]Thomas H.Cormen: 《算法导论 第二版》[M],机械工程出版社,第263页。

心得体会

这学期的课程设计我选了个最难的课题“B树与B+树及其操作”,正好也是老师没有讲过的,所以说自己在这个课题上废了很大劲,因为是没有学过的,所以自己就到处找相关资料来自学B树,有上网找相关课件,也有找别的书籍来学习B树的知识,大概用了四周的时间来学习,最后还是只弄懂了B树的相关知识,也许是自己能力有限吧,B树也只搞懂了概念,以及插入,查找这两个操作,删除的代码没有写出来,B+树压根就没看懂,所以也没有写代码,大部分时间全用在了B树上。虽然这个课题只完成了一部分,但是自己也尽力了,毕竟自己能力有限,老师没有讲过,全靠自学来的,所以自己也问心无愧了。

  通过这学期的课程设计我明白了自己还有很多要学习的东西,不是说只学懂了课本上的知识就行了,还有很多老师没有讲到的知识也需要自己去学习,学无止境,不能为了考试而学习,要为了求知而学习。

教师评语

计算机学院课程设计答辩记录表

附录

B树与B+树及其操作源代码:

#include <stdio.h>

#include <malloc.h>

#include <iostream.h>

#define m 3

#define n 7

typedef struct BTNode

{

    int keynum;

    struct BTNode *parent;

    int key[m+1];

    struct BTNode *ptr[m+1];

}BTNode,*BTree;

typedef struct

{

    BTNode *pt;

    int i;

    int tag;

}Result;

//在结点中查找关键字

int SearchNode(BTree p,int k)

{

    int i=1;

    while(i<=p->keynum)

    {

        if(k<p->key[i])

            return i-1;

       else

           if(k==p->key[i])

              return -1;

           else i++;

    }

    return i-1;

}

//在B树中查找关键字k

Result SearchBTree(BTree t,int k)//t为B树根节点

{

    BTree p=t,q=NULL;

   int found=0;

    int i=0;

    Result result;

    while(p&&!found)

    {

        i=SearchNode(p,k);

       if(i==-1)

       {

           result.pt=p;

           result.i=i;

           result.tag=1;

           return result;

       }

       while(p->ptr[i])

       {

           p=p->ptr[i];

           i=SearchNode(p,k);

       }

        if(i>0&&p->key[i]==k)

            found=1;

        else

        {

            q=p;

            p=p->ptr[i];

        }

    }

    if(found)

    {

        result.pt=p;

        result.i=i;

        result.tag=1;

    }

    else

    {

        result.pt=q;

        result.i=i;

        result.tag=0;

    }

    return result;

}

//将关键字插入节点

BTree Insert(BTree q,int i,int x,BTree ap)

 {

  // insert the key X between the key[i] and key[i+1]

  // at the pointer node q

  int j;

  for(j=q->keynum;j>i;j--)

  {

    q->key[j+1]=q->key[j];

    q->ptr[j+1]=q->ptr[j];

  }

  q->key[i+1]=x;

  q->ptr[i+1]=ap;

  if(ap)

      ap->parent=q; 

  q->keynum++;

  return q;

}

//分裂节点

BTree split(BTree q,int s,BTree ap)

{

  //move key[s+1...m],p->ptr[s...m] int the new pointer *ap

  int i,j;

  ap=(BTree)malloc(sizeof(BTNode));

  ap->ptr[0]=q->ptr[s];

  for(i=s+1,j=1;i<=q->keynum;i++,j++)

  {

    ap->key[j]=q->key[i];

    ap->ptr[j]=q->ptr[i];

  }

  ap->keynum=q->keynum-s;

  ap->parent=q->parent;

  for(i=0;i<=q->keynum-s;i++)

    if(ap->ptr[i])

       ap->ptr[i]->parent=ap;

    q->key[q->keynum]=0;

    q->keynum=s-1;

    return ap;

}

//建立新的节点

BTree NewRoot(BTree T,BTree p,int x,BTree ap)

{

  T=(BTree)malloc(sizeof(BTNode));

  T->keynum=1; 

  T->ptr[0]=p; 

  T->ptr[1]=ap; 

  T->key[1]=x;

  if(p)

      p->parent=T; 

  if(ap)

      ap->parent=T;

  T->parent=NULL;

  return T;

}

//建立B-树

BTree InsertBTree(BTree T,int K,BTree q,int i)

 {

  // 在m阶B树T上结点*q的key[i]与key[i+1]之间插入关键字K。

  // 若引起结点过大,则沿双亲链进行必要的结点分裂调整,使T仍是m阶B树。

  BTree ap;

  int finished, needNewRoot, s;

  int x;

  if(!q)                      // T是空树(参数q初值为NULL)

    T=NewRoot(T,NULL,K,NULL); // 生成仅含关键字K的根结点*T

  else

  {

    x=K;  ap=NULL;  finished=needNewRoot=0;    

    while(!needNewRoot&&!finished)

    {

      q=Insert(q,i,x,ap); // 将x和ap分别插入到q->key[i+1]和q->ptr[i+1]

      if(q->keynum< m)

         finished = 1;  // 插入完成

      else

      {  // 分裂结点*q

        // 将q->key[s+1..m], q->ptr[s..m]和

        // q->recptr[s+1..m]移入新结点*ap

        s=(m+1)/2;  

       ap=split(q,s,ap);  

       x=q->key[s];

       q->key[s]=0;

        if(q->parent)

       {  // 在双亲结点*q中查找x的插入位置

          q=q->parent;

         i=SearchNode(q, x);

       }

       else needNewRoot=1;

      } // else

    } // while

    if(needNewRoot)        // 根结点已分裂为结点*q和*ap

      T=NewRoot(T,q,x,ap); // 生成新根结点*T,q和ap为子树指针

  }

  return T;

} // InsertBTree

//搜索指定节点

int found(BTree t,int k)

{

    int i=1;

    BTree p=t;

    while(i<=p->keynum)

    {

       if(k==p->key[i])

           return i;

       else

           if(k<p->key[i])

           {

              if(p->ptr[i-1])

              {

                  p=p->ptr[i-1];

                  i=found(p,k);

                  return i;

              }

              else

                  return -1;

           }

           else

              i++;

    }

    if(p->ptr[i-1])

    {

       p=p->ptr[i-1];

       i=found(p,k);

       return i;

    }

    return -1;

}

//先序遍历输出

void inorder(BTree t)

{

    int i;

    if(t!=NULL)

    {

       printf("( ");

       for(i=1;i<=t->keynum;i++)

           printf("%d ",t->key[i]);

       printf(")   ");

       for(i=0;i<=t->keynum;i++)

           if(t->ptr[i])

              inorder(t->ptr[i]);

           else i++;

    }

}

int main()

{

    cout<<"====================================================================="<<endl;

    cout<<"******************************        *******************************"<<endl;

    cout<<"******************************        *******************************"<<endl;

    cout<<"******************************插入页面*******************************"<<endl;

    cout<<"******************************        *******************************"<<endl;

    cout<<"******************************        *******************************"<<endl;

    cout<<"====================================================================="<<endl;

    printf("\n");

    printf("\n");

    printf("\n");

    BTree root=NULL;

    Result result;

    int i,x,array[n];

    char ch[5];  

    printf("输入关键字序列\n");

    for(i=0;i<n;i++)

    {

       printf("输入第%d个数据:\n",i+1);

       scanf("%d",&array[i]);

    }

    i=0;

    while(i<n)

    {

       result=SearchBTree(root,array[i]);//寻找关键字在B树中应该插入的位置

       if(result.i==-1)

           i++;

       else

       {

           printf("将第%d个关键字  %d  插入B-树中;\n",i+1,array[i]);

           root=InsertBTree(root,array[i],result.pt,result.i); //插入结点

           i++;

       }

    }

    printf("插入后的B树如下:\n");

    inorder(root);   //先序遍历

    printf("\n");

    printf("\n");

    printf("\n");

    cout<<"====================================================================="<<endl;

    cout<<"******************************        *******************************"<<endl;

    cout<<"******************************        *******************************"<<endl;

    cout<<"******************************查找页面*******************************"<<endl;

    cout<<"******************************        *******************************"<<endl;

    cout<<"******************************        *******************************"<<endl;

    cout<<"====================================================================="<<endl;

    printf("\n");

    printf("\n");

    do

    {

       printf("请输入要查找的关键字:\n");

       scanf("%d",&x);

       i=found(root,x);

       if(i!=-1)

           printf("%d在节点中的序号---------[%d]\n",x,i);

       if(i==-1)

           printf("不能查找到关键字\n");

           printf("是否继续查询?“是”请输入:1 “否”请输入:0\n");

           scanf("%s",ch);

    }while (ch[0]=='1');

}

更多相关推荐:
数据结构课程设计实验报告.doc

数据结构课程实验报告专业指导老师班级姓名学号完成日期一实验目的1掌握线性表的顺序存储结构和链式存储结构2熟练掌握顺序表和链表基本算法的实现3掌握利用线性表数据结构解决实际问题的方法和基本技巧4按照实验题目要求独...

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

数据结构与算法课程设计报告姓名林小琼学号0907022118班级09网络工程设计时间20xx11020xx114审阅教师目录一课程设计的目的与要求含设计指标2二方案实现与调试221仓库管理系统222通讯录管理系...

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

课程课程设计系电子信息与计算机科学系专业计算机科学与技术班级文计1111姓名毕萌玉张菁张帅学号20xx905141221011任课教师高慧学年学期20xx20xx2学期20xx年6月29日任务分配程序员张菁主要...

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

软件111班18号赵庆珍数据结构课程设计任务书学期12131班级软件111一设计目的数据结构是一门实践性较强的软件基础课程为了学好这门课程必须在掌握理论知识的同时加强上机实践本课程设计的目的就是要达到理论与实际...

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

仲恺农业工程学院课程设计报告课程名称院系专业班级学号姓名指导老师计算机科学与技术计算机102班20xx10214203成筠目录题目一二算法设计包括程序流程图如函数功能入口及出口参数说明函数需求和规格说明问题描述...

《数据结构课程设计》赫夫曼编码实验报告

目录一概述1二系统分析1三概要设计2四详细设计441赫夫曼树的建立4411选择选择parent为0且权值最小的两个根结点的算法5412统计字符串中字符的种类以及各类字符的个数7413构造赫夫曼树842赫夫曼编码...

《数据结构课程设计》赫夫曼编码实验报告

数据结构课程设计实验报告赫夫曼编码实验课程名称数据结构课程设计专业班级11级计科2班学生姓名王琦学号1140901020xx指导教师冯韵实验时间20xx年9月24日20xx至20xx学年第1学期第1至9周1目录...

数据结构课程设计报告基于无向图的校园导游系统[1]

重庆科技学院课程设计报告院系电气与信息工程学院专业班级计科普0902学生姓名周杨学号20xx441622设计地点单位计算机基础自主学习中心I306设计题目校园导游咨询完成日期20xx年1月14日指导教师评语成绩...

淮海工学院数据结构课程设计报告书——全国著名景点导游咨询

淮海工学院计算机工程学院课程设计报告设计名称数据结构课程设计选题名称全国著名景点导游咨询姓名学号110913121专业班级软件工程软件091系院计算机工程学院设计时间设计地点软件工程实验室教室数据结构课程设计报...

数据结构课程设计实验报告 安徽大学

20xx726实验一停车场管理系统设计要求1问题描述设计一个停车场管理系统模拟停车场运作此程序具备以下功能1若车辆到达则显示汽车在停车场内或便道上的停车位置2若车辆离开则显示汽车在停车场内停留的时间和应缴纳的费...

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

实验一线性表逆置一问题描述分别以不同存储结构实现线性表的就地逆置线性表的就地逆置就是在原表的存储空间内将线性表a1a2a3ananan1a2a1二基本要求用顺序存储结构实现线性表的就地逆置并将结果输出三数据结构...

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

数据结构课程设计报告姓名陈白杨班级软092老师王森玉学号099074177实验一农夫过河问题一题目农夫过河问题二问题描述从前一人农夫带着一只狼一只羊和一棵白菜注意该狼已被农夫驯服了但还是会吃羊他要将所有东西安全...

数据结构课程设计实验报告(35篇)