C++ 实现广义表：数据结构与代码示例

广义表是一种递归定义的数据结构，可以用链表来表示。每个节点可以是一个原子元素或者是一个子广义表。下面是一个简单的 C++ 实现：

定义节点结构体

struct Node {
    bool isAtom; // 是否是原子元素
    union {
        char atom; // 原子元素值
        struct Node* head; // 子广义表的头节点
    };
    struct Node* tail; // 下一个节点
};

实现创建广义表的函数

Node* createList(const string& str, int& i) {
    Node* node = nullptr;
    bool isAtom = false;
    char atom = '\0';
    while (i < str.length()) {
        char c = str[i];
        i++;
        if (c == '(') {
            node = new Node;
            node->isAtom = false;
            node->head = createList(str, i);
        } else if (c == ')') {
            return node;
        } else if (c == ',') {
            node->tail = createList(str, i);
        } else {
            atom = c;
            isAtom = true;
            node = new Node;
            node->isAtom = isAtom;
            node->atom = atom;
        }
    }
    return node;
}

实现打印广义表的函数

void printList(Node* node) {
    if (node == nullptr) {
        return;
    }
    if (node->isAtom) {
        cout << node->atom;
    } else {
        cout << '(';
        printList(node->head);
        cout << ')';
    }
    if (node->tail != nullptr) {
        cout << ',';
        printList(node->tail);
    }
}

测试代码

int main() {
    string str = '(a,b,(c,d),e)';
    int i = 0;
    Node* list = createList(str, i);
    printList(list);
    return 0;
}

输出结果为：(a,b,(c,d),e)

完整代码如下：

#include <iostream>
#include <string>
using namespace std;

struct Node {
    bool isAtom; // 是否是原子元素
    union {
        char atom; // 原子元素值
        struct Node* head; // 子广义表的头节点
    };
    struct Node* tail; // 下一个节点
};

Node* createList(const string& str, int& i) {
    Node* node = nullptr;
    bool isAtom = false;
    char atom = '\0';
    while (i < str.length()) {
        char c = str[i];
        i++;
        if (c == '(') {
            node = new Node;
            node->isAtom = false;
            node->head = createList(str, i);
        } else if (c == ')') {
            return node;
        } else if (c == ',') {
            node->tail = createList(str, i);
        } else {
            atom = c;
            isAtom = true;
            node = new Node;
            node->isAtom = isAtom;
            node->atom = atom;
        }
    }
    return node;
}

void printList(Node* node) {
    if (node == nullptr) {
        return;
    }
    if (node->isAtom) {
        cout << node->atom;
    } else {
        cout << '(';
        printList(node->head);
        cout << ')';
    }
    if (node->tail != nullptr) {
        cout << ',';
        printList(node->tail);
    }
}

int main() {
    string str = "(a,b,(c,d),e)";
    int i = 0;
    Node* list = createList(str, i);
    printList(list);
    return 0;
}