[广义表](6.2)线性扩展广义表基本操作

扩展线性存储结构比头尾链存储结构层次清晰，并且便于理解，扩展线性存储结构可以将广义表看作线性表的扩展，只不过是线性表的数据域只支持原子元素，而广义表的数据域可以是原子也可以是另一个广义表

线性扩展存储结构定义如下所示：

typedef struct GLNode
{
    int tag;
    union {
        AtomType data;
        struct GLNode* hp;
    };
    struct GLNode* tp;
}*GList, GLNode;

逻辑图如下所示：

同时，对应广义表的12种基本操作函数声明如下：

/*------------------广义表操作------------------*/
Status InitGList(GList* L);
/*创建空的广义表*/

void visit(GList L);
/*初始条件：广义表L存在
  操作结果：遍历广义表L*/

int DepthGList(GList L);
/*初始条件：广义表L存在
  操作结果：返回广义表L的深度*/

int LengthGList(GList L);
/*初始条件：广义表L存在
  操作结果：返回广义表L的长度*/

Status CreateGList(GList* L, String S);
/*初始条件：S为广义表的书写形式串
  操作结果：通过S创建广义表L*/

Status CopyGList(GList* L, GList T);
/*初始条件：广义表L存在
  操作结果：通过广义表L，复制广义表T*/

GList GetHead(GList L);
/*初始条件：广义表L存在
  操作结果：返回广义表表头*/

GList GetTail(GList L);
/*初始条件：广义表L存在
  操作结果：返回广义表L表尾*/

Status DestroyGList(GList* L);
/*初始条件：广义表L存在
  操作结果：销毁广义表L*/

Status InsertFirst_GL(GList* L, GList e);
/* 初始条件: 广义表L存在 */
 /*操作结果: 插入元素e作为广义表L的第一元素(表头,也可能是子表) */

Status DeleteFirst_GL(GList* L, GList* e);
/*初始条件：*广义表L存在*/
/*操作结果：删除广义表的表头元素，并用e返回其值*/

