当前位置：首页 > news >正文

数据结构与算法之美：广义表

news 2025/7/12 19:48:13

Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！

我的博客：<但凡.

我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》、《C++修炼之路》、《Linux修炼：终端之内洞悉真理》

欢迎点赞，关注！

1、广义表的定义

广义表（Generalized List）是一种非线性的数据结构，可以看作线性表的推广。与线性表不同，广义表中的元素可以是原子（不可再分的单个数据项），也可以是另一个广义表，意思就是广义表可以嵌套广义表。这种递归定义使得广义表具有高度的灵活性。

广义表的长度定义为最外层包含的元素个数，深度定义为嵌套的层数。例如，广义表 (a, (b, c), d) 的长度为 3（元素分别为 a、(b, c) 和 d），深度为 2（嵌套一层子表 (b, c)）。

2、广义表的表示方法

广义表通常用括号和逗号表示，形式为：
LS = (a₁, a₂, ..., aₙ)
其中 LS 是广义表名，aᵢ 可以是原子或子表。空表用 () 表示。

广义表的存储结构通常采用链式实现，每个结点包含两个域：

(1)tag：标识结点类型（0 为原子，1 为子表）。

(2)联合域：若 tag=0，存储原子值 data；若 tag=1，存储指向子表的指针 sublist。

(3)next：指向下一个结点的。

2、广义表的操作

创建广义表
通过递归解析输入字符串实现。例如，输入 (a,(b,c),d)：

遇到 ( 时创建子表，递归处理后续元素。
遇到原子时直接存储。
遇到 ) 时结束当前子表。

求广义表长度
遍历顶层元素计数，直到 next 为 NULL。例如 (a,(b,c),d) 的长度为 3。

求广义表深度
递归计算子表的最大深度加 1。空表深度为 1，原子深度为 0。
公式：
depth(LS) = 1 + max{depth(aᵢ) | aᵢ ∈ LS}

遍历广义表
递归访问每个元素：

若为原子，直接输出。
若为子表，递归遍历子表内容。

3、广义表模拟实现

3.1、节点

struct GLNode {NodeType tag;union {char atom;GLNode* sublist;};GLNode* next;GLNode(NodeType t, char a = '\0', GLNode* sl = nullptr, GLNode* n = nullptr): tag(t), next(n) {if (t == ATOM) atom = a;else sublist = sl;}
};

3.2、各种操作

class GeneralizedList {
public:GeneralizedList() : head(nullptr) {}~GeneralizedList() { destroy(head); }void create(const string& s) {int pos = 0;head = createHelper(s, pos);}int depth() const { return depthHelper(head); }void print() const { printHelper(head); cout << endl; }private:GLNode* head;GLNode* createHelper(const string& s, int& pos) {if (pos >= s.size() || s[pos] == ')') return nullptr;GLNode* node = nullptr;if (s[pos] == '(') {pos++;node = new GLNode(SUBLIST);node->sublist = createHelper(s, pos);pos++; // skip ')'}else {if (s[pos] == ',') pos++;if (s[pos] == '(') {pos++;node = new GLNode(SUBLIST);node->sublist = createHelper(s, pos);pos++; // skip ')'}else{node = new GLNode(ATOM, s[pos]);pos++;}}node->next = createHelper(s, pos);return node;}void destroy(GLNode* node) {if (!node) return;if (node->tag == SUBLIST) destroy(node->sublist);destroy(node->next);delete node;}int depthHelper(GLNode* node) const {if (!node) return 0;int max_depth = 0;while (node) {if (node->tag == SUBLIST) {int d = depthHelper(node->sublist) + 1;if (d > max_depth) max_depth = d;}node = node->next;}return max_depth;}void printHelper(GLNode* node) const {if (!node) return;if (node->tag == ATOM) {cout << node->atom;}else {cout << "(";printHelper(node->sublist);cout << ")";}if (node->next) {cout << ",";printHelper(node->next);}}
};

3.3、测试代码

#define _CRT_SECURE_NO_WARNINGS 1
#include"head.h"
int main() {GeneralizedList gl;// 测试用例1: (a,(b,c),d)gl.create("(a,(b,c),d)");cout << "List: ";gl.print();cout << "Depth: " << gl.depth() << endl; // 应输出2// 测试用例2: ((a,(b)),c)GeneralizedList gl2;gl2.create("((a,(b)),c)");cout << "List: ";gl2.print();cout << "Depth: " << gl2.depth() << endl; // 应输出3// 测试用例3: aGeneralizedList gl3;gl3.create("a");cout << "List: ";gl3.print();cout << "Depth: " << gl3.depth() << endl; // 应输出1return 0;
}