C++ 实现广义表：存储不同类型元素的链表结构

实现一个广义表可以使用链表来存储，每个节点分为两种类型：原子节点和子表节点。原子节点存储的是元素，而子表节点存储的是一个指向子表的指针。

下面是一个示例的广义表的结构体定义：

struct GLNode {
    int tag; // 标记，0表示原子节点，1表示子表节点
    union {
        char data; // 原子节点存储的元素
        GLNode* subList; // 子表节点存储的子表指针
    } value;
    GLNode* next; // 下一个节点指针
};

接下来是一些常用的操作：

创建空表

GLNode* createEmptyList() {
    GLNode* newList = new GLNode;
    newList->tag = 1; // 标记为子表节点
    newList->value.subList = nullptr;
    newList->next = nullptr;
    return newList;
}

插入元素

void insertElem(GLNode* list, char elem) {
    // 创建新节点
    GLNode* newNode = new GLNode;
    newNode->tag = 0; // 标记为原子节点
    newNode->value.data = elem;
    newNode->next = nullptr;

    // 找到最后一个节点
    GLNode* lastNode = list;
    while (lastNode->next != nullptr) {
        lastNode = lastNode->next;
    }

    // 将新节点插入到最后一个节点之后
    lastNode->next = newNode;
}

插入子表

void insertSubList(GLNode* list, GLNode* subList) {
    // 创建新节点
    GLNode* newNode = new GLNode;
    newNode->tag = 1; // 标记为子表节点
    newNode->value.subList = subList;
    newNode->next = nullptr;

    // 找到最后一个节点
    GLNode* lastNode = list;
    while (lastNode->next != nullptr) {
        lastNode = lastNode->next;
    }

    // 将新节点插入到最后一个节点之后
    lastNode->next = newNode;
}

打印广义表

void printList(GLNode* list) {
    if (list == nullptr) {
        return;
    }

    if (list->tag == 0) { // 原子节点
        std::cout << list->value.data << ' '; 
    } else { // 子表节点
        std::cout << '(';
        GLNode* subList = list->value.subList;
        while (subList != nullptr) {
            printList(subList);
            subList = subList->next;
        }
        std::cout << ') ';
    }
}

示例代码：

int main() {
    // 创建广义表 (a, b, (c, d))
    GLNode* list = createEmptyList();
    insertElem(list, 'a');
    insertElem(list, 'b');
    GLNode* subList = createEmptyList();
    insertElem(subList, 'c');
    insertElem(subList, 'd');
    insertSubList(list, subList);

    // 打印广义表
    printList(list);
    std::cout << std::endl;

    return 0;
}

输出结果：

a b (c d)