广义表的存储及比较

本文记录了关于广义表的存储，以及比较两个广义表是否相等的一个题目。

1 题目描述

【问题描述】

请写出判断两个广义表是否相等的递归算法，如果两个广义表相等，则输出1，否则输出0。如A=((a))，B=((a))，则A=B，输出1。要求输入的广义表采用链式存储结构存储，并基于链式存储结构编写递归函数。

【输入形式】

输入为由原子元素（数字，字符）、逗号、圆括号组成的广义表。先输入一个广义表，回车后再输入一个广义表。

【输出形式】

数字1，或者0。

【样例输入】

((a),b)

((a),b)

【样例输出】

1

【样例说明】
【评分标准】如果广义表未采用链式存储结构存储，或未基于链式存储结构编写递归函数，都不得分

2 基本思路

思路很简单。用链式结构存储，然后递归比较是否相等。但是由于自己的指 针知识学的很不扎实。做这道简单的题目做了好久。下面介绍一下我做的时候遇到的难点。

难点一：链式结构的设计。因为可能括号层数很多。所以我就设计成这样的结构。

typedef struct GLNode {
    int tag;
    char atom;
    struct GLNode *hp;
    struct GLNode *tp;
}glNode,*Glist;

tag代表标签，如果标签为0，就表示是一个普通元素。这时把hp赋值空（tp代表同层中的另一个元素，hp表示下一层。）。如果标签为1，则表示是（m,n)这种类型的元素。所以要创建子层，然后hp指向它。
这里你可能会问，为啥不把hp和atom设计成一个union类型，这，，，只能说自己太菜了，玩不六union.

数据结构的设计其实并不难。大概是脑子短路了，才觉得这很难😥.

难点二：如果将输入的字符串存入结构。
如果是单个元素，貌似很容易，但是如果是有括号，那怎么办呢。到右括号时看成一个元素。额，貌似不对，如果多个括号怎么办。于是这里我用一个变量记录括号层数。左括号+1，右括号-1，变量为0时也就是成功的剥离出了一个带括号的元素。

难点三：如何比较是否相等，这个其实是比较简单的递归。每一层的比较方式都相同，如果遇到子层，则递归调用，就好了，同一层的就在比较方法里进行比较。

3 具体实现

1.数据的剥离：

Glist storage2(string s) {
    Glist head = new glNode;
    Glist temp;
    Glist w = head;
    int flag = 0;
    int point = 1;
    for (int i = 1; i < s.length(); ++i) {
        if(s[i] == '(') {
            flag++;
           }
        if(s[i] == ')') {
            flag--;
        }
        if ((s[i] == ',' && flag == 0) || i == s.length() - 1 ) {
            storage(temp, s.substr(point, i - point));
            w->tp = temp;
            w = w->tp;
            flag = 0;
            point = i + 1;
        }
    }
    return head->tp;
}

看着是不是有点懵，有一种想小声嘀咕（这是什么垃圾代码）的冲动。好吧，我也有这种冲动。不过尽管如此，我还是想解释一下我的代码😂。首先申请一个头节点。然后定义一个结构体的指针变量temp。然后再定义一个结构体的指针变量w。w指向头节点。前两个判断语句就不说了，用来判断层数的。然后第三个if，一旦执行，就表示找到了一个元素，一开始point指向1（去除了最外围的‘（’），然后找到了一个元素，此时i应该指向的是逗号，然后就应该明白元素的截取了。flag=0表示重新计算层次。

接下来是硬核。w->tp = temp,这是什么意思，这里storage函数的意思是，把元素按照约定的方式存储，然后把第一个节点返回来。

这时候相当于返回绿圈中的节点。如果传入的参数就是单个元素，则返回类似第一个圈的节点。否则就返回第二个圈的节点。然后我们要做什么，就像图上所说的。把头节点指向它不就可以吗。这就是w->tp = temp;然后w = w->tp,这样就可存储右面的绿圈了。

2.数据的存储：

void storage(Glist &l, string s) {
    l = new glNode;
    l->tp = NULL;
    if(s[0] == '('){
            l->tag = 1;
            l->atom = ' ';
            if(s.length() < 2) {
                return;
            }
            storage(l->hp, s.substr(1,s.length() - 2));
    } else {
            l->tag = 0;
            l->hp = NULL;
            l->atom = s[0];
            if(s.length() < 2) {
                return;
            }
            storage(l->tp, s.substr(2,s.length() - 2));
        }
}

