精华内容
下载资源
问答
  • (部分图片源自网络,侵删。部分代码参考《数据结构》(吴伟民)) (可执行文件和代码稍后上传) 一、B-Tree的定义 计算机科学中,B(英语:B-tree)是一种自平衡的,能够保持数据有序。...B这种数据结构

    (部分图片源自网络,侵删。部分代码参考《数据结构》(吴伟民))
    (可执行文件和代码稍后上传)

    一、B-Tree的定义

    计算机科学中,B树(英语:B-tree)是一种自平衡的树,能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作,都在对数时间内完成。B树,概括来说是一个一般化的二叉查找树(binary search tree),可以拥有多于2个子节点。与自平衡二叉查找树不同,B树为系统大块数据的读写操作做了优化。B树减少定位记录时所经历的中间过程,从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。

    m阶B树的特点:
    (1)树中每个结点最多含有m棵子树。
    (2)若根节点非终端结点,至少有两棵子树
    (3)除根节点之外的所有非终端结点,则至少有(m+1)/2棵子树
    (4)每个非终端结点:关键字按升序排序,个数大于等于(m-1)/2,小于等于m-1
    (5)所有叶子结点出现在同一层,不包含任何信息
    在这里插入图片描述
    例:如图所示这是一棵3阶B树。符合上述特点。

    二、基本操作

    (一)需要实现的基本操作

    1—创建B-Tree
    2—销毁B-Tree
    3—删除关键字
    4—查找关键字
    5—中序遍历B-Tree
    6—插入关键字
    7—先序遍历B-Tree
    8—层次遍历B-Tree

    (二)操作函数之间的关系

    在这里插入图片描述
    在这里插入图片描述
    Main.c中的灰色节点都是调用的BTree.C中的操作函数

    (三)操作函数功能描述

    (1)BTree.c

    int SearchBTNode(BTNode *p,KeyType k);
    功能:在节点中查找关键字
    void SearchBTree(BTree T,KeyType k,Result *r);
    功能:在m阶b树上查找关键字void InsertBTree(BTree *T,KeyType k,BTNode *q,int i);
    功能:在b树插入关键字
    void newRoot(BTree *T,BTNode*p,KeyType x,BTNode *ap);
    功能:生成新的根节点 
    void Insert(BTree *q,int i,KeyType x,BTNode *ap);
    功能:插入关键字和新结点指针
    void split(BTree *q,int s,BTree *ap);
    功能:将节点分裂为两个节点
    void Inorder(BTree T);
    功能:中序遍历整棵B树,可以快速看出操作是否出错
    void preorder(BTree T);
    功能:先序遍历整颗B树,以缩进的方式展示B树
    void Destroy(BTree *T);
    功能:销毁整个B树
    void DeleteBTree(BTree *p,int i,BTree *T);
    功能:删除B树上某个关键字
    void Successor(BTree *p,int i);
    功能:交换被删节点和最下层非终端节点最小关键字
    void Remove(BTree*p,int i);
    功能:从节点p中删除key[i]
    void Restore(BTree *p,BTree* T);
    功能:调整B树
    void MoveLeft(BTree *q,int j);
    功能:找左兄弟节点借关键字
    void MoveRight(BTree *q,int j);
    功能:找右兄弟节点借关键字
    void Combine(BTree *q,int j);
    功能:和父母节点合并
    int Depth(BTree T);
    功能:求B树的深度
    Status InitQueue(LinkList *L);                                  
    功能:初始化队列 
    LNode* CreateNode(BTree t);                                     
    功能:新建一个结点 
    Status Enqueue(LNode *p,BTree t);                               
    功能:元素q入队列
    Status Dequeue(LNode *p,BTree *q);                            
    功能:出队列,并以q返回值
    Status IfEmpty(LinkList L);                                     
    功能:队列判空 
    void DestroyQueue(LinkList L);                                  
    功能:销毁队列 
    Status Traverse(BTree t,LinkList L,int newline,int sum);        
    功能:用队列遍历输出B树 
    Status PrintBTree(BTree t);
    功能:完成建立队列,遍历输出和销毁操作
    

    (2)main.c

    void welcome();
    功能:主菜单
    void CreateBTree();
    功能:创建B-Tree
    void destroyBTree();
    功能:销毁B-Tree
    void searchKey();
    功能:查找关键字
    void delete();
    功能:删除关键字
    void insertKey();
    功能:插入关键字
    

    三、数据存储结构

    #define m 3//b树的阶
    typedef int KeyType;//关键字类型为数字
    
    typedef struct BTNode
    {
        int keynum;					//结点当前关键字个数
        KeyType key[m+1];			//关键字数组,key[0]未用
        struct BTNode *parent;		//双亲结点指针
        struct BTNode *ptr[m+1];  //孩子结点指针数组
    }BTNode,*BTree;					//b树的结点及指针类型
    
    typedef struct{                    
        BTree pt;						//指向找到的结点
        int i;						//1<=i<=m,在结点中的关键字位置; 
        int tag; 						//1查找成功,0查找失败
    }Result; 							//B树查找结果类型 
    
    typedef enum status{             
        TRUE,FALSE,OK,ERROR,OVERFLOW,EMPTY
    }Status;							//枚举类型返回值
    
    typedef struct LNode{			    
    BTree data;					//数据域
        struct LNode *next;			//指针域
    }LNode, *LinkList;				//队列和队列结点类型 
    

    四、代码实现

    (一)BTree.c(此处按照操作函数关系图的最上层函数分别实现)

    1.searchBTree

    在m阶b树上查找关键字
    *参数:*在m阶b树上查找关键字k,用r返回查找结果
    *思路:*迭代法。调用查找结点函数。如果找到关键字或者已经查询到叶子节点退出循环。
    在循环里需要判断查找结点函数返回的是关键字数组下标还是插入置指针数组下标。
    如果是前者就退出循环,是后者则指针下移,直到为叶子结点。
    若查找成功则标记tag为1
    否则tag=0,若要插入关键字为k的记录,应位于pt结点中的第i-1个和第i个关键字 之间

    void SearchBTree(BTree T,KeyType k,Result *r){
        int i=0;
        int found=0;//用来判断是否查询到该关键字
        BTree p=T,q=NULL;
        while (p!=NULL&&found==0)
        {
            i=SearchBTNode(p,k);
            if(i<=p->keynum&&p->key[i]==k)found=1;//k在p节点里
            else{//k不在p节点里
                q=p;
                p=p->ptr[i-1];//指针下移
            }
        }
        if(1==found){
            (*r).pt=p;
            (*r).i=i;
            (*r).tag=1;
            printf("查找成功\n");
            printf("i=%d",i);
        }
        else{//自然退出while循环
            (*r).pt=q;
            (*r).i=i;
            (*r).tag=0;
            printf("查找失败\n");
        }
    }
    

    在节点中查找关键字
    参数:p是被查找结点,k是需要查找的关键字
    返回值:关键字数组下标或插入位置指针数组下标
    思路:i在for循环中递增实现遍历比较该节点关键字,k大于该关键字时i++
    情况1:在p中找到k了
    情况2:在p中没找到k(找到比k大的数或者整个结点的关键字都遍历完了)
    这时候都退出循环,返回i,在外层函数会验证这个i是指关键字数组下标还是插入位 置指针数组下标

    int SearchBTNode(BTNode *p,KeyType k){//查找p所指节点中k的位置
        int i=1;
        for(;i<=p->keynum&&k>p->key[i];i++);
        return i;
    }
    
    2.InsertBTree

    在b树插入关键字
    参数:在T树的q所指节点的i位置插入关键字k
    思路:
    1.插入一个元素时,首先在B树中是否存在,如果不存在,即比较大小寻找插入位置,在叶子结点处结束,然后在叶子结点中插入该新的元素
    如图所示:
    在这里插入图片描述
    2、如果叶子结点空间足够,这里需要向右移动该叶子结点中大于新插入关键字的元素,如果空间满了以致没有足够的空间去添加新的元素,则将该结点进行“分裂”,将一半数量的关键字元素分裂到新的其相邻右结点中,中间关键字元素上移到父结点中(当然,如果父结点空间满了,也同样需要“分裂”操作)
    如图所示:
    在这里插入图片描述在这里插入图片描述
    3、当结点中关键元素向右移动了,相关的指针也需要向右移。如果在根结点插入新元素,空间满了,则进行分裂操作,这样原来的根结点中的中间关键字元素向上移动到新的根结点中,因此导致树的高度增加一层
    在这里插入图片描述

    void InsertBTree(BTree *T,KeyType k,BTNode *q,int i){
        KeyType x;
        int s,finished=0,needNewRoot=0;
        BTree ap;
        if(NULL==q){
            newRoot(&(*T),NULL,k,NULL);
        }//生成新的根节点
        else{
            x=k;
            ap=NULL;
            while(0==needNewRoot&&0==finished){
                Insert(&q,i,x,ap);
                if(q->keynum<m ){
                    finished=1;
                }
                else
                {
                    s=(m+1)/2;
                    split(&q,s,&ap);
                    x=q->key[s];
                    if(q->parent!=NULL){
                        q=q->parent;
                        i=SearchBTNode(q,x);
                    }
                    else needNewRoot=1;
                }
            }
            if(1==needNewRoot){
                newRoot(&(*T),q,x,ap);
            }
        }
    }
    

    新建根节点
    参数:x为新根节点的关键字,t是树原来的根节点,p为新根节点的0号子树,ap为新根节点的1号子树。
    思路:只需要新建结点,赋值,调整指针即可

    void newRoot(BTree *T,BTNode*p,KeyType 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;
    }
    

    插入关键字
    参数:q为被插入结点,i为需要插入的位置下标,x为需要插入的关键字,ap为新结点指针,需要称为p结点的子树
    思路:从后往前遍历结点的同时将数据和指针后移。直到找到插入位置为止

    void Insert(BTree *q,int i,KeyType x,BTNode *ap){
        int j,n=(*q)->keynum;
        for(j=n;j>=i;j--){
            (*q)->key[j+1]=(*q)->key[j];
            (*q)->ptr[j+1]=(*q)->ptr[j];
        }
        (*q)->key[i]=x;
        (*q)->ptr[i]=ap;
        if(ap)ap->parent=(*q);
        (*q)->keynum++;
    }
    

    分裂结点
    参数:q是被分裂节点,s是分裂位置下标,ap在函数中指向新结点
    思路:将q分裂成两个结点,前一半保留,后一半用遍历的方式保存到ap所指新结点里

    void split(BTree *q,int s,BTree *ap){
        int i,j,n=(*q)->keynum;
        (*ap)=(BTNode*)malloc(sizeof(BTNode));
        (*ap)->ptr[0]=(*q)->ptr[s];
        for(i=s+1,j=1;i<=n;i++,j++){
            (*ap)->key[j]=(*q)->key[i];
            (*ap)->ptr[j]=(*q)->ptr[i];
        }
        (*ap)->keynum=n-s;//j-1?
        (*ap)->parent=(*q)->parent;
        for(i=0;i<=n-s;i++){
            if((*ap)->ptr[i]!=NULL)(*ap)->ptr[i]->parent=(*ap);
        }
        (*q)->keynum=s-1;
    }
    
    3.Inorder

    中序遍历b树
    参数:T为b树根节点
    思路:此处参考二叉树的中序遍历递归算法,如果其他操作都正确的话,按照b树的特点,中序遍历输出一定是一个升序排列。

    void Inorder(BTree T){
        if(T==NULL)return;
        int i;
        for(i=0;i<T->keynum;i++){
            Inorder(T->ptr[i]);
            printf(" %d ",T->key[i+1]);
        }
        Inorder(T->ptr[i]);
    }
    
    4.Preorder

    先序遍历b树
    参数:T为b树根节点
    思路:此处参考二叉树的先序遍历递归算法,先序遍历的方法可以按照缩进的方式来表现b树的结构,每次访问节点的时候调用一下求深度的函数,输出相应个数的空格即可实现缩进。

    void preorder(BTree T){
        if(T==NULL)return;
        int i,j;
        j=Depth(T);
        for(i=0;i<j;i++){
            printf("    ");
        }
        printf("[");
        printf("关键字:%d |",T->keynum);
        for(i=0;i<T->keynum;i++){
            printf(" %d ",T->key[i+1]);
        }
        printf("]");
        if(T->parent){
            printf("T->parent->keynum=%d   ",T->parent->keynum);
            printf("T->parent->key[1]=%d",T->parent->key[1]);
        }
        printf("\n");
        for(i=0;i<=T->keynum;i++){
            preorder(T->ptr[i]);
        }
    }
    
    5.Destroy

    后序遍历实现释放节点销毁b树
    参数:T某节点
    思路:此处参考二叉树的销毁算法,先序遍历和中序遍历都不能实现销毁b树,反而会造成“野指针”,先释放完父母节点再访问孩子节点这种操作是禁止的

    void Destroy(BTree *T){
        if((*T)==NULL)return;
        int i;
        BTNode *p=(*T);
        if(p!=NULL){
            for(i=0;i<=p->keynum;i++){
                BTNode*q=p->ptr[i];
                Destroy(&(q));
            }
            free(p);
        }
        
        (*T)=NULL;
    }
    
    6.DeleteBTree

    删除关键字
    参数:删除T树中p所指结点的第i个关键字
    思路:首先需要明确一点:删除非叶子结点必然会导致不满足B树性质
    那么可以这样处理:被删关键字为该结点中第i个关键字key[i],则可从指针ptr[i]所指的子树中找出最小关键字,代替key[i]的位置,然后在叶结点中删去最小关键字。 因此,把在非叶结点删除关键字的问题就变成了删除叶子结点中的关键字的问题了调用successor函数
    (1)被删关键字所在结点的关键字数目不小于(m-1)/2,则只需从结点中删除关键字和相应下标的指针,树的其它部分不变,调用remove函数
    (2)被删关键字所在结点的关键字数目等于(m-1)/2,则需调整。调用restore函数

    void DeleteBTree(BTree *p,int i,BTree *T){
        if((*p)->ptr[i]!=NULL){//如果*p不指向根节点
            Successor(&(*p),i);//将该数用它右边子树的最左下端覆盖,p指向覆盖的数
            printf("sccessor:\n");
            PrintBTree(*T);
            printf("\n");
            system("pause");
            DeleteBTree(&(*p),1,&(*T));//删除新调整的关键字
        }
        else{
            Remove(&(*p),i);//移除p里的第i个关键字
            printf("remove:\n");
            PrintBTree(*T);
            printf("\n");   
            system("pause");
            if((*p)->keynum<(m-1)/2){
                Restore(&(*p),&(*T));//调整B-Tree布局
            }
        }
    }
    

    找出最小关键字代替被删非叶子节点关键字函数
    参数:被删关键字所在节点为p,i为下标
    思路:例:
    在这里插入图片描述
    找该关键字右边子树的最左边的叶子节点的第一个关键字,覆盖原关键字并把指针置为需要删除的关键字所在的叶子节点。

    void Successor(BTree *p,int i){
        BTNode *q;
        for(q=(*p)->ptr[i];q->ptr[0]!=NULL;q=q->ptr[0]);
        (*p)->key[i]=q->key[1];
        (*p)=q;
    }
    

    在节点中删除关键字的函数
    参数:p为被删关键字所在节点,i为下标
    思路:使用for循环将前一位的关键字覆盖即可

    void Remove(BTree*p,int i){
        int j;
        for(j=i;j<=(*p)->keynum;j++){
            (*p)->key[j]=(*p)->key[j+1];
        }
        (*p)->keynum--;
    }
    

    调整B树结构函数
    参数:P指向引起结构需要调整的节点,T为b树根节点
    思路:
    情况有如下四种:
    1.判断p是不是指向根节点,若p指向根节点且p内不含关键字,则根节点指针下移至零号子树并释放根节点,否则返回空
    2.如果p有左兄弟且左兄弟的关键字个数>(m-1)/2,则优先向左兄弟借它的最大关键字,调用moveleft函数。
    3.如果p左兄弟关键字个数不够但是有右兄弟且右兄弟关键字个数够,则向右兄弟借,调用moveright函数。
    4.如果这两者都不够借,这时候找父母节点借并合并节点,调用combine函数。

    最后判断父母节点是否符合b树的结构,不符合则需要继续向上调整,调用自身restore函数。

    void Restore(BTree *p,BTree* T){
        BTNode*q;
        q=(*p)->parent;//此函数内对某点的操作都需要传某节点的父母节点作为参数
        if(q==NULL){//如果(*p)已经是根节点???
            if((*p)->keynum==0){
                (*T)=(*p)->ptr[0];
                if(*T){
                    (*T)->parent=NULL;
                }
                free((*p));
            }
            return;
        }
        int j=0;
        int b=0;//是否调整成功?0为未成功,1为成功
        for(j=0;j<=q->keynum;){//找到下标
            if((*p)==q->ptr[j]){
                break;
            }
            j++;
        }
        
        if(j>0&&b==0){
            if(q->ptr[j-1]->keynum>(m-1)/2){
                MoveLeft(&q,j);//找左兄弟节点借
                printf("moveleft:\n");
                PrintBTree(*T);
                printf("\n");
                system("pause");
                b=1;
            }
            else{b=0;} 
        }
        if(j<q->keynum&&b==0){
            if(q->ptr[j+1]->keynum>(m-1)/2){
                MoveRight(&q,j);//找右兄弟节点借
                printf("moveright:\n");
                PrintBTree(*T);
                printf("\n");        
                system("pause");
                b=1;
            }
            else{b=0;} 
        }
        if(b==0){//左右节点都借不了
            Combine(&q,j);//和父母节点的某关键字合并
            printf("combine:\n");
            PrintBTree(*T);
            printf("\n");
            system("pause");
            b=1;
        }
        //?
        if(b==1&&q->keynum<(m-1)/2){//如果父母节点不符合条件继续对其进行布局
            Restore(&q,&(*T));
        }
    }
    

    向左兄弟借最大关键字函数
    参数:注意!!!这里的q指的是被调整节点的双亲结点。j是q的ptr数组指向被调整结点的下标。这么设计的好处是对兄弟的操作更为方便,可以直接通过改变ptr下标进行。
    思路:
    先找到被调整结点p和他的左兄弟lbro。
    p中的关键字和指针全部向后移动1位腾出key[1]和ptr[0]的位置。且p的关键字个数加1.
    将双亲结点的key[j]和左兄弟最右子树赋给p的key[1]和ptr[0].改变子树的父母指针为p。
    最后用左兄弟的最大关键字覆盖双亲结点q的key[j].左兄弟的关键字个数减一即可。

    void MoveLeft(BTree *q,int j){
        int i;
        BTNode*p;//需要调整的节点
        BTNode*lbro;//p的左兄弟
        p=(*q)->ptr[j];
        lbro=(*q)->ptr[j-1];
        for(i=p->keynum;i>=0;i--){//p点所有指针和关键字向后移1位腾出最左的位置
            p->key[i+1]=p->key[i];
            p->ptr[i+1]=p->ptr[i];
        }
        p->key[1]=(*q)->key[j];
        p->ptr[0]=lbro->ptr[lbro->keynum];
        p->keynum++;
        if(lbro->ptr[lbro->keynum]){
            lbro->ptr[lbro->keynum]->parent=p;
        }
        (*q)->key[j]=lbro->key[lbro->keynum];
        lbro->ptr[lbro->keynum]=NULL;
        lbro->keynum--;
    }
    

    向右兄弟借最小关键字函数
    参数:注意!!!这里的q指的是被调整节点的双亲结点。j是q的ptr数组指向被调整结点的下标。这么设计的好处是对兄弟的操作更为方便,可以直接通过改变ptr下标进行。
    思路:例如下图:
    在这里插入图片描述
    先找到被调整结点p和他的右兄弟lbro。p的关键字个数加1.
    将双亲结点的key[j+1]和右兄弟最左子树赋给p的key[p->keynum]和ptr[p->keynum].改变子树的父母指针为p。
    用右兄弟的最小关键字覆盖双亲结点q的key[j+1].右兄弟中的关键字和指针全部向前移动1位覆盖key[1]和ptr[0]的位置。右兄弟的关键字个数减一即可。

    void MoveRight(BTree *q,int j){
        int i;
        BTNode*p;
        BTNode*rbro;
        p=(*q)->ptr[j];
        rbro=(*q)->ptr[j+1];
        p->keynum++;
        p->key[p->keynum]=(*q)->key[j+1];
        p->ptr[p->keynum]=rbro->ptr[0];
        if(rbro->ptr[0])
        {
            rbro->ptr[0]->parent=p;
        }
        (*q)->key[j+1]=rbro->key[1];
        for(i=1;i<=rbro->keynum;i++)
        {
            rbro->key[i-1]=rbro->key[i];
            rbro->ptr[i-1]=rbro->ptr[i];        
        }
        rbro->keynum--;    
    }
    

    与双亲结点中关键字结合函数
    参数:注意!!!这里的q指的是被调整节点的双亲结点。j是q的ptr数组指向被调整结点的下标。这么设计的好处是对兄弟的操作更为方便,可以直接通过改变ptr下标进行。
    思路:例如下图:展示的是与双亲结点对应关键字还有右兄弟合并
    在这里插入图片描述
    先找到被调整结点p和他的左兄弟lbro和右兄弟rbro
    经过分析向左合并的代码比向右合并的代码简单非常多,因为不需要多一轮关键字和指针的移位。
    情况如下:
    1.如果p有左兄弟则优先与左兄弟和双亲结点的对应关键字合并。
    2.如果p只有右兄弟,则还是按照左合并的逻辑,让右兄弟来左合并p(此部分代码冗余但是因为时间关系没有修改好)
    向左合并逻辑如下:
    1.左兄弟的结尾加上双亲结点q->key[j],然后将p的所有指针和关键字接入左兄弟的结尾。
    2.释放p结点的空间,双亲结点后面的指针和关键字分别向前移动1位

    void Combine(BTree *q,int j){
        int i;
        BTNode *p;
        BTNode*lbro;
        BTNode*rbro;
        p=(*q)->ptr[j];
        if(j>0&&j<=(*q)->keynum){//combine with leftbro
            lbro=(*q)->ptr[j-1];
            lbro->keynum++;
            lbro->key[lbro->keynum]=(*q)->key[j];
            lbro->ptr[lbro->keynum]=p->ptr[0];
            if(p->ptr[0]){
                p->ptr[0]->parent=lbro;
            }
            i=1;
            for(;i<=p->keynum;i++){
                lbro->keynum++;
                lbro->key[lbro->keynum]=p->key[i];
                lbro->ptr[lbro->keynum]=p->ptr[i];
                if(p->ptr[i]){
                    p->ptr[i]->parent=lbro;
                }
            }
            (*q)->ptr[j]=NULL;
            free(p);p=NULL;
            for(i=j;i<(*q)->keynum;i++){
                (*q)->key[i]=(*q)->key[i+1];
                (*q)->ptr[i]=(*q)->ptr[i+1];
            }
            (*q)->keynum--;
        }
        else{//combine with rightbro
            rbro=(*q)->ptr[j+1];
            p->keynum++;
            p->key[p->keynum]=(*q)->key[j+1];
            p->ptr[p->keynum]=rbro->ptr[0];
            if(rbro->ptr[0]){
                rbro->ptr[0]->parent=p;
            }
            i=1;
            for(;i<=rbro->keynum;i++){
                p->keynum++;
                p->key[p->keynum]=rbro->key[i];
                p->ptr[p->keynum]=rbro->ptr[i];
                if(rbro->ptr[i]){
                    rbro->ptr[i]->parent=p;
                }
            }
            (*q)->ptr[j+1]=NULL;
            free(rbro);rbro=NULL;
            for(i=j+1;i<(*q)->keynum;i++){
                (*q)->key[i]=(*q)->key[i+1];
                (*q)->ptr[i]=(*q)->ptr[i+1];
            }
            (*q)->keynum--;
        }
    }
    
    7.Depth

    求树的深度
    参数:B树结点T
    思路:因为b树的所有叶子都在同一层,所以求b树的深度非常简单,只要一直遍历到叶子结点即可。

    int Depth(BTree T){
        if(T==NULL){
            return 0;
        }
        BTree p;
        int i=1;
        for(p=T;p->ptr[0]!=NULL;i++,p=p->ptr[0]);
        return i;
    }
    
    8.printBTree

    (这个函数经过修改可以用在二叉树上)
    输出B树
    参数:B树根结点T
    思路:需要输出B树的结构的话,按照计算机的逻辑,需要从根节点开始一层一层向下打印,显然先序,中序,后序遍历无法满足这个要求。层次遍历需要用到队列。

    Status PrintBTree(BTree t){
        LinkList L;
        if(t==NULL){
            printf("  B树为空树");
            return OK;
        }
        InitQueue(&L);//初始化队列 
        Traverse(t,L,0,0);//利用队列输出 
        DestroyQueue(L);//销毁队列 
        return OK;
    }
    

    层次遍历B树
    参数:t为b树结点,L为队列,newline标志何时应该换行,sum标志新一行有多少个关键字。
    思路:访问某节点的同时,把他们的孩子节点都入队,用sum标记个数。如果L队列不为空,就出队一个节点,同时调用自身又把这个节点的所有子节点入队。如此循环直到队列为空为止。

    Status Traverse(BTree t,LinkList L,int newline,int sum){
        int i;
        BTree p;
        if(t!=NULL){
            printf("  [ ");
            printf("关键字:%d |",t->keynum);
            Enqueue(L,t->ptr[0]);//入队         
            for(i=1;i<=t->keynum;i++){
                printf(" %d ",t->key[i]);
                Enqueue(L,t->ptr[i]);//子结点入队 
            }
            sum+=t->keynum+1;
            printf("]");
            if(newline==0){//需要另起一行 
                printf("\n");
                newline=sum-1;
                sum=0;
            }
            else
                newline--;
        }
    
        if(IfEmpty(L)==FALSE){//l不为空 
            Dequeue(L,&p);//出队,以p返回 
            Traverse(p,L,newline,sum); //遍历出队结点 
        }
        return OK;
    }
    

    其他队列相关操作

    //初始化队列 
    Status InitQueue(LinkList *L){
        (*L)=(LNode*)malloc(sizeof(LNode));//分配结点空间 
        if(*L==NULL) //分配失败              
            return OVERFLOW;
        (*L)->next=NULL;
        return OK;
    }
    //新建结点 
    LNode* CreateNode(BTNode *p){
        LNode *q;
        q=(LNode*)malloc(sizeof(LNode));//分配结点空间
        if(q!=NULL){ //分配成功 
            q->data=p;
            q->next=NULL;
        }
        return q;
    }
    //元素q入队列
    Status Enqueue(LNode *p,BTNode *q){ 
        if(p==NULL)                                     
            return ERROR;                               
        while(p->next!=NULL) //调至队列最后 
            p=p->next;
        p->next=CreateNode(q);//生成结点让q进入队列 
        return OK;
    }
    //出队列,并以q返回值 
    Status Dequeue(LNode *p,BTree *q){
        LNode *aq;
        if(p==NULL||p->next==NULL) //删除位置不合理 
            return ERROR; 
        aq=p->next;//修改被删结点aq的指针域
        p->next=aq->next;                               
        (*q)=aq->data;
        free(aq); //释放结点aq
        return OK;
    }
    //队列判空 
    Status IfEmpty(LinkList L){
        if(L==NULL) //队列不存在 
            return ERROR;
        if(L->next==NULL)//队列为空 
            return TRUE;
        return FALSE;//队列非空 
    }
    //销毁队列 
    void DestroyQueue(LinkList L){
        LinkList p;
        if(L!=NULL){
            p=L;
            L=L->next;
            free(p); //逐一释放 
            DestroyQueue(L);
        }
    }
    

    (二)main.c(此处按照操作函数关系图的最上层函数分别实现)

    为了方便写函数,这里使用了全局变量
    BTree T;
    KeyType key[100];
    T用来指向B树的根节点,key[100]用来一次向B树插入多个关键字。

    1.主菜单
    void welcome()
    {
        int choice;  
      A:system("cls");
        printf("                              主菜单\n");
        printf("  ----------------------------------------------------\n");
        printf("******************************************************\n");
        printf("\n");
        printf("  1---创建B-Tree                   2---销毁B-Tree\n");
        printf("\n");
        printf("  3---删除关键字                    4---查找关键字 \n");
        printf("\n");
        printf("  5---中序遍历B-Tree               6---插入关键字\n");
        printf("\n");           
        printf("  7---先序遍历B-Tree               8---层次遍历B-Tree\n");
        printf("\n");
        printf("  9---退出菜单\n");
        printf("\n");
        printf("***************************************************\n");
        printf("  -------------------------------------------------\n");
        printf("\n");               
        printf("请输入序号:\n");
        fflush(stdin);
        scanf("%d",&choice);
        switch(choice)
        {
            case 1:CreateBTree();system("pause"); goto A;
            case 2:destroyBTree();system("pause"); goto A;
            case 3:delete();system("pause"); goto A;
            case 4:searchKey();system("pause"); goto A;
            case 5:Inorder(T);printf("\n");system("pause"); goto A;
            case 6:insertKey();printf("\n");system("pause"); goto A;
            case 7:preorder(T);printf("\n");system("pause"); goto A;
            case 8:PrintBTree(T);printf("\n");system("pause"); goto A;
            case 9:destroyBTree();break;
            default:goto A;
        } 
        return; 
    } 
    
    2.创建B树
    void CreateBTree(){
        if(T!=NULL){
            printf("B-TRee已存在,不可以重复创建\n");
            return;
        }
        printf("please enter the key(当输入为-1时结束输入):\n");
        int i;
        for(i=1;i<100;i++){//key数组的零号单元未用
            scanf("%d",&key[i]);
            if(key[i]<0){
                key[i]=-1;
                break;
            }
        }
        Result r;
        for(i=1;i<100&&key[i]!=-1;i++){
            SearchBTree(T,key[i],&r);
            if(r.tag==1){
                printf("%d 该关键字已存在!\n",key[i]);
            }
            else{
                InsertBTree(&T,key[i],r.pt,r.i);
            }
        }
        printf("B-Tree生成成功!\n");
        PrintBTree(T);
        printf("\n");
        printf("Depth=%d\n",Depth(T));
    }
    
    3.销毁B树
    void destroyBTree(){
        Destroy(&T);
        printf("BTree销毁成功\n");
        PrintBTree(T);
    }
    
    4.查找关键字
    void searchKey(){
        KeyType k;
        printf("请输入需要查找的关键字\n");
        scanf("%d",&k);
        printf("%d",k);
        system("pause");
        Result r;
        SearchBTree(T,k,&r);
        if (r.tag==1)
        {
            printf("查找成功\n");
            printf("r.pt->i=%d",r.pt->keynum);
        if(r.pt->parent){
            printf("r.pt->parent->keynum=%d  ",r.pt->parent->keynum);
            printf("r.pt->parent->key[1]=%d",r.pt->parent->key[1]);
        }
        }
        else
        {
            printf("查找失败\n");
        }
    }
    
    5.删除关键字
    void delete(){
        Result r;
        KeyType k;
        printf("请输入需要删除的关键字\n");
        scanf("%d",&k);
        printf("%d",k);
        system("pause");
        SearchBTree(T,k,&r);
        if(r.tag==0){
            printf("该关键字不存在\n");
            return;
        }
        DeleteBTree(&(r.pt),r.i,&T);
        PrintBTree(T);
        system("pause");
    }
    
    6.插入关键字
    void insertKey(){
        printf("please enter the key(当输入为-1时结束输入):\n");
        int i;
        for(i=1;i<100;i++){//key数组的零号单元未用
            scanf("%d",&key[i]);
            if(key[i]<0){
                key[i]=-1;
                break;
            }
        }
        Result r;
        for(i=1;i<100&&key[i]!=-1;i++){
            SearchBTree(T,key[i],&r);
            if(r.tag==1){
                printf("%d 该关键字已存在!\n",key[i]);
            }
            else{
                InsertBTree(&T,key[i],r.pt,r.i);
            }
        }
        printf("B-Tree插入成功!\n");
        PrintBTree(T);
        printf("\n");
        printf("Depth=%d\n",Depth(T));
    }
    

    五、测试

    (一)初始测试数据

    10 9 8 7 6 5 4 3 2 1 -1

    (二)测试步骤

    1.初始化,输入初始数据序列
    2.插入11 12 13 -1
    3.删除6
    4.删除10
    5.删除7

    (三)测试预期

    在这里插入图片描述

    (四)测试结果(成功)

    1.生成功能
    在这里插入图片描述
    2.插入功能无误
    在这里插入图片描述
    3.Remove函数和combine函数无误
    在这里插入图片描述
    4.Moveright函数无误
    在这里插入图片描述
    5.sccessor函数无误
    在这里插入图片描述

    (五)其他功能测试

    1.菜单
    在这里插入图片描述
    2.中序遍历
    在这里插入图片描述
    3.先序遍历
    在这里插入图片描述
    4.查找
    在这里插入图片描述
    5.销毁
    在这里插入图片描述

    六、可执行文件和代码

    https://download.csdn.net/download/weixin_45849757/15601786

    展开全文
  • 数据结构 - 逻辑结构和存储结构

    万次阅读 2017-10-15 22:18:18
    程序=算法+数据结构 N.沃思(Niklaus Wirth)教授提出:  程序=算法+数据结构  以上公式说明了如下两个问题:  (1)算法决定如何构造和组织数据(算法→数据结构)。  (2)算法的选择依赖于作为基础的...

    程序=算法+数据结构

    N.沃思(Niklaus Wirth)教授提出: 
    程序=算法+数据结构 
    以上公式说明了如下两个问题: 
    (1)算法决定如何构造和组织数据(算法→数据结构)。 
    (2)算法的选择依赖于作为基础的数据结构(数据结构→算法)。 
    软件=程序+文档(软件工程的观点)


    求解非数值计算的问题

    主要考虑的是设计出合适的数据结构及相应的算法。 
    即:首先要考虑对相关的各种信息如何表示、组织和存储? 
    因此,可以认为:数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。


    数据结构基本概念

    几个概念: 
    数据(Data):是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。 
    数据元素(Data Element):是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 
    数据项是数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。 
    数据对象(Data Object):是性质相同的数据元素的集合。是数据的一个子集。

    什么是数据结构? 
    定义1—- 
    是相互之间存在一种或多种特定关系的数据元素的集合。 
    定义2—- 
    按某种逻辑关系组织起来的一批数据(或称带结构的数据元素的集合)应用计算机语言并按一定的存储表示 方式把它们存储在计算机的存储器中,并在其上定义了一个运算的集合。


    逻辑结构

    数据元素间抽象化的相互关系(简称为逻辑结构)。 
    与数据的存储无关,独立于计算机,它是从具体问题抽象出来的数学模型。 
    存储结构(物理结构)—- 
    数据元素及其关系(数据的逻辑结构)在计算机存储器中的存储形式。 
    是逻辑结构用计算机语言的实现,它依赖于计算机语言。 
    运算(算法)

    逻辑结构—划分方法一 
    (1)线性结构—- 
    有且仅有一个开始和一个终端结点,并且所有结点都最多只有一个直接前趋和一个后继。 
    例如:线性表、栈、队列、串 
    (2)非线性结构—- 
    一个结点可能有多个直接前趋和直接后继。 
    例如:树、图等。

    逻辑结构—划分方法二 
    一、集合 结构中的数据元素除了同属于一种类型外,别无其它关系。 
    二、线性结构 结构中的数据元素之间存在一对一的关系。 
    三、树型结构 结构中的数据元素之间存在一对多的关系。 
    四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。


    存储结构

    存储结构两方面的内容: 
    (1)数据元素自身值的表示(数据域) 
    (2)该结点与其它结点关系的表示(链域) 
    两种基本的存储方法: 
    (1)顺序存储方法(顺序存储结构) 
    (2)链接存储方法(链式存储结构) 
    同一种逻辑结构可采用不同的存储方法(以上两种之一或组合),这主要考虑的是运算方便及算法的时空要求。


    数据结构的运算(对数据的操作)

    ⑴ 建立(Create)一个数据结构; 
    ⑵ 消除(Destroy)一个数据结构; 
    ⑶ 从一个数据结构中删除(Delete)一个数据元素; 
    ⑷ 把一个数据元素插入(Insert)到一个数据结构中; 
    ⑸ 对一个数据结构进行访问(Access); 
    ⑹ 对一个数据结构(中的数据元素)进行修改(Modify) 
    ⑺ 对一个数据结构进行排序(Sort); 
    ⑻ 对一个数据结构进行查找(Search)。


    数据类型及抽象数据类型

    数据类型:在一种程序设计语言中,变量所具有的数据种类。 
    例1、 在FORTRAN语言中,变量的数据类型有整型、实型、和复数型 
    例2、在C语言中 
    数据类型:基本类型和构造类型 
    基本类型:整型、浮点型、字符型 
    构造类型:数组、结构、联合、指针、枚举型、自定义 
    注意:数据结构不同于数据类型,也不同于数据对象,它不仅要描述数据对象的数据类型,而且要描述数据对象各元素之间的相互关系。

    抽象数据类型(Abstract Data Type ,简称ADT):是指一个数学模型以及定义在该模型上的一组操作。 
    ADT的定义仅是一组逻辑特性描述, 与其在计算机内的表示和实现无关。因此,不论ADT的内部结构如何变化,只要其数学特性不变,都不影响其外部使用。 
    ADT的形式化定义是三元组:ADT=(D,S,P) 
    其中:D是数据对象,S是D上的关系集,P是对D的基本操作集。 
    ADT的一般定义形式是: 
    ADT <抽象数据类型名>{ 
    数据对象: <数据对象的定义> 
    数据关系: <数据关系的定义> 
    基本操作: <基本操作的定义> 
    } ADT <抽象数据类型名>

    其中数据对象和数据关系的定义用伪码描述。 
    基本操作的定义是: 
    <基本操作名>(<参数表>) 
    初始条件: <初始条件描述> 
    操作结果: <操作结果描述> 
    初始条件:描述操作执行之前数据结构和参数应满足的条件;若不满足,则操作失败,返回相应的出错信息。 
    操作结果:描述操作正常完成之后,数据结构的变化状况和 应返回的结果。


    算法

    算法的概念和描述: 
    什么是算法? 
    所谓算法(Algorithm)是对特定问题求解方法(步骤)的一种描述。 
    为解决某一特定问题而由若干条指令组成的有穷序列。 
    适合于计算机程序实现的求解问题的方法

    算法的概念和描述: 
    一个算法必须满足以下五个准则: 
    (1)有穷性—执行了有限条指令后一定要终止。 
    (2)确定性(无二义)— 
    算法的每一步操作都必须有确切定义,不得有任何歧义性。 
    (3)可(能)行性— 
    算法的每一步操作都必须是可行的,即每步操作均能在有限时间内完成。 
    (4)输入数据— 
    一个算法有n(n>=0)个初始数据的输入。 
    (5)输出数据— 
    一个算法有一个或多个与输入有某种关系的有效信息的输出。

     常见函数的时间复杂度按数量递增排列及增长率。 
    常数阶O(1) 
    对数阶O(log2n) 
    线性阶O(n) 
    线性对数阶O(nlog2n) 
    平方阶O(n2) 
    立方阶O(n3) 
    …… 
    k次方阶O(nk) 
    指数阶O(2n)


    空间复杂度(Space complexity)

    :是指算法编写成程序后,在计算机中运行时所需存储空间大小的度量。记作: S(n)=O(f(n)) 
    其中: n为问题的规模(或大小) 
    该存储空间一般包括三个方面: 
    指令常数变量所占用的存储空间; 
    输入数据所占用的存储空间; 
    辅助(存储)空间。 
    一般地,算法的空间复杂度指的是辅助空间。 
    一维数组a[n]: 空间复杂度 O(n) 
    二维数组a[n][m]: 空间复杂度 O(n*m)



    展开全文
  • 二叉查找树ADT

    2019-02-13 10:15:00
    二叉查找树ADT  定义:是一个二叉树,其中每一个节点的值大于左子树的所有值而小于右子的所有值  平衡二叉树:平衡是指一个二叉树的任何节点的深度均不得过深 AVL  定义:是一个二叉查找,每个节点的左子树...

    二叉查找树ADT

      定义:是一个二叉树,其中每一个节点的值大于左子树的所有值而小于右子树的所有值

      平衡二叉树:平衡是指一个二叉树的任何节点的深度均不得过深

    AVL树

      定义:是一个二叉查找树,每个节点的左子树与右子树的高度差最多为1,AVL树的结构变化(添加或者删除元素可以通过旋转调整),从新满足AVL树的要求

    旋转

      插入旋转:左左与右右使用单旋转,左右与右左使用双旋转,旋转从不满足AVL性质的深度最大的节点开始,调整该节点的大深度的子树  

    转载于:https://www.cnblogs.com/flydoging/p/10348112.html

    展开全文
  • 逻辑结构:集合结构、线性结构、形结构、图形结构 物理结构(即存储结构):顺序存储、链式存储 链式存储结构: 其实定义的时候都是定义的一个节点的类型,之后在初始化的时候再根据逻辑结构的类型把一个个节点给...

    1.概述

    数据结构 = 逻辑结构 + 物理结构

    逻辑结构:集合结构、线性结构、树形结构、图形结构

    物理结构(即存储结构):顺序存储、链式存储

    链式存储结构:
    其实定义的时候都是定义的一个节点的类型,之后在初始化的时候再根据逻辑结构的类型把一个个节点给组合起来

    抽象数据类型(Abstract Data Type,ADT):
    指一个数学模型及定义在该模型上的一组操作。
    我们自己定义了链式存储结构,如下面的代码中所写,之后我们就可以运用那些操作了,例如settergetter方法。

    2.单向链表:

    节点:数据域 + 指向下一节点的指针(为了方便叙述,就直接使用C语言里面的指针这个名词了,不过java里面是没有指针这个概念的哦,下同)

    class ListNode{
        private int data;
        private ListNode next;
    
        public ListNode(int data) {
          this.data = data;
        }
    
        public int getData() {
          return data;
        }
    
        public void setData(int data) {
          this.data = data;
        }
    
        public ListNode getNext() {
          return next;
        }
    
        public void setNext(ListNode next) {
          this.next = next;
        }
      }
    

    3. 双向链表

    节点:数据域 + 指向前一个的指针 + 指向后一个的指针

    class DLLNode{
        private int data;
        private DLLNode next;
        private DLLNode previous;
    
        public DLLNode(int data) {
          this.data = data;
        }
    
        public int getData() {
          return data;
        }
    
        public void setData(int data) {
          this.data = data;
        }
    
        public DLLNode getNext() {
          return next;
        }
    
        public void setNext(DLLNode next) {
          this.next = next;
        }
    
        public DLLNode getPrevious() {
          return previous;
        }
    
        public void setPrevious(DLLNode previous) {
          this.previous = previous;
        }
      }
    

    4. 二叉树

    节点:数据域 + 指向右孩子的指针 + 指向左孩子的指针
    可以发现,二叉树节点的定义其实和双向链表的定义是一样的,所以得灵活变通啊,二叉树节点的组合可以去看我的前一篇博客点这里

     class BinaryTreeNode{
        private int data;
        private BinaryTreeNode left;
        private BinaryTreeNode right;
    
        public BinaryTreeNode(int data) {
          this.data = data;
        }
    
        public BinaryTreeNode() {
        }
    
        public int getData() {
          return data;
        }
    
        public void setData(int data) {
          this.data = data;
        }
    
        public BinaryTreeNode getLeft() {
          return left;
        }
    
        public void setLeft(BinaryTreeNode left) {
          this.left = left;
        }
    
        public BinaryTreeNode getRight() {
          return right;
        }
    
        public void setRight(BinaryTreeNode right) {
          this.right = right;
        }
      }
    
    展开全文
  • 参考资料:《数据结构与算法分析——C语言描述》4.3一节 #include #include #define N 10 typedef struct BinTreeNode { int data; struct BinTreeNode *left; struct BinTreeNode *right; }BinTreeNode,*...
  • 数据结构逻辑结构与存储结构

    千次阅读 2013-12-24 22:10:00
    存储结构是数据的逻辑结构用计算机语言的实现,常见的存储结构有 顺序存储,链式存储,索引存储,以及散列存储。其中散列所形成的存储结构叫散列表(又叫哈希表),因此哈希表也是一种存储结构。栈只是一种抽象数据...
  • 因现实世界中的事物集已经被存储到了计算机中,所以就给其起了个泛化了的名字叫数据对象 所以课本上的定义是逻辑结构:是指数据对象中的数据元素之间的相互关系 现实世界中的某一事物集 => 数据对象 某一事物集合中...
  • 数据结构、逻辑结构和物理结构

    千次阅读 2009-12-12 16:18:00
    数据结构逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 数据结构是信息的一种组织...
  • 我不想费脑去记录那些半懂不懂的晦涩概念,比如说数据结构是数据元素的关系的集合,太...文章目录数据结构数据的逻辑结构(数据对象中数据元素的相互关系,面向问题)集合结构线性结构形结构图形结构数据的物理...
  • adt

    2010-03-24 08:43:00
    ADT定义:一个ADT是一个仅由保存的数据类型和可能在这个数据类型上进行的操作定义的。开发者们只能通过ADT的操作方法来访问ADT的属性,而且他们不会知道这个数据类型内部各种操作是如何实现的。那么访问ADT就需要出...
  • 一、逻辑结构类型集合:数据元素间仅同属一个集合,无其他关系。线性结构:1:1关系,开始和终端节点都是唯一的,除了开始节点和终端节点以外,其余节点都有且仅有一个前驱节点,有且仅有一个后继节点。形结构:1:n...
  • 逻辑结构类型 在不会产生混淆的前提下,常将数据的逻辑结构简称为数据结构。 集合:指数据元素之间除了“同属一个集合”的关系外,无其他关系。 线性结构:节点之间存在一对一的关系。特点:开始节点、终端节点都...
  • 数据结构与算法 -- 栈 ADT

    千次阅读 2017-02-14 10:08:09
    这两天翻了下数据结构与算法分析和严蔚敏的数据结构这两本书,受益很多。不过大多的示例不够完整,需要自己动手编写程序。又看了遍培训时的笔记,虽然很糙但是精华的部分还是可以借鉴的。还有看到了不错的博文,参看...
  • 1.表、队列、栈、、散列表、堆(ADT)与数组、链表的关系与区分(数据结构中的概念)  首先,明确两个概念:数据结构与...比如:表就是一种插入与删除位置任意的逻辑结构,队列就是一种先进先出的逻辑结构,栈是
  • 今天再一次读这样的文章,我读数据结构有了一次更深刻的认识;不象在学校学习的时候那么肤浅,也不象在使用的过程中所理解的偏激;总是认为对数据结果有了详细的认识,现在看来不是这样了...继续学习,温故知新呀.. ...
  • 文章目录简介几个概念和线性表的对比的抽象数据类型的存储结构(设计上非常灵活)父亲表示法示例孩子表示法:很像图的邻接表由多重链表表示法引入孩子兄弟表示法 简介 看完这段话就感觉里面肯定有递归。 也...
  • 2.1 逻辑结构与物理结构 2.1.1 逻辑结构 逻辑结构:是指数据对象中数据元素之间的相互关系。 逻辑结构分为以下四种: 1、集合结构:集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系。数据结构中的...
  • ADT】 第四章

    2018-08-23 21:57:30
    ,大部分操作的运行时间平均为O(log N) 是按照大小顺序存储的,不可重复的集合 Collection中基于二叉查找实现了TreeSet和TreeMap类 1 1.1 基础知识 1.2 节点的声明 1.3 的遍历 1.3.1 先序遍历 ...
  • 数据结构 声明:教材为《数据结构(C语言第二版)》,严蔚敏,李冬梅,吴伟民编著 前言:博客的写作出于个人意愿。本来是想来总结每周课程的,但为了方便和大家一起学习,我尽量偏向半总结半学习,用更通俗的语言...
  • 线性表(linear list)是最常用且最简单的数据结构。简言之,一个线性表是n个数据元素的有限序列。至于每个数据元素的具体含义,在不同的情况下各不相同。例如,26个英文字母的字母表: (A,B,C,D,......Z) ...
  • 数据的逻辑结构和存储结构是密不可分的两个方面,一个算法的设计取决于所选定的逻辑结构,而算法的实现依赖于所采用的存储结构。 二、逻辑结构和物理结构(存储结构) 1.逻辑结构 1)定义 逻辑结构是指数据对象中...
  • 1、数据结构的基本概念 在计算机学科中数据结构表示数据在计算机...(1)逻辑结构--抽象层 主要描述的是数据元素之间的逻辑关系 (2)物理结构--结构层 主要描述的是数据元素之间的位置关系 (3)运算结构--实现层
  • 1.数据:描述客观事物的数字、字符以及能输入机器且被处理的各种符号的集合。 2.数据元素:数据元素是组成数据的基本单位,通常称为记录。 3.数据项:不可分割的最小单位...通常有:表结构结构、图形结构。 5....
  • 本设计使学生牢固掌握AVL及其实现方法,并应用该结构实现集合抽象数据类型,提升学生对数据结构与数据抽象的认识,提高学生的综合实践与应用能力。1.2 设计内容本设计分为三个层次:以二叉链表为存储结构,设计与...
  • 数据结构 **数据结构是计算机存储、组织数据的方式。**数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,266
精华内容 1,306
关键字:

adt树逻辑结构