数据结构与算法 广义表

### 广义表的数据结构

广义表是一种复杂的数据结构，能够表示多种其他数据结构的形式。作为一种可嵌套列表的结构，它不仅限于线性序列，还可以表达更复杂的层次关系[^2]。

#### 存储结构类型定义

为了有效地实现广义表的操作，在计算机内存中的存储通常采用链式存储结构来保存其元素之间的逻辑关联。每个节点包含两个指针域：一个指向当前结点所含有的原子项；另一个则用于链接下一个兄弟结点或是子表的第一个成员。对于非空广义表而言，第一个元素被称为“表头”，其余部分组成的子表称为“表尾”。

struct GList {
    bool isAtom;       // 是否为原子标志位
    union {            // 节点值联合体
        int atomValue; // 若isAtom=true，则此字段有效
        struct Node* subGlistPtr;
    } value;

    struct Node *nextSibling; // 同级下一节点指针
};

#### 基本操作算法

##### 求解广义表深度

通过递归方法计算给定广义表的最大层数：

int Depth(GList L) {
    if (L.isAtom || !L.value.subGlistPtr)
        return 0;
    
    int maxDepth = 0;
    for (auto p = L.value.subGlistPtr; p != nullptr; p = p->nextSibling) {
        int currentDepth = Depth(*p);
        if (currentDepth > maxDepth)
            maxDepth = currentDepth;
    }
    return maxDepth + 1;
}

##### 表尾添加新元素

要在一个已存在的广义表后面追加新的单个元素或整个子表，可以通过遍历到原表最后一个位置并创建相应的新节点完成连接工作。

void AppendElement(GList &gL, const GList& newElem){
    auto ptr = &gL;
    while(ptr->value.subGlistPtr && ptr->nextSibling!=nullptr){
        ptr=ptr->nextSibling;
    }

    if(!ptr->value.subGlistPtr){ // 如果是首次插入
        ptr->value.subGlistPtr=new std::make_unique<GList>(newElem);
    }else{
        ptr->nextSibling=new std::make_unique<GList>(newElem);
    }
}

#### 应用场景实例

由于广义表具有高度灵活性的特点，因此非常适合用来描述那些内部存在分支结构的信息模型，比如XML文档解析、文件目录树形展示以及自然语言处理领域内的句法分析等问题都可以借助这一工具得到简化解决。