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

数据结构C语言描述5(图文结合)--广义表讲解与实现

article 2024/11/28 17:41:56

前言

  • 这个专栏将会用纯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;
}

http://www.kler.cn/a/413067.html

相关文章：

  • Git旧文件覆盖引发思考
  • 命令行版 postman 之 post 小工具
  • Python学习第十三天--面向对象，类和对象
  • 爬虫与反爬-Ja3指纹风控（Just a moment...）处理方案及参数说明
  • shell中的EOF，字符块
  • 使用UKEY进行数字签名和加密 -- HSM、PKCS#11与Signtool
  • 小程序基础：流程。
  • 计算机网络：运输层 —— TCP 的超时重传机制
  • LLM-pruner源码解析
  • VS2022的MFC的ReadString的问题
  • 熔断限流：业务实现自我保护
  • C++ ADL参数依赖查找
  • scala统计词频
  • 嵌入式工程师面试笔试总结——day2
  • TorchMoji使用教程/环境配置（2024）
  • 记录下在html文件中如何直接使用npm依赖，以threejs为例
  • sentry前端接入 报错403
  • 2022 年 3 月青少年软编等考 C 语言三级真题解析
  • YourPHPCMS Register_checkEmail存在sql注入漏洞
  • uniapp中的事件:v-on
  • Spring Boot 3 集成 Spring Security（3）数据管理
  • 同时多平台git配置：GitHub和Gitee生成不同的SSH Key
  • WPF——自定义ToolTip
  • Git远程仓库过大导致clone失败的解决方法
  • pytorch 和tensorflow loss.item()` 只能用于只有一个元素的张量. 防止显存爆炸
  • 什么是缓存击穿？如何避免之布隆过滤器