8.1 广义表的定义第 8章 广义表
8.2 广义表的存储结构
8.3 广义表的运算本章小结
8.1 广义表的定义广义表简称表,它是线性表的推广 。 一个广义表是 n(n≥0)个元素的一个序列,若 n=0时则称为空表 。 设 ai为广义表的第 i个元素,则广义表 GL的一般表示与线性表相同：
GL=(a1,a2,…,ai,…,an)
其中 n表示广义表的长度,即广义表中所含元素的个数,n≥0。如果 ai是单个数据元素,则 ai是广义表 GL的原子；如果 ai是一个广义表,则 ai是广义表 GL的子表。
广义表具有如下重要的特性：
(1)广义表中的数据元素有相对次序；
(2)广义表的长度定义为最外层包含元素个数；
(3)广义表的深度定义为所含括弧的重数 。 其中,原子的深度为 0,空表的深度为 1；
(4)广义表可以共享；一个广义表可以为其他广义表共享；这种共享广义表称为再入表；
(5)广义表可以是一个递归的表 。 一个广义表可以是自已的子表 。 这种广义表称为递归表 。 递归表的深度是无穷值,长度是有限值；
(6)任何一个非空广义表 GL均可分解为表头
head(GL) = a1和表尾 tail(GL) = ( a2,…,a n) 两部分。
为了简单起见,下面讨论的广义表不包括前面定义的再入表和递归表,即只讨论一般的广义表 。 另外,我们规定用小写字母表示原子,用大写字母表示广义表的表名 。 例如：
A=()
B=(e)
C=(a,(b,c,d))
D=(A,B,C)=((),(e),(a,(b,c,d)))
E=((a,(a,b),((a,b),c)))
如果把每个表的名字 (若有的话 )写在其表的前面,则上面的 5个广义表可相应地表示如下：
A()
B(e)
C(a,(b,c,d))
D(A(),B(e),C(a,(b,c,d)))
E((a,(a,b),((a,b),c)))
若用圆圈和方框分别表示表和单元素,并用线段把表和它的元素 (元素结点应在其表结点的下方 )连接起来,则可得到一个广义表的图形表示 。 例如,上面五个广义表的图形表示如下图所示 。
c a b
a b
E
d
e a
b c
D
A B C
d b c
C
a
B
e
A
a
A() B(e) C(a,(b,c,d)) D(A(),B(e),C(a,(b,c,d)))
E((a,(a,b),((a,b),c)))
8.2 广义表的存储结构广义表是一种递归的数据结构,因此很难为每个广义表分配固定大小的存储空间,所以其存储结构只好采用动态链式结构 。
我们将一个广义表看成一棵树,为了方便存储,将其转换成一棵二叉树 。 其转换过程已在第 6章中介绍过,这里以示例中的广义表 C说明其转换过程 。 如下图所示,左边的图表示转换的中间状态,右边的图表示转换的最终状态,即一棵二叉树 。 从二叉树中看到,有两类结点,一类为圆圈结点,在这里对应子表；另一类为方形结点,在这里对应原子 。
C
a
b c d
C
a
b c d
C 1 ∧
0 a 1 ∧
0 b 0 c 0 d ∧
typedef struct lnode
{ int tag; /*结点类型标识 */
union
{ ElemType data;
struct lnode *sublist;
} val;
struct lnode *link; /*指向下一个元素 */
} GLNode; /*广义表结点类型定义 */
广义表的两种基本情况,
… g1
1 ∧ ∧
g2 1 ∧
* * * * * * ∧
第 1 个元素 第 2 个元素 第 n 个元素
（ a ）空表 （ b ）非空表为原子的情况,
g3 0 a ∧
8.3 广义表的运算
1,求广义表的长度在广义表中,同一层次的每个结点是通过 link域链接起来的,所以可把它看做是由 link域链接起来的单链表 。 这样,求广义表的长度就是求单链表的长度,可以采用以前介绍过的求单链表长度的方法求其长度 。
求广义表长度的非递归算法如下：
int GLLength(GLNode *g) /*g为一个广义表头结点的指针 */
{
int n=0;
g=g->val.sublist; /*g指向广义表的第一个元素 */
while (g!=NULL)
{ n++;
g=g->link;
}
return n;
}
2,求广义表的深度对于带头结点的广义表 g,广义表深度的递归定义是它等于所有子表中表的最大深度加 1。 若 g为原子,
其深度为 0。
求广义表深度的递归模型 f()如下：
f(g)=
0 若 g为原子
1 若 g为空表
MAX{f(subg)}+1 其他情况,subg为 g的子表
int GLDepth(GLNode *g) /*求带头结点的广义表 g的深度 */
{ int max=0,dep;
if (g->tag==0) return 0; /*为原子时返回 0*/
g=g->val.sublist; /*g指向第一个元素 */
if (g==NULL) return 1; /*为空表时返回 1*/
while (g!=NULL) /*遍历表中的每一个元素 */
{ if (g->tag==1) /*元素为子表的情况 */
{ dep=GLDepth(g); /*递归调用求出子表的深度 */
if (dep>max) max=dep;
/*max为同一层所求过的子表中深度的最大值 */
}
g=g->link; /*使 g指向下一个元素 */
}
return(max+1); /*返回表的深度 */
}
3,建立广义表的链式存储结构假定广义表中的元素类型 ElemType为 char类型,每个原子的值被限定为英文字母。
并假定广义表是一个表达式,其格式为：元素之间用一个逗号分隔,表元素的起止符号分别为左、右圆括号,
空表在其圆括号内不包含任何字符。例如,(a,(b,c,d))”
就是一个符合上述规定的广义表格式。
生成广义表链式存储结构的算法如下：
GLNode *CreatGL(char *&s)
{ GLNode *h;char ch;ch=*s; /*取一个扫描字符 */
s++; /*串指针后移一位 */
if (ch!='\0') /*串未结束判断 */
{ h=(GLNode *)malloc(sizeof(GLNode));/*创建新结点 */
if (ch=='(') /*当前字符为左括号时 */
{ h->tag=1; /*新结点作为表头结点 */
h->val.sublist=CreatGL(s);
/*递归构造子表并链到表头结点 */
}
else if (ch==')') h=NULL; /*遇到 ')'字符,子表为空 */
else
{ h->tag=0; /*新结点作为原子结点 */
h->val.data=ch;
}
}
else h=NULL; /*串结束,子表为空 */
ch=*s; /*取下一个扫描字符 */
s++; /*串指针后移一位 */
if (h!=NULL) /*串未结束判断 */
if (ch==',') /*当前字符为 ','*/
h->link=CreatGL(s); /*递归构造后续子表 */
else /*串结束 */
h->link=NULL; /*处理表的最后一个元素 */
return h; /*返回广义表指针 */
}
4,输出广义表以 h作为带表头附加结点的广义表的表头指针,打印输出该广义表时,需要对子表进行递归调用。输出一个广义表的算法如下：
void DispGL(GLNode *g) /*g为一个广义表的头结点指针 */
{ if (g!=NULL) /*表不为空判断 */
{ if (g->tag==1) /*为表结点时 */
{ printf("("); /*输出 '('*/
if (g->val.sublist==NULL) printf(""); /*输出空子表 */
else DispGL(g->val.sublist); /*递归输出子表 */
}
else printf("%c",g->val.data); /*为原子时输出元素值 */
if (g->tag==1) printf(")"); /*为表结点时输出 ')'*/
if (g->link!=NULL)
{ printf(",");
DispGL(g->link); /*递归输出后续表的内容 */
}
}
}
本章小结本章的基本学习要点如下：
(1)掌握广义表的定义 。
(2)重点掌握广义表的链式存储结构 。
(3)掌握广义表的基本运算,包括创建广义表,输出广义表,求广义表的长度和深度 。
(4)灵活运用广义表这种数据结构解决一些综合应用问题。
练习教材中 p182习题 1和 2。
8.2 广义表的存储结构
8.3 广义表的运算本章小结
8.1 广义表的定义广义表简称表,它是线性表的推广 。 一个广义表是 n(n≥0)个元素的一个序列,若 n=0时则称为空表 。 设 ai为广义表的第 i个元素,则广义表 GL的一般表示与线性表相同：
GL=(a1,a2,…,ai,…,an)
其中 n表示广义表的长度,即广义表中所含元素的个数,n≥0。如果 ai是单个数据元素,则 ai是广义表 GL的原子；如果 ai是一个广义表,则 ai是广义表 GL的子表。
广义表具有如下重要的特性：
(1)广义表中的数据元素有相对次序；
(2)广义表的长度定义为最外层包含元素个数；
(3)广义表的深度定义为所含括弧的重数 。 其中,原子的深度为 0,空表的深度为 1；
(4)广义表可以共享；一个广义表可以为其他广义表共享；这种共享广义表称为再入表；
(5)广义表可以是一个递归的表 。 一个广义表可以是自已的子表 。 这种广义表称为递归表 。 递归表的深度是无穷值,长度是有限值；
(6)任何一个非空广义表 GL均可分解为表头
head(GL) = a1和表尾 tail(GL) = ( a2,…,a n) 两部分。
为了简单起见,下面讨论的广义表不包括前面定义的再入表和递归表,即只讨论一般的广义表 。 另外,我们规定用小写字母表示原子,用大写字母表示广义表的表名 。 例如：
A=()
B=(e)
C=(a,(b,c,d))
D=(A,B,C)=((),(e),(a,(b,c,d)))
E=((a,(a,b),((a,b),c)))
如果把每个表的名字 (若有的话 )写在其表的前面,则上面的 5个广义表可相应地表示如下：
A()
B(e)
C(a,(b,c,d))
D(A(),B(e),C(a,(b,c,d)))
E((a,(a,b),((a,b),c)))
若用圆圈和方框分别表示表和单元素,并用线段把表和它的元素 (元素结点应在其表结点的下方 )连接起来,则可得到一个广义表的图形表示 。 例如,上面五个广义表的图形表示如下图所示 。
c a b
a b
E
d
e a
b c
D
A B C
d b c
C
a
B
e
A
a
A() B(e) C(a,(b,c,d)) D(A(),B(e),C(a,(b,c,d)))
E((a,(a,b),((a,b),c)))
8.2 广义表的存储结构广义表是一种递归的数据结构,因此很难为每个广义表分配固定大小的存储空间,所以其存储结构只好采用动态链式结构 。
我们将一个广义表看成一棵树,为了方便存储,将其转换成一棵二叉树 。 其转换过程已在第 6章中介绍过,这里以示例中的广义表 C说明其转换过程 。 如下图所示,左边的图表示转换的中间状态,右边的图表示转换的最终状态,即一棵二叉树 。 从二叉树中看到,有两类结点,一类为圆圈结点,在这里对应子表；另一类为方形结点,在这里对应原子 。
C
a
b c d
C
a
b c d
C 1 ∧
0 a 1 ∧
0 b 0 c 0 d ∧
typedef struct lnode
{ int tag; /*结点类型标识 */
union
{ ElemType data;
struct lnode *sublist;
} val;
struct lnode *link; /*指向下一个元素 */
} GLNode; /*广义表结点类型定义 */
广义表的两种基本情况,
… g1
1 ∧ ∧
g2 1 ∧
* * * * * * ∧
第 1 个元素 第 2 个元素 第 n 个元素
（ a ）空表 （ b ）非空表为原子的情况,
g3 0 a ∧
8.3 广义表的运算
1,求广义表的长度在广义表中,同一层次的每个结点是通过 link域链接起来的,所以可把它看做是由 link域链接起来的单链表 。 这样,求广义表的长度就是求单链表的长度,可以采用以前介绍过的求单链表长度的方法求其长度 。
求广义表长度的非递归算法如下：
int GLLength(GLNode *g) /*g为一个广义表头结点的指针 */
{
int n=0;
g=g->val.sublist; /*g指向广义表的第一个元素 */
while (g!=NULL)
{ n++;
g=g->link;
}
return n;
}
2,求广义表的深度对于带头结点的广义表 g,广义表深度的递归定义是它等于所有子表中表的最大深度加 1。 若 g为原子,
其深度为 0。
求广义表深度的递归模型 f()如下：
f(g)=
0 若 g为原子
1 若 g为空表
MAX{f(subg)}+1 其他情况,subg为 g的子表
int GLDepth(GLNode *g) /*求带头结点的广义表 g的深度 */
{ int max=0,dep;
if (g->tag==0) return 0; /*为原子时返回 0*/
g=g->val.sublist; /*g指向第一个元素 */
if (g==NULL) return 1; /*为空表时返回 1*/
while (g!=NULL) /*遍历表中的每一个元素 */
{ if (g->tag==1) /*元素为子表的情况 */
{ dep=GLDepth(g); /*递归调用求出子表的深度 */
if (dep>max) max=dep;
/*max为同一层所求过的子表中深度的最大值 */
}
g=g->link; /*使 g指向下一个元素 */
}
return(max+1); /*返回表的深度 */
}
3,建立广义表的链式存储结构假定广义表中的元素类型 ElemType为 char类型,每个原子的值被限定为英文字母。
并假定广义表是一个表达式,其格式为：元素之间用一个逗号分隔,表元素的起止符号分别为左、右圆括号,
空表在其圆括号内不包含任何字符。例如,(a,(b,c,d))”
就是一个符合上述规定的广义表格式。
生成广义表链式存储结构的算法如下：
GLNode *CreatGL(char *&s)
{ GLNode *h;char ch;ch=*s; /*取一个扫描字符 */
s++; /*串指针后移一位 */
if (ch!='\0') /*串未结束判断 */
{ h=(GLNode *)malloc(sizeof(GLNode));/*创建新结点 */
if (ch=='(') /*当前字符为左括号时 */
{ h->tag=1; /*新结点作为表头结点 */
h->val.sublist=CreatGL(s);
/*递归构造子表并链到表头结点 */
}
else if (ch==')') h=NULL; /*遇到 ')'字符,子表为空 */
else
{ h->tag=0; /*新结点作为原子结点 */
h->val.data=ch;
}
}
else h=NULL; /*串结束,子表为空 */
ch=*s; /*取下一个扫描字符 */
s++; /*串指针后移一位 */
if (h!=NULL) /*串未结束判断 */
if (ch==',') /*当前字符为 ','*/
h->link=CreatGL(s); /*递归构造后续子表 */
else /*串结束 */
h->link=NULL; /*处理表的最后一个元素 */
return h; /*返回广义表指针 */
}
4,输出广义表以 h作为带表头附加结点的广义表的表头指针,打印输出该广义表时,需要对子表进行递归调用。输出一个广义表的算法如下：
void DispGL(GLNode *g) /*g为一个广义表的头结点指针 */
{ if (g!=NULL) /*表不为空判断 */
{ if (g->tag==1) /*为表结点时 */
{ printf("("); /*输出 '('*/
if (g->val.sublist==NULL) printf(""); /*输出空子表 */
else DispGL(g->val.sublist); /*递归输出子表 */
}
else printf("%c",g->val.data); /*为原子时输出元素值 */
if (g->tag==1) printf(")"); /*为表结点时输出 ')'*/
if (g->link!=NULL)
{ printf(",");
DispGL(g->link); /*递归输出后续表的内容 */
}
}
}
本章小结本章的基本学习要点如下：
(1)掌握广义表的定义 。
(2)重点掌握广义表的链式存储结构 。
(3)掌握广义表的基本运算,包括创建广义表,输出广义表,求广义表的长度和深度 。
(4)灵活运用广义表这种数据结构解决一些综合应用问题。
练习教材中 p182习题 1和 2。
