C语言简单的数据结构：双向链表的实现

目录：

  • 1.双向链表的结构和初始化
    • 1.1双向链表的结构
    • 1.2双向链表的初始化
  • 2.双向链表的相关操作
    • 2.1双向链表的尾插、打印和头插
      • 2.11双向链表的尾插
      • 2.12双向链表的打印
      • 2.13双向链表的头插
    • 2.2双向链表的尾删和头删
      • 2.21双向链表的尾删
      • 2.22双向链表的头删
    • 2.3双向链表查找和任意位置插入、删除
      • 2.31双向链表查找
      • 2.32双向链表任意位置之后插入
      • 2.33双向链表任意位置删除
    • 2.4双向链表的销毁
  • 本文代码：

1.双向链表的结构和初始化

1.1双向链表的结构

之前我们的单向链表指的是：不带头单向不循环链表
而双向链表指的是：带头双向循环链表
在这里插入图片描述
其中头节点为哨兵位（不存储任何数据），尾部要指向哨兵位
它的节点有：数据，指向下一个节点的指针和指向下一个节点的指针
在这里插入图片描述
这就是双向链表的节点定义，写入VS：
在这里插入图片描述

1.2双向链表的初始化

当双向链表为NULL时，还有一个头节点，说一初始化时就是创建一个哨兵位
在这里插入图片描述

首先是申请链表：
在这里插入图片描述
在这里插入图片描述
接着是哨兵位的创建（放入一个无效数据就行）
在这里插入图片描述
测试：
在这里插入图片描述
在这里插入图片描述

2.双向链表的相关操作

2.1双向链表的尾插、打印和头插

2.11双向链表的尾插

这里的传参是什么呢？
在这里插入图片描述
58c66ffd3020b137a.png)
47be39ed4525a16999a787187d86.png)
对于这个问题其实很简单，对于完成操作来说这两种都可以，但是我们使用第一种是没办法改变哨兵位的，但是我们第二种有机会改变哨兵位的，如果让我们代码更安全一点，就使用第一个

在这里插入图片描述
在这里插入图片描述
这里的d3就是phead指向的prev指针
在这里插入图片描述
我们优先修改newnode指向，然后在修改phead的指向
我们再来判断NULL链表的情况：
当插入NULL指针时，并不会对NULL指针进行解引用，这个代码就没问题
在这里插入图片描述
这两行代码不能直接进行交换，因为会找不到d3这个数据，从而改变不了

2.12双向链表的打印

在这里插入图片描述
在这里插入图片描述
这里要用到哨兵为来确定是否循环一遍
测试：
在这里插入图片描述

2.13双向链表的头插

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
顺序为3 1 4 2
测试：
在这里插入图片描述

2.2双向链表的尾删和头删

在这里插入图片描述

2.21双向链表的尾删

首先要判断链表必须有效并且链表不能为NULL
在这里插入图片描述
在这里插入图片描述
我们只对2 3进行改变就行了
在这里插入图片描述
测试：
在这里插入图片描述

2.22双向链表的头删

在这里插入图片描述
在这里插入图片描述
测试：
在这里插入图片描述

2.3双向链表查找和任意位置插入、删除

2.31双向链表查找

在这里插入图片描述

进行遍历，然后进行判断
测试：
在这里插入图片描述

2.32双向链表任意位置之后插入

在这里插入图片描述
还是对newnode进行改变然后在该pos指针
测试：
在这里插入图片描述

2.33双向链表任意位置删除

删除位置理论上不能为phead，但是没有phead参数，无法增加校验
在这里插入图片描述
也是先将pos后的指针先修改好，然后在修改pos前的指针
测试：
在这里插入图片描述
这里虽然对实参进行改变了，但这里为什么不传二级指针呢
这里是为了保持接口一致性，方便我们的记忆，我们可以通过外部值NULL来解决
在这里插入图片描述
这里我们之前的初始化代码也可以进行优化
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
一个以参数的方式初始化，一个以返回值的方法初始化

2.4双向链表的销毁

销毁后要向下走，所以我们要将指针存一下
在这里插入图片描述
这里也是一级指针，所以无法改变头节点
在这里插入图片描述
手动置为NULL即可

本文代码：

List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

LTNode* LTBuyNode(LTDataType x);//申请空间
//void LTInit(LTNode** pphead);//初始化
LTNode* LTInit();

void LTPrint(LTNode* phead);
//插入数据
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);

void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

LTNode* LTFind(LTNode* phead, LTDataType x);
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);

void LTDestroy(LTNode* phead);

List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

LTNode* LTBuyNode(LTDataType x)
{
	//申请节点
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(1);
	}
	node->data = x;
	node->next = node->prev = node;
	return node;
}

//void LTInit(LTNode** pphead)
//{
//	*pphead = LTBuyNode(-1);
//}

LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}


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

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead phead->prev newnode
	newnode->prev = phead->prev;
	newnode->next = phead;

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

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);

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

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

void LTPopBack(LTNode* phead)
{
	//链表必须有效并且链表不能为NULL
	assert(phead && phead->next != phead);

	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
	
	LTNode* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	free(del);
	del = NULL;
}

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;

	pos->next->prev = newnode;
	pos->next = newnode;
}

void LTErase(LTNode* pos)
{
	assert(pos);
	//pos理论上不能为phead，但是没有phead参数，无法增加校验

	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

void ListTest01()
{
	//LTNode* plist = NULL;
	//LTInit(&plist);
	LTNode* plist = LTInit();

	//LTPushBack(plist, 1);
	//LTPrint(plist);
	//LTPushBack(plist, 2);
	//LTPrint(plist);
	//LTPushBack(plist, 3);
	//LTPrint(plist);
	//LTPushBack(plist, 4);
	//LTPrint(plist);
	LTPushFront(plist, 4);
	LTPrint(plist);
	LTPushFront(plist, 3);
	LTPrint(plist);
	LTPushFront(plist, 2);
	LTPrint(plist);
	LTPushFront(plist, 1);
	LTPrint(plist);
	LTDestroy(plist);
	plist = NULL;
}

void ListTest02()
{
	//LTNode* plist = NULL;
	//LTInit(&plist);
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTDestroy(plist);
	plist = NULL;
}

void ListTest03()
{
	//LTNode* plist = NULL;
	//LTInit(&plist);
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	LTNode* find1 = LTFind(plist, 3);
	if (find1 == NULL)
	{
		printf("找不到\n");
	}
	else
	{
		printf("找到了\n");
	}
	LTNode* find2 = LTFind(plist, 5);
	if (find2 == NULL)
	{
		printf("找不到\n");
	}
	else
	{
		printf("找到了\n");
	}
	LTDestroy(plist);
	plist = NULL;
}

void ListTest04()
{
	//LTNode* plist = NULL;
	//LTInit(&plist);
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	LTNode* find1 = LTFind(plist, 2);
	LTInsert(find1, 66);
	LTPrint(plist);
	LTNode* find2 = LTFind(plist, 4);
	LTInsert(find2, 99);
	LTPrint(plist);
	LTNode* find3 = LTFind(plist, 66);
	LTErase(find3);
	find3 = NULL;
	LTPrint(plist);
	LTNode* find4 = LTFind(plist, 99);
	LTErase(find4);
	find4 = NULL;
	LTPrint(plist);
	LTDestroy(plist);
	plist = NULL;
}

int main()
{
	//ListTest01();
	//ListTest02();
	//ListTest03();
	ListTest04();
	return 0;
}

以上就是本文的全部内容了，希望对大家有所帮助，大家加油！！！

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

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

相关文章

实力认证！亚数产品入选《中国网络安全行业全景图（第十一版）》

实力认证！亚数产品入选《中国网络安全行业全景图（第十一版）》

2024年4月12日&#xff0c;安全牛第十一版《中国网络安全行业全景图》&#xff08;以下简称“全景图”&#xff09;正式发布。 亚数信息科技&#xff08;上海&#xff09;有限公司&#xff08;以下简称“亚数”&#xff09;成功入选数字证书、加解密、密钥管理三项细分领域。 此…
阅读更多...
开发同城O2O跑腿系统源码：构建高效便捷的本地服务平台教程

开发同城O2O跑腿系统源码：构建高效便捷的本地服务平台教程

为了满足用户对便捷的需求&#xff0c;今天我们将一同探讨如何开发一个高效便捷的同城O2O跑腿系统&#xff0c;以构建一个功能全面、操作简单的本地服务平台。 一、确定需求和功能 在开发同城O2O跑腿系统之前&#xff0c;首先需要明确系统的需求和功能。用户可以通过该系统发布…
阅读更多...
使用LangChain和Llama-Index实现多重检索RAG

使用LangChain和Llama-Index实现多重检索RAG

大家好&#xff0c;在信息检索的世界里&#xff0c;查询扩展技术正引领着一场效率革命。本文将介绍这一技术的核心多查询检索&#xff0c;以及其是如何在LangChain和Llama-Index中得到应用的。 1.查询扩展 查询扩展是一种信息检索技术&#xff0c;通过在原始查询的基础上增加…
阅读更多...
python辅助QQ登入

python辅助QQ登入

python辅助QQ登入 import pyautogui import time import random from pyautogui import ImageNotFoundException# 生成随机等待时间&#xff0c;范围在1到3秒之间 random_time random.uniform(1, 3)def find_and_click(image_path, moveFalse, execute_nextTrue):try:image_l…
阅读更多...
达梦数据库：安装达梦数据库客户端并配置python调用

达梦数据库：安装达梦数据库客户端并配置python调用

前言 本文主要介绍了达梦数据库的客户端安装方案、python调用方案。本文使用的达梦数据库版本为 V8&#xff0c;如果使用的是其他版本&#xff0c;操作可能会有些许差异。 下载 前往官网安装&#xff1a;产品下载 | 达梦数据库 根据自己的系统版本进行选择&#xff0c;而后点击…
阅读更多...
基于SpringBoot的“论坛管理系统”的设计与实现（源码+数据库+文档+PPT)

基于SpringBoot的“论坛管理系统”的设计与实现（源码+数据库+文档+PPT)

基于SpringBoot的“论坛管理系统”的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 论坛管理系统结构图 前台首页功能界面图 用户登录…
阅读更多...
高速公路信息化大会 | 云轴科技ZStack分享云原生超融合在高速公路行业的应用

高速公路信息化大会 | 云轴科技ZStack分享云原生超融合在高速公路行业的应用

近日&#xff0c;作为第二十六届高速公路信息化大会分论坛之一&#xff0c;由中国公路学会邀请、英特尔支持和协办《第四届英特尔智慧化方案助力高速新基建升级论坛》在合肥顺利召开。来自智慧交通建设领域的创新企业和技术专家共聚一堂&#xff0c;围绕改扩建高速公路提升和数…
阅读更多...
Odoo｜手把手教你Odoo集成drools，完成物料规则配置与报价单自动审核!

Odoo｜手把手教你Odoo集成drools，完成物料规则配置与报价单自动审核!

一、背景介绍 在实际业务中&#xff0c;售前根据客户需求选择相应的产品和对应的物料来生成报价单。然而&#xff0c;在填写报价单的过程中&#xff0c;可能会出现物料漏选或数量不准确的情况&#xff0c;这会对后续备货和生产效率造成重大影响。此外&#xff0c;由于产品和物料…
阅读更多...
安装docker的PHP环境NLMP环境在国产deepin操作系统上

安装docker的PHP环境NLMP环境在国产deepin操作系统上

1： 先安装docker 安装完后执行，权限设置 sudo usermod -aG docker $USER或者sudo usermod -aG docker kentrl#添加当前用户到Docker用户组中 sudo newgrp docker#更新用户组数据，必须执行否则无效 sudo systemctl restart docker 先看目录结构： 2：按照目录结构挂载磁盘，…
阅读更多...
渐进式交付实践：通过 Argo Rollouts 和 FSM Gateway 实现金丝雀发布

渐进式交付实践：通过 Argo Rollouts 和 FSM Gateway 实现金丝雀发布

渐进式交付&#xff08;Progressive delivery&#xff09;是一种软件发布策略&#xff0c;旨在更安全、更可控地将新版本软件逐步推出给用户。它是持续交付的进一步提升&#xff0c;允许开发团队在发布新版本时拥有更细粒度的控制&#xff0c;例如可以根据用户反馈、性能指标和…
阅读更多...
一键恢复备忘录，3个方法快速找回丢失记忆

一键恢复备忘录，3个方法快速找回丢失记忆

备忘录是我们日常生活中一个重要的记录工具&#xff0c;用来记录待办事项、重要日期、提醒事项等等。然而&#xff0c;有时我们可能会不小心删除一些重要的备忘录&#xff0c;导致信息的丢失。 这时候&#xff0c;恢复备忘录就变得非常重要。在本文中&#xff0c;我们将介绍三…
阅读更多...
IDEA报错然后pycharm闪退

IDEA报错然后pycharm闪退

pycharm闪退&#xff0c;在C盘的USER文件夹下有报错文件 打开一看&#xff0c;说内存不足 # There is insufficient memory for the Java Runtime Environment to continue. # Native memory allocation (mmap) failed to map 14596177920 bytes for G1 virtual space # Possib…
阅读更多...
工业控制（ICS）---modbus

工业控制（ICS）---modbus

Modbus Modbus&#xff0c;市场占有率高、出题频率高,算是最常见的题目&#xff0c;因为这个协议也是工控领域最常见的协议之一&#xff0c;主要有三类 Modbus/RTU 从机地址1B功能码1B数据字段xBCRC值2B 最大长度256B&#xff0c;所以数据字段最大长度252B Modbus/ASCII …
阅读更多...
嵌入式面试-回答I2C

嵌入式面试-回答I2C

说明&#xff1a; 此文章是在阅读了一些列面试相关资料之后对于一些常见问题的整理&#xff0c;主要针对的是嵌入式软件面试中涉及到的问答&#xff0c;努力精准的抓住重点进行描述。若有不足非常欢迎指出&#xff0c;感谢&#xff01;在总结过程中有些答案没标记参考来源&…
阅读更多...
项目7-音乐播放器6+评论区

项目7-音乐播放器6+评论区

1.准备前端界面 前端小白&#xff1a;怎么为你的网页增加评论功能&#xff1f;&#xff08;一&#xff09;_为网页添加评论区怎么弄-CSDN博客 参考的上述文章的前端代码 我们从上述前端图片知道&#xff0c;我们数据库需要准备的字段&#xff1a; id,commentuserName,coomen…
阅读更多...
JavaWeb开发02-MYSQL-DDL-DML-DQL-多表设计-多表查询-事务-索引

JavaWeb开发02-MYSQL-DDL-DML-DQL-多表设计-多表查询-事务-索引

一、MySQL概述 通过SQL语句可以操作数据库 关系型数据库&#xff1a; 只要是关系型数据库就可以用SQL语句这一统一标准进行操作数据库 1.MYSQL数据模型 客户端通过SQL语句交给了数据库管理系统DBMS&#xff0c;进行相应操作&#xff0c;创建一个一个数据库&#xff0c;体现为一…
阅读更多...
python3如何提取汉字

python3如何提取汉字

采用正则表达式的方法对字符串进行处理。 str1 "&#xff5b;我%$是&#xff0c;《速$.度\发》中 /国、人"&#xff08;1&#xff09;提取汉字 汉字的范围为”\u4e00-\u9fa5“&#xff0c;这个是用Unicode表示的。 import re res1 .join(re.findall([\u4e00-\u9fa…
阅读更多...
力扣HOT100 - 141. 环形链表

力扣HOT100 - 141. 环形链表

解题思路&#xff1a; public class Solution {public boolean hasCycle(ListNode head) {Set<ListNode> set new HashSet<>();while (head ! null) {if (!set.add(head)) {return true;}head head.next;}return false;} }
阅读更多...
基于Matlab机器人工具箱对Dobot机械臂的研究

基于Matlab机器人工具箱对Dobot机械臂的研究

文章目录 文章目录 前言 一、Dobot Mangician 分析 二、Matlab 机器人工具箱 1. 建立模型 2. DoBot 正向运动学 3. Dobot 逆运动学 4. Dobot workpace 5. Dobot轨迹规划 三、Dobot studio 1. DoBot teaching 2. DoBot Python 程序 总结 前言 在本实验中&#xf…
阅读更多...
第四届大数据工程与教育国际会议（BDEE 2024）即将召开！

第四届大数据工程与教育国际会议（BDEE 2024）即将召开！

第四届大数据工程与教育国际会议&#xff08;BDEE 2024&#xff09;将于2024年8月9-11日在泰国清迈举行。数据驱动教育变革&#xff0c;智慧点亮未来课堂&#xff01;BDEE 2024是专注于大数据工程与教育领域的重要学术会议&#xff0c;全球大数据与教育精英齐聚&#xff0c;在数…
阅读更多...
最新文章

Copyright @ 2022~2023