NOJ数据结构014——求广义表的深度

谁践踏了优雅 2022-11-19 01:16 114阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]

广义表有两种存储结构，分别为头尾链表存储结构和同层结点链存储结构。  
本题使用了这两种方法构建广义表，第二种方法写得略有粗糙，不过说实话，个人认为第二种方法更容易实现。  
话不多说，直接上代码。

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef enum {
        ATOM, LIST} ElemTag;
    //ATOM = 0,表示原子，LIST = 1表示子表
    
    typedef struct GLNode
    {
        
        ElemTag tag; //标志
        union {
        
            int atom; //原子结点
            struct {
        struct GLNode *hp, *tp;}htp; //表结点
        }atom_htp;
    }GLNode, *GList;
    
    typedef struct Devforge
    {
        
        ElemTag tag; //标志
        union {
        
            int atom; //原子结点
            struct Devforge *head; //表结点
        }atom_hp;
        struct Devforge *tail;
    }Devforge, *DevforgeLink;
    
    GList L;
    DevforgeLink M;
    
    void CreateAtom(GList L, char sign); //创建原子节点
    void CreateList(GList L);        //创建子表节点
    char* SearchAddress(char *str);//寻找字符串str对应 ')' 的位置
    void Create_GList_1(GList s, char* str);  //头尾链表存储结构创建广义表
    void Create_GList_2(DevforgeLink s, char* str);  //创建同层结点链存储结构广义表
    int Depth_1(GList L);          //求头尾链表存储结构广义表深度
    int Depth_2(DevforgeLink M);   //求同层结点链存储结构广义表深度
    
    int main()
    {
        
        int dep_1, dep_2;
        char *str;
        str = (char *) malloc (sizeof(char));
        L = (GList) malloc (sizeof(GLNode));
        M = (DevforgeLink) malloc (sizeof(Devforge));
        scanf("%s", str);
        Create_GList_1(L, str+1); //少建一个表
        Create_GList_2(M, str);
        dep_1 = Depth_1(L);
        dep_2 = Depth_2(M);
        printf("%d\n%d", dep_1, dep_2);
        return 0;
    }
    
    void CreateAtom(GList L, char sign)
    {
          //创建原子节点
        L->tag = ATOM;
        L->atom_htp.atom = sign;
    }
    
    void CreateList(GList L)
    {
        //创建子表节点
        L->tag = LIST;
        L->atom_htp.htp.hp = NULL;
        L->atom_htp.htp.tp = NULL;
    }
    
    char* SearchAddress(char *str)
    {
         //寻找字符串str对应 ')' 的位置
      //此函数作用是在递归结束返回上一层后让字符串到应该读取的下一位，相当于输入字符的步骤
        if (str[0] == '\0') {
        
            return 0;
        }
        int flag = 1, len = strlen(str);
        int i;
        for(i = 0; i < len; i++) {
        
            if (str[i] == '(') {
        
                flag++;
            }
            if (str[i] == ')') {
        
                flag--;
            }
            if (flag == 0) {
        
                break;
            }
        }
        if (str[i+1] == '\0') {
        
            return 0;
        }
        return (str+i+1);
    }
    
    void Create_GList_1(GList s, char* str)
    {
          //头尾链表存储结构创建广义表
        if (str[0] == '(') {
         //str 为 '(' 时
            CreateList(s);
            s->atom_htp.htp.hp = (GList) malloc (sizeof(GLNode));
            str = str + 1;
            Create_GList_1(s->atom_htp.htp.hp, str);
            str = SearchAddress(str); //让str跳跃至上一层，即对应')'处
            if (str == 0) {
        
                return; //字符串无了，结束函数
            }
        }
        else if (str[0] == ')') {
           //str 为 ')' 时
            return;
        }
        else if (str[0] == ',') {
         //str 为 ',' 时
            s->atom_htp.htp.tp = (GList) malloc (sizeof(GLNode));
            str = str + 1;
            Create_GList_1(s->atom_htp.htp.tp, str);
            return;
        }
        else {
              //str为 字母 时
            CreateList(s);
            s->atom_htp.htp.hp = (GList) malloc (sizeof(GLNode));
            CreateAtom(s->atom_htp.htp.hp, str[0]);
            str = str + 1;
        }
        //下一个字符有两种可能
        if (str[0] == ')') {
           //str 为 ')' 时
            return;
        }
        else if (str[0] == ',') {
         //str 为 ',' 时
            s->atom_htp.htp.tp = (GList) malloc (sizeof(GLNode));
            str = str + 1;
            Create_GList_1(s->atom_htp.htp.tp, str);
            return;
        }
    }
    
    void Create_GList_2(DevforgeLink s, char* str)
    {
          //同层结点链存储结构
        if (str[0] == '(') {
         //str 为 '(' 时
            s->tag = LIST;
            s->atom_hp.head = (DevforgeLink) malloc (sizeof(Devforge));
            str = str + 1;
            Create_GList_2(s->atom_hp.head, str);
            str = SearchAddress(str); //让str跳跃至上一层，即对应')'处
            if (str == 0) {
        
                return; //字符串无了，结束函数
            }
        }
        else if (str[0] == ')') {
           //str 为 ')' 时
            s = NULL;
            return;
        }
        else if (str[0] == ',') {
         //str 为 ',' 时
            s->tail = (DevforgeLink) malloc (sizeof(Devforge));
            str = str + 1;
            Create_GList_2(s->tail, str);
            return;
        }
        else {
              //str为 字母 时
            s->tag = ATOM;
            s->atom_hp.atom = str[0];
            str = str + 1;
        }
        //下一个字符有两种可能
        if (str[0] == ')') {
           //str 为 ')' 时
            s->tail = NULL;
            return;
        }
        else if (str[0] == ',') {
         //str 为 ',' 时
            s->tail = (DevforgeLink) malloc (sizeof(Devforge));
            str = str + 1;
            Create_GList_2(s->tail, str);
            return;
        }
    }
    
    int Depth_1(GList L)
    {
          //求广义表深度
        int d = 0, max = 0;
        GList s;
        s = L;
        if (L == NULL) return 1;
        if (L->tag == ATOM) return 0;
        while(s != NULL) {
        
            d = Depth_1(s->atom_htp.htp.hp);
            if (d > max) {
        
                max = d;
            }
            s = s->atom_htp.htp.tp;
        }
        return (max+1);
    }
    
    int Depth_2(DevforgeLink M)
    {
        
        int d = 0, max = 0;
        DevforgeLink s;
        s = M->atom_hp.head;
        if (M->tag == ATOM) {
        
            return 0;
        }
        if (s == NULL) {
        
            return 1;
        }
        while (s != NULL) {
        
            if (s->tag == LIST) {
        
                d = Depth_2(s);
            }
            if (d > max) {
        
                max = d;
            }
            s = s->tail;
        }
        return (max+1);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221022/c65cfa38f151458ba24b97c012842a6c.png