Question

八、数据结构-线性扩展-广义表

Answer 1

广义表的成分可以是单元素，也可以是有结构的表。线性表是一种特殊的广义表，但广义表不一定是线性表，也不一定是线性结构。
广义表的基本运算：
（1）求表头GetHead(L)：非空广义表的第一个元素，可以是一个单元素，也可以是一个子表
（2）求表尾GetTail(L)：非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表
例题： A=(a,b,(c,d),(e,(f,g)))，
GetHead(GetTail(GetHead(GetTail(GetTail(A))))) 结果为？（答案：d）
过程：
tail第一步： (b,(c,d),(e,(f,g)))
tail第二步：（(c,d),(e,(f,g)))
head第三步：（c,d）
tail第四步：（d）
head第五步：d

广义表特点：

广义表的图形表示： （图中○表示广义表，□表示原子）

广义表的存储：
因为广义表的数据元素可以是不同结构，所以难以用顺序存储，通常用链式存储的方式。广义表的链式存储又包括头尾链表和扩展线性链表两种。

表结点包括三个域：标志域、指示表头指针域和指示表尾指针域。
原子结点包括两个域：标志域和值域。