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

嵌入式入门Day22

article 2024/12/5 3:24:01

数据结构Day3

  • 双向链表
    • 创建双向链表
    • 双向链表判空
    • 申请节点封装数据
    • 双向链表头插
    • 双向链表遍历
    • 按位置查找返回节点地址
    • 指定位置插入
    • 头删
    • 指定位置删除
    • 按位置修改数据
    • 销毁双向链表
  • 循环链表
    • 循环链表的操作（以单链表为例）
      • 单向循环链表的节点结构体
      • 循环链表的创建
      • 循环链表判空
      • 循环链表尾插
      • 带头节点的循环链表遍历
      • 循环链表的尾删
      • 循环链表删除头节点
      • 使用头指针的循环链表遍历
      • 删除循环链表
  • 作业

在这里插入图片描述

双向链表

由于单向链表只能从某个节点开始单向访问其后继节点，并没有储存其前驱节点信息。访问前面的节点是不容易办到的
为了能够凑某个节点开始，既可以访问前驱节点又可以访问后继节点，在结构中多家一个指向前驱节点的指针

typedef struct Node
{
	union
	{
		datatype data;
		int len;
	}
	struct Node *prio;
	struct NOde *next;
}Node, *Node_ptr;

创建双向链表

Node_ptr list_create()
{
	//堆区申请空间
	Node_ptr L = (Node_ptr)malloc(sizeof(Node));
	if (NULL == L)
	{
		printf("链表创建失败\n");
		return NULL;
	}
	//初始化
	L->len = 0;
	L->prio = NULL;
	L->next = NULL;

	printf("链表创建成功\n");

	return L;
}

双向链表判空

//判空 1表示空 0表示非空
int list_empty(Node_ptr L)
{
	//判断合法性
	if (NULL == L)
	{
		return 1;	
	}
	//判断是否为空
	return L->next == NULL;
}

申请节点封装数据

//申请节点封装数据
static Node_ptr list_node_apply(datatype e)
{
	//堆区申请空间
	Node_ptr p = (Node_ptr)malloc(sizeof(Node));
	if (NULL == p)
	{
		return NULL;
	}
	
	//数据封装
	p->data = e;
	p->next = NULL;
	p->prio = NULL;

	return p;
}

双向链表头插

//头插
int list_insert_head(Node_ptr L, datatype e)
{
	//判断链表合法性
	if (NULL == L)
	{
		printf("链表不合法\n");
		return -1;
	}
	//申请节点封装数据
	Node_ptr p = list_node_apply(e);
	if (NULL == p)
	{
		return -1;
	}

	//判断链表是否为空
	if (list_empty(L))
	{
		//空双向链表头插
		L->next = p;
		p->prio = L;
	}else
	{
		//非空双向链表头插
		p->prio = L;
		p->next = L->next;
		L->next->prio = p;
		L->next = p;
	}
	L->len++;
	return 0;
}

双向链表遍历

//显示
void list_show(Node_ptr L)
{
	if (NULL == L || list_empty(L))
	{
		return ;
	}
	printf("链表中的元素为：");
	Node_ptr p = L->next;
	while (p)
	{
		printf("%c\t",p->data);
		p = p->next;
	}
	putchar(10);
	return;
}

按位置查找返回节点地址

//按位置寻找节点
Node_ptr list_search_pos(Node_ptr L, int pos)
{
	if (NULL == L || list_empty(L) || pos < 0 || pos > L->len)
	{
		return NULL;
	}

	Node_ptr q = L;
	for (int i = 0; i < pos; i++)
	{
		q = q->next;
	}
	return q;
}

指定位置插入

  1. 插入时，可以找到其前驱节点后插入，也可以找到要插入的位置直接插入
  2. 尾插是需要注意，不要访问到NULL
//按位置插入
int list_insert_pos(Node_ptr L, int pos, datatype e)
{
	//检查链表和插入位置
	if (NULL == L || pos < 1 || pos > L->len+1)
	{
		return -1;
	}
	//定位到插入位置的前一个节点
	Node_ptr q = list_search_pos(L, pos-1);
	//申请节点封装数据
	Node_ptr p = list_node_apply(e);
	if (NULL == p)
	{
		return -1;
	}
	//判断是中间插入还是尾插
	if (q->next == NULL)
	{
		p->prio = q;
		q->next = p;
	}else
	{
		p->prio = q;
		p->next = q->next;
		q->next->prio = p;
		q->next = p;
	}
	//表长变化
	L->len++;
	return 0;
}

头删

  1. 注意删除的节点是否为最后一个节点，还是不要访问到关于NULL的空间
