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