作者：解学武

广义表的长度

通过前一节对广义表的介绍，例子中给出了几个广义表的长度。例如：空表的长度为 0，只含有一个原子的广义表长度为 1，等等。

广义表的长度指的是广义表中数据元素的数量。这里需要指明的是，一个广义表中，一个原子算做是一个元素，一个子表也只算做一个元素。

在 LS = (a₁,a₂,…,a_n) 中，a_i表示原子或者子表， LS 的长度为 n。

广义表的深度

广义表的深度，指的是广义表中括号的重数。
例如：C=(a,(b,c,d))：
图1中，从前往后数左括号的数量就是广义表C的深度，为2；也可以从右往左数右括号的数量（红色）。

求解广义表的深度

求广义表的深度之前，首先要将广义表用某个数据结构表示出来，在前边学习广义表时，介绍了两种表示广义表的方法。这里采用的方法是第一种。

表示结构为：（拿广义表C为例） 求广义表深度的算法用到的是递归的思想，解题思路是：

1. 从广义表 C 的开头位置，一次遍历表中每个数据元素：当遍历对象为原子时，返回原子的深度为 0 ；遍历对象为表 C 的子表时，继续遍历子表中的数据元素。
2. 递归的出口有两个：当遍历对象为原子时，返回 0 ；遍历对象为空表时，返回 1 （空表的深度为 1 ）；
3. 设置一个初始值为 0 的整形变量 max ，用 max 和遍历过程中返回的整形数值进行比较，取大的那一个，知道程序结束，max + 1就是广义表的深度。

实现代码为：

int GlistDepth(Glist C){
    //如果表C为空表时，直接返回长度1；
    if (!C) {
        return 1;
    }
    //如果表C为原子时，直接返回0；
    if (C->tag==0) {
        return 0;
    }
    int max=0;//设置表C的初始长度为0；
    for (Glist pp=C; pp; pp=pp->ptr.tp) {
        int dep=GlistDepth(pp->ptr.hp);
        if (dep>max) {
            max=dep;//每次找到表中遍历到深度最大的表，并用max记录
        }
    }
    //程序运行至此处，表明广义表不是空表，由于原子返回的是0，而实际长度是1，所以，此处要+1；
    return max+1;
}

完整代码演示

#include <stdio.h>
#include <stdlib.h>

typedef struct GLNode{
    int tag;//标志域
    union{
        char atom;//原子结点的值域
        struct{
            struct GLNode * hp,*tp;
        }ptr;//子表结点的指针域，hp指向表头；tp指向表尾
    };
}*Glist,GNode;

Glist creatGlist(Glist C){
    //广义表C
    C=(Glist)malloc(sizeof(GNode));
    C->tag=1;
    //表头原子‘a’
    C->ptr.hp=(Glist)malloc(sizeof(GNode));
    C->ptr.hp->tag=0;
    C->ptr.hp->atom='a';
    //表尾子表（b,c,d）,是一个整体
    C->ptr.tp=(Glist)malloc(sizeof(GNode));
    C->ptr.tp->tag=1;
    C->ptr.tp->ptr.hp=(Glist)malloc(sizeof(GNode));
    C->ptr.tp->ptr.tp=NULL;
    //开始存放下一个数据元素（b,c,d）,表头为‘b’，表尾为（c,d）
    C->ptr.tp->ptr.hp->tag=1;
    C->ptr.tp->ptr.hp->ptr.hp=(Glist)malloc(sizeof(GNode));
    C->ptr.tp->ptr.hp->ptr.hp->tag=0;
    C->ptr.tp->ptr.hp->ptr.hp->atom='b';
    C->ptr.tp->ptr.hp->ptr.tp=(Glist)malloc(sizeof(GNode));
    //存放子表(c,d)，表头为c，表尾为d
    C->ptr.tp->ptr.hp->ptr.tp->tag=1;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.hp=(Glist)malloc(sizeof(GNode));
    C->ptr.tp->ptr.hp->ptr.tp->ptr.hp->tag=0;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.hp->atom='c';
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp=(Glist)malloc(sizeof(GNode));
    //存放表尾d
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->tag=1;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp=(Glist)malloc(sizeof(GNode));
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp->tag=0;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp->atom='d';
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.tp=NULL;
    return C;
}
//求广义表的深度，递归调用
int GlistDepth(Glist C){
    if (!C) {
        return 1;
    }
    if (C->tag==0) {
        return 0;
    }
    int max=0;
    for (Glist pp=C; pp; pp=pp->ptr.tp) {
        int dep=GlistDepth(pp->ptr.hp);
        if (dep>max) {
            max=dep;
        }
    }
    return max+1;
}
int main(int argc, const char * argv[]) {
    Glist C=creatGlist(C);
    printf("%d",GlistDepth(C));
    return 0;
}

运行结果：

声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。