数据结构——广义表

发表于 更新于 分类于 ， 阅读次数：

数据结构——广义表

广义表的定义和相关概念

广义表是线性表的推广，其中的元素可以是原子（即不可再分的基本数据项），也可以是子表。广义表的一些常用术语包括： - 长度：广义表的长度是其顶层元素的个数。 - 深度：广义表中元素嵌套的最大深度。 - 表头：广义表中的第一个元素。 - 表尾：去掉表头后剩下的部分。

例子

  • A = ()
  • B = (a, b, c)c)`
  • C = (a, (b, c, d), e)
  • D = (a, b, (e, f, g))
  • E = ((a, b), c, (d, e, (f, g)))
  • F = ((), ((), ()))

下表展示了图片中的几个广义表的长度、深度、表头和表尾的具体值：

广义表 长度 深度 表头 表尾
A 0 1 空 ()
B 3 1 a (b, c)
C 3 2 a ((b, c, d), e)
D 3 3 a (b, (e, f, g))
E 4 3 (a, b) (c, (d, e, (f, g)))
F 3 3 () ((), ((), ()))

广义表的存储结构

IMG_20241021_153619

由于广义表中的每个元素可能是原子或子表，因此在广义表的存储结构中存在两类结点：

  1. 原子节点：用于存储单个元素。
  2. 子表节点：用于存储子表的指针。

为了区分元素是原子还是子表，结构中还设置了一个标识域 type

1
enum GListNodeType { ATOM, LIST }; // 结点类型：原子或子表

当type值为1，说明存入原子的值；为2，说明存入子广义表的头指针

广义表定义如下：

1
2
3
4
5
6
7
8
9
typedef char ElemType; // 原子的类型定义为字符类型
typedef struct GListNode {
    GListNodeType type; // 类型域，表示该节点是原子还是子表
    union {
        ElemType data; // 如果是原子节点，则存储数据
        struct GListNode *sublist; // 如果是子表节点，则存储指向子表的指针
    };
    struct GListNode *next; // 指向下一个表节点的指针
} GListNode, *GList; // GList 表示广义表的指针类型
IMG_20241021_154058

代码

求广义表长度

1
2
3
4
5
6
7
8
9
10
// 求广义表的长度
int LengthGList(GList list) {
    int length = 0;
    GList current = list;
    while (current != NULL) {
        length++;
        current = current->next;
    }
    return length;
}

求广义表深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 求广义表的深度
int DepthGList(GList list) {
    if (list == NULL) {
        return 1;  // 空表深度为 1
    }
    int maxDepth = 1;
    GList current = list;
    while (current != NULL) {
        if (current->type == LIST) {
            int sublistDepth = DepthGList(current->value.sublist) + 1;
            if (sublistDepth > maxDepth) {
                maxDepth = sublistDepth;
            }
        }
        current = current->next;
    }
    return maxDepth;
}

打印

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 打印广义表
void PrintGList(GList list) {
    if (list == NULL) {
        printf("()");
        return;
    }
    printf("(");
    GList current = list;
    while (current != NULL) {
        if (current->type == ATOM) {
            printf("%c", current->value.data);
        } else if (current->type == LIST) {
            PrintGList(current->value.sublist);
        }
        if (current->next != NULL) {
            printf(", ");
        }
        current = current->next;
    }
    printf(")");
}

线性表章节小结

IMG_20241021_155320