广义表-求广义表深度,建立广义表,复制广义表

简介: 广义表-求广义表深度,建立广义表,复制广义表

广义表-求广义表深度,建立广义表,复制广义表


例:

广义表(a,(a,b),d,e,((i,j),k)) 求广义表的长度和深度

长度为5,深度为3

长度:有效逗号个数+1

深度:有效括号个数


求广义表的深度


广义表的深度指的是广义表中括弧的重数;

空表的深度为1,因为有一对括弧;

原子的深度为0;

解题思路:

1)遍历该广义表各个数据元素,求该元素的深度。如果该元素是原子,则返回深度0;如果该元素是子表,则遍历该子表的深度;

2)递归的出口状态,或者叫做终结状态:当遍历数据元素为原子时返回0,当遍历数据元素为空表时,返回1;

3)设置一个变量max用来记录数据元素中最长的深度;初始化max=0;遍历过程中max与返回的整型值进行比较,取值较大的那一个。直到程序结束。max+1就是广义表的深度;

代码


int GetGListDepth(GList L){
    if(!L) return 1;
    if(L->tag==0) return 0;
    for(int max=0, pp=L;pp;pp=pp->ptr.tp){
        dep=GetGListDepth(pp->ptr.hp);
        if(dep>max)  max=dep;
    }
    return max+1  //非空表的深度是各元素深度最大值加1
}


复制广义表


任何一个非空的广义表均可分解成表头和表尾。反之,一对确定的表头和表尾可唯一确定一个广义表。

由此,复制一个广义表只要分别复制其表头和表尾,然后合成即可。

复制一个广义表,也是不断的复制表头和表尾的过程。如果表头或者表尾同样是一个广义表,依旧复制其表头和表尾。

所以,复制广义表的过程,其实就是不断的递归,复制广义表中表头和表尾的过程。


递归的出口条件:

 如果当前遍历的数据元素为空表,则直接返回空表。

 如果当前遍历的数据元素为该表的一个原子,那么直接复制,返回即可。


代码实现:


Status CopyGList(GList &T, GList L){
        if(!L) T=NULL;  //直接返回空表
        else{
                if(!(T=(GList)malloc(sizeof(GLNode))))  exit(OVERFLOW);  //如果L不是空表,给T分配内存空间
                T->tag=L->tag;
                if(L->tag ==ATOM)  T->atom=L->atom; //直接复制原子
                else
                {
                        CopyGList(T->ptr.hp, L->ptr.hp); //复制表头
                        CopyGList(T->ptr.tp, L->ptr.tp); //复制表尾
                }
       }          return OK;
}


建立广义表的存储结构


typedef struct GLNode{
    int tag;//标志域
    union{
        int atom;//原子结点的值域
        struct GLNode *hp;//子表结点的指针域,hp指向表头
    };
    struct GLNode * tp;//这里的tp相当于链表的next指针,用于指向下一个数据元素
}*Glist
相关文章
树与二叉树的概念 性质及其存储结构
树与二叉树的概念 性质及其存储结构
101 0
|
4月前
广义表,广义表的定义和计算
广义表的定义和概念,包括空表、单元素表、嵌套子表以及如何计算广义表的长度、取表头、取表尾和计算广义表的深度。
141 1
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
4月前
【数据结构】环形、相交、回文、分割、合并、反转链表
【数据结构】环形、相交、回文、分割、合并、反转链表
41 0
|
9月前
|
树的存储结构以及树,二叉树,森林之间的转换
树的存储结构以及树,二叉树,森林之间的转换
52 0
数据结构实验八 数组和广义表的基本操作及应用
数据结构实验八 数组和广义表的基本操作及应用
127 0
什么是广义表
什么是广义表
117 0
二叉树习题系列1--将二叉搜索树排序树转化为双向链表
二叉树习题系列1--将二叉搜索树排序树转化为双向链表
【数据结构】线性表之单链表(讲解实现——带动图理解)(1)
单链表 单链表的优点 1.头部和中间插入或删除数据效率高,无需挪动。 2.按照需求申请释放空间,无需担心空间不够用。 单链表的缺点 1.不可以进行下标随机访问。 2.复杂度是O(n) 3.反向遍历困难 单链表是线性表的一种,单链表是链式存储的线性表,不同于单链表,链表在内存空间中不连续,而是由结构体内的next指针下一条数据进行链接🧐
【数据结构oj】树的度(树和二叉树的相互转化)
【数据结构oj】树的度(树和二叉树的相互转化)
97 0

热门文章

最新文章