【数据结构初阶】双链表

双链表

    • 1.双链表的实现
      • 1.1结口实现
      • 1.2申请结点
      • 1.3初始化双链表
      • 1.4打印双链表
      • 1.5尾插
      • 1.6尾删
      • 1.7头插
      • 1.8头删
      • 1.9计算大小
      • 1.10查找
      • 1.11pos位置插入
      • 1.12删除pos位置
      • 1.12删除双链表
    • 全部码源

1.双链表的实现

1.1结口实现

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

typedef int LTDateType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDateType date;
}LTNode;

//创造结点
LTNode* BuyLTNode(LTDateType x);

//初始化双链表
LTNode* LTInit();

//打印双链表
void LTPrint(LTNode* phead);

//尾插
void LTPushBack(LTNode* phead, LTDateType x);

//尾删
void LTPopBack(LTNode* phead);

//头插
void LTPushFront(LTNode* phead, LTDateType x);

//头删
void LTPopFront(LTNode* phead);

//计算
int LTSize(LTNode* phead);

//查找
LTNode* LTFind(LTNode* phead, LTDateType x);

//pos位置插入
void LTInsert(LTNode* pos, LTDateType x);

//删除pos位置
void LTErase(LTNode* pos);

//销毁双链表
void LTDestroy(LTNode* phead);

1.2申请结点

//创造结点
LTNode* BuyLTNode(LTDateType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	node->date = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

1.3初始化双链表

//初始化双链表
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

1.4打印双链表

//打印双链表
void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("phead<=>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<=>", cur->date);
		cur = cur->next;
	}
	printf("\n");
}

1.5尾插

在这里插入图片描述

//尾插
void LTPushBack(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);

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

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

1.6尾删

在这里插入图片描述

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

1.7头插

在这里插入图片描述

//头插
void LTPushFront(LTNode* phead, LTNode* x)
{
	assert(phead);

	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;

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

1.8头删

在这里插入图片描述

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTNode* first = phead->next;
	LTNode* second = first->next;
	free(first);
	phead->next = second;
	second->prev = phead;
}

1.9计算大小

//计算
int LTSize(LTNode* phead)
{
	assert(phead);

	int size = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

1.10查找

//查找
LTNode* LTFind(LTNode* phead, LTDateType x)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->date == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

1.11pos位置插入

在这里插入图片描述

//在pos位置插入
void LTInsert(LTNode* pos, LTDateType x)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* newnode = BuyLTNode(x);

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

1.12删除pos位置

在这里插入图片描述

//删除pos位置
void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posNext = pos->next;
	LTNode* posPrev = pos->prev;
	free(pos);
	posPrev->next = posNext;
	posNext->prev = posPrev;
}

1.12删除双链表

//销毁双链表
void LTDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = cur->next;
	}
	free(phead);
}

全部码源

List.h

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

typedef int LTDateType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDateType date;
}LTNode;

//创造结点
LTNode* BuyLTNode(LTDateType x);

//初始化双链表
LTNode* LTInit();

//打印双链表
void LTPrint(LTNode* phead);

//尾插
void LTPushBack(LTNode* phead, LTDateType x);

//尾删
void LTPopBack(LTNode* phead);

//头插
void LTPushFront(LTNode* phead, LTDateType x);

//头删
void LTPopFront(LTNode* phead);

//计算
int LTSize(LTNode* phead);

//查找
LTNode* LTFind(LTNode* phead, LTDateType x);

//pos位置插入
void LTInsert(LTNode* pos, LTDateType x);

//删除pos位置
void LTErase(LTNode* pos);

//销毁双链表
void LTDestroy(LTNode* phead);

List.c

#include"List.h"

//创造结点
LTNode* BuyLTNode(LTDateType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	node->date = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

//初始化双链表
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

//打印双链表
void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("phead<=>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<=>", cur->date);
		cur = cur->next;
	}
	printf("\n");
}

//尾插
void LTPushBack(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);

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

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

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

//头插
void LTPushFront(LTNode* phead, LTNode* x)
{
	assert(phead);

	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;

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

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTNode* first = phead->next;
	LTNode* second = first->next;
	free(first);
	phead->next = second;
	second->prev = phead;
}

//计算
int LTSize(LTNode* phead)
{
	assert(phead);

	int size = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

//查找
LTNode* LTFind(LTNode* phead, LTDateType x)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->date == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

//在pos位置插入
void LTInsert(LTNode* pos, LTDateType x)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* newnode = BuyLTNode(x);

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

//删除pos位置
void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posNext = pos->next;
	LTNode* posPrev = pos->prev;
	free(pos);
	posPrev->next = posNext;
	posNext->prev = posPrev;
}