Status GListEmpty(GList L)
{ /* 初始条件: 广义表L存在
  操作结果: 判定广义表L是否为空 */

同时最难的CreateGList函数对应的字符串操作如下所示，为了简化操作，首先作以下约定

字符串为定长顺序表
字符串的首字符从0开始

/*字符串操作*/
int StrCompare(String S, String T)//比较S和T是否相等
{
    int i = 0;
    while (S[i] != '\0' && T[i] != '\0')
    {
        if (S[i] > T[i])
            return 1;
        if (S[i] < T[i])
            return -1;
        i++;
    }
    if (S[i] == '\0' && T[i] != '\0')
        return -1;
    if (S[i] != '\0' && T[i] == '\0')
        return 1;
    return 0;
}
int StrLength(String S)//判断串S的长度
{
    int i = 0;
    while (S[i] != '\0')
    {
        i++;
    }
    return i;
}

Status SubString(String T, String S, int pos, int len)//自pos起从S中截取长度为len的子串到T中
{
    if (pos < 0 || len<0 || pos + len>StrLength(S))
        exit(OVERFLOW);
    int j = 0;
    for (int i = pos; i < pos + len; i++, j++)
    {
        T[j] = S[i];
    }
    T[j] = '\0';
    return OK;
}

Status StrCopy(String T, String S)//由S复制得到串T
{
    int i = 0;
    while (S[i] != '\0')
    {
        T[i] = S[i];
        i++;
    }
  T[i]='\0';
    return OK;
}
int StrEmpty(String S)//判断字符串S是否为空
{
    if (S[0] == '\0')
        return 1;
    return 0;
}
Status InitString(String S)//创建空字符串
{
    S[0] = '\0';
    return OK;
}
Status CleanString(String S)//清除字符串
{
    memset(S,'\0',sizeof(char)*MAX_STRINGSIZE);//MAX_STRINGSIZE=255
    return OK;
}

下面，我们利用递归思想，逐步讲解lists的操作：

创建广义表

创建广义表的思路和头尾链结构类同，步骤如下：

在给定书写串进行判断的时候会有两种情况，这两种情况为函数的出口，也是基本项：
- 给定表头（字符串长度为1）为原子
- 给定表头（字符串为“（）”）为空
上列两种情况分别对应于空表和原子结点
除上述两种情况外，还有一种情况给定字符串长度大于１也不为“（）”的话，就为子表
- 如果为子表的话，就需要先为子表去除外层括号
- 然后再利用sever取出表头，将子表表头与给定字符串取出的表头进行递归
- 同时还需要判断表尾是否为空，如果不为空的话，利用循环将表尾不断与表头连接

根据上述思路，代码如下所示：

Status CreateGList(GList* L, String S)
/*初始条件：S为广义表的书写形式串
  操作结果：通过S创建广义表L*/
{
    (*L) = (GList)malloc(sizeof(GLNode));
    char* s = "( )";
    String sub, hstr;
    if (!StrCompare(S, s))//给定字符串为"（ ）"为空表
    {
        (*L)->sign = LIST;
        (*L)->hp = NULL;
        (*L)->tp = NULL;
    }
    else if (StrLength(S) == 1)//给定字符为单个字符，为原子结点
    {
        (*L)->sign = ATOM;
        (*L)->data = S[0];
        (*L)->tp = NULL;
    }
    else//其他情况为子表
    {
        (*L)->sign = LIST;
        (*L)->tp = NULL; 
        SubString(sub, S, 1, StrLength(S) - 2);//去外层括号
        sever(sub, hstr);//分离表头和表尾
        CreateGList(&(*L)->hp, hstr);
        GList p = (*L)->hp;
        while (!(StrEmpty(sub)))
        {
            sever(sub, hstr);//不断取出表头
            CreateGList(&p->tp, hstr);
            p = p->tp;
        }
    }
  return OK;
}

同时分割表头和表尾函数sever如下所示

void sever(String str, String hstr)
//将非空串str分割成两部分：hsub为第一个'，'之前的子串，str为之后的子串
{
    int n = StrLength(str);
    int i = 0, k = 0;//k记尚未配对的左括号个数
    String ch;
    do {//搜索最外层的第一个逗号
        SubString(&ch, str, i, 1);
        if (ch[0] == '(')
            k++;
        else if (ch[0] == ')')
            k--;
        i++;
    } while (i < n && (ch[0] != ',' || k != 0));
    if (i < n)
    {
        SubString(hstr, str, 0, i - 1);//截取，前面的子串存入hstr
        SubString(str, str, i, n - i);//截取，后面的子串存入hstr
    }
    else
    {
        StrCopy(hstr, str);
        CleanString(str);
    }
}

复制广义表

复制广义表的操作和遍历类同，思路与头尾链存储结构相似，稍作修改，步骤如下：

每次遍历广义表T的一个结点的同时，为L分配一个结点，会出现下列几种情况
- 当T为NULL时，直接为L赋空
- 当T为原子结点时，直接复制原子，同时递归表尾
- 当T为子表时，递归表头
上述三种情况把广义表逐层分解的一个个结点进行复制

代码如下：

Status CopyGList(GList* L, GList T)
/*初始条件：广义表L存在
  操作结果：通过广义表L，复制广义表T*/
{
    (*L) = (GList)malloc(sizeof(GLNode));
    if (!T)
        (*L) = NULL;
    else
    {
        (*L)->sign = T->sign;//复制枚举变量
        if ((*L)->sign == ATOM)
            (*L)->data = T->data;
        else
            CopyGList(&(*L)->hp, T->hp);
        CopyGList(&(*L)->tp, T->tp);
    }
}

深度与长度

我们通过之前的学习可以知道，深度为最大括号数，也就是最大子表数，而长度为第一层结点的个数，同时需要注意：

原子长度为1
空表深度为1，长度为0

通过上述定义，我们可以写出求深度的递归函数，与遍历也无大区别，需要注意的是，每一层子表返回的时候需要加1，同时需要判断它的表尾是否更深，则在表头结束后和表尾结束后都需要更新max值

代码如下：

int DepthGList(GList L)
/*初始条件：广义表L存在
  操作结果：返回广义表L的深度*/
{
    int dep = 0, max = 0;
    if (L&&L->sign == LIST && L->hp != NULL)
    {
        dep = DepthGList(L->hp) + 1;
        if (dep > max)
            max = dep;
    }
    if (L&&L->tp != NULL)
    {
        dep = DepthGList(L->tp);
    }
    if (dep > max)
        max = dep;
    return max;
}

深度图示如下：

长度就跟简单了，它只需遍历最上层的子表数，这个时候我们可以将广义表当做线性表来看。

代码如下所示：

int LengthGList(GList L)
/*初始条件：广义表L存在
  操作结果：返回广义表L的长度*/
{
    int len = 0;
    if (L&&L->sign == ATOM)//为单个原子
        return 1;
    if (L&&L->sign == LIST && L->hp == NULL)//为空表
        return 0;
    GList p = L->hp;
    while (p)
    {
        len++;
        p = p->tp;
    }
    return len;
}

销毁广义表

销毁也和遍历类同，利用一个指针存储它的表头和表尾，然后逐步释放，出口条件为传入结点为空，需要注意的是，原子结点和表结点的区别：

若是原子结点，则直接赋空，并传入表尾
若是表结点，则传入表头和表尾

Status DestroyGList(GList* L)
/*初始条件：广义表L存在
  操作结果：销毁广义表L*/
{
    GList ph, pt;
    if ((*L))
    {//由pt和ph接替表头和表尾
        if ((*L)->sign == ATOM)
            ph = NULL;
        else
            ph = (*L)->hp;
        pt = (*L)->tp;
        free(*L);
        *L = NULL;
        DestroyGList(&ph);
        DestroyGList(&pt);
    }
}

遍历广义表

遍历广义表是广义表递归操作的基础点，我们知道，当函数为原子的时候，则直接打印出来，而当函数为子表的时候，就继续传入它的表头，而一个归纳项则是，不管元素是子表还是原子，只要表尾不空，则传入表尾。

代码如下所示：

void visit(GList L)
/*初始条件：广义表L存在
  操作结果：遍历广义表L*/
{
    if (L&&L->sign == ATOM)
        printf("%c", L->data);
    else
        visit(L->hp);
    if (L && L->tp != NULL)
        visit(L->tp);
}

取表头

在笔记之前，我们先复习下广义表表头与表尾的定义：

任何一个非空列表其表头可能是原子，也可能是列表，而其表尾必定是列表
例如：
- B=（e）
  - GetHead(B)=e
  - GetTail(B)=( )
- D=(A,B,C)
  - GetHead(D)=A
  - GetTail(D)=(B,C)

取表头的操作难点就在于表头为一子表，那么会有以下几种情况：

表L为空表
- 空表无表头
表头为子表
- 需要通过CopyGList函数复制子表
表头为原子
- 直接复制原子结点即可

通过上述分析，我们可以得到代码如下：

GList GetTail(GList L)
/*初始条件：广义表L存在
  操作结果：返回广义表L表尾*/
{
    GList T;
    if (!L || L->sign == LIST && L->hp == NULL)
    {
        printf("空表无表尾");
        exit(OVERFLOW);
    }
    T = (GList)malloc(sizeof(GLNode));
    if (!T)
        exit(OVERFLOW);
    T->sign = LIST;
    T->tp = NULL;
    CopyGLis(&T->hp, L->hp->tp);
    return T;
}

取表尾

通过上述取表头可知，表尾只可能有以下两种情况：

表L为空表
- 空表无表尾
不为空的情况
- 复制表尾，一定为一个列表

代码如下所示：

GList GetTail(GList L)
/*初始条件：广义表L存在
  操作结果：返回广义表L表尾*/
{
    GList T;
    if (!L || L->sign == LIST && L->hp == NULL)
    {
        printf("空表无表尾");
        exit(OVERFLOW);
    }
    T = (GList)malloc(sizeof(GLNode));
    if (!T)
        exit(OVERFLOW);
    T->sign = LIST;
    T->tp = NULL;
    CopyGList(&T->hp, L->hp->tp);
    return T;
}

其余操作：

下述操作均为简单，则不做单独记录，看代码既能理解

Status InitGList(GList* L)
/*创建空的广义表*/
{
    (*L) = (GList)malloc(sizeof(GLNode));
    if (!(*L))
        return OVERFLOW;
    (*L)->hp = NULL;
    (*L)->tp = NULL;
    return OK;
}
Status InsertFirst_GL(GList* L, GList e)
/* 初始条件: 广义表L存在 */
 /*操作结果: 插入元素e作为广义表L的第一元素(表头,也可能是子表) */
{
    if (!(*L))
    {
        printf("广义表为空");
        return ERROR;
    }
    else
    {
        GList p = (*L)->hp;
        (*L)->hp = e;
        e->tp = p;
    }
    return OK;
}

Status DeleteFirst_GL(GList* L, GList* e)
/*初始条件：*广义表L存在*/
/*操作结果：删除广义表的表头元素，并用e返回其值*/
{
    if (!(*L))
    {
        *e = *L;
    }
    else {
        *e = (*L)->hp;
        (*L)->hp = (*e)->tp;
        (*e)->tp = NULL;
    }
    return OK;
}
Status GListEmpty(GList *L)
/* 初始条件: 广义表L存在
 操作结果: 判定广义表L是否为空 */
{
    if (!(*L) || (*L)->sign == LIST && (*L)->hp == NULL)
        return OK;
    else
        return ERROR;
}

此笔记参考了大佬的博客，在此特别感谢，大佬博客中利用的是动态串来实现广义表操作，原文链接点击此出即可

总结

总的来说，通过之前的记录，广义表有三个状态：为空，子表，原子，这三个状态确定了操作的基本，通过三个状态来进行重复的递归达到目的，对比两种存储结构，线性扩展存储结构比头尾链存储结构清晰易懂，故书上介绍的是头尾链存储结构的操作，通过广义表的遍历我们可以知道基本项和归纳项，上述操作均测试通过，以下附上完整的测试代码：

#define _CRT_SECURE_NO_WARNINGS
#define MAX_STRLENG 255

typedef int Status;

/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#include<stdio.h>
#include<stdlib.h>
typedef enum {
    ATOM, LIST
}ElemTag;
typedef struct GLNode
{
    ElemTag sign;
    union {
        char data;
        struct GLNode* hp;
    };
    struct GLNode* tp;
}*GList, GLNode;

typedef unsigned char String[MAX_STRLENG];

/*字符串操作*/
int StrCompare(String S, String T)//比较S和T是否相等
{
    int i = 0;
    while (S[i] != '\0' && T[i] != '\0')
    {
        if (S[i] > T[i])
            return 1;
        if (S[i] < T[i])
            return -1;
        i++;
    }
    if (S[i] == '\0' && T[i] != '\0')
        return -1;
    if (S[i] != '\0' && T[i] == '\0')
        return 1;
    return 0;
}
int StrLength(String S)//判断串S的长度
{
    int i = 0;
    while (S[i] != '\0')
    {
        i++;
    }
    return i;
}

Status SubString(String T, String S, int pos, int len)//自pos起从S中截取长度为len的子串到T中
{
    if (pos < 0 || len<0 || pos + len>StrLength(S))
        exit(OVERFLOW);
    int j = 0;
    for (int i = pos; i < pos + len; i++, j++)
    {
        T[j] = S[i];
    }
    T[j] = '\0';
    return OK;
}

Status StrCopy(String T, String S)//由S复制得到串T
{
    int i = 0;
    while (S[i] != '\0')
    {
        T[i] = S[i];
        i++;
    }
    T[i] = '\0';
    return OK;
}
int StrEmpty(String S)//判断字符串S是否为空
{
    if (S[0] == '\0')
        return 1;
    return 0;
}
Status InitString(String S)//创建空字符串
{
    memset(S, '\0', sizeof(char) * MAX_STRLENG);
    return OK;
}
Status CleanString(String S)//清除字符串
{
    memset(S, '\0', sizeof(char) * MAX_STRLENG);
    return OK;
}
void sever(String str, String hstr)
//将非空串str分割成两部分：hsub为第一个'，'之前的子串，str为之后的子串
{
    int n = StrLength(str);
    int i = 0, k = 0;//k记尚未配对的左括号个数
    String ch;
    do {//搜索最外层的第一个逗号
        SubString(&ch, str, i, 1);
        if (ch[0] == '(')
            k++;
        else if (ch[0] == ')')
            k--;
        i++;
    } while (i < n && (ch[0] != ',' || k != 0));
    if (i < n)
    {
        SubString(hstr, str, 0, i - 1);//截取，前面的子串存入hstr
        SubString(str, str, i, n - i);//截取，后面的子串存入hstr
    }
    else
    {
        StrCopy(hstr, str);
        CleanString(str);
    }
    
}
/*------------------广义表操作------------------*/
void visit(GList L)
/*初始条件：广义表L存在
  操作结果：遍历广义表L*/
{
    if (L&&L->sign == ATOM)
        printf("%c", L->data);
    else
        visit(L->hp);
    if (L && L->tp != NULL)
        visit(L->tp);
}
int DepthGList(GList L)
/*初始条件：广义表L存在
  操作结果：返回广义表L的深度*/
{
    int dep = 0, max = 0;
    if (L&&L->sign == LIST && L->hp != NULL)
    {
        dep = DepthGList(L->hp) + 1;
        if (dep > max)
            max = dep;
    }
    if (L&&L->tp != NULL)
    {
        dep = DepthGList(L->tp);
    }
    if (dep > max)
        max = dep;
    return max;
}

int LengthGList(GList L)
/*初始条件：广义表L存在
  操作结果：返回广义表L的长度*/
{
    int len = 0;
    if (L&&L->sign == ATOM)//为单个原子
        return 1;
    if (L&&L->sign == LIST && L->hp == NULL)//为空表
        return 0;
    GList p = L->hp;
    while (p != NULL)
    {
        len++;
        p = p->tp;
    }
    return len;
}
Status CreateGList(GList* L, String S)
/*初始条件：S为广义表的书写形式串
  操作结果：通过S创建广义表L*/
{
    (*L) = (GList)malloc(sizeof(GLNode));
    char* s = "( )";
    String sub, hstr;
    if (!StrCompare(S, s))//给定字符串为"（ ）"为空表
    {
        (*L)->sign = LIST;
        (*L)->hp = NULL;
        (*L)->tp = NULL;
    }
    else if (StrLength(S) == 1)//给定字符为单个字符，为原子结点
    {
        (*L)->sign = ATOM;
        (*L)->data = S[0];
        (*L)->tp = NULL;
    }
    else//其他情况为子表
    {
        (*L)->sign = LIST;
        (*L)->tp = NULL; 
        SubString(sub, S, 1, StrLength(S) - 2);//去外层括号
        sever(sub, hstr);//分离表头和表尾
        CreateGList(&(*L)->hp, hstr);
        GList p = (*L)->hp;
        while (!(StrEmpty(sub)))
        {
            sever(sub, hstr);//不断取出表头
            CreateGList(&p->tp, hstr);
            p = p->tp;
        }
    }
}

Status CopyGList(GList* L, GList T)
/*初始条件：广义表L存在
  操作结果：通过广义表L，复制广义表T*/
{
    (*L) = (GList)malloc(sizeof(GLNode));
    if (!T)
        (*L) = NULL;
    else
    {
        (*L)->sign = T->sign;//复制枚举变量
        if ((*L)->sign == ATOM)
            (*L)->data = T->data;
        else
            CopyGList(&(*L)->hp, T->hp);
        CopyGList(&(*L)->tp, T->tp);
    }
}

GList GetHead(GList L)
/*初始条件：广义表L存在
  操作结果：返回广义表表头*/
{
    GList h;
    InitGList(&h);//h置空表
    if (!L || L->sign == LIST && L->hp == NULL)
    {
        printf("空表无表头\n");
        exit(0);
    }
    h = (GList)malloc(sizeof(GLNode));
    if (!h)
        exit(OVERFLOW);
    h->sign = L->hp->sign;
    h->tp = NULL;
    if (h->sign == ATOM)
        h->data = L->hp->data;
    else
        CopyGList(&h->hp, L->hp->hp);
    return h;
}

GList GetTail(GList L)
/*初始条件：广义表L存在
  操作结果：返回广义表L表尾*/
{
    GList T;
    if (!L || L->sign == LIST && L->hp == NULL)
    {
        printf("空表无表尾");
        exit(OVERFLOW);
    }
    T = (GList)malloc(sizeof(GLNode));
    if (!T)
        exit(OVERFLOW);
    T->sign = LIST;
    T->tp = NULL;
    CopyGList(&T->hp, L->hp->tp);
    return T;
}

Status DestroyGList(GList* L)
/*初始条件：广义表L存在
  操作结果：销毁广义表L*/
{
    GList ph, pt;
    if ((*L))
    {//由pt和ph接替表头和表尾
        if ((*L)->sign == ATOM)
            ph = NULL;
        else
            ph = (*L)->hp;
        pt = (*L)->tp;
        free(*L);
        *L = NULL;
        DestroyGList(&ph);
        DestroyGList(&pt);
    }
}
Status InitGList(GList* L)
/*创建空的广义表*/
{
    (*L) = (GList)malloc(sizeof(GLNode));
    if (!(*L))
        return OVERFLOW;
    (*L)->hp = NULL;
    (*L)->tp = NULL;
    return OK;
}
Status InsertFirst_GL(GList* L, GList e)
/* 初始条件: 广义表L存在 */
 /*操作结果: 插入元素e作为广义表L的第一元素(表头,也可能是子表) */
{
    if (!(*L) || !e)
    {
        printf("广义表为空");
        return ERROR;
    }
    else
    {
        GList p = (*L)->hp;
        (*L)->hp = e;
        e->tp = p;
    }
    return OK;
}

Status DeleteFirst_GL(GList* L, GList* e)
/*初始条件：*广义表L存在*/
/*操作结果：删除广义表的表头元素，并用e返回其值*/
{
    if (!(*L))
    {
        *e = *L;
    }
    else {
        *e = (*L)->hp;
        (*L)->hp = (*e)->tp;
        (*e)->tp = NULL;
    }
    return OK;
}
Status GListEmpty(GList *L)
/* 初始条件: 广义表L存在
 操作结果: 判定广义表L是否为空 */
{
    if (!(*L) || (*L)->sign == LIST && (*L)->hp == NULL)
        return OK;
    else
        return ERROR;
}
int main()
{
    /*在此约定：1.书写形式串正确，最大长度为255
                2.字符串操作起始位置为0，采用定长顺序线性结构*/
    String S;
    printf("请输入广义表的书写形式串(无误情况)：");
    gets(S);
    GList L, T;
    CreateGList(&L, S);
    if (GListEmpty(&L))
        exit(OVERFLOW);
    printf("\n广义表L为：");
    visit(L);
    printf("\n深度为：");
    printf("%d，长度为：%d", DepthGList(L), LengthGList(L));
    printf("\n通过L复制T得到:");
    CopyGList(&T, L);
    visit(T);

    printf("\n将T销毁：");
    DestroyGList(&T);
    if (GListEmpty(&T))
        printf("销毁成功\n");
    else
        exit(ERROR);

    CopyGList(&T, L);
    printf("\n将T插入L的表头为：");
    InsertFirst_GL(&L, T);

    printf("\n插入后L为：");
    visit(L);
    printf("\n插入后深度为：%d长度为：%d", DepthGList(L), LengthGList(L));

    system("pause");
    return 0;
}

本文链接：

https://nullcode.fun/39.html