首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

软考备考之广义表理解

什么是广义表?

百度百科解释如下:

广义表(Lists,又称列表)是一种非线性的数据结构,是线性表的一种推广。即广义表中放松对表元素的原子限制,容许它们具有其自身结构。它被广泛的应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中,广义表是一种最基本的数据结构,就连LISP 语言的程序也表示为一系列的广义表。(又见LISP,自从看了《黑客与画家》总感觉这LISP出现频率高了不少……)

广义表定义

广义表是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的表尾。

广义表是递归定义的 [1]

广义表表示

(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(…)))

广义表运算

由于广义表是对线性表和树的推广,并且具有共享和递归特性的广义表可以和有向图(见第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的非空表(只不过该表中惟一的一个元素是空表),对其可进行分解,得到的表头和表尾均是空表()。

看了下说明还是不能够很理解,让我们来做道例题来加强理解:

2009年软考真题:若广义表L=((x,y,z),a,(u,t,w)),则从L中取出原子项y的运算是___?

A.head(tail(tail(L)))

B.tail(head(head(L)))

C.head(tail(head(L)))

D.tail(tail(head(L)))

正确答案:C

head(L) = (x,y,z) ; tail(L) = (a,(u,t,w))

head(head(L)) = x

tail(head(L)) = (y,z) //这一步理解了就行 tail得到的却是head外组成的新的广义表

head(tail(head(L))) = y

要注意的是head得到的是一个原子,而tail得到的却是原子外组成的新的广义表,不管是只有一个元素,但也是一个广义表,而不是直接的元素。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180511A21Z4H00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券