//销毁双链表
void LTDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = cur->next;
	}
	free(phead);
}

test.c

#include"List.h"

void TestList1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);
	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);

	LTPushFront(plist, 20);
	LTPrint(plist);
}

void TestList2()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	LTSize(plist);
}

void TestList3()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);
	LTPrint(plist);
	LTNode* pos = LTFind(plist, 3);
	LTInsert(pos, 20);
	LTPrint(plist);
}

void TestList4()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);
	LTPrint(plist);
	LTNode* pos = LTFind(plist, 3);
	LTErase(pos);
	LTPrint(plist);
}


int main()
{
	TestList4();
	return 0;
}

💘不知不觉,【数据结构初阶】双链表 以告一段落。通读全文的你肯定收获满满,让我们继续为数据结构学习共同奋进!!!

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

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

相关文章

2023下半年软件设计师考试知识点大全思维导图

软件设计师考试知识点大全思维导图 2023年下半年第一次机考 复习资料 以上是我在学习过程中根据自己的知识结构的特点及刷到的考题 做的导图&#xff0c;有需要的可以留言发原版的 mmap格式文件 方便自己拓展. 软考资料 这是网上找的资料 汇总免费放在这里 吧![ 链接&#x…

聊一聊go的单元测试

文章目录 概要一、测试框架1.1、testing1.2、stretchr/testify1.3、smartystreets/goconvey1.4、cweill/gotests 二、打桩和mock2.1、打桩2.2、mock2.2.1、mockgen 三、基准测试和模糊测试3.1、基准测试3.2、模糊测试 四、总结4.1、小结4.2、其他4.3、参考资料 概要 软件测试是…

java学习part06数组

62-数组-数组的概述_哔哩哔哩_bilibili 这篇 Java 基础&#xff0c;我吹不动了 - 掘金 (juejin.cn) 1.数组概念 重点 2.数组声明和初始化 new的时候要么给出静态初始化的数据{a,b,c}&#xff0c;要么给出动态初始化指定长度 [4]。 否则报错&#xff0c;初始化必须确定长度…

Redis字典实现

前言 字典又称符号表&#xff0c;关联数组或者映射(map)。是一种保存键值对的抽象数据结构。在字典中一个键和一个值进行关联。这些关联的值被称为键值对。 字典中每一个键都是独一无二的&#xff0c;没有重复的。我们可以通过键来查找值&#xff0c;更新值或者删除整个键值对等…

【封装UI组件库系列】搭建项目及准备工作

封装UI组件库系列第一篇搭建项目 前言 &#x1f31f;搭建项目 创建工程 基本结构 1.创建8个组件展示页面 ​ 2.配置路由文件router/index.js 3.页面布局 &#x1f31f;总结 前言 在前端开发中&#xff0c;大家可能已经用过各种各样的UI组件库了&#xff0c;现在市面上热…

最大子段和(分治法+动态规划法)

求最大子段和 此类问题通常是求数列中连续子段和的最大值&#xff0c;经典的股票问题就是考察的这个思想及拓展。 例题&#xff1a; AcWing:1054. 股票买卖 Leetcode:53. 最大子数组和 分治法O(nlogn) 此类问题时分适合采用分治思想&#xff0c;因为所有子区间 [ s t a r t …

网工内推 | 国企、港企网工,年底双薪,NA以上认证即可

01 中航期货有限公司 招聘岗位&#xff1a;信息技术部-网络工程师 职责描述&#xff1a; 1、负责总部、分支机构、外联单位网络的日常运维、故障和应急处置&#xff0c;特别是定期监测设备的运行状态&#xff0c;对存在隐患的地方及时发现改正&#xff0c;保持网络稳定通畅&am…

利用JDBC及Servlet实现对信息录入注册功能的实现

利用JDBC及Servlet实现对登录注册功能的实现&#xff1b; 1.题目要求&#xff1a; 1、新建一个数据库名为&#xff08;个人姓名拼音&#xff09;&#xff0c;表&#xff08;学生所在城市&#xff09;&#xff0c;字段&#xff08;sid&#xff1a;学号&#xff0c;sname&#x…

从硬件到软件:揭秘磁盘结构和文件系统组织

