表头表尾存储(Head-Tail Storage)

广义表通常采用头、尾指针的链表结构。

结点定义

对于每一个结点:

  • 若 tag=0,表示这是一个原子结点,data 区域存放该原子的值
  • 若 tag=1,表示这是一个表结点,hp 指向子表头,tp 指向广义表的下一个元素

存储方式

基于表头、表尾分析法:

  • 表节点为框架,元素只在原子节点中出现
  • 原子节点只在表头出现
  • 构建顺序相当于将表头弹出,剩下的作为表尾

示例:广义表 A = (c, B), B = (d, e) 的存储结构采用头尾指针链表方式,每个表结点包含指向表头的指针 hp 和指向表尾的指针 tp,原子结点存储具体元素值。

链接到

  • 上一个知识点:2.2 子表存储
  • 下一个知识点:无(本章最后一个知识点)