求广义表深度（C语言）

在这里插入图片描述

广义表有两种形式，
1.头尾链表存储结构
一个表结点由三个域构成（标志域，指向表头的指针域，指向表尾的指针域），元素结点由两个域构成（标志域，值域）

2.同层结点链表存储结构

在这里插入图片描述
本题使用表节点头指针+下一个节点的广义表形式。

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

typedef struct Node
{
    int tag;//0则为原子结点，1则为表结点
    union{
        char atom;
        struct Node *head;
    }ptr;
    struct Node *tail;
}GList;

void CreatList(GList *GL);
int GetDepth(GList *GL);

void CreatList(GList *GL)
{
    char s;
    s =getchar();
    if(s=='('){ //s='('时，则构造子表
        GL->tag=1;
        GL->ptr.head=(GList*)malloc(sizeof(GList));
        CreatList(GL->ptr.head);//GL->ptr.head为构建子表
     }

    else{//判断易知，此时s只能为字母、')'或者','
        if(s==')'){ //s=')'时，令GL->tail=NULL，同时退出本层递归
            GL=NULL;
            return;
        }
        if(s==','){ //s=','时，构造后继表(当前表的后一个）
            GL->tail=(GList*)malloc(sizeof(GList));
            CreatList(GL->tail);//GL->tail为构造后继表
            return;
        }
        GL->tag=0;//s为字母
        GL->ptr.atom=s;
       }
       //下一个字母s只能为')'或者','
    s=getchar();
    if(s==')'||s=='\n')//s=')'时结束
    {
        GL->tail=NULL;
    }
    else{//s=','时，构造后继表
        GL->tail=(GList*)malloc(sizeof(GList));
        CreatList(GL->tail);
    }
    return;
}

int GetDepth(GList *GL)
{
    int max=0,depth;
    GList *p;
    if(GL->tag==0)//原子结点深度返回0
    {
        return 0;
    }
    p=GL->ptr.head;//进入子表
    if(p==NULL)
    {
        return 1;
    }
    while(p)
    {
        if(p->tag==1)
        {
            depth = GetDepth(p);

        if(depth>max){
                max = depth;
            }
        }
        p=p->tail;//进入后继表
    }
    return max+1;

}

int main()
{
    GList *GL;
    GL = (GList*)malloc(sizeof(GList));
    CreatList(GL);
    int depth;
    depth = GetDepth(GL);
    printf("%d\n%d",depth,depth);
    return 0;
}

在这里插入图片描述

我们还可以写一个函数来输出广义表：

void PrintGList(GList *GL)//先子表，再数据，再后继表
{
    if(GL->tag==1)//要是为表结点
    {
        printf("(");
        if(GL->ptr.head!=NULL)//子表不为空，递归输出子表
        {
            PrintGList(GL->ptr.head);
        }
        printf(")");
    }
    else
    {
      printf("%c",GL->ptr.atom);
    }
    if(GL->tail!=NULL)//后继表不为空，继续递归输出后继表
    {
        printf(",");
        PrintGList(GL->tail);
    }
}

感谢大佬的文章让我得以参考。

求广义表深度（C语言）

推荐阅读