//头删
int list_delete_head(Node_ptr L)
{
	//判断链表合法性
	if (NULL == L || list_empty(L))
	{
		return -1;
	}
	//标记将要删除的节点
	Node_ptr p = L->next;

	//将头指针的后继修改为标记节点的后继
	L->next = p->next;

	//如果该节点后继不为空
	if (NULL !=  p->next)
	{
		//将他的前驱修改为头结点
		p->next->prio = L;
	}
	//释放内存空间
	free(p);
	//释放指针
	p = NULL;
	//表长变化
	L->len--;
	return 0;
}

指定位置删除

  1. 可以找到制定位置的前驱进行删除，也可以直接定位到该位置进行删除
  2. 注意删除的是否为最后一个节点，如果时依旧不能访问到NULL
//按位置删除
int list_delete_pos(Node_ptr L, int pos)
{
	//判断链表和位置的合法性
	if (NULL == L || pos < 1 || pos > L->len)
	{
		return -1;
	}
	//标记指针
	Node_ptr p = list_search_pos(L,pos);
	//将该节点前驱的后继指向该节点的后继
	p->prio->next = p->next;
	//如果该节点后继不为空
	if (NULL != p->next)
	{
		//将该节点后继的前驱指向该节点的前驱
		p->next->prio = p->prio;
	}
	//释放空间
	free(p);
	//释放指针  
	p = NULL;
	//表长变化
	L->len--;
	return 0;

}

按位置修改数据

//按位置更新
int list_update_pos(Node_ptr L, int pos, datatype e)
{
	//合法性判断
	if (NULL == L || list_empty(L) || pos < 1 || pos > L->len)
	{
		return -1;
	}
	//定位到待修改节点
	Node_ptr p = list_search_pos(L,pos);
	//更改数据域
	p->data = e;
	return 0;
}

销毁双向链表

//销毁双向链表
void list_destroy(Node_ptr *L)
{
	if (NULL == *L)
	{
		return;
	}
	while (!list_empty(*L))
	{
		list_delete_head(*L);
	}
	free(*L);
	*L = NULL;
}

循环链表

  1. 循环链表：首尾相接的链表称为循环链表
    特点：在循环链表中，没有一个节点的指针域为空
  2. 分类：
    • 单向循环链表：将单链表的最后一个节点的指针域指向第一个节点的地址
    • 双向循环链表：将头结点的前驱指向最后一个节点，最后一个节点的后继指向第一个节点

循环链表的操作（以单链表为例）

单向循环链表的节点结构体

typedef char datatype;

typedef struct Node
{
	union 
	{
		int len;   			//头节点数据域
		datatype data; 		//普通节点数据域
	};

	struct Node *next; 		//指针域
}Node, *Node_ptr;

循环链表的创建

//创建循环链表
Node_ptr list_create()
{
	//申请头节点空间
	Node_ptr p = (Node_ptr)malloc(sizeof(Node));
	if (NULL == p)
	{
		return NULL;
	}
	//头节点初始化
	p->len = 0;
	p->next = p;
	printf("创建成功\n");
	return p;
}

循环链表判空

int list_empty(Node_ptr L)
{
	//指向头节点指向自己表示循环链表为空
	if (L == L->next || NULL == L)
	{
		return 1;
	}else
	{
		return 0;
	}
}

循环链表尾插

//尾插
int list_insert_tail(Node_ptr L, datatype e)
{
	//判断链表合法性
	if (NULL == L)
	{
		return -1;
	}
	//定位到链表的最后一个节点
	Node_ptr q = L;
	while (q->next != L)
	{
		q = q->next;
	}
	//申请空间封装数据
	Node_ptr p = (Node_ptr)malloc(sizeof(Node));
	if (NULL == p)
	{
		return -1;
	}
	//尾插逻辑
	p->data = e;
	p->next = NULL;
	p->next = q->next;
	q->next = p;
	
	return 0;
}

带头节点的循环链表遍历

//遍历
void list_show(Node_ptr L)
{
	//判断链表是否满足遍历条件
	if (NULL == L || list_empty(L))
	{
		return ;
	}
	printf("链表中的元素分别为：");
	//从链表的第一个节点开始
	Node_ptr q = L->next;
	while (q != L)
	{
		//输出每一个节点的数据域
		printf("%c\t",q->data);
		q = q->next;
	}
	putchar(10);

}

循环链表的尾删