又是一段垃圾代码，这段代码就只讲一下元素截取吧，第一个截取，去外层括号（例如，传入的是(a,b)，这时把外层括号剥离）。第二个截取，就是a,b这种情况，把前面的a存储起来，然后把a,剥离，存储b。第一个if（s.len…是为了地方()的情况。第二个if(s.len…..是为了判别传入的元素只有一个这种情形。

对于一个没怎么学过c++的人来说，new似乎很神奇，其实它就等价于(Glist)malloc(sizeof(glNode))，不过new和malloc是有很大区别的，具体可以
参考这篇博文 ，这里再讲一种错误的情况，一开始我写的时候，传入的是temp,不过，我把temp的指向改为了head->tp;然后我在storage函数中（参数为Glist l,没有&别名)直接写Glist n = new glNode,然后l = n;然后在storage2函数中temp=temp->tp,本想着这样实现。

后来就发现这种做法是错误的，根本无法运行，temp = temp->tp这句根本无法执行，为啥无法执行呢，因为temp是空的。你（我）可能会问，l = n,不就相当于temp = n，这不是有值吗。其实一开始的时候，temp = head->tp,这时temp就是空，然后传入，l= n,这句话执行以后并没有让head->tp = n,temp的指向依旧是空，只不过l的指向改变了，换句话说就是你传入的是temp存储的值，你并没有对temp里面存的内容改变成功。

所以这时候就可以用别名，这时传入的参数其实就是head->tp的地址，上边传入的其实是一个空值。如果不想用别名，那么就得传入temp的地址，即传入&temp,参数也得改为Glist l,然后（l)=n;这样也可样，但是比较复杂。

这里我花了很长时间，不得不佩服我啊😅。

3.数据的比较：

int cha(Glist l, Glist m) {
    int cnt = 0;
    while(l != NULL && m != NULL) {
        if(l->tag == 0 && m->tag == 0) {
            if(l->atom != m->atom) {
                cnt++;
            }
        } else if(l->tag == 1 && m->tag == 1) {
            cnt+=cha(l->hp,m->hp);
        } else {
            cnt++;
            break;
        }
        l = l->tp;
        m = m->tp;
        if ((l == NULL && m != NULL) || (l != NULL && m == NULL)) {
            cnt++;
            break;
        }
    }
    return cnt;
}

这个就太简单了，就不说了。cnt=0时，即所有元素都相等。！=0，即有元素不相等。

4 全部代码

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

typedef struct GLNode {
    int tag;
    char atom;
    struct GLNode *hp;
    struct GLNode *tp;
}glNode,*Glist;

void storage(Glist &l, string s) {
    l = new glNode;
    l->tp = NULL;
    if(s[0] == '('){
            l->tag = 1;
            l->atom = ' ';
            if(s.length() < 2) {
                return;
            }
            storage(l->hp, s.substr(1,s.length() - 2));
    } else {
            l->tag = 0;
            l->hp = NULL;
            l->atom = s[0];
            if(s.length() < 2) {
                return;
            }
            storage(l->tp, s.substr(2,s.length() - 2));
        }
}

Glist storage2(string s) {
    Glist head = new glNode
    Glist temp;
    Glist w = head;
    int flag = 0;
    int point = 1;
    for (int i = 1; i < s.length(); ++i) {
        if(s[i] == '(') {
            flag++;
           }
        if(s[i] == ')') {
            flag--;
        }
        if ((s[i] == ',' && flag == 0) || i == s.length() - 1 ) {
            storage(temp, s.substr(point, i - point));
            w->tp = temp;
            w = w->tp;
            flag = 0;
            point = i + 1;
        }
    }
    return head->tp;
}



int cha(Glist l, Glist m) {
    int cnt = 0;
    while(l != NULL && m != NULL) {
        if(l->tag == 0 && m->tag == 0) {
            if(l->atom != m->atom) {
                cnt++;
            }
        } else if(l->tag == 1 && m->tag == 1) {
            cnt+=cha(l->hp,m->hp);
        } else {
            cnt++;
            break;
        }
        l = l->tp;
        m = m->tp;
        if ((l == NULL && m != NULL) || (l != NULL && m == NULL)) {
            cnt++;
            break;
        }
    }
    return cnt;
}

int main()
{
    string d1 = "((a,b),c)";
    string d2 = "((a,b),c)";
    Glist h1 = storage2(d1);
    Glist h2 = storage2(d2);
    int flag = cha(h1,h2);
    if(flag == 0) {
        printf("%d",1);
    } else {
        printf("%d",0);
    }
    return 0;
}

5 一点收获

1.查错，一开始对指向的认知错误，之所以用了很长时间，也是因为自己的查错能力不行，以后再遇到这种情况是，一定要冷静，从头开始履，然后debug，或者打印值，找到错误的语句，然后勇于推翻自己，不要老认为自己想的是对的。错误的认知对人的危害是非常大的。

2.勇于动手，一开始剥离元素对自己来说是比较难的。感觉自己做不出来，就一直没动手，动手之后才发现，思路就是在一点一点中被挖掘出来。所以遇到较难的，难以实现的，要勇于动手。