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