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

一、 基本概念

  • 线性表

    • 由 n (n≥0) 个数据元素组成的有限有序序列
    • 线性表的每个元素都具有相同的数据类型
  • 如果一个线性表中还包括一个或者多个子表,那 就称之为广义表 (Generalized Lists,也称 Multi-list) 一般记作: L= (x0,x1,…,xi,…,xn-1)

    • L是广义表的 名称
    • n为 长度
    • 每个xi (0≤i≤n-1)是L的成员。可以是单个元素,即原子 (atom); 也可以是一个广义表,即子表 (sublist)
    • 广义表的 深度:表中元素都化解为原子后的括 号层数

L= (x0,x1,…,xi,…,xn-1)

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

二、 广义表的各种类型

2.1 纯表 (pure list)

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

5.2 可重入表和循环表

循环表:

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

三、 广义表的存储

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

3.1 广义表存储ADT

不带头结点的广义表链

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

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

四、 广义表的周游算法

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

五、思考

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

参考资料

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

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学