C++ 廣義表遍歷與節點計算：遞歸算法實現指南

廣義表定義回顧

廣義表是線性表的推廣，元素可以是原子項或子表。典型結構：

struct GNode {
    int tag;          // 0: 原子, 1: 子表
    union {
        char atom;    // 原子值
        GNode* hp;    // 子表頭指針
    } val;
    GNode* tp;        // 尾部指針（下一個元素）
};

遍歷與計數遞歸算法

// 計算廣義表中原子項總數
int CountAtoms(GNode* L) {
    if (!L) return 0;
    if (L->tag == 0) return 1 + CountAtoms(L->tp);
    // 子表：遞歸計算子表原子數 + 繼續遍歷尾部
    return CountAtoms(L->val.hp) + CountAtoms(L->tp);
}

// 深度優先遍歷輸出（如 LISP 風格）
void PrintGList(GNode* L) {
    if (!L) return;
    if (L->tag == 0) {
        cout << L->val.atom;
    } else {
        cout << '(';
        PrintGList(L->val.hp);
        cout << ')';
    }
    if (L->tp) {
        cout << ',';
        PrintGList(L->tp);
    }
}

輸入解析關鍵點

從字符串構建廣義表需實現詞法分析器，處理 ( ) , 和原子字符。建議使用遞歸下降解析：

GNode* Parse(const string& s, int& pos) {
    if (pos >= s.size()) return nullptr;
    if (s[pos] == '(') {
        pos++; // 跳過 '('
        GNode* head = new GNode{1, {.hp = Parse(s, pos)}, nullptr};
        GNode* cur = head;
        while (pos < s.size() && s[pos] == ',') {
            pos++;
            cur->tp = new GNode{1, {.hp = Parse(s, pos)}, nullptr};
            cur = cur->tp;
        }
        if (pos < s.size() && s[pos] == ')') pos++;
        return head;
    } else if (isalnum(s[pos])) {
        GNode* node = new GNode{0, {.atom = s[pos++]}, nullptr};
        if (pos < s.size() && s[pos] == ',') {
            pos++;
            node->tp = Parse(s, pos);
        }
        return node;
    }
    return nullptr;
}

完整程序框架

int main() {
    string input;
    getline(cin, input); // 如: (a,(b,c),d)
    int pos = 0;
    GNode* list = Parse(input, pos);
    cout << "原子總數: " << CountAtoms(list) << endl;
    cout << "表結構: ";
    PrintGList(list);
    cout << endl;
    // 釋放內存...
    return 0;
}