数据结构C语言描述6(图文结合)--广义表讲解与实现
创作时间:
作者:
@小白创作中心
数据结构C语言描述6(图文结合)--广义表讲解与实现
引用
CSDN
1.
https://m.blog.csdn.net/weixin_74085818/article/details/144094347
前言
这个专栏将会用纯C实现常用的数据结构和简单的算法；有C基础即可跟着学习，代码均可运行；准备考研的也可跟着写，个人感觉，如果时间充裕，手写一遍比看书、刷题管用很多，这也是采用纯C语言实现的原因之一；欢迎收藏 + 关注，将会持续更新。
广义表是线性表的推广，也被称为列表（lists),广义表一般记作：
LS=（a1，a2，a3，…，an）
其中，LS是表的名称，n是表的长度。在线性表的定义中，ai (1<=i<=n）只能限于单个元素，但是在广义表中ai可以是 单个元素，也可以是广义表，分别称为广义表LS的 原子 和 子表 。 当广义表非空时，第一个元素（a1）被称为表头，其余元素（a2，a3，…，a n）被称为子表。
广义表常用表示
- **E=()：**E是一个空表，其长度为0。
- 广义表()和(())不同
- 前者是长度为0的空表
- 后者是长度为l的非空表(只不过该表中惟一的一个元素是空表)
- 广义表()和(())不同
- **L=(a，b) ：**L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表
- **A=(x，L)=(x，(a，b))：**A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。
- **B=(A，y)=((x，(a，b))，y)：**B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。
- **C=(A，B)=((x，(a，b))，((x，(a，b))，y))：**C的长度为2，两个元素都是子表。
- **D=(a，D)=(a，(a，(a，(…))))：**D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。
2️⃣ 两层广义表
3️⃣ 三层广义表
4️⃣ 四层广义表
广义表的深度
一个表的"深度"是指表展开后所含括号的层数。
- E=()：深度为1
- L=(a，b) ：深度为1
- A=(x，L)=(x，(a，b))：深度为2
- B=(A，y)=((x，(a，b))，y)：深度为3
- C=(A，B)=((x，(a，b))，((x，(a，b))，y))：深度为4
- D=(a，D)=(a，(a，(a，(…))))：深度为∞
广义表实现
封装广义表节点
typedef struct GeneralizedList {
bool flag; // true：表节点， false：原子节点
union {
DataType data; // 原节点，储存数据
struct GeneralizedList* glist; // 表节点，储存表
};
struct GeneralizedList* next;
}GList;
创建广义表
- 空表定义：
# - 递归思路：
- 返回值：void，参数：当前节点指针；
- 递归结束条件：顺序执行完即可；
- 单层递归逻辑：以
(x,(a,b))为例- 从左到右，遍历，如果是
#，说明是空表，直接赋值为null即可，如果是(，则需要创建表 然后递归指向表节点 ，如果是x，即是原子节点，则创建原子节点， 递归指向下一个节点 ； - 后面一种情况是，
,、）这两个，如果是,，则说明 递归去创建下一个节点 ，如果是)，则说明这一层表已经到头了，next指向NULL。
- 从左到右，遍历，如果是
/*
空表:#
例子：
(x,(a,b))
((x,(a,b)),y,(z,f))
*/
void create_glist(GList** list)
{
assert(list);
char key;
scanf_s("%c", &key, 1);
// 从做到有开始读，首先有三种情况，#，(， 数据
if (key == '#') {
*list = NULL;
}
else if (key == '(') {
*list = (GList*)calloc(1, sizeof(GList));
assert(*list);
(*list)->flag = true;
create_glist(&((*list)->glist));
}
else { // 读取数据
*list = (GList*)calloc(1, sizeof(GList));
assert(*list);
(*list)->flag = false;
(*list)->data = key; // 读取数据
}
// 其他情况：',' ')'
scanf_s("%c", &key, 1);
if (*list == NULL) { // 空表后面不进行任何操作，GList为NULL
return;
}
else if (key == ',') {
create_glist(&((*list)->next));
}
else if (key == ')' || key == '\n') { // '\n' 是因为出入数据中有换行，这个时候就是的一个广义表创建完成
(*list)->next = NULL;
}
}
递归遍历
- 存储结构：以节点形式存储，如下图：
- 递归思路：
- 返回值：
void，参数：节点指针 - 结束条件：从上到下顺序即可
- 单层递归逻辑：
- 如果是表节点，打印
(，看这个表节点 是否存储了节点 ，list->glist == NULL(没有，则打印#)，否则，就 递归遍历表节点指向的这个表 ，后打印) - 如果不是表节点，则是原子节点，则打印数据即可
- 打印
，打印完数据或者）后，如果下一个next指向不为NULL，则打印,
- 如果是表节点，打印
- 返回值：
- 递归思路：
// 遍历,脑子有广义表图形
void print_glist(GList* list)
{
if (list->flag == true) {
printf("(");
if (list->glist == NULL)
printf("#");
else
print_glist(list->glist);
// 递归完成，这个时候就是一个表打印完成
printf(")");
}
else {
printf("%c", list->data);
}
if (list->next != NULL) {
printf(",");
print_glist(list->next);
}
}
求深度
递归思路：
- 返回值：最大层数，参数：节点
- 递归结束条件：节点为空，或者这个节点为原子节点
- 单层递归逻辑：
// 场景：不为空、且是表节点，则递归
// 画图思路：先以一层为例返回
int depth_glist(GList* list)
{
int max_depth = 0;
if (list == NULL) {
return 0;
}
if (list->flag == false) {
return 0;
}
GList* t = list;
while (t) {
int res = depth_glist(list->glist);
max_depth = max_depth > res ? max_depth : res;
t = t->next;
}
return max_depth + 1;
}
删除节点
递归逻辑：
- 返回值：
void，参数：节点指针 - 结束条件：从上到下顺序即可
- 单层递归逻辑：
- 如果这个节点数据是要删除的数据，则按照链表删除方式即可，接着递归。
- 如果不是，则判断：如果是表节点，则递归表，如果是原子节点，则递归下一个节点。
// 要修改指针的指向
// 递归条件：不相等、为表节点
void erase(GList** list, char k)
{
if (*list == NULL) {
return;
}
if ((*list)->data == k) {
GList* t = *list;
*list = (*list)->next;
free(t);
t = NULL;
erase(list, k);
}
else {
if ((*list)->flag == true) {
erase(&(*list)->glist, k);
}
else {
erase(&(*list)->next, k);
}
}
}
总代码
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int DataType;
typedef struct GeneralizedList {
bool flag; // true：表节点， false：原子节点
union {
DataType data; // 原节点，储存数据
struct GeneralizedList* glist; // 表节点，储存表
};
struct GeneralizedList* next;
}GList;
/*
(x,(a,b))
空表:#
((x,(a,b)),y,(z,f))
*/
void create_glist(GList** list)
{
assert(list);
char key;
scanf_s("%c", &key, 1);
// 从做到有开始读，首先有三种情况，#，(， 数据
if (key == '#') {
*list = NULL;
}
else if (key == '(') {
*list = (GList*)calloc(1, sizeof(GList));
assert(*list);
(*list)->flag = true;
create_glist(&((*list)->glist));
}
else { // 读取数据
*list = (GList*)calloc(1, sizeof(GList));
assert(*list);
(*list)->flag = false;
(*list)->data = key; // 读取数据
}
// 其他情况：',' ')'
scanf_s("%c", &key, 1);
if (*list == NULL) { // 空表后面不进行任何操作，GList为NULL
return;
}
else if (key == ',') {
create_glist(&((*list)->next));
}
else if (key == ')' || key == '\n') { // '\n' 是因为出入数据中有换行，这个时候就是的一个广义表创建完成
(*list)->next = NULL;
}
}
// 遍历,脑子有广义表图形
void print_glist(GList* list)
{
if (list->flag == true) {
printf("(");
if (list->glist == NULL)
printf("#");
else
print_glist(list->glist);
// 递归完成，这个时候就是一个表打印完成
printf(")");
}
else {
printf("%c", list->data);
}
if (list->next != NULL) {
printf(",");
print_glist(list->next);
}
}
// 场景：不为空、且是表节点，则递归
// 画图思路：先以一层为例返回
int depth_glist(GList* list)
{
int max_depth = 0;
if (list == NULL) {
return 0;
}
if (list->flag == false) {
return 0;
}
GList* t = list;
while (t) {
int res = depth_glist(list->glist);
max_depth = max_depth > res ? max_depth : res;
t = t->next;
}
return max_depth + 1;
}
// 要修改指针的指向
// 递归条件：不相等、为表节点
void erase(GList** list, char k)
{
if (*list == NULL) {
return;
}
if ((*list)->data == k) {
GList* t = *list;
*list = (*list)->next;
free(t);
t = NULL;
erase(list, k);
}
else {
if ((*list)->flag == true) {
erase(&(*list)->glist, k);
}
else {
erase(&(*list)->next, k);
}
}
}
int main()
{
GList* list = NULL;
create_glist(&list);
print_glist(list);
putchar('\n');
printf("max_depth: %d\n", depth_glist(list));
erase(&list, 'b');
print_glist(list);
return 0;
}
热门推荐
鹤鸣九皋：充满吉祥寓意的鹤形文物
深度剖析鹿茸行业：2025-2031年市场机会与投资潜力
漳平水仙茶发酵工艺：乌龙茶中的独特方块茶饼
“层次分明”写作八法，让你成为文章高手
口腔CT检查费用及注意事项全解析
全解析蓝牙耳机选购策略：从音质、舒适度到续航能力全面指南
近10种沙坦降压药，降压谁更强？谁会独占鳌头？
清华大学研究：每周饮用含糖饮料超七次，男性脱发风险增加3倍
膳食纤维不只帮助排便，还能减少脂肪吸收！搭配油炸物一起吃促进代谢
如何打造团队经理人设
斤与克的换算关系及其在日常生活中的重要性解析
股市舆情监测有什么用？5个股市舆情实用分析方法
平安信用卡逾期协商方案有哪些？协商还款流程是什么？
酷爱演霸总的张翰，终于把自己变成了"霸总"
2025AMC8真题答案及考情分析：难度提升，分数线预测出炉
病案首页质控与医疗人工智能的结合：推动医疗质量的提升
孕妇每天喝豆浆好吗
如何有效应对市场中的反弹现象？这种现象对投资者的策略调整有哪些启示？
掉头发几根才算正常？不想英年早秃该怎么办？
十二星座职场路：性格双刃剑与突破之道
小角落，大生态，深文化｜梧桐书屋——城市缝隙间的自然文明星火
脑肽神经酸的作用与功效
如何通过小额投资，逐步积累财富？
5个降低物欲的方法 改变消费观做到极简省钱！
螺丝滑扣问题应如何有效解决？这种解决方法在实际应用中有何效果？
南水北调：跨流域壮举，工程特色铸就水利传奇
商业分析的最核心：行业洞察
灰指甲的四大判断标准及四种治疗方案
关于煤炭的10个有趣冷知识
住院二次报销在哪里办理