数据结构第8章广义表.ppt

《数据结构第8章广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构第8章广义表.ppt（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、n n广义表的基本概念广义表的基本概念n n广义表的广义表的存储结构存储结构一、广义表一、广义表定义定义定义定义:广义表广义表广义表广义表（lists)lists)lists)lists)是是是是 n n n n(0 0 0 0)个元素的有限序列，个元素的有限序列，个元素的有限序列，个元素的有限序列，记作记作记作记作:LS=(LS=(LS=(LS=(a1,a2,an)其中，其中，其中，其中，ai或是原子或是原子或是原子或是原子 或是一个广义表或是一个广义表或是一个广义表或是一个广义表 n n n n 是广义表的长度是广义表的长度是广义表的长度是广义表的长度 通常用小写表示原子，大写表示广义表。

2、通常用小写表示原子，大写表示广义表。例：例：E=()L=(a,b)A=(x,L)=(x,(a,b)B=(A,y)=(x,L),y)=(x,(a,b),y)C=(A,B)=(x,(a,b),(x,(a,b),y)D=(a,D)=(a,(a,(a,)特点特点：（：（1）广义表的元素可以是子表（广义表）。）广义表的元素可以是子表（广义表）。（2）一个广义表可以为其他多个广义表共享。）一个广义表可以为其他多个广义表共享。（3）广义表可以是递归表。）广义表可以是递归表。注：注：F=()与与E=()的区别的区别 n=1 n=0广义表的逻辑结构广义表的逻辑结构a11 a1n ai1 aij ain am1

3、amnAmn=A=(1,2,3,n)二维数组二维数组A是由是由n个元素组成的广义表，个元素组成的广义表，其中每个元素是由一列元素组成的子表。其中每个元素是由一列元素组成的子表。线性结构的推广线性结构的推广例：多维数组就是广义表例：多维数组就是广义表A=(1,2,3,m)二维数组二维数组A是由是由m个元素组成的广义表，个元素组成的广义表，其中每个元素是由一行元素组成的子表。其中每个元素是由一行元素组成的子表。a1j j=aij amj i=(ai1 aij ain)广义表的基本运算广义表的基本运算取表头：取表头：HeadLS=a1 取第一元取第一元素素例：例：headA=head(x,L)=x

4、head(a,b),(c,d)=(a,b)LS=(LS=(a1,a2,an)取表尾：取表尾：TailLS=(=(a2,an)由第二个元素到最后一个元素组成的子表由第二个元素到最后一个元素组成的子表例：例：tail(a,b,c,d)=(b,c,d)tailA=tail(x,L)=tail(x,(a,b)=(a,b)tail(e)=()tailheadtail(a,b),(c,d)=?求表的深度：求表的深度：DepthLS括号嵌套的最大层数括号嵌套的最大层数求表的长度：求表的长度：LengthLS(d)例：例：depth(a,(b,c),(d,(e),()=4广义表的存储结构广义表的存储结构由于广

5、义表中元素可以是原子，也可以是子表，只能采用链方式。由于广义表中元素可以是原子，也可以是子表，只能采用链方式。单链表示法：以单链表形式链接各结点。单链表示法：以单链表形式链接各结点。当元素为原子时，存储其元素值。当元素为原子时，存储其元素值。当元素为子表时，存储指向子表的指针。当元素为子表时，存储指向子表的指针。结点结构结点结构tag data/sublist linktag=1 元素为子表元素为子表sublist指向子表指向子表0 元素为原子元素为原子data存储元素值存储元素值typedef struct node int tag;struct node*link;union struct

6、 node*sublist;datatype data;element;lists;结点数据类型结点数据类型LS=(a,(b,c),(),(d,e),f)0 a1 0 b0 c1 110 f0 d0 eLS单链表示法单链表示法1 headheadtailLS=headtailtailLS=求广义表的深度求广义表的深度基本思想：基本思想：依次求出每个元素的深度，依次求出每个元素的深度，则最大值则最大值+1为其表的深度。为其表的深度。其中：其中：原子元素的深度原子元素的深度=0 利用递归求出子表的深度利用递归求出子表的深度d=0d=0d=0max=0d=1d=1max=0d=0d=0max=0d=1d=0max=1d=2max=2d=3