C++广义表怎么递归求深度和元素原子个数-C++-PHP中文网

广义表深度定义为括号最大嵌套层数，空表()深度为1，原子深度为0，非空子表深度为1+子表最大深度；原子个数统计需穿透所有子表，原子计1、空表计0、子表递归累加。

c++广义表怎么递归求深度和元素原子个数

广义表递归求深度：注意空表和子表的边界处理

广义表的深度定义为括号嵌套的最大层数，空表 () 深度为 1，原子不增加深度，而每个非空子表会带来一层嵌套。关键在于：遇到子表要递归进其内部，但必须把当前层的“1 +” 和子表返回值取最大，不能简单累加。

常见错误是把 depth = 1 + max_depth_of_sublists 写成 depth += ...，导致多层子表被重复加；或者忽略空表——() 是合法广义表，它没有子节点，但深度仍是 1。

递归入口统一用一个 getDepth() 成员函数，对空表直接返回 1
遍历表头时，若当前元素是子表（即 isList() == true），调用其 getDepth() 并参与 max 计算
原子节点（isAtom() == true）不贡献深度，跳过
初始调用前确保表结构已正确解析，否则 getDepth() 可能访问空指针

示例片段（假设节点类型为 GListNode，含 isList()、getSublist()、next）：

int GListNode::getDepth() const {
    if (!this) return 0;
    if (isAtom()) return 0; // 原子无深度
    if (isEmpty()) return 1; // () → 深度 1
    int maxSubDepth = 0;
    for (auto p = getFirst(); p; p = p->next) {
        if (p->isList()) {
            maxSubDepth = std::max(maxSubDepth, p->getSublist()->getDepth());
        }
    }
    return 1 + maxSubDepth;
}

统计原子个数：递归展开所有层级，只计非子表节点

原子个数就是广义表中所有不可再分的元素总数，包括数字、字符、字符串等，但不含任何 () 或嵌套结构。难点在于：子表本身是节点，但它的内容才含原子，所以必须「穿透」每一层子表调用统计，而不能只看当前层。

典型误操作是只遍历首层节点，漏掉深层嵌套里的原子；或把空表 () 当作一个原子计数（实际它不含原子，应计 0）。

原子节点：直接计 1
空表节点：isEmpty() == true → 返回 0
非空子表节点：递归调用其 countAtoms()，结果累加
务必区分「节点类型」和「节点内容」——isList() 为真时，需取 getSublist() 再统计，而不是给这个节点本身加 1

简写示意：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

int GListNode::countAtoms() const {
    if (!this) return 0;
    if (isAtom()) return 1;
    if (isEmpty()) return 0;
    int cnt = 0;
    for (auto p = getFirst(); p; p = p->next) {
        if (p->isAtom()) cnt++;
        else if (p->isList()) cnt += p->getSublist()->countAtoms();
    }
    return cnt;
}