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

前言

  • 这个专栏将会用纯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为NULLreturn;}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("#");elseprint_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为NULLreturn;}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("#");elseprint_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.rhkb.cn/news/479771.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

鸿蒙学习使用本地真机运行应用/元服务 (开发篇)

文章目录 1、前提条件2、使用USB连接方式3、使用无线调试连接方式4、运行 1、前提条件 在Phone和Tablet中运行HarmonyOS应用/元服务的操作方法一致&#xff0c;可以采用USB连接方式或者无线调试的连接方式。两种连接方式是互斥的&#xff0c;只能使用一种&#xff0c;无法同时…

48-基于单片机的LCD12864时间调控和串口抱站

目录 一、主要功能 二、硬件资源 三、程序编程 四、实现现象 一、主要功能 基于51单片机的公交报站系统&#xff0c;可以手动报站&#xff0c;站名十个。 在lcd12864上显示时间&#xff08;年月日时分秒&#xff09;和站名&#xff0c;时间可以设置&#xff0c; 仿真中可以…

【汽车制动】汽车制动相关控制系统

目录 1.ABS (Anti-lock Brake System&#xff0c;防抱死制动系统) 2.EBD&#xff08;Electronic Brake-force Distribution&#xff0c;电子制动力分配系统&#xff09; 3.TCS&#xff08;Traction Control System&#xff0c;牵引力控制系统&#xff09; 4.VDC&#xff08…

DDR3与MIG IP核详解(一)

一、ddr3(全称第三代双倍速率同步动态随机存储器)&#xff1a; 1、特点&#xff1a;1&#xff1a;掉电无法保存数据&#xff0c;需要周期性的刷新。2:时钟上升沿和下降沿都会传输数据。 3&#xff1a;突发传输&#xff0c;突发长度 Burst Length一般为…

【算法 python A*算法的实现】

- 算法实现&#xff1a; import heapqclass Node:def __init__(self, position, g0, h0):self.position position # 节点的位置self.g g # 从起点到当前节点的成本self.h h # 从当前节点到终点的启发式估计成本self.f g h # 总成本self.parent None # 父节点def __…

苹果系统中利用活动监视器来终止进程

前言 苹果系统使用的时候总是感觉不太顺手。特别是转圈的彩虹球出现的时候&#xff0c;就非常令人恼火。如何找到一个像Windows那样任务管理器来终止掉进程呢&#xff1f; 解决办法 Commandspace 弹出搜索框吗&#xff0c;如下图&#xff1a; 输入“活动”进行搜索&#xff…

深度学习—损失函数及BP算法初步学习Day36

损失函数 1.MAE MAE&#xff08;Mean Absolute Error&#xff0c;平均绝对误差&#xff09;通常也被称为 L1-Loss&#xff0c;通过对预测值和真实值之间的绝对差取平均值来衡量他们之间的差异。。 MAE的公式如下&#xff1a; MAE 1 n ∑ i 1 n ∣ y i − y ^ i ∣ \text{…

[UUCTF 2022 新生赛]ez_rce

[UUCTF 2022 新生赛]ez_rce 我们来分析一下这个代码&#xff1a; 首先是isset看我们有没有传一个为空的值&#xff0c;如果为空就输出居然都不输入参数&#xff0c;可恶!!!!!!!!!不为空就GET传参赋值给$code &#xff0c;接着 如果 $code 中不包含这些模式中的任何一个&#x…

Flutter:启动屏逻辑处理02:启动页

启动屏启动之后&#xff0c;制作一个启动页面 新建splash&#xff1a;view 视图中只有一张图片sliding.png就是我们的启动图 import package:flutter/material.dart; import package:get/get.dart; import index.dart; class SplashPage extends GetView<SplashController…

系统思考—共同看见

在一家零售企业的项目中&#xff0c;团队频繁讨论客户流失的严重性&#xff0c;但每次讨论的结果都无法明确找出问题的根源。大家都知道客户流失了&#xff0c;但究竟是什么原因导致的&#xff0c;始终没有一致的答案。市场部认为是客户体验差&#xff0c;客服部门觉得是响应慢…

数据结构(Java版)第四期:ArrayLIst和顺序表(上)

目录 一、顺序表 1.1. 接口的实现 二、ArrayList简介 2.1. ArrayList的构造 2.2. ArrayList的常见操作 2.3. ArrayList的扩容机制 三、ArrayList的具体使用 3.1. 洗牌算法 3.2. 杨辉三角 一、顺序表 上一期我们讲到过&#xff0c;顺序表本质上和数组是差不多的&#…

Python编程语言中的优雅艺术:数值分隔符的巧妙运用

在Python编程的世界里&#xff0c;有许多精巧的设计让代码更优雅、更易读。今天要分享的是一个看似简单却能大幅提升代码可读性的特性 —— 数值分隔符。这个特性从Python 3.6版本开始引入&#xff0c;它用一种极其优雅的方式解决了大数值表示的难题。 数值分隔符的本质与应用…

心情追忆:构建支付模块的五个基本接口设计

之前&#xff0c;我独自一人开发了一个名为“心情追忆”的小程序&#xff0c;旨在帮助用户记录日常的心情变化及重要时刻。我从项目的构思、设计、前端&#xff08;小程序&#xff09;开发、后端搭建到最终部署。经过一个月的努力&#xff0c;通过群聊分享等方式&#xff0c;用…

实验三 z变换及离散时间LTI系统的z域分析

实验原理 有理函数z 变换的部分分式展开 【实例2-1】试用Matlab 命令对函数 X ( z ) 18 18 3 − 1 − 4 z − 2 − z − 3 X\left(z\right)\frac{18}{183^{-1} -4z^{-2} -z^{-3} } X(z)183−1−4z−2−z−318​ 进行部分分式展开&#xff0c;并求出其z 反变换。 B[18]; A…

Web登录页面设计

记录第一个前端界面&#xff0c;暑假期间写的&#xff0c;用了Lottie动画和canvas标签做动画&#xff0c;登录和注册也连接了数据库。 图片是从网上找的&#xff0c;如有侵权私信我删除&#xff0c;谢谢啦~

【es6】原生js在页面上画矩形及删除的实现方法

画一个矩形&#xff0c;可以选中高亮&#xff0c;删除自己效果的实现&#xff0c;后期会丰富下细节&#xff0c;拖动及拖动调整矩形大小 实现效果 代码实现 class Draw {constructor() {this.x 0this.y 0this.disX 0this.disY 0this.startX 0this.startY 0this.mouseDo…

高级 K8s 面试题(Advanced K8S Interview Questions)

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:Linux运维老纪的首页…

HiISP(一)

系列文章目录 文章目录 系列文章目录前言一、Hi3518EV200 芯片架构1.1. ARM子系统1.2. 图像子系统&#xff08;Image Subsystem&#xff09;1.3. 视频子系统&#xff08;Video Subsystem&#xff09;1.4. 存储与接口模块1.5. 通用功能模块1.6. DDR与总线1.7. 数据流1.7.1. 数据…

京东物流与亿纬锂能达成战略合作,双方跨界意义何在?

首先&#xff0c;这一合作有助于双方实现资源共享和优势互补。京东物流作为国内领先的物流服务商&#xff0c;拥有先进的物流技术和丰富的运营经验&#xff0c;能够为亿纬锂能提供高效、安全、可靠的物流服务。而亿纬锂能作为新能源领域的佼佼者&#xff0c;拥有先进的电池技术…

103.【C语言】数据结构之二叉树的三种递归遍历方式

目录 1.知识回顾 2.分析二叉树的三种遍历方式 1.总览 2.前序遍历 3.中序遍历 4.后序遍历 5.层序遍历 3.代码实现 1.准备工作 2.前序遍历函数PreOrder 测试结果 3.中序遍历函数InOrder 测试结果 4.后序遍历函数PostOrder 测试结果 4.底层分析 1.知识回顾 在99.…