广义表

2023-11-08 10:39:22

情景介绍（不重要）：一开始还真不知道有这个广义表，算法书上也没有看到。直到做题才看到广义表。度娘找了几篇博客都讲的很散很乱。所以写下这篇博客希望能够让自己和看到这篇博客的人能够理解广义表。如果有错误请评论给我我看到后会及时更改
将分为一下几点进行描述：

广义表的介绍
扩展线性表的存储结构
真题训练

广义表的介绍

广义表：广义表其实就是一个典型的单向链表，即线性表的一种。存储的类型包括原子元素（单个数据）或另一个广义表（子表）

广义表的结构

Tag:既然存储类型是数据或表，就需要准备一个标签来标明当前存储数据是数据还是表，那个Tag的作用就是充当一个标识作用。0表示数据、1表示子表、2表示另一张广义表。
1. 对于用2表示另一张广义表我对度娘结果的少部分查询中仅仅在一处发现，但是如果不用2表示对于代码计算深度会出现无法计算的问题。这里我选择使用2来表示另一张广义表
List/Data：专门用于存储数据
Link：用于连接同一层的下一个结点

广义表的表示

书面表示

以 L = (A,b,(c,d)) 为例

书面表示法无需表示Tag与Link。
大写字母表示一个广义表，当仅仅只有一个广义表时一般用大写L表示
用（）表示一张表，数据用,隔开。
1. 如果嵌套一张子表，可以继续用（）来表示
2. 如果嵌套其他广义表，可以用对应表的大小字母表示

所以L = (A,b,(c,d))表示的意思是：有一张广义表L，里面包含的数据是另一个广义表A、数据b、子表。子表元素为数据b、数据c

注意点：

空表的表示形式不是L=NULL,而是L=()
在有些奇奇怪怪的地方，广义表的表示可能会省略=。长的是这样：L(a,(b,c))

画图表示

正确的画法应该是箭头初始端应该画到框框内，但是我用的画图软件这样子好麻烦就懒得弄了

注意点：

每一张广义表或子表都必须带有一个头结点去连接对应的值
当内容为空时，用∧来表示
有些书上广义表的数据如果连接的是另一张空的广义表，则会在对应数据位直接用∧表示，而不是选择去连接。（我这里认为如果这么表示可能对于像我一样脑子不灵光的人去理解深度会有点What，所以我选择画图的时候进行连接）

广义表的长度与深度

深度

广义表的深度：括号最大层数；可以理解为树的结点最大层次。看例题

L=()深度为1
L=(a,b,c,d,e,f,g）深度为1
L=(a,b,(c,d),e) 深度为2
L=((),(),()) 深度为2
L=((a,c),(c,(d,e),f)) 深度为3

长度

广义表的长度：第一层结点的个数或深度为1的结点个数。看例题

L=（）长度为1
L=（a,b）长度为2
L=（a,（b,c））长度为2
L=（（a）,（b），（c,(a,())）长度为3

TAIL表尾指令和HEAD表头指令

Tail指令

Tail指令（表尾）：，将头结点指向广义表第一层第二个元素，并抛弃第一个元素。

书面表示形式：
1. L=(a,b,c);Tail[L]=(b,c)
2. L=((a,b),c);Tail[L]=(c)
画图表示：

结论：表尾的结果一定是子表

Head指令

Head指令（表头）：直接获取广义表的第一层的第一个元素

书面表示形式：
1. L=(a,b,c);Head[L]=a
2. L=((a,b),c);Head[L]=((a,b));Head[Head[L]]=(a,b);Head[Head[Head[L]]]=a
画图表示：

结论：表头的结果可以是原子，也可以是子表

扩展线性表的存储结构

作为拓展和了解

由之前的图可知广义表存储结构的一个很大的缺点。
一、tag竟然出现了2，这样每个表在tag字段就需要用2bit来存储，且会造成11(B)被浪费。那么可以让每次连接其他的广义表时直接连接其第一个元素而不是表头
二、对于画图阶段，每次连接一个子表或其他广义表时都需要先在数据处连接表头，再连接数据。这样对于计算深度及其不方便。那么对于同一层的结点都用Link去连接

真题训练

现在已经讲解完了广义表的全部内容，因为属于理论科学，如果你是要考试的人建议您还是仔细阅读你考试大纲对于此处的解释，可能我讲的和你们考的有些区别

题目一：一个非空广义表的表尾（）——广东工业大学2019
A：不可能是子表；B：只能是子表；C：只能是原子；D：可能是子表或原子

题目二：设广义表L=((a,b,c)),则L的长度和深度分别为()——上海海事大学2018
A：1 1；B：1 3；C：1 2；D： 2 3

题目三：若广义表L满足Head(L)=Tail(L),则L为()——扬州大学2017
A：()；B：(())；C：((),())；D：((),(),())

题目四：已知广义表L=((x,y,z),a,(u,y,t))，从L中取出y的操作时？——此题简化

----------------------------------解析线-----------------------------------

解析：

题目一：B，表尾必是子表，表头可以是子表可以是原子。若错误可以查看Tail指令和Head指令
题目二：C，长度表示广义表第一层的元素个数，深度为括号最大层数
题目三：B，
1. 注意A的操作是没有意义的NULL != ()
2. B中Tail[L]应该是空，但是空的表示不是NULL而是()。() == ()
3. C：() != (())
4. D：() != ((),())
题目四：Head[Tail[Head[Tail[Tail[L]]]]]
1. Tail[L] = (a,(u,y,t))
2. Tail[Tail[L]] = ((u,y,t))
3. Head[Tail[Tail[L]]] = (u,y,t)
4. Tail[Head[Tail[Tail[L]]]] = (y,t)
5. Head[Tail[Head[Tail[Tail[L]]]]] = y

码农公寓