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

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

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

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

逻辑图如下所示:

img

同时,对应广义表的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)为原子
    • 给定表头(字符串为“()”)为空
  • 上列两种情况分别对应于空表和原子结点
  • 除上述两种情况外,还有一种情况给定字符串长度大于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;
}

深度图示如下:

img

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

代码如下所示:

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
1 + 9 =
快来做第一个评论的人吧~