广义表结构定义、表示及运算
不好意思，小偷又光顾你家，带走了你 10% 的财产！（人民政府再次提醒大家有钱要存银行）下次努力哦！……广义表的概念
广义表(Lists，又称列表)是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。
1、广义表定义
广义表是n(n≥0)个元素a1，a2，…，ai，…，an的有限序列。
其中：
①ai--或者是原子或者是一个广义表。
②广义表通常记作：
Ls=( a1，a2，…，ai，…，an)。
③Ls是广义表的名字，n为它的长度。
④若ai是广义表，则称它为Ls的子表。
注意：
①广义表通常用圆括号括起来，用逗号分隔其中的元素。
②为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。
③若广义表Ls非空(n≥1)，则al是LS的表头，其余元素组成的表(a1，a2，…，an)称为Ls的表尾。
④广义表是递归定义的
2、广义表表示
（1）广义表常用表示
① E=()
E是一个空表，其长度为0。
② L=(a，b)
L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表
③ A=(x，L)=(x，(a，b))
A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。
④ B=(A，y)=((x，(a，b))，y)
B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。
⑤ C=(A，B)=((x，(a，b))，((x，(a，b))，y))
C的长度为2，两个元素都是子表。
⑥ D=(a，D)=(a，(a，(a，(…))))
D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。
（2）广义表的深度
一个表的"深度"是指表展开后所含括号的层数。
【例】表L、A、B、C的深度为分别为1、2、3、4，表D的深度为∞。
（3）带名字的广义表表示
如果规定任何表都是有名字的，为了既表明每个表的名字，又说明它的组成，则可以在每个表的前面冠以该表的名字，于是上例中的各表又可以写成：
①E()
②L(a，b)
③A(x，L(a，b))
④B(A(x，L(a，b))，y)
⑤C(A(x，l(a，b))，B(A(x，L(a，b))，y))
⑥D(a，D(a，D(…)))
（4）广义表的图形表示
（a）广义表的图形表示：
①图中的分支结点对应广义表
②非分支结点一般是原子
③但空表对应的也是非分支结点。
【例】下图给出了几个广义表的图形表示。
（b）广义表的图形形状划分：
①与树对应的广义表称为纯表，它限制了表中成分的共享和递归
②允许结点共享的表称再入表
【例】上图(d),子表A是共享结点，它既是C的一个元素，又是子表B的元素；
③允许递归的表称为递归表
【例】上图(e)，表D是其自身的子表。
（5）递归表、再人表、纯表、线性表之间的关系满足：
http://student.zjzk.cn/course_ware/data_structure/web/guangyibiao/guangy1.gif
广义表不仅是线性表的推广，也是树的推广。
3、广义表运算
由于广义表是对线性表和树的推广，并且具有共享和递归特性的广义表可以和有向图(见第7章)建立对应，因此广义表的大部分运算与这些数据结构上的运算类似。
在此，只讨论广义表的两个特殊的基本运算：取表头head(Ls)和取表尾tail(Ls)。
根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。
【例】
head(L)=a， tail(L)=(b)
head(B)=A， tail(B)=(y)
由于tail(L)是非空表，可继续分解得到：
head(tail(L))=b， tail(tail(L))=()
对非空表A和(y)，也可继续分解。
注意:
广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()。 你买的股票升值，获利 1218 思明论坛！
下次努力哦！……:smile 支持下.
:sad Me有待学习.:happy :happy 你抢了我滴沙发，之所以发这贴是因为昨天和同学讨论时无意论及此结构，我上学期上数据结构时就发现04和05级的书都没有详细介绍这个结构，05的只讲了小部分概念，没有算法，04的连提都没提到，上学期学Data Structrue时我在网上看过一个技术学校的计算机课件，里面详细讲解了Lists还给出了算法描述，觉得书打着高职的旗号有意删减某些内容的做法实在可笑，而老师为了顾及通过率，也没有深入讲解算法（想想上学期自己看得好辛苦），下个学期06软件的学弟学妹学习Data Structrue或许老师也不会讲解，所以要做好自学的准备，实在是不忍让这样的惊天动地的结构不为人所知，你们要知道：表，是表他妈生的；树，是树他妈生的；表如果有了树的心，那他就再也不是表，而是广义表...... 看不懂...... 我也看不董也~~~` 學習一下.......... 看不明白
没有学过 :titter LS你怎么用一个老男人的头像来做自己的论坛头像？ 原帖由 zkkpkk 于 2007-4-24 23:30 发表
:titter LS你怎么用一个老男人的头像来做自己的论坛头像？
因为LS是男的。。。。 你与朋友聚赌赢了 92 思明论坛，热心值减 4 ！
下次努力哦！……原帖由 鱈之衝突 于 2007-4-25 08:01 发表
因为LS是男的。。。。
他是男的？他那个泰利是《狼之标记》里的泰利，年近40，养子洛克也成年了 由于某人需要，顶起``` 顶起，同样基于图论的邻接表就要出了:titter
页:
[1]