当前位置:首页 >> 工学 >>

数据结构 第8章 广义表


第8章

广义表

8.1 广义表的定义 8.2 广义表的存储结构 8.3 广义表的运算
本章小结

8.1

广义表的定义

广义表简称表,它是线性表的推广。 广义表简称表 它是线性表的推广。一个广义 它是线性表的推广 表是n(n≥0)个元素的一个序列 若 n=0时则称为空 个元素的一个序列,若 表是 个元素的一个序列 时则称为空 为广义表的第i个元素 则广义表GL的一 个元素,则广义表 表 。 设 ai为广义表的第 个元素 则广义表 的一 般表示与线性表相同: 般表示与线性表相同: GL=(a1,a2,…,ai,…,an) 其中n表示广义表的长度 即广义表中所含元 其中 表示广义表的长度,即广义表中所含元 表示广义表的长度 素的个数,n≥0。如果 i是单个数据元素 则ai是广 素的个数 。如果a 是单个数据元素,则 义表GL的原子 如果a 是一个广义表,则 的原子; 义表 的原子;如果 i是一个广义表 则ai是广义 的子表。 表GL的子表。 的子表

广义表具有如下重要的特性: 广义表具有如下重要的特性: (1)广义表中的数据元素有相对次序; 广义表中的数据元素有相对次序; 广义表中的数据元素有相对次序 (2)广义表的长度定义为最外层包含元素个数; 广义表的长度定义为最外层包含元素个数; 广义表的长度定义为最外层包含元素个数 (3)广义表的深度定义为所含括弧的重数。其中 原 广义表的深度定义为所含括弧的重数。其中,原 广义表的深度定义为所含括弧的重数 子的深度为0,空表的深度为 空表的深度为1; 子的深度为 空表的深度为 ; (4)广义表可以共享 ; 一个广义表可以为其他广义 广义表可以共享; 广义表可以共享 表共享;这种共享广义表称为再入表; 表共享;这种共享广义表称为再入表; (5)广义表可以是一个递归的表。一个广义表可以 广义表可以是一个递归的表。 广义表可以是一个递归的表 是自已的子表。这种广义表称为递归表。 是自已的子表 。 这种广义表称为递归表 。 递归表的 深度是无穷值,长度是有限值 长度是有限值; 深度是无穷值 长度是有限值; (6)任何一个非空广义表 均可分解为表头 任何一个非空广义表GL均可分解为表头 任何一个非空广义表 head(GL) = a1和表尾 和表尾tail(GL) = ( a2,…,an) 两部分。 两部分。

为了简单起见,下面讨论的广义表不包括前面定 为了简单起见 下面讨论的广义表不包括前面定 义的再入表和递归表,即只讨论一般的广义表 即只讨论一般的广义表。 义的再入表和递归表 即只讨论一般的广义表 。 另 我们规定用小写字母表示原子,用大写字母表示 外 ,我们规定用小写字母表示原子 用大写字母表示 我们规定用小写字母表示原子 广义表的表名。例如: 广义表的表名。例如: 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))) 若用圆圈和方框分别表示表和单元素,并用线段把表 若用圆圈和方框分别表示表和单元素 并用线段把表 和它的元素(元素结点应在其表结点的下方 连接起来,则 元素结点应在其表结点的下方)连接起来 和它的元素 元素结点应在其表结点的下方 连接起来 则 可得到一个广义表的图形表示。 例如,上面五个广义表 可得到一个广义表的图形表示 。 例如 上面五个广义表 的图形表示如下图所示。 的图形表示如下图所示。

A()

B(e)

C(a,(b,c,d))

D(A(),B(e),C(a,(b,c,d)))

E((a,(a,b),((a,b),c)))
A B e C A b c d e D B a b c d C a a b a b c E

a

8.2 广义表的存储结构
广义表是一种递归的数据结构,因此很难为每个 广义表是一种递归的数据结构 因此很难为每个 广义表分配固定大小的存储空间,所以其存储结构只 广义表分配固定大小的存储空间 所以其存储结构只 好采用动态链式结构。 好采用动态链式结构。 我们将一个广义表看成一棵树,为了方便存储 将 我们将一个广义表看成一棵树 为了方便存储,将 为了方便存储 其转换成一棵二叉树。其转换过程已在第6章中介绍 其转换成一棵二叉树。其转换过程已在第 章中介绍 这里以示例中的广义表C说明其转换过程 过 ,这里以示例中的广义表 说明其转换过程 。 如下 这里以示例中的广义表 说明其转换过程。 图所示,左边的图表示转换的中间状态 左边的图表示转换的中间状态,右边的图表示 图所示 左边的图表示转换的中间状态 右边的图表示 转换的最终状态,即一棵二叉树 从二叉树中看到,有 即一棵二叉树。 转换的最终状态 即一棵二叉树。从二叉树中看到 有 两类结点,一类为圆圈结点 在这里对应子表; 一类为圆圈结点,在这里对应子表 两类结点 一类为圆圈结点 在这里对应子表;另一类 为方形结点,在这里对应原子 在这里对应原子。 为方形结点 在这里对应原子。

C

C a

a b
C 1


c

d

b

c

d

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; /*指向下一个元素 指向下一个元素*/ 指向下一个元素 /*广义表结点类型定义 广义表结点类型定义*/ 广义表结点类型定义 /*结点类型标识 结点类型标识*/ 结点类型标识

广义表的两种基本情况 :
g2 1


g1

1





*

*

*

*



*

*



第 1 个元素 (a)空表

第 2 个元素 (b)非空表

第 n 个元素

为原子的情况 :
g3 0 a


8.3 广义表的运算
1. 求广义表的长度 在广义表中,同一层次的每个结点是通过 在广义表中 同一层次的每个结点是通过link域链 同一层次的每个结点是通过 域链 接起来的,所以可把它看做是由 接起来的 所以可把它看做是由link域链接起来的单 所以可把它看做是由 域链接起来的单 链表。这样,求广义表的长度就是求单链表的长度 求广义表的长度就是求单链表的长度,可 链表。这样 求广义表的长度就是求单链表的长度 可 以采用以前介绍过的求单链表长度的方法求其长度。 以采用以前介绍过的求单链表长度的方法求其长度 。

求广义表长度的非递归算法如下: 求广义表长度的非递归算法如下:
int GLLength(GLNode *g) /*g为一个广义表头结点的指针 为一个广义表头结点的指针*/ 为一个广义表头结点的指针 { int n=0; g=g->val.sublist; while (g!=NULL) { } return n; } n++; g=g->link; /*g指向广义表的第一个元素 指向广义表的第一个元素*/ 指向广义表的第一个元素

2. 求广义表的深度 对于带头结点的广义表g,广义表深度的递归定义 对于带头结点的广义表 广义表深度的递归定义 是它等于所有子表中表的最大深度加1。 为原子, 是它等于所有子表中表的最大深度加 。若g为原子 为原子 其深度为0。 其深度为 。 求广义表深度的递归模型f()如下: 求广义表深度的递归模型 如下: 如下
0 f(g)= 1 MAX{f(subg)}+1 若g为原子 为原子 若g为空表 为空表 其他情况,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=*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++; 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)重点掌握广义表的链式存储结构 (2)重点掌握广义表的链式存储结构。 重点掌握广义表的链式存储结构。 (3)掌握广义表的基本运算 包括创建广义表、输出 掌握广义表的基本运算,包括创建广义表 掌握广义表的基本运算 包括创建广义表、 广义表、求广义表的长度和深度。 广义表、求广义表的长度和深度。 (4)灵活运用广义表这种数据结构解决一些综合应 灵活运用广义表这种数据结构解决一些综合应 用问题。 用问题。

练习 教材中p182习题 和2。 习题1和 。 教材中 习题


相关文章:
数据结构练习题-数组和广义表
数据结构练习题-数组和广义表_工学_高等教育_教育专区。已知二维数组 A[3][5...即元素 A[7][4]的起始地址与 A 按列存放时 A[2][8]的起始地址一致。 ...
数据结构习题第五章 数组和广义表答案
数据结构习题第五章 数组和广义表答案_理学_高等教育_教育专区。第 5 章数组和广义表 一、单项选择题 1. C 2. C 3. B 4.A 5.C 6. A 7.A 8. C ...
数据结构 广义表应用方案
数据结构 广义表的创建和... 8页 2下载券 数据结构第8章 广义表 21页 1下载...2. 功能要求 要求完成以下功能: ⑴ 插入:将某位本科生或研究生插入到广义表的...
数据结构第1-8章(清华大学出版社 唐宁九主编)
第一章 概论本章的重点是了解数据结构的逻辑结构、存储结构、数据的运算三方面的...广义表是 n(n≥0)个元素 a1,a2,a3...an 的有限序列,其中的 ai 或者是...
数据结构第五章数组和广义表练习及答案
数据结构第五章数组和广义表练习及答案_工学_高等教育_教育专区。数据结构(C语言...A 8、数组 A 中,每个元素的长度为 3 个字节,行下标 i 从 1 到 8,列...
数据结构第5章 数组和广义表
数据结构第5章 数组和广义表数据结构第5章 数组和广义表隐藏>> 第5 章 数组和广义表本章主要内容: 1、数组的定义、基本运算和存储结构 2、特殊矩阵的压缩存储 ...
(答案)数据结构第五章 数组与广义表
(答案)数据结构第五章 数组与广义表_电脑基础知识_IT/计算机_专业资料。第五章 数组与广义表 5.1 (1) (2) (3) (4) 288; 1282; 1072; 1276。 5.2 ...
(习题)数据结构第五章 数组与广义表
(习题)数据结构第五章 数组与广义表_电脑基础知识_IT/计算机_专业资料。第五章 数组与广义表 5.1 假设有二维数组 A6×8,每个元素用相邻的 6 个字节存储, ...
数据结构数组和广义表自测题(附答案)
第一个字节地址为 1282 ;若按行 存储时,元素 A14 的第一个字节地址为 (8+...10.求下列广义表操作的结果: (1) GetHead【((a,b),(c,d))】=== (a,...
数据结构第4章 数组和广义表
数据结构第4章 数组和广义表 隐藏>> 第4章 数组和广义表 【例 4-1】二维数组 A 的每一个元素是由 6 个字符组成的串,其行下标 i=0,1,…,8,列 下标 ...
更多相关标签: