94.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删

目录

1.双向链表

2.结构体的定义

3.示意图

3.代码示例

1.双向链表的尾插

示意图

代码

main.c

List.h

List.c

详细分析代码的执行过程

双向链表的初始化

2.双向链表的打印

代码

3.双向链表的尾删


1.双向链表

以一种典型的双向链表为例:带头双向循环链表(带头:哨兵位的节点)

2.结构体的定义

typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;

3.示意图

head为带哨兵位的头节点,无有效数值,只储存第一个有效节点的地址,负责找到第一个节点

特点:

1.prev指向前一个节点,next指向下一个节点

2.末尾的next指向哨兵位的头

3.哨兵位的头的prev指向末尾(不用像单向链表那样循环找尾节点)

3.代码示例

List.h

#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
typedef int LTDataType;
 
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;

void LTInit();
void LTDestory();
void LTPushBack(LTNode* phead,LTDataType x);
void LTPopBack(LTNode* phead);

用结构体定义节点,节点有三部分构成:next指针,prev指针和数据,符合双向节点的定义

 

注:prev为previous的缩写

1.双向链表的尾插

示意图

非空链表

空链表

和之前的无头的单向链表有所不同,这里的带哨兵位的头节点

未尾插之前,head->prev指向head->next,head->next指向head->prev(这样可以实现双向循环)

千万不要被箭头的指向所误导!!!!

不是head->prev=head->next;head->next=head->prev;

箭头指向的是head节点
head->prev=head;head->next=head;

尾插之后

实现过程和非空链表一样

*无论对于空链表还是非空链表,尾插都只需要4步,即修改四个指针*

tail指向尾节点

代码

main.c
#include "List.h"
void TestList()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
}

int main()
{
	TestList();
	return 0;
}
List.h
#include <assert.h>
typedef int LTDataType;
 
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;

LTNode* LTInit();
LTNode* BuyListNode(LTDataType x);
void LTPushBack(LTNode* phead, LTDataType x);
List.c
#include "List.h"
LTNode* LTInit()
{
	LTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc");
		return NULL;
	}
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

详细分析代码的执行过程

进入main函数-->调用TestList函数-->调用LTInit函数-->调用BuyListNode函数

在BuyListNode函数中,先为新的节点开辟空间,之后node指向新节点,如果node为NULL,则开辟失败返回NULL,如果开辟成功继续向下执行①prev和next置NULL ②写入节点的data值

返回node指针,BuyListNode函数结束

双向链表的初始化

在LTInit函数中,phead得到node的值

已知phead存储的值为00 c0 a0 98,求phead->next = phead;和phead->prev = phead;执行完后按小端序计算0x00c0a098~0x00c0a09f处的数据

解:

按照结构体成员变量定义的先后顺序

phead->prev存储在0x00C0A098~0x00C0A09B处,phead->next存储在0x00C0A09C~0x00C0A09F处

因此答案为98 a0 c0 00 98 a0 c0 00

返回phead后,LTInit函数结束

在TestList函数中,plist得到phead的值

调用LTPushBack函数

在LTPushBack函数中,phead得到plist的值(这里没有传二级指针,修改结构体成员变量的值只需要一级指针),断言phead,确保phead不为NULL

调用BuyListNode,返回新节点的地址给newnode

只有带哨兵位的头结点时,LTNode* tail = phead->prev;等价为LTNode* tail = phead;

LTPushBack函数结束

剩下的分析思想一样,略去

2.双向链表的打印

让cur指针指向head节点的下一个节点,循环打印,当cur直到head时,停止打印

代码

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("head<=>");
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

3.双向链表的尾删

尾删要单独判断是否只有带哨兵位的头节点

写一个LTEmpty函数

bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

直接将phead->next == phead结果的真假返回,比if判断要简洁

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));//注意感叹号
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;//定义指向tail的前一个节点的指针
	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
	tail = NULL;
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/912478.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

「QT」几何数据类 之 QPoint 整型点类

✨博客主页何曾参静谧的博客&#x1f4cc;文章专栏「QT」QT5程序设计&#x1f4da;全部专栏「VS」Visual Studio「C/C」C/C程序设计「UG/NX」BlockUI集合「Win」Windows程序设计「DSA」数据结构与算法「UG/NX」NX二次开发「QT」QT5程序设计「File」数据文件格式「PK」Parasolid…

黑马点评1 session实现短信验证码登录

1 什么是session cookie的session的应用场景&#xff1a;cookie可以用来保存用户的登陆信息&#xff0c;如果删除cookie则下一次用户仍需要重新登录 session就类似于我们拿到钥匙去开锁&#xff0c;拿到的就是我们个人的信息&#xff0c;一般我们可以在session中存放个人的信息…

[Docker#3] LXC | 详解安装docker | docker的架构与生态

目录 1.LXC容器操作 安装LXC LXC容器操作步骤 2.理论 LXC 是什么&#xff1f; Docker 是什么 Docker 和虚拟机的区别 Docker 和 JVM 虚拟化的区别 Docker 版本 ⭕Docker 官方网站&#xff08;建议收藏&#xff09; Docker 架构 生活案例 Docker 生态 Docker 解决…

MySQL数据库专栏(五)连接MySQL数据库C API篇

摘要 本篇文章主要介绍通过C语言API接口链接MySQL数据库&#xff0c;各接口功能及使用方式&#xff0c;辅助类的封装及调用实例&#xff0c;可以直接移植到项目里面使用。 目录 1、环境配置 1.1、添加头文件 1.2、添加库目录 2、接口介绍 2.1、MySql初始化及数据清理 2.1.…

从0开始深度学习(27)——卷积神经网络(LeNet)

1 LeNet神经网络 LeNet是最早的卷积神经网络之一&#xff0c;由Yann LeCun等人在1990年代提出&#xff0c;并以其名字命名。最初&#xff0c;LeNet被设计用于手写数字识别&#xff0c;最著名的应用是在美国的邮政系统中识别手写邮政编码。LeNet架构的成功证明了卷积神经网络在…

如何用C#和Aspose.PDF实现PDF转Word工具

在本篇博文中&#xff0c;我将详细讲解如何用C#实现一个PDF转Word工具。这款工具基于Aspose.PDF库&#xff0c;实现PDF文件转为Word&#xff08;DOC/DOCX&#xff09;格式的功能&#xff0c;并通过用户友好的界面和状态提示提升用户体验。希望通过这篇文章帮助大家理解软件的实…

运维技术之文件系统(File System for 0peration and Maintenance Technology)

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 本人主要分享计算机核心技…

IoTDB 与 HBase 对比详解:架构、功能与性能

五大方向&#xff0c;洞悉 IoTDB 与 HBase 的详尽对比&#xff01; 在物联网&#xff08;IoT&#xff09;领域&#xff0c;数据的采集、存储和分析是确保系统高效运行和决策准确的重要环节。随着物联网设备数量的增加和数据量的爆炸式增长&#xff0c;开发者和决策者们需要选择…

【Vue】Vue2和Vue3响应式原理

前言 Vue 3 的核心部分可以分为三个主要模块&#xff1a;Compiler、Reactivity 和 Runtime。响应式的处理逻辑在 Reactivity 部分。 Compiler&#xff08;编译器&#xff09;&#xff1a;Template > 渲染函数 将 Vue 的模板&#xff08;Template&#xff09;转换成 JavaS…

哪些人群适合考取 PostgreSQL 数据库 PGCM 证书?

#postgresql#&#xff0c;作为开源数据库领域的佼佼者&#xff0c;凭借其强大的功能和广泛的应用场景&#xff0c;吸引了大量数据库从业者的关注。它代表着持有者在PostgreSQL数据库管理、优化、安全和高可用性设计等方面的专家级技能。 PGCM证书适合那些具备扎实理论基础和一…

C++高级编程(9)

九、STL模板库 1.C函数模板 函数模板是一个独立于类型的函数&#xff0c;可产生函数特定类型的版本。通过对参数类型进行参数化&#xff0c;获取有相同形式的函数体。 它是一个通用函数&#xff0c;它可适应一定范围内的不同类型对象的操作。 函数模板将代表着不同类型的一组…

深圳世界之窗:文化与娱乐交织的旅游胜地

深圳世界之窗位于广东省深圳市南山区华侨城&#xff0c;是中国著名的缩微景区。它以弘扬世界文化为宗旨&#xff0c;将世界奇观、历史遗迹、民间歌舞表演、高科技游乐项目等融为一体&#xff0c;为游客打造出一个不出国门就能领略世界风情的旅游胜地。 从文化角度来看&#xff…

贪心day04(买卖股票的最佳时机)

1.买卖股票的最佳时机 题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a;我们其实只需遍历一篇就可以解决这个问题。首先我们定义一个min为无穷大值&#xff0c;再遍历只要有数字比min跟小我们就更改min的值就好&#xff0c;此时我们只需要找出…

ClickHouse创建账号和连接测试

在之前搭建ClickHouse的时候&#xff0c;把账户相关的去掉了&#xff0c;所以登录和连接的时候是不需要账号密码的&#xff0c;但是实际项目中&#xff0c;肯定是需要根据需要创建账号。 一&#xff0c;创建账号 1&#xff0c;进入到 /etc/clickhouse-server&#xff0c; 编辑…

网页版五子棋——匹配模块(客户端开发)

前一篇文章&#xff1a;网页版五子棋——用户模块&#xff08;客户端开发&#xff09;-CSDN博客 目录 前言 一、前后端交互接口设计 二、游戏大厅页面 1.页面代码编写 2.前后端交互代码编写 3.测试获取用户信息功能 结尾 前言 前面文章介绍完了五子棋项目用户模块的代码…

10. java基础知识(下)

文章目录 一、一带而过二、字符串类型String1. 简单了解2. 关于结束符\03. 自动类型转换与强制类型转换 三、API文档与import导包1. API文档2. import导包 四、java中的数组1. 创建2. 遍历3. 补充4. Arrays类① 简单介绍② 练习 五、方法的重载六、规范约束七、内容出处 一、一…

Sam Altman:年底将有重磅更新,但不是GPT-5!

大家好&#xff0c;我是木易&#xff0c;一个持续关注AI领域的互联网技术产品经理&#xff0c;国内Top2本科&#xff0c;美国Top10 CS研究生&#xff0c;MBA。我坚信AI是普通人变强的“外挂”&#xff0c;专注于分享AI全维度知识&#xff0c;包括但不限于AI科普&#xff0c;AI工…

《Python编程实训快速上手》第四天--字符串操作

一、处理字符串 1、单引号和双引号 Python中单双引号均可以表示字符串&#xff0c;区别在于&#xff1a; 1、双引号中可以使用到单引号 2、单引号字符串中如果要使用单引号&#xff0c;要使用到转义字符 \ \ \t \n \\ 原始字符串 在开始的引号前加r&#xf…

原生html+js输入框下拉多选带关闭模块完整案例

<!DOCTYPE html> <html> <head> <title>多选下拉框</title> <style> * { box-sizing: border-box; margin: 0; padding: 0; } .multi-select-container { position: relative; width: 300px; margin: 20px; font-family: Arial, sans-seri…

在 Ubuntu 操作系统上:改变 App 任务栏菜单的背景色

Ubuntu 官方默认的终端&#xff0c;与操作系统的主题 theme 无关。