数据结构考试要求-第四章 串，数组和广义表

第四章 串，数组和广义表

广义表

广义表（又称列表Lists）是n>=0个元素的有限序列，其中每个ai或者是原子，或者是一个广义表

通常广义表记作：LS=(a1,a2,...,an)，
其中LS为表名，n为表的长度，每一个ai为标的元素
表头：若LS非空，其中第一个元素a1就是表头。记作head(LS) = a1,
表尾：除表头之外的其他元素组成的表。记作head(LS) = (a2,...an)
**注：表尾不是最后一个元素，而是一个子表**
1
2
3
4
5

• 广义表中的数据元素有相对次序；一个直接前驱和一个直接后继
• 广义表的长度定义为最外层所包含元素的个数；
• 广义表的深度定义为该广义表展开后所包含括号的重数；原子深度为0，空表深度为1
• 广义表可以为其他广义表共享；如A=(1,2);B=(A,3)
• 广义表可以递归；如F=(a, F)=(a,(a,…)),注意：递归表深度是无穷的，长度是有限的
• 广义表是可以多层次的

广义表的链式存储结构

需要原子类型和表类型两种结点类型，，若列表不空，则可分解为表头和表尾，一对确定的表头和表尾可唯一确定列表。

[tag，subLists/data，link]
若tag=0，表示该结点为原子结点，存储data
tag=1表示该结点为子表节点，存储subLists
link保存当前结点的兄弟结点的地址

typedef struct Inode {
    int tag;
    union {
        int data;               // 存放原子结构
        struct Inode* subLists; // 存放子表结构
    }val;
    struct Inode* link;
}LNode;
// 广义表基本操作算法思想
void func(LNode* g) {
    assert(g);
    if (g->tag == 1) {
        func(g);
    }
    else
    	// 原子处理语句
    func(g->Link);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25