&#x1f4df;作者主页&#xff1a;慢热的陕西人 &#x1f334;专栏链接&#xff1a;Linux &#x1f4e3;欢迎各位大佬&#x1f44d;点赞&#x1f525;关注&#x1f693;收藏&#xff0c;&#x1f349;留言 本博客主要内容讲解了从磁盘的硬件结构&#xff0c;再到操作系统内部是…

采集1688整店商品(店铺所有商品、店铺列表api)

返回数据&#xff1a; 请求链接 {"user": [],"items": {"item": [{"num_iid": "738354436678","title": "国产正品i13 promax全网通5G安卓智能手机源头厂家批发手机","pic_url": "http…

Altium Designer内电层(Plan)GND和POWER出现的死铜如何去除-AD

1.问题描述 更多遇到的是顶层底层敷铜时出现清楚死铜&#xff1b;但是在内电层有时候也会出现死铜。这时候不去除死铜就会在DRC中报错。 2.解决办法1-多边形填充挖空 在工具栏&#xff1a; 放置——多边形填充挖空&#xff1b;然后再错误高亮处的死铜周围画多边形&#xff0c…

制作Go程序的Docker容器(以及容器和主机的网络问题)

今天突然遇到需要将 Go 程序制作成 Docker 的需求&#xff0c;所以进行了一些研究。方法很简单&#xff0c;但是官方文档和教程有些需要注意的地方&#xff0c;所以写本文进行记录。 源程序 首先介绍一下示例程序&#xff0c;示例程序是一个 HTTP 服务器&#xff0c;会显示si…

机器学习第10天:集成学习

文章目录 机器学习专栏 介绍 投票分类器 介绍 代码 核心代码 示例代码 软投票与硬投票 bagging与pasting 介绍 核心代码 随机森林 介绍 代码 结语 机器学习专栏 机器学习_Nowl的博客-CSDN博客 介绍 集成学习的思想是很直观的&#xff1a;多个人判断的结合往往比…

通信网络安全防护定级备案流程介绍(附流程图)

通信网络安全防护定级备案是拥有增值电信业务经营许可证并且有开展电信业务的企业要做的一件事情。刚接触这块的家人们在填报操作的时候可能对具体通信网络安全防护定级备案流程还不是很清楚&#xff0c;所以就给大家画张具体的流程图吧&#xff0c;可以更加直观的了解。 通信…

栈和队列知识点+例题

1.栈 1.1栈的概念及结构 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端成为栈顶&#xff0c;另一端成为栈底。遵守后进先出的原则&#xff08;类似于弹夹&#xff09; 压栈&#xff1a;栈的插入操…

【考研数学】正交变换后如果不是标准型怎么办?| 关于二次型标准化的一些思考

文章目录 引言一、回顾二次型的定义是什么&#xff1f;什么叫标准二次型&#xff1f;怎么化为标准型&#xff1f; 二、思考写在最后 引言 前阵子做了下 20 年真题&#xff0c;问题大大的&#xff0c;现在订正到矩阵的第一个大题&#xff0c;是关于二次型正交变换的。和常规不同…

『亚马逊云科技产品测评』活动征文|通过lightsail一键搭建Drupal VS 手动部署

『亚马逊云科技产品测评』活动征文&#xff5c;通过lightsail一键搭建Drupal 提示&#xff1a;授权声明&#xff1a;本篇文章授权活动官方亚马逊云科技文章转发、改写权&#xff0c;包括不限于在 Developer Centre, 知乎&#xff0c;自媒体平台&#xff0c;第三方开发者媒体等亚…

面试官:你能说说常见的前端加密方法吗?

给大家推荐一个实用面试题库 1、前端面试题库 &#xff08;面试必备&#xff09; 推荐&#xff1a;★★★★★ 地址&#xff1a;web前端面试题库 前言 本篇文章略微介绍一下前端中常见的加密算法。前端中常见的加密算法主要形式包括——哈希函数&#xff0c;对称…

图片叠加_图片压缩

图片叠加 try {/* 1 读取第一张图片*/File fileOne new File("1.png");BufferedImage imageFirst ImageIO.read(fileOne);/* 2读取第二张图片 */File fileTwo new File("2.png");BufferedImage imageSecond ImageIO.read(fileTwo);//创建一个最底层画…

Ftrans自动同步软件:满足企业级数据同步的需求

随着数字经济的发展&#xff0c;企业数字化的办公场景越来越复杂&#xff0c;其中一个急需解决的问题就是企业不同服务器之间的文件自动同步的需求。然而&#xff0c;目前市场上的同步软件通常有很多的缺点&#xff0c;让用户感到困扰。 1、数据安全&#xff1a;在同步数据的过…