【12.2】高级数据结构-- 广义表

一、 基本概念

• 线性表

• 由 n (n≥0) 个数据元素组成的有限有序序列

• 线性表的每个元素都具有相同的数据类型

• 如果一个线性表中还包括一个或者多个子表，那 就称之为广义表 (Generalized Lists，也称 Multi-list) 一般记作: L= (x0，x1，…，xi，…，x_n-1)

• L是广义表的 名称

• n为 长度

• 每个xi (0≤i≤n-1)是L的成员。可以是单个元素，即原子 (atom)； 也可以是一个广义表，即子表 (sublist)

• 广义表的 深度:表中元素都化解为原子后的括 号层数

L= (x0，x1，…，xi，…，x_n-1)

• 表头 head = x0
• 表尾 tail = (x1，…，xn-1)
• 规模更小的表
• 有利于存储和实现

二、 广义表的各种类型

2.1 纯表 (pure list)

• 从根结点到任何叶结点只有一条路径
• 即任何一个元素 (原子、子表) 在广义表中只出现一次

5.2 可重入表和循环表

循环表：

• 包含回路
• 循环表的深度为无穷大

三、 广义表的存储

• 图 ⊇ 再入表 ⊇ 纯表 (树) ⊇ 线性表
• 广义表是线性与树形结构的推广
• 递归表是有回路的再入表
• 广义表应用
• 函数的调用关系
• 内存空间的引用关系
• LISP 语言

3.1 广义表存储ADT

不带头结点的广义表链

• 在删除结点的时候会出现问题
• 删除结点 data 就必须进行链调整

• 增加头指针，简化删除、插入操作
• 重入表，尤其是循环表
• mark 标志位——图的因素

四、 广义表的周游算法

对带表头结点的循环广义表的遍历

五、思考

• 广义表与树、图各有什么区别与联系?
• 怎么实现广义表遍历的算法?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