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

数据结构中的宝藏秘籍之广义表

news 来源：原创 2025/8/14 23:13:32

广义表，也被称作列表（Lists），是一种递归的数据结构。它就像一个神秘的盒子，既可以装着单个元素（原子），也可以嵌套着其他的盒子（子列表）。比如广义表 (a (b c) d)，其中 a 和 d 是原子，而 (b c) 则是一个子列表。这种嵌套结构使得广义表能够轻松表示各种复杂的关系，就像一位万能的画家，能描绘出树形结构、图结构等多样的 “画作”。

与普通的线性表相比，广义表的元素类型更加丰富多样，不仅可以是相同类型的元素，还能包含不同类型的元素，甚至可以嵌套其他的广义表。这种灵活性让广义表在处理复杂数据时游刃有余，成为了数据结构中的 “多面手”。

先上代码：

#include <stdio.h>
#include <stdlib.h>// 定义原子类型为字符型
typedef char AtomType;// 定义元素标签类型，用于区分原子和列表
typedef enum { ATOM, LIST } ElemTag;// 定义广义表节点结构体
typedef struct GLNode 
{ElemTag tag;  // 标记该节点是原子还是列表union {AtomType atom;  // 如果是原子，存储原子的值struct GLNode *child;  // 如果是列表，指向子列表} UNION;struct GLNode *next;  // 指向下一个节点
} GLNODE;// 定义元素标志类型，用于读取字符串时识别不同元素
typedef enum { LP = 1, RP = 2, Atom = 3, End = 4 } ElemFlag;// 从 str[*pi] 开始读入一个元素
ElemFlag GetElem(char str[], int *pi, AtomType *pe)
{while (str[*pi] == ' ') (*pi)++;// 跳过空格if (str[*pi] == '\0') return End;// 如果到达字符串末尾，返回 End 标志if (str[*pi] == '(')// 如果遇到左括号，返回 LP 标志，并将指针后移{		(*pi)++;return LP;}if (str[*pi] == ')') // 如果遇到右括号，返回 RP 标志，并将指针后移{(*pi)++;return RP;}// 如果是原子，将字符赋值给 pe，并将指针后移，返回 Atom 标志*pe = str[*pi];(*pi)++;return Atom;
}// 建广义表
GLNODE *Glist_Create(char str[], int *pi) 
{GLNODE *p;AtomType e;// 根据读取的元素类型进行不同处理switch (GetElem(str, pi, &e)) {case Atom:// 为原子节点分配内存p = (GLNODE *)malloc(sizeof(GLNODE));if (p == NULL) {fprintf(stderr, "内存分配失败\n");exit(EXIT_FAILURE);}p->tag = ATOM;p->UNION.atom = e;p->next = Glist_Create(str, pi);// 递归创建下一个节点return p;case LP:// 为列表节点分配内存p = (GLNODE *)malloc(sizeof(GLNODE));if (p == NULL) {fprintf(stderr, "内存分配失败\n");exit(EXIT_FAILURE);}p->tag = LIST;p->UNION.child = Glist_Create(str, pi);// 递归创建子列表p->next = Glist_Create(str, pi);// 递归创建下一个节点return p;case RP:return NULL;case End:return NULL;}return NULL;
}// 求表深度
int GList_Depth(GLNODE *L) 
{GLNODE *p;int depth1, max = 0;if (L == NULL || L->tag == ATOM) return 0;// 如果是原子节点，深度为 0for (p = L->UNION.child; p; p = p->next) // 遍历子列表{depth1 = GList_Depth(p);// 递归计算子列表的深度if (depth1 > max) max = depth1;}return max + 1;// 列表深度为子列表最大深度加 1
}// 遍历广义表，打印层次括号
void GList_Traverse(GLNODE *L) 
{GLNODE *p;for (p = L; p != NULL; p = p->next) {if (p->tag == ATOM) {printf("%c ", p->UNION.atom);// 打印原子节点的值} else {printf("(");// 遇到列表节点，打印左括号GList_Traverse(p->UNION.child);// 递归遍历子列表printf(")");// 打印右括号}}
}// 复制广义表
GLNODE *GList_Copy(GLNODE *L) 
{GLNODE *head = NULL, *p, *newNode, *tail = NULL;if (!L) return NULL;for (p = L; p != NULL; p = p->next) {// 为新节点分配内存newNode = (GLNODE *)malloc(sizeof(GLNODE));if (newNode == NULL) {fprintf(stderr, "内存分配失败\n");exit(EXIT_FAILURE);}if (head == NULL) {head = tail = newNode;} else {tail->next = newNode;tail = newNode;}if (p->tag == ATOM) {newNode->tag = ATOM;// 复制原子节点newNode->UNION.atom = p->UNION.atom;} else {newNode->tag = LIST;// 复制列表节点，递归复制子列表newNode->UNION.child = GList_Copy(p->UNION.child);}}if (tail) {tail->next = NULL;}return head;
}int main() 
{char str[30] = "(a (b c) d)";  // 广义表的字符串表示int i = 0;GLNODE *L1, *L2;L1 = Glist_Create(str, &i);		// 创建广义表 L1GList_Traverse(L1);				// 遍历并打印广义表 L1printf("%d\n", GList_Depth(L1));// 计算并打印广义表 L1 的深度L2 = GList_Copy(L1);			// 复制广义表 L1 到 L2GList_Traverse(L2);				// 遍历并打印广义表 L2printf("%d\n", GList_Depth(L2));// 计算并打印广义表 L2 的深度return 0;
}

（一）数据结构定义：搭建广义表的基石

typedef struct GLNode 
{ElemTag tag;  // 标记该节点是原子还是列表union {AtomType atom;  // 如果是原子，存储原子的值struct GLNode *child;  // 如果是列表，指向子列表} UNION;struct GLNode *next;  // 指向下一个节点
} GLNODE;

这段代码定义了广义表的节点结构 GLNODE。tag 字段就像一个神奇的标签，能够区分节点是原子还是列表。UNION 联合体则根据 tag 的值，巧妙地存储原子或指向子列表的指针。next 指针则负责将各个节点连接起来，形成一个有序的链条。这种设计让广义表能够灵活地表示不同类型的元素和复杂的嵌套结构，为后续的操作奠定了坚实的基础。

（二）广义表的创建：从字符串到数据结构的神奇转变

GLNODE *Glist_Create(char str[], int *pi) 
{// ...
}

Glist_Create 函数是广义表创建的核心。它通过 GetElem 函数从输入的字符串中逐个读取元素，就像一位细心的工匠，根据元素的类型（原子、左括号、右括号、字符串结束）进行不同的处理。遇到原子时，为其创建一个原子节点；遇到左括号时，创建一个列表节点，并递归地创建子列表。递归的方式让代码简洁而高效，能够轻松应对广义表的嵌套结构，就像一位技艺高超的魔术师，将字符串神奇地转化为广义表的数据结构。

（三）广义表的深度计算：探索广义表的 “深度” 秘密

int GList_Depth(GLNODE *L) 
{// ...
}

GList_Depth 函数用于计算广义表的深度。对于原子节点，其深度为 0；对于列表节点，则递归地计算子列表的深度，并取子列表最大深度加 1 作为当前列表的深度。递归的思想在这里再次发挥了重要作用，让我们能够轻松地探索广义表的 “深度” 秘密，就像一位勇敢的探险家，深入广义表的内部，测量其嵌套的层次。

（四）广义表的遍历：揭开广义表的 “庐山真面目”

void GList_Traverse(GLNODE *L) 
{// ...
}

GList_Traverse 函数就像一位导游，带领我们遍历广义表并打印其层次括号表示。遇到原子节点时，直接打印原子的值；遇到列表节点时，先打印左括号，递归地遍历子列表，再打印右括号。通过递归遍历，我们能够清晰地看到广义表的层次结构，揭开它的 “庐山真面目”，仿佛置身于一个神秘的迷宫中，一步步揭开它的神秘面纱。

（五）广义表的复制：克隆一个一模一样的广义表

GLNODE *GList_Copy(GLNODE *L) 
{// ...
}

GList_Copy 函数用于复制广义表。它遍历原广义表的每个节点，为新节点分配内存，并根据节点类型复制原子或递归地复制子列表。这样，我们就可以得到一个与原广义表结构完全相同的新广义表，就像克隆技术一样，复制出一个一模一样的 “双胞胎”。

运行：

四、广义表的应用场景：无处不在的 “魔法工具”

（一）编译器设计：解析代码的得力助手

在编译器中，广义表可以用于表示语法树。语法树是源代码的一种抽象表示，它反映了代码的语法结构。广义表的嵌套结构正好可以用来表示语法树的层次关系，方便编译器进行语法分析和代码生成。就像一位聪明的翻译官，将源代码翻译成计算机能够理解的机器语言。

（二）人工智能：构建知识图谱的强大武器

在人工智能领域，广义表可以用于表示知识图谱。知识图谱是一种语义网络，用于表示实体之间的关系。广义表可以将实体和关系表示为节点和子列表，从而方便进行知识的存储和推理。就像一位智慧的导师，帮助人工智能系统更好地理解和处理知识。

（三）图形处理：绘制复杂图形的神奇画笔

在图形处理中，广义表可以用于表示复杂的图形结构。例如，一个三维模型可以由多个子模型组成，每个子模型又可以由多个基本图形组成。广义表可以很好地表示这种层次结构，方便进行图形的渲染和处理。就像一位天才的画家，用神奇的画笔绘制出绚丽多彩的图形世界。

五、总结与展望

通过递归的方式，我们可以方便地实现广义表的创建、深度计算、遍历和复制等操作。

数据结构中的宝藏秘籍之广义表

广义表，也被称作列表（Lists），是一种递归的数据结构。它就像一个神秘的盒子，既可以装着单个元素（原子），也可以嵌套着其他的盒子（子列表）。比如广义表 (a (b c)…...

编程日记 2025/8/14 23:13:32

电流模式控制学习

电流模式控制电流模式控制（CMC）是开关电源中广泛使用的一种控制策略，其核心思想是通过内环电流反馈和外环电压反馈共同调节占空比。相比电压模式控制，CMC具有更快的动态响应和更好的稳定性，但也存在一些固有缺点。 …...

编程日记 2025/8/1 17:10:23

汽车免拆诊断案例 | 2011款雪铁龙世嘉车刮水器偶尔自动工作

故障现象一辆2011款雪铁龙世嘉车，搭载1.6 L 发动机，累计行驶里程约为19.8万km。车主反映，该车刮水器偶尔会自动工作，且前照灯偶尔会自动点亮。故障诊断接车后试车发现，除了上述故障现象以外，当用遥控器…...

编程日记 2025/8/9 6:09:37

#去除知乎中“盐选”付费故事

添加油猴脚本，去除知乎中“盐选”付费故事 // UserScript // name 盐选内容隐藏脚本 // namespace http://tampermonkey.net/ // version 0.2 // description 自动隐藏含有“盐选专栏”或“盐选”文字的回答卡片 // author YourName // mat…...

编程日记 2025/8/14 23:09:07

github 项目迁移到 gitee

1. 查看远程仓库地址 git remote -v 2. 修改远程仓库地址确保 origin 指向你的 Gitee 仓库，如果不是，修改远程地址。 git remote set-url origin https://gitee.com/***/project.git 3. 查看本地分支 git branch 4. 推送所有本地分支 git p…...

编程日记 2025/8/14 13:48:23

2025年03月中国电子学会青少年软件编程（Python）等级考试试卷（五级）答案 + 解析

青少年软件编程（Python）等级考试试卷（五级）分数：100 题数：38 一、单选题(共25题，共50分) 1. 以下哪个选项不是Python中的推导式？（） A. 列表推导式 B. 字典推导式 C. 集合推导式 D. 元组推导式正确答案：D 答案解析：Python中的推导式包括列表推导式、字典推导式…...

编程日记 2025/8/11 18:01:57

[Unity]-[UI]-[Prefab] 关于UGUI UI Prefab的制作技巧

从上到下，从外到里，多用空物体套壳这个意思就是说在使用ugui时制作prefab时，要遵循“从上到下，从外到里，多用空物体套壳”的原则，好处就是后面好修改，并且可以复用不同的prefab子模块。且在布…...

编程日记 2025/8/1 17:09:07

【Reading Notes】（8.3）Favorite Articles from 2025 March

【March】雷军一度登顶中国首富，太厉害了（2025年03月02日） 早盘，小米港股一路高歌猛进，暴涨4%，股价直接飙到52港元的历史新高。这一波猛如虎的操作，直接把雷军的身家拉到了2980亿元&#xff0c…...

编程日记 2025/8/1 17:08:57

2021-11-09 C++倍数11各位和为13

缘由c函数题找数字的-编程语言-CSDN问答 void 倍数11各位和为13(int n, int& b, int* h) {//缘由https://ask.csdn.net/questions/7559803?spm1005.2025.3001.5141b !(n % 11);while(n)*h n % 10, n / 10; }int a 1, b 1, c 0, d 0;while (a < 100){倍数11各位和…...

编程日记 2025/8/14 4:24:29

2025年03月中国电子学会青少年软件编程（Python）等级考试试卷（六级）真题

青少年软件编程（Python）等级考试试卷（六级） 分数：100 题数：38 答案解析：https://blog.csdn.net/qq_33897084/article/details/147341458 一、单选题(共25题，共50分) 1. 在tkinter的…...

编程日记 2025/8/11 0:10:27

Linux简介

一、Linux 简介 Linux 内核最初只是由芬兰人林纳斯托瓦兹（Linus Torvalds）在赫尔辛基大学上学时出于个人爱好而编写的。 Linux 是一套免费使用和自由传播的类 Unix 操作系统，是一个基于 POSIX 和 UNIX 的多用户、多任务、支持多线程和多 CP…...

编程日记 2025/8/14 23:13:09

每天学一个 Linux 命令（22）：pwd

可访问网站查看，视觉品味拉满： http://www.616vip.cn/22/index.html pwd 命令用于打印当前工作目录（Print Working Directory）的绝对路径，帮助用户快速确认自己在文件系统中的位置。虽然简单，但它是终端操作中不可或缺的基础命令，尤其在处理相对路径或脚本编写时尤为…...

编程日记 2025/8/14 23:12:02

Windows 11设置开机自动运行 .jar 文件

Windows 11设置开机自动运行 .jar 文件打开启动文件夹： 按下 Win R，输入 shell:startup，回车。此路径为当前用户的启动文件夹： C:\Users\<用户名>\AppData\Roaming\Microsoft\Windows\Start Menu\Programs\Startup创…...

编程日记 2025/8/14 23:12:02

西门子博途软件崩溃

西门子博途软件编译/仿真崩溃是因为项目中OPC UA的接口问题解决拌饭见 https://support.industry.siemens.com/cs/document/109971630/tia-portal-%E5%9C%A8%E7%BC%96%E8%AF%91-plc-%E6%97%B6%E5%B4%A9%E6%BA%83?dti0&dlzh&lcen-WW...

编程日记 2025/8/1 17:07:28

12芯束装光纤不同包层线颜色之间的排列顺序

为什么光纤线必须按照以下颜色顺序进行排序？这其实是为了防止光污染的问题，不同颜色在传递光时从包层表皮漏光传感到梳妆的其它纤芯上，会有光污染的问题，而为了减少并防止光污染的现象，所以在光通信之中，需…...

编程日记 2025/8/14 4:30:57

数据驱动、精准协同：高端装备制造业三位一体生产管控体系构建

开篇引入鉴于集团全面推行生产运营体建设以及对二级单位生产过程管控力度逐步加强，某高端装备制造企业生产部长王总正在开展新的一年企业生产管控规划工作，为了能够更好地进行体系规划与建设应用，特邀请智能制造专家小智来进行讨论交流。王…...

编程日记 2025/8/7 15:56:27

HAL详解

一、直通式HAL 这里使用一个案例来介绍直通式HAL，选择MTK的NFC HIDL 1.0为例，因为比较简单，代码量也比较小，其源码路径：vendor/hardware/interfaces/nfc/1.0/ 1、NFC HAL的定义 1）NFC HAL数据类型通常定…...

编程日记 2025/8/14 2:55:46

RAG知识库中引入MCP

MCP（Memory, Context, Planning）是一种增强AI系统认知能力的框架。将MCP引入RAG知识库可以显著提升系统的性能和用户体验。下面我将详细介绍如何实现这一整合。 MCP框架概述 MCP框架包含三个核心组件： Memory（记忆）：存储和管理历史交互和知识Context（上下文）：理解当…...

编程日记 2025/8/14 1:25:33

再读bert（Bidirectional Encoder Representations from Transformers）

再读 BERT，仿佛在数字丛林中邂逅一位古老而智慧的先知。初次相见时，惊叹于它以 Transformer 架构为罗盘，在预训练与微调的星河中精准导航，打破 NLP 领域长久以来的迷雾。而如今，书页间跃动的不再仅是 Attention 机制精…...

编程日记 2025/8/14 23:09:07

C# 单例模式

创建一个类在类中定义方法 internal class Config {// 实现单利模式private static Config instance null;private Config() { }private static object Locker new object(); // 定义lock锁// 通过公有的方法返回实力public static Config GetInstance(){// 空的自己构造…...

编程日记 2025/8/14 7:01:51

mainwidget.cpp:1741:21: error: use of undeclared identifier ‘mainTab‘

这个错误表明在你的代码中，mainTab 这个变量没有被正确声明或定义。这通常是因为以下原因之一： 变量未声明：mainTab 可能没有在类的成员变量中声明。变量未初始化：mainTab 可能没有在构造函数中正确初始化。作用域问题&#x…...

编程日记 2025/8/13 23:20:24

OpenCV day6

函数内容接上文：OpenCV day4-CSDN博客 , OpenCV day5-CSDN博客目录平滑（模糊） 25.cv2.blur()： 26.cv2.boxFilter(): 27.cv2.GaussianBlur()： 28.cv2.medianBlur(): 29.cv2.bilateralFilter()： 锐…...

编程日记 2025/8/14 23:10:37

MySQL：Join连接的原理

连接查询的执行过程： 确定第一个需要查询的表【驱动表】选取代价最小的访问方法去执行单表查询语句从驱动表每获取到一条记录，都需要到t2表中查找匹配的记录两表连接查询需要查询一次t1表，两次t2表，在两表的连接查询中&…...

编程日记 2025/8/6 17:13:22

Linux MySQL版本升级（rpm安装方式）

一、背景近期生产环境扫描发现MySQL的多个安全漏洞。目前厂商已经发布了升级补丁以修复此安全问题，补丁获取链接：https://www.oracle.com/security-alerts/cpuoct2024.html 二、升级注意事项备份数据：升级前务必备份数据库。检查兼容性&…...

编程日记 2025/8/5 20:11:22

数字图像处理（膨胀与腐蚀）

腐蚀核心原理：结构元四肢运算结果全为1，则结构元中心为1，否则为0。怎么计算是否为1还是为0 结构元的值与前景的值进行与运算，如果结构元四肢的与运算结果全为1，则结构元中心为1，否则为0。假设下图为结构…...

编程日记 2025/8/14 23:08:06

J值即正义——Policy Gradient思想、REINFORCE算法，以及贪吃蛇小游戏（三）

文章目录前情提要谁的J值大呢？那么 ∇ θ J ( θ ) \nabla_\theta J(\theta) ∇θJ(θ)要怎么求呢？构建loss函数**代码实现示例**（PyTorch伪代码）：前情提要上回咱说道，对于强化学习而言，J值即正义。比如，你当了老板，你手下的两个高管，分别都为公司的发展提出了…...

编程日记 2025/8/14 21:28:52

pdfjs库使用3

.App { text-align: center; height: 100vh; display: flex; flex-direction: column; background-color: #f5f5f5; } /* PDF 查看器容器样式 */ .pdf-viewer { flex: 1; padding: 20px; max-width: 100%; margin: 0 auto; box-sizing: border-box; background-color: white;…...

编程日记 2025/8/11 5:18:49