Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
概念
广义表（Generalized Lists）是n（n≥0）个数据元素a1，a2，…，ai，…，an 的有序序列，一般记作：
ls＝（a1，a2，…，ai，…，an）
其中：ls 是广义表的名称，n 是它的长度每个ai（1≤i≤n）是ls 的成员：它可以是单个元素（“
广义表ls 的
单元素
”），也可以是一个广义表（“
广义表ls 的
子表
”）。
当广义表ls 非空时，称第一个元素a1 为ls 的表头（head），称其余元素组成的表（a2，…，ai，…，an）为ls 的表尾（tail）。
广义表的重要性质：
⑴广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，…。
⑵广义表可以是递归的表，即广义表也可以是其自身的子表。例如表E 就是一个递归的表。
⑶广义表可以为其他表所共享。例如，表A、表B、表C 是表D 的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。
一些广义表的例子：
A ＝（）
B ＝（e）
C ＝（a，（b，c，d））
D ＝（A，B，C）
E ＝（a，E）
F ＝（（））
存储结构
头尾表示法
由于广义表中的数据元素既可能是列表也可能是单元素，相应地在头尾表示法中结点的结构形式有两种：一种是
表结点，用以表示列表；另一种是
元素结点，用以表示单元素：
表结点，用以表示列表；另一种是
元素结点，用以表示单元素：
- 表结点中包括一个指向表头的指针和指向表尾的指针；
- 元素结点中应该包括所表示单元素的元素值。
- 为了区分这两类结点，在结点中还要设置一个标志域：如果标志为1，则表示该结点为表结点；如果标志为0，则表示该结点为元素结点。
例子：
A ＝（）
B ＝（e）
C ＝（a，（b，c，d））
D ＝（A，B，C）
E ＝（a，E）
F ＝（（））
采用头尾表示法容易分清列表中单元素或子表所在的
层次
。例如，在广义表D 中，单元素a 和e 在同一层次上，而单元素b、c、d 在同一层次上且比a 和e 低一层，子表B 和C 在同一层次上。另外，最高层的表结点的个数即为广义表的长度。例如，在广义表D 的最高层有三个表结点，其广义表的长度为3。
孩子兄弟表示法
两种结点形式：一种是
有孩子结点，用以表示
列表；另一种是
无孩子结点，用以表示
单元素。
有孩子结点，用以表示
列表；另一种是
无孩子结点，用以表示
单元素。
- 在有孩子结点中包括一个指向第一个孩子（长子）的指针和一个指向兄弟的指针
- 在无孩子结点中包括一个指向兄弟的指针和该元素的元素值
- 为了能区分这两类结点，在结点中还要设置一个标志域：如果标志为1，则表示该结点为有孩子结点；如果标志为0，则表示该结点为无孩子结点。
例子：
A ＝（）
B ＝（e）
C ＝（a，（b，c，d））
D ＝（A，B，C）
E ＝（a，E）
F ＝（（））
采用孩子兄弟表示法时，表达式中的左括号“（”对应存储表示中的tag=1 的结点，且最高层结点的tp域必为NULL。
参考来源：C语言中文网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/167189.html原文链接：https://javaforall.net
