3、广义表的两种存储结构图:A = (( ),a,(b,(c,d)),(e,f))
时间: 2023-10-07 14:06:20 浏览: 251
广义表是一种可以包含多种数据类型的数据结构,它可以嵌套包含其他广义表,因此需要使用树形结构来表示。广义表的两种存储结构图如下:
1. 链式存储结构
链式存储结构使用链表来存储广义表中的元素,每个节点包含两个指针,一个指向该节点的下一个元素,一个指向该节点所包含的子广义表的头节点。对于广义表 A = (( ),a,(b,(c,d)),(e,f)),其链式存储结构如下图所示:
```
+---+---+ +---+---+---+ +---+---+---+---+
head -> | o-|-------->| o-|----|----|---->| o-|----|----|----|
+---+---+ +---+---+---+ +---+---+---+---+
| a | | b | |-------->| c | d | 0 |
+---+---+ +---+---+ +---+---+---+---+
| o-|------------> | e | | f | 0 |
+---+---+ +---+---+ +---+---+---+
```
2. 顺序存储结构
顺序存储结构使用数组来存储广义表中的元素,其中每个元素可以是一个原子或者一个指向子广义表的指针。对于广义表 A = (( ),a,(b,(c,d)),(e,f)),其顺序存储结构如下图所示:
```
+---+---+---+---+---+---+---+---+---+---+
| H | 0 | a | 1 | b | 3 | c | d | 0 | e |
+---+---+---+---+---+---+---+---+---+---+
| f | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+
```
其中,H 表示广义表的头指针,0 表示空指针。在顺序存储结构中,每个元素的下标都对应着该元素在广义表中的位置,例如 A[2] 表示第二个元素 a,A[4] 表示第四个元素 b,A[5] 表示它的子广义表的头指针。因此,要访问广义表中的一个元素,只需要知道它的下标即可。
阅读全文