//尾删
int list_delete_tail(Node_ptr L)
{
	//判断链表是否符合尾删条件
	if (NULL == L || list_empty(L))
	{
		return -1;
	}
	//定位到倒数第二个节点
	Node_ptr q = L;
	while (q->next->next != L)
	{
		q = q->next;
	}
	//释放最后一个节点的内存空间
	free(q->next);
	//当前节点的后继修改为头节点
	q->next = L;
	//长度变化
	L->len--;

}

循环链表删除头节点

//删除头结点
Node_ptr list_head_delete(Node_ptr L)
{	
	//判断链表合法性
	if (NULL == L)
	{
		return NULL;
	}
	//链表判空
	if (list_empty(L))
	{
		//为空，直接释放L头节点，并返回NULL
		free(L);
		return NULL;
	}
	//不为空，将最后一个节点后继修改为第一个节点（以前是头节点）
	Node_ptr q = L->next;
	while (q->next != L)
	{
		q = q->next;
	}
	q->next = L->next;
	//释放头节点
	free(L);
	L = NULL;
	//返回一个头指针，用于使用链表
	return q->next;
}

使用头指针的循环链表遍历

//去头后遍历链表
void list_dseplay(Node_ptr H)
{
	if (NULL == H)
	{
		return ;
	}
	printf("链表中的元素分别为：");
	//使用头指针时，H就已经是第一个元素了
	Node_ptr q = H;
	//先输出H元素的数据,后移直到重新回到H节点 
	do
	{
		printf("%c\t",q->data);
		q = q->next;
	} while (q != H);
	putchar(10);
}

删除循环链表

//销毁
void list_destroy(Node_ptr H)
{	
	//判断
	if (NULL == H)
	{
	 	return;
	}
	while (H->next != H)
	{
		Node_ptr p = H->next;
		H->next = p->next;
		free(p);
		p = NULL;
	}

	free(H);
	H = NULL;
	return;
}

作业

约瑟夫问题

#include "looplinklist.h"
int main(int argc, const char *argv[])
{
	//创建一个循环链表
	Node_ptr L = list_create();
	//控制循环变量
	int n;
	//用户提示
	printf("请输入参与游戏的人数:");
	//输入 
	scanf("%d", &n);
	//循环尾插
	for (int i = 0; i < n; i++)
	{
		list_insert_tail(L,i+1);
	}
	//展示链表中的数据
	list_show(L);
	//删除头节点
	L = list_head_delete(L);	

	//定义遍历指针
	Node_ptr p = L;

	//定义计数标志
	int count = 0;

	printf("出列顺序为：");
	//循环到只有最后一个节点
	while (p->next != p)
	{
		//计数增加
		count++;
		//每计数到二进行头删操作，删除第三个节点
		if (count == 2)
		{
			printf("%d\t",p->next->data);
			Node_ptr q = p->next;
			p->next = q->next;
			free(q);
			q = NULL;
			count = 0;
		}
		//遍历指针后移
		p = p->next;		
	}
	//输出最后一个节点
	printf("%d\n",p->data);
	//销毁循环链表
	list_destroy(L);
	//释放指针
	L = NULL;
	//展示链表
	list_show(L);
	return 0;
}

运行结果如下
在这里插入图片描述


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

相关文章：

  • C_字符串的一些函数
  • 第四十四篇 EfficientNetV1、V2模型详解
  • mybatis-plus 对于属性为null字段不更新
  • 性能监控系统Prometheus、Node-exporter与Grafana部署详解搭建
  • 飞凌嵌入式受邀亮相OpenHarmony人才生态大会2024
  • for循环和while循环区别、特点、优势
  • 学习JavaEE的日子 Day36 字符流
  • 三菱汽车决定退出中国市场，发展重心转移至东南亚
  • 优先算法 —— 双指针系列 - 三数之和
  • 机器学习：机器学习项目的完整周期
  • VS Code配置Lua调试环境
  • 【Verilog】实验三 数码管实验
  • 使用 Pytorch 构建 Vanilla GAN
  • Jenkins环境搭建及简单介绍
  • 十、软件设计架构-微服务-服务调用Dubbo
  • Ubuntu24.04初始化教程(包含基础优化、ros2)
  • 高效处理 iOS 应用中的大规模礼物数据：以直播项目为例（1-礼物池）
  • Ajax：回忆与节点
  • 使用R语言优雅的获取任意区域的POI，道路，河流等数据
  • StarRocks存算分离在得物的降本增效实践
  • 基于Pyside6开发一个通用的在线升级工具
  • Liunx系统编程——shell的简单实现
  • HO-VMD-TCN西储大学轴承故障诊断
  • 分治的思想（力扣965、力扣144、牛客KY11）
  • SQL进阶技巧：非等值连接--单向近距离匹配
  • python 的while break continue 嵌套循环