广义表简称表它是线性表的推廣。一个广义表是n(n>=0)个元素的一个有限序列当n=0时称为空表。在一个非空的广义表中其元素可以是某一确定类型的对象,这种元素被稱为单元素;也可以是由单元素构成的表这种元素被称为子表或表元素。显然广义表的定义是递归的,广义表是线性表的递归数据结構
设ai为广义表的第i个元素,则广义表的一般表示与线性表相同
其中,n表示广义表的长度即广义表中所含元素的个数,n>=0
同线性表一樣,也可以用一个标识符来命名一个广义表例如:用LS命名上面的广义表,则为:LS(a1,a2,a3...an+1,an)在广义表的讨论中,为了把单元素同表元素区别開来一般用小写字母表示表元素,用大写字母表示表
- A是一个空表,不含任何元素其长度为0;
- B是一个只含有单元素e的表,其长度为1;
- CΦ有两个元素第1个元素是单元素a,第2个元素是表元素(a,b,c),C的长度为2;
- D中有3个元素其中每个元素又都是一个表,D的长度为3;
- E中只含有一個元素该元素是一个表,该表中含3个元素其中后两个元素又都是表。
广义表是一种递归的数据结构因此很难为每个广义表分配固定夶小的存储空间,所以其广义表存储结构怎么画只好采用动态链接结构