当前位置：首页 > article >正文

数据结构：广义表（ Generalized List）及其实现

article 2025/2/21 6:54:45

什么是广义表？

广义表（Generalized List）是一种扩展的线性表，它可以存储原子（单个数据元素）或子表（另一个广义表）。广义表的特点是：它可以递归定义，也就是说，一个广义表的元素可以是另一个广义表。

举个例子：

A = (1, 2, 3)：这是一个普通的线性表，包含 3 个原子。
B = (1, (2, 3), 4)：这是一个广义表，包含 2 个原子和 1 个子表 (2, 3)。
C = (1, (2, (3, 4)), 5)：这是一个更复杂的广义表，包含嵌套的子表。

广义表的灵活性使其非常适合表示复杂的数据结构，比如树、图等。

广义表的存储方式

1. 顺序存储

顺序存储是用数组来存储广义表。由于广义表的元素可以是原子或子表，因此需要额外的标记来区分原子和子表。

优点：

访问速度快，可以通过下标直接访问元素。
实现简单。

缺点：

插入和删除操作需要移动大量数据，效率低。
数组大小固定，不适合动态变化的广义表。

2. 链式存储

链式存储是用链表来存储广义表。每个节点可以是原子节点或子表节点，通过指针连接。

优点：

插入和删除操作效率高，不需要移动大量数据。
适合动态变化的广义表。

缺点：

访问速度慢，需要从头开始遍历。
内存开销大，每个节点需要额外存储指针。

广义表的基本概念

1. 长度

广义表的长度是指广义表中元素的个数。例如：

A = (1, 2, 3) 的长度是 3。
B = (1, (2, 3), 4) 的长度是 3（原子 1、子表 (2, 3) 和原子 4）。

2. 深度

广义表的深度是指广义表中嵌套的层数。例如：

A = (1, 2, 3) 的深度是 1。
B = (1, (2, 3), 4) 的深度是 2。
C = (1, (2, (3, 4)), 5) 的深度是 3。

广义表的基本操作

广义表的基本操作包括：增、删、查、改。下面我们用大白话解释这些操作。

增加元素：
- 在广义表的指定位置插入一个原子或子表。
删除元素：
- 删除广义表中指定位置的原子或子表。
查找元素：
- 查找广义表中是否存在指定的原子或子表。
修改元素：
- 修改广义表中指定位置的原子或子表。

C 语言实现广义表

下面是一个简单的广义表实现代码，包含初始化、插入、删除、查找和打印功能。

#include <stdio.h>
#include <stdlib.h>

// 定义广义表节点类型
typedef enum { ATOM, LIST } NodeType;

// 定义广义表节点结构体
typedef struct GLNode {
    NodeType tag;  // 节点类型：ATOM（原子）或 LIST（子表）
    union {
        char data;  // 原子数据
        struct GLNode *sublist;  // 子表指针
    };
    struct GLNode *next;  // 指向下一个节点的指针
} GLNode;

// 创建原子节点
GLNode* CreateAtom(char data) {
    GLNode *node = (GLNode*)malloc(sizeof(GLNode));
    node->tag = ATOM;
    node->data = data;
    node->next = NULL;
    return node;
}

// 创建子表节点
GLNode* CreateList(GLNode *sublist) {
    GLNode *node = (GLNode*)malloc(sizeof(GLNode));
    node->tag = LIST;
    node->sublist = sublist;
    node->next = NULL;
    return node;
}

// 插入元素
void InsertElement(GLNode *list, int pos, GLNode *element) {
    GLNode *current = list;
    for (int i = 0; i < pos && current != NULL; i++) {
        current = current->next;
    }
    if (current != NULL) {
        element->next = current->next;
        current->next = element;
    }
}

// 删除元素
void DeleteElement(GLNode *list, int pos) {
    GLNode *current = list;
    for (int i = 0; i < pos && current != NULL; i++) {
        current = current->next;
    }
    if (current != NULL && current->next != NULL) {
        GLNode *temp = current->next;
        current->next = temp->next;
        free(temp);
    }
}

// 查找元素
GLNode* FindElement(GLNode *list, char data) {
    GLNode *current = list;
    while (current != NULL) {
        if (current->tag == ATOM && current->data == data) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

// 打印广义表
void PrintList(GLNode *list) {
    GLNode *current = list;
    printf("广义表内容：");
    while (current != NULL) {
        if (current->tag == ATOM) {
            printf("%c ", current->data);
        } else if (current->tag == LIST) {
            printf("(");
            PrintList(current->sublist);
            printf(") ");
        }
        current = current->next;
    }
}

int main() {
    // 创建广义表 B = (1, (2, 3), 4)
    GLNode *sublist = CreateList(CreateAtom('2'));
    sublist->next = CreateAtom('3');
    GLNode *list = CreateAtom('1');
    list->next = CreateList(sublist);
    list->next->next = CreateAtom('4');

    PrintList(list);  // 打印广义表
    printf("\n");

    // 插入元素
    InsertElement(list, 1, CreateAtom('5'));
    PrintList(list);  // 打印广义表
    printf("\n");

    // 删除元素
    DeleteElement(list, 2);
    PrintList(list);  // 打印广义表
    printf("\n");

    // 查找元素
    GLNode *target = FindElement(list, '2');
    if (target != NULL) {
        printf("找到元素：%c\n", target->data);
    } else {
        printf("未找到元素\n");
    }

    return 0;
}