09年自考《数据结构》各章要点一[11]

广义表是n(n≥)个元素的有限序列其中的元素是原子或者是一个广义表

广义表表头和表尾的概念

·若广义表LS非空(n≥)则这个广义表的第一个元素就是表头

·其余的元素组成的表称为LS的表尾所以表尾必是一个子表

广义表有两种表示法一种是括号表示法一种是图形表示法

广义表与树(形结构)相对应这个广义表就是纯表

如果一个广义表的结点又可以被其他结点所共享则这个表称为再入表

允许递归的表称为递归表

线性表∈纯表(树)∈再入表∈递归表可见广义表是对线性表和树的推广

广义表有两个特殊的基本运算

·取表头head(LS)取表中的第一个数据元素不能对空表操作

·取表尾tail(LS);取除表头外其余数据元素构成的子表不能对空表操作

[] [] [] [] [] [] [] [] [] [] []