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

数据结构 第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和 。 教材中 习题


相关文章:
第8章 广义表_图文.ppt
第8章 广义表 - 第8章 广义表 8.1 广义表的定义 8.2 广义表的存储结构 8.3 广义表的运算 本章小结 8.1 广义表的定义 广义表简称 表 , 它是线性表的推广...
数据结构之第8章 广义表_图文.ppt
数据结构第8章 广义表 - 第8章 广义表 8.1 广义表的定义 8.2 广义表的存储结构 8.3 广义表的运算 本章小结 8.1 广义表的定义 广义表简称表,它是线性表的...
数据结构广义表_图文.ppt
数据结构广义表 - 第8章 8.1 8.2 8.3 广义表 广义表的定义 广义表的存储结构 广义表的运算 本章小结 8.1 广义表的定义 广义表简称表,它是线性表的推广。一...
第8章 广义表_图文.ppt
第8章 广义表 - 第8章 广义表 章 8.1 广义表的定义 8.2 广义表的存储结构 8.3 广义表的运算 本章小结 8.1 广义表的定义 广义表简称表 它是线性表的推广。...
第8章 广义表_图文.ppt
第8章 广义表 - 第8章 8.1 8.2 8.3 广义表 广义表的定义 广义表的存储结构 广义表的运算 本章小结 8.1 广义表的定义 广义表简称表,它是线性表的推广。一...
数据结构课件(李春葆 第3版)第8章 广义表_图文.ppt
数据结构课件(李春葆 第3版)第8章 广义表_工学_高等教育_教育专区。第8章 广义表 8.1 广义表的定义 8.2 广义表的存储结构 8.3 广义表的运算本章小结 8.1 ...
数据结构第五章数组和广义表习题及答案.doc
数据结构第五章数组和广义表习题及答案_计算机软件及应用_IT/计算机_专业资料。...(1≤i≤n,i-2≤j≤i+2),B 中的第 8 个元素是 A 中的第_ _行,第...
java数据结构第8章 图.ppt
第9章 绪论 线性表 排序 栈与队列 数组和广义表 树和二叉树 查找 图 综合...? 8.2.1 邻接矩阵 8.2.2 邻接表 《数据结构(Java版)》叶核亚 8.2.1 ...
数据结构 数组与广义表_图文.ppt
数据结构 数组与广义表 - 第五章 数组和广义表 1 第五章 数组和广义表 ? ? ? 本章前讨论的线性结构数据元素都是非结构 的原子类型,元素值不可再分。本章...
数据结构练习题-数组和广义表.doc
即元素 A[7][4]的起始地址与 A 按列存放时 A[2][8]的起始地址一致。 ...数据结构 第5章 数组和... 18页 免费 第五章数组和广义表习题... 11...
数据结构第1-8章(清华大学出版社 唐宁九主编).doc
数据结构第1-8章(清华大学出版社 唐宁九主编)_工学_高等教育_教育专区。第一...广义表是 n(n≥0)个元素 a1,a2,a3...an 的有限序列,其中的 ai 或者是...
数据结构 数组和广义表习题.doc
数据结构 数组和广义表习题_理学_高等教育_教育专区。第五章 数组和广义表习题一、选择题 1.已知广义表 LS=((a,b,c),(d,e,f)), 运用 head 和 tail 函数...
数据结构-广义表.ppt
第5章-2 1 2 3 广义表 广义表的定义 广义表的存储结构 广义表的运算本章小结 5.1 广义表的定义 广义表简称表,它是线性表的推广。一个广义 表是 n(n≥0) ...
数据结构数组和广义表自测题(附答案).doc
数据结构数组和广义表自测题(附答案) - 第 4~5 章 串和数组 ~一、填空题
数据结构广义表本_图文.ppt
数据结构广义表本_数学_自然科学_专业资料。第五章 广义表 本讲内容 1.广义表的定义 2.广义表的顺序存储 3.广义表的递归算法 广义表的定义定义 广义表是由零个或...
数据结构递归与广义表.doc
数据结构第章广义表 27页 1财富值喜欢此文档的还喜欢 广义表的运算 23页 免费 广义表的非递归建立与遍历 8页 5财富值 广义表 22页 1财富值 十套数据结构试题...
《数据结构》习题集:第5章_数组与广义表.doc
数据结构》习题集:第5章_数组与广义表 - 数据结构课后练习题 第 5 章 数组与广义表 第 5 章 数组与广义表 一、 1. 选择题 2. 3. 4. 5. 6. 7. ...
数据结构课件第6章 数组和广义表_图文.ppt
数据结构课件第6章 数组和广义表 - 第6章 数组和广义表 6.1 数组 6.2 稀疏矩阵 6.3 广义表 本章小结 6.1.1 数组的基本概念 从逻辑结构上看,数组A是n(n...
数据结构_数组和广义表_图文.ppt
数据结构_数组和广义表_计算机软件及应用_IT/计算机_...8 6 1 8 7
第五章数组和广义表习题_数据结构.doc
第五章数组和广义表习题_数据结构 - 习题五 数组和广义表 一、单项选择题 1.
更多相关标签: