C语言数据结构-双向链表

文章目录

  • 1 双向链表的结构
  • 2 双向链表的实现
    • 2.1 定义双向链表的数据结构
    • 2.2 打印链表
    • 2.3 初始化链表
    • 2.4 销毁链表
    • 2.5 尾插,头插
    • 2.6 尾删,头删
    • 2.7 根据头次出现数据找下标
    • 2.8 定点前插入
    • 2.9 删除pos位置
    • 2.10 定点后插入
  • 3 完整代码
    • 3.1 List.h
    • 3.2 Lish.c
    • 3.3 test.c

1 双向链表的结构

在这里插入图片描述

带头链表的头结点,实际是"哨兵位",哨兵位节点不存储任何有效元素,只是站在这里"放哨的".
哨兵位的意义:遍历循环链表避免死循环.

2 双向链表的实现

笔者在删除,插入数据时,画好图后,也好了代码,但是在调试中多次出现代码位置出错,导致写的代码的含义不符合预期.
所以说思路一定要清晰,多多检查调试

2.1 定义双向链表的数据结构

typedef int ListDataType;

typedef struct ListNode
{
	ListDataType data;		//整型数据
	struct ListNode* next;	//前驱指针
	struct ListNode* pre;	//后驱指针

}ListNode;

2.2 打印链表

链表的第一个数据是phead->next,哨兵位不存储数据
循环链表中,遍历一遍,碰到phead为止

void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;	//头结点,哨兵位的下一位
	while (cur != phead)//双向循环链表,循环到哨兵位为止
	{
		printf("%d-> ", cur->data);
		cur = cur->next;
	}
}

在这里插入图片描述

2.3 初始化链表

定义一个双向循环链表后,初始化链表,此时只有一个phead(哨兵位),前驱指针和后驱指针都指向phead自己
哨兵位的数据(data)在应用中不使用,就设置成-1了,与笔者之后使用的正整数形成差异

ListNode* ListInit()
{
	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	if (phead == NULL)
	{
		perror("malloc error");
		return;
	}
	phead->data = -1;
	phead->next = phead->pre = phead;
	return phead;
}

在这里插入图片描述

调试中发现,phead,phead->next,phead->pre地址相同,data都是笔者设置的-1.

2.4 销毁链表

遍历一遍链表进行销毁,cur碰到phead哨兵位为止
释放cur前,记录下cur->next,释放cur后,把cur->next赋值给cur,以此避免销毁cur后,cur->next不能指向下一个节点的情况
最后再把哨兵位释放,置空.

void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;	//头结点,哨兵位的下一位
	while (cur!=phead)
	{
		//释放cur前,记录下cur->next,释放cur后,把cur->next赋值给cur
		ListNode* NEXT = cur->next;
		free(cur);
		cur = NEXT;
	}
	//释放哨兵位
	free(phead);
	phead = NULL;
}

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2.5 尾插,头插

先写一个创建内存空间的函数,创建node后,画图示意头插和尾插
一定注意编写代码的顺序,看看笔者注释所说的
在这里插入图片描述
在这里插入图片描述

//插入数据前创建内存空间
ListNode* ListBuyNode(ListDataType x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = x;
	node->next = node->pre = NULL;

	return node;
}

void ListPushBack(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* node = ListBuyNode(x);

	//先处理新节点前驱指针和后驱指针
	node->pre = phead->pre;
	node->next = phead;
	//再处理原链表最后一个节点和phead
	phead->pre->next = node;
	phead->pre = node;
}

void ListPushFront(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* node = ListBuyNode(x);
	//先处理新节点前驱指针和后驱指针
	node->pre = phead;
	node->next = phead->next;
	//再处理phead和原链表第一个节点(phead->next)
	phead->next->pre = node;
	phead->next = node;

}

初始化成功,我们插入一个数据"1",成功插入在这里插入图片描述
在这里插入图片描述

2.6 尾删,头删

删除链表至少有除哨兵位的一个数据,换句话说,链表不能只有一个哨兵位
在这里插入图片描述

在这里插入图片描述

void ListPopBack(ListNode* phead)
{
	assert(phead);
	//链表不能只有一个哨兵位
	assert(phead->next != phead);
	ListNode* del = phead->pre;
	//删除节点的前驱指针
	del->pre->next = phead;
	//phead的前驱指针
	phead->pre = del->pre;
}

void ListPopFront(ListNode* phead)
{
	assert(phead && phead->next != phead);
	ListNode* del = phead->next;

	del->next->pre = phead;
	phead->next = del->next;

	free(del);
	del = NULL;

}

在这里插入图片描述

在这里插入图片描述

2.7 根据头次出现数据找下标

这个Find()函数在笔者的多篇博客都有提到缺点,但是我们主要实现功能,笔者在力扣题写过找多个相同元素,删多个相同元素的题

ListNode* ListFind(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}

在这里插入图片描述

在这里插入图片描述

2.8 定点前插入

在这里插入图片描述

void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* node= ListBuyNode(x);
	//先处理node
	node->next = pos;
	node->pre = pos->pre;
	//在处理pos->pre和pos
	pos->pre->next= node;
	node->next->pre = node;

}

在这里插入图片描述

2.9 删除pos位置

在这里插入图片描述

void ListErase(ListNode* pos)
{
	assert(pos);
	pos->next->pre = pos->pre;
	pos->pre->next = pos->next;
	free(pos);
	pos = NULL;
}

在这里插入图片描述
在这里插入图片描述

2.10 定点后插入

在这里插入图片描述

void ListInsertAfter(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* node = ListBuyNode(x);
	//node的prev 和 next
	node->next = pos->next;
	node->pre = pos;

	//pos的next 和 pos->next的prev
	pos->next = node;
	node->next->pre = node;
}

在这里插入图片描述

3 完整代码

3.1 List.h

#define _CRT_SECURE_NO_WARNINGS
#include<stdbool.h>
#include<stddef.h>
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//0 定义双向循环链表节点结构
typedef int ListDataType;

typedef struct ListNode
{
	ListDataType data;
	struct ListNode* next;	//前驱指针
	struct ListNode* pre;	//后驱指针

}ListNode;

//0 打印链表
void ListPrint(ListNode* phead);

//1 初始化链表
ListNode* ListInit();

//2 销毁链表
void ListDestory(ListNode* phead);

//3 尾插,头插
void ListPushBack(ListNode* phead, ListDataType x);
void ListPushFront(ListNode* phead, ListDataType x);

//4 尾删,头删
void ListPopBack(ListNode* phead);
void ListPopFront(ListNode* phead);

//5 根据数找到第一次出现的下标
ListNode* ListFind(ListNode* phead, ListDataType x);
  
//6 定点前插入
void ListInsert(ListNode* pos, ListDataType x);

//7 删除pos位置
void ListErase(ListNode* pos);

//8 定点后插入
void ListInsertAfter(ListNode* pos, ListDataType x);

3.2 Lish.c

#include "List.h"

void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)//双向循环链表,循环到哨兵位为止
	{
		printf("%d-> ", cur->data);
		cur = cur->next;
	}
}

ListNode* ListInit()
{
	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	if (phead == NULL)
	{
		perror("malloc error");
		return;
	}
	phead->data = -1;
	phead->next = phead->pre = phead;
	return phead;
}

void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;	//头结点,哨兵位的下一位
	while (cur!=phead)
	{
		//释放cur前提前记录下cur->next,释放cur后,把cur->next赋值给cur
		ListNode* NEXT = cur->next;
		free(cur);
		cur = NEXT;
	}
	//释放哨兵位
	free(phead);
	phead = NULL;
}

//插入数据前创建内存空间
ListNode* ListBuyNode(ListDataType x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = x;
	node->next = node->pre = NULL;

	return node;
}

void ListPushBack(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* node = ListBuyNode(x);

	//先处理新节点前驱指针和后驱指针
	node->pre = phead->pre;
	node->next = phead;
	//再处理原链表最后一个节点和phead
	phead->pre->next = node;
	phead->pre = node;
}

void ListPushFront(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* node = ListBuyNode(x);
	//先处理新节点前驱指针和后驱指针
	node->pre = phead;
	node->next = phead->next;
	//再处理phead和原链表第一个节点(phead->next)
	phead->next->pre = node;
	phead->next = node;

}

void ListPopBack(ListNode* phead)
{
	assert(phead);
	//链表不能只有一个哨兵位
	assert(phead->next != phead);
	ListNode* del = phead->pre;
	//删除节点的前驱指针
	del->pre->next = phead;
	//phead的前驱指针
	phead->pre = del->pre;
}

void ListPopFront(ListNode* phead)
{
	assert(phead && phead->next != phead);
	ListNode* del = phead->next;

	del->next->pre = phead;
	phead->next = del->next;

	free(del);
	del = NULL;

}

ListNode* ListFind(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}

void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* node= ListBuyNode(x);
	//先处理node
	node->next = pos;
	node->pre = pos->pre;
	//在处理pos->pre和pos
	pos->pre->next= node;
	node->next->pre = node;

}

void ListErase(ListNode* pos)
{
	assert(pos);
	pos->next->pre = pos->pre;
	pos->pre->next = pos->next;
	free(pos);
	pos = NULL;
}

void ListInsertAfter(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* node = ListBuyNode(x);
	//node的prev 和 next
	node->next = pos->next;
	node->pre = pos;

	//pos的next 和 pos->next的prev
	pos->next = node;
	node->next->pre = node;
}

3.3 test.c

#include"List.h"

void test1()
{
	ListNode* plist = ListInit();
}

void test2()
{
	ListNode* plist = ListInit();;
	ListPushBack(plist, 1);
	ListPushBack(plist, 4);
	ListPushBack(plist, 7);

	ListPrint(plist);  //1->4->7->
	ListDestory(plist);
}

void test3()
{
	ListNode* plist = ListInit();;
	ListPushFront(plist, 1);
	ListPushFront(plist, 4);
	ListPushFront(plist, 7);

	ListPrint(plist);//7->4->1->
	ListDestory(plist);
}

void test4()
{
	ListNode* plist = ListInit();;
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPushBack(plist, 6);
	ListPushBack(plist, 7);
	ListPushBack(plist, 8);
	ListPushBack(plist, 9);
	ListPrint(plist);
	printf("\n");

	ListPopBack(plist);
	ListPopBack(plist);
	ListPopFront(plist);
	ListPopFront(plist);

	ListPrint(plist);
	ListDestory(plist);
}

void test5()
{
	ListNode* plist = ListInit();;
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPrint(plist);
	printf("\n");

	//测试指定位置
	ListNode* Find1 = ListFind(plist, 2);
	ListNode* Find2 = ListFind(plist, 4);
	ListInsert(Find1, 10);
	ListInsertAfter(Find2, 20);
	ListPrint(plist);
	printf("\n");

	ListErase(Find1);
	ListPrint(plist);
	ListDestory(plist);
}

int main()
{
	//test1();
	//test2();
	//test3();
	//test4();
	test5();


	return 0;
}

笔者在删除,插入数据时,画好图后,也好了代码,但是在调试中多次出现代码位置出错,导致写的代码的含义不符合预期.
所以说思路一定要清晰,多多检查调试

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

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

相关文章

redis中缓存雪崩，缓存穿透，缓存击穿等

redis中缓存雪崩，缓存穿透，缓存击穿等

缓存雪崩 由于原有缓存失效&#xff08;或者数据未加载到缓存中&#xff09;&#xff0c;新缓存未到期间&#xff08;缓存正常从Redis中获取&#xff0c;如下图&#xff09;所有原本应该访问缓存的请求都去查询数据库了&#xff0c;而对数据库CPU和内存造成巨大压力&#xff0c…
阅读更多...
数据结构算法-希尔排序算法

数据结构算法-希尔排序算法

引言 在一个普通的下午&#xff0c;小明和小森决定一起玩“谁是老板”的扑克牌游戏。这次他们玩的可不仅仅是娱乐&#xff0c;更是要用扑克牌来决定谁是真正的“大老板”。 然而&#xff0c;小明的牌就像刚从乱麻中取出来的那样&#xff0c;毫无头绪。小森的牌也像是被小丑掷…
阅读更多...
C++ 学习系列 -- 实现简单的 String

C++ 学习系列 -- 实现简单的 String

1 标准库 std::string c 中的 std::string 是一个重要的字符串的类, 我们在日常工作中常常与之打交道。 string是C标准库的重要部分&#xff0c;主要用于字符串处理。使用string库需要在同文件中包括该库 #include<string> std::string 实际上是 std::basic_string<…
阅读更多...
基于ssm应急资源管理系统论文

基于ssm应急资源管理系统论文

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本应急资源管理系统就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据信息…
阅读更多...
jupyter notebook设置代码提示（代码补全）

jupyter notebook设置代码提示（代码补全）

1.当你打开jupyter notebook时&#xff0c;写代码的时候是默认没有代码提示的。 在base环境依次输入以下四行命令&#xff1a; pip install jupyter_contrib_nbextensions jupyter contrib nbextension install --user pip install jupyter_nbextensions_configurator jupyter …
阅读更多...
系统架构设计师教程（二）计算机系统基础知识

系统架构设计师教程（二）计算机系统基础知识

系统架构设计师 2.1 计算机系统概述2.2 计算机硬件2.2.1 计算机硬件组成2.2.2 处理器2.2.3 存储器2.2.4 总线2.2.5 接口2.2.6 外部设备 2.3 计算机软件2.3.1 计算机软件概述2.3.2 操作系统2.3.3 数据库关系数据库关系数据库设计的特点及方法关系数据库设计的基本步骤 分布式数据…
阅读更多...
python3使用pandas备份mysql数据表

python3使用pandas备份mysql数据表

操作系统 &#xff1a;CentOS 7.6_x64 Python版本&#xff1a;3.9.12 MySQL版本&#xff1a;5.7.38 日常开发过程中&#xff0c;会遇到mysql数据表的备份需求&#xff0c;需要针对单独的数据表进行备份并定时清理数据。 今天记录下python3如何使用pandas进行mysql数据表的备…
阅读更多...
ubuntu20 安装docker

ubuntu20 安装docker

一.官网安装文档 &#xff08;基本按官方文档安装&#xff09; Install Docker Engine on Ubuntu | Docker Docs 二.安装步骤 1.docker 需要64位操作系统、linux内核要在3.1以上 #uname -r 2.卸载可能存在的旧版本 #sudo apt-get remove docker docker-engine docker-ce …
阅读更多...
整数分析 C语言xdoj43

整数分析 C语言xdoj43

问题描述 给出一个整数n&#xff08;0<n<100000000&#xff09;。求出该整数的位数&#xff0c;以及组成该整数的所有数字中的最大数字和最小数字。 输入说明 输入一个整数n&#xff08;0<n<100000000&#xff09; 输出说明 在一行上依次输出整数n的位…
阅读更多...
【无标题】安装环境

【无标题】安装环境

这里写目录标题 清华镜像加速 安装cuda11.3 PyTorch 1.10.1https://pytorch.org/get-started/previous-versions/[如果没有可以点Previous pyTorch Versions&#xff0c;这里面有更多的更早的版本](https://pytorch.org/get-started/locally/) 复制非空文件夹cp: -r not specif…
阅读更多...
Linux下通过find找文件---通过修改时间查找（-mtime）

Linux下通过find找文件---通过修改时间查找（-mtime）

通过man手册查找和-mtime选项相关的内容 man find | grep -A 3 mtime # 这里简单介绍了 -mtime &#xff0c;还有一个简单的示例-mtime n Files data was last modified n*24 hours ago. See the comments for -atime to understand how rounding affects the interpretati…
阅读更多...
Linux——缓冲区与C库的实现原理

Linux——缓冲区与C库的实现原理

一.缓冲区 1缓冲区的概念 缓冲区的本质就是一段内存 2.缓冲区存在的意义 提高使用者的效率 同时因为缓冲区的存在也提高了操作系统的效率 举例一个例子&#xff1a; 假如你在云南要给你北京的朋友寄东西。方法一&#xff1a;你可以亲自己去北京把东西交给他&#xff0c;方…
阅读更多...
28. 深度学习进阶 - LSTM

28. 深度学习进阶 - LSTM

文章目录 Hi, 你好。我是茶桁。 我们上一节课&#xff0c;用了一个示例来展示了一下我们为什么要用RNN神经网络&#xff0c;它和全连接的神经网络具体有什么区别。 这节课&#xff0c;我们就着上一节课的内容继续往后讲&#xff0c;没看过上节课的&#xff0c;建议回头去好好…
阅读更多...
深度学习 | 前馈神经网络与反向传播算法

深度学习 | 前馈神经网络与反向传播算法

目录 一、Logistic函数 二、前馈神经网络&#xff08;FNN&#xff09; 三、反向传播算法&#xff08;BP算法&#xff09; ​四、基于前馈神经网络的手写体数字识别 一、Logistic函数 Logistic函数是学习前馈神经网络的基础。所以在介绍前馈神经网络之前&#xff0c;我们首…
阅读更多...
消息队列使用指南

消息队列使用指南

介绍 消息队列是一种常用的应用程序间通信方法&#xff0c;可以用来在不同应用程序或组件之间传递数据或消息。消息队列就像一个缓冲区&#xff0c;接收来自发送方的消息&#xff0c;并存储在队列中&#xff0c;等待接收方从队列中取出并处理。 在分布式系统中&#xff0c;消…
阅读更多...
对无向图进行邻接矩阵的转化，并且利用DFS（深度优先）和BFS（广度优先）算法进行遍历输出， 在邻接矩阵存储结构上，完成最小生成树的操作。

对无向图进行邻接矩阵的转化，并且利用DFS（深度优先）和BFS（广度优先）算法进行遍历输出， 在邻接矩阵存储结构上，完成最小生成树的操作。

一 实验目的 1&#xff0e;掌握图的相关概念。 2&#xff0e;掌握用邻接矩阵和邻接表的方法描述图的存储结构。 3&#xff0e;掌握图的深度优先搜索和广度优先搜索遍历的方法及其计算机的实现。 4&#xff0e;理解最小生成树的有关算法 二 实验内容及要求 实验内容&#…
阅读更多...
【Angular开发】Angular在2023年之前不是很好

【Angular开发】Angular在2023年之前不是很好

做一个简单介绍&#xff0c;年近48 &#xff0c;有20多年IT工作经历&#xff0c;目前在一家500强做企业架构&#xff0e;因为工作需要&#xff0c;另外也因为兴趣涉猎比较广&#xff0c;为了自己学习建立了三个博客&#xff0c;分别是【全球IT瞭望】&#xff0c;【架构师酒馆】…
阅读更多...
第 119 场 LeetCode 双周赛题解

第 119 场 LeetCode 双周赛题解

A 找到两个数组中的公共元素 模拟 class Solution { public:vector<int> findIntersectionValues(vector<int> &nums1, vector<int> &nums2) {unordered_set<int> s1(nums1.begin(), nums1.end()), s2(nums2.begin(), nums2.end());vector<…
阅读更多...
C语言进阶之路-数据结构篇

C语言进阶之路-数据结构篇

目录 一、学习目标 二、数据结构 1.基本概念 线性关系&#xff1a; 非线性关系&#xff1a; 存储形式 2. 算法分析 2.1 时间复杂度 2.2 空间复杂度 2.3 时空复杂度互换 总结 一、学习目标 了解数据结构的基本概念了解算法的分析方法 二、数据结构 1.基本概念 数据结…
阅读更多...
Si24R03—低功耗 SOC 芯片（集成RISC-V内核+2.4GHz无线收发器）

Si24R03—低功耗 SOC 芯片（集成RISC-V内核+2.4GHz无线收发器）

Si24R03是一款高度集成的低功耗SOC芯片&#xff0c;其集成了基于RISC-V核的低功耗MCU和工作在2.4GHz ISM频段的无线收发器模块。 MCU模块具有低功耗、Low Pin Count、宽电压工作范围&#xff0c;集成了13/14/15/16位精度的ADC、LVD、UART、SPI、I2C、TIMER、WUP、IWDG、RTC等丰…
阅读更多...
最新文章

Copyright @ 2022~2023