【数据结构】05.双向链表

一、双向链表的结构

在这里插入图片描述

注意：这里的“带头”跟前面我们说的“头节点”是两个概念，带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”。
“哨兵位”存在的意义：遍历循环链表避免死循环。

二、双向链表的实现

2.1 双向链表结点的创建

typedef int DLType;
//创建结构体
typedef struct DList
{
	DLType data;
	struct DList* prev;
	struct DList* next;
}DL;

2.2 双向链表的初始化与销毁

//初始化phead
DL* init(void)
{
	DL* phead = BuyNewNode(0);
	return phead;
}

//销毁链表，这里需要主要phead是形参，这里的最后将phead置空并不能将原链表中的phead置空，
//因此原链表中的phead需要手动置空，详细实现见源码
void DLDesdroy(DL* phead)
{
	assert(phead);
	DL* tail =phead->next;
 
	while (tail != phead)
	{
		DL* next = tail->next;
		free(tail); 
		tail= next;
	}
	free(phead);
	phead = NULL;
}

2.3 双向链表的增删查改

由于多次创建结点，因此我们将它提炼为一个函数

//创造新的节点
DL* BuyNewNode(DLType  x)
{
	DL* newnode = (DL*)malloc(sizeof(DL));
	if (newnode == NULL)
	{
		perror("malloc is failed!\n");
		return 1;
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}

//尾插
void  DLPushBack(DL* phead,DLType x)
{
	assert(phead);
 
	DL* newnode = BuyNewNode(x);
 
	newnode->next = phead;
	phead->prev->next = newnode;
 
	newnode->prev = phead->prev;
	phead->prev = newnode;
}
 
 
//尾删
void DLPopBack(DL* phead)
{
	assert(phead);
	assert(phead->next != phead);
 
	DL* tail = phead->prev;
	DL* prev = tail->prev;
 
	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;  
 
}
 
//头插
void DLPushFront(DL* phead, DLType x)
{
	assert(phead);
 
	DL* newnode = BuyNewNode(x);
 
	DL* first = phead->next;
 
	newnode->next = first;
	first->prev = newnode;
	phead->next = newnode;
	newnode->prev=phead;
}
 
//头删
void DLPopFront(DL* phead)
{
	assert(phead);
	assert(phead->next != phead);
 
	DL* first = phead->next;
	DL* second = first->next;
 
	phead->next = second;
	second->prev = phead;
 
	free(first);
	first = NULL;
}
 
 
//查找
DL* DLFind(DL* phead,DLType x)
{
	assert(phead);
 
	DL* cur = phead->next;
	while ( cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
 
 
 
//pos位置插入数据
void DLInsert(DL* pos,DLType x)
{
	assert(pos);
 
	DL* newnode = BuyNewNode(x);
	DL* prev = pos->prev;
    
	prev->next = newnode;
	newnode->prev = prev;
 
    newnode->next = pos;
	pos->prev = newnode;
}
 
//pos位置之后插入数据
void DLInsertAfter(DL* pos, DLType x)
{
	assert(pos);
 
	DL* newnode = BuyNewNode(x);
	DL* next = pos->next;
 
	newnode->next = next;
	next->prev = newnode;
	pos->next = newnode;
	newnode->prev = pos;
}
 
//删除pos位置元素
void  DLErase(DL* pos)
{
	assert(pos);
 
	DL* next = pos->next;
	DL* prev = pos->prev;
 
	prev->next = next;
	next->prev = prev;
 
	free(pos);
	pos = NULL;
}

2.4 双向链表的打印

//打印链表
void DLPrint(DL* phead)
{
	DL* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

2.5 双向链表的源码

//DL.h
 
#pragma once
 
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int DLType;
 
typedef struct DList
{
	DLType data;
	struct DList* prev;
	struct DList* next;
}DL;
 
//初始化
DL* init(void);
//打印
void DLPrint(DL* phead);
 
//尾插、尾删
void  DLPushBack(DL* phead, DLType x);
void DLPopBack(DL* phead);
 
//头插、头删
void  DLPushFront(DL* phead, DLType x);
void  DLPopFront(DL* phead);
 
//查找
DL* DLFind(DL* phead, DLType x);
 
//指定位置插入数据、指定位置之后插入数据
void  DLInsert(DL* pos, DLType x);
void DLInsertAfter(DL* pos, DLType x);
 
//删除pos
void  DLErase(DL* phead);
 
void DLDesdroy(DL** phead);

//DL.c
#include "DList.h"
 
 
//创造新的节点
DL* BuyNewNode(DLType  x)
{
	DL* newnode = (DL*)malloc(sizeof(DL));
	if (newnode == NULL)
	{
		perror("malloc is failed!\n");
		return 1;
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}
 
 
//初始化phead
DL* init(void)
{
	DL* phead = BuyNewNode(0);
	return phead;
}
 
 
//打印链表
void DLPrint(DL* phead)
{
	DL* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
 
 
//尾插
void  DLPushBack(DL* phead,DLType x)
{
	assert(phead);
 
	DL* newnode = BuyNewNode(x);
 
	newnode->next = phead;
	phead->prev->next = newnode;
 
	newnode->prev = phead->prev;
	phead->prev = newnode;
}
 
 
//尾删
void DLPopBack(DL* phead)
{
	assert(phead);
	assert(phead->next != phead);
 
	DL* tail = phead->prev;
	DL* prev = tail->prev;
 
	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;  
 
}
 
//头插
void DLPushFront(DL* phead, DLType x)
{
	assert(phead);
 
	DL* newnode = BuyNewNode(x);
 
	DL* first = phead->next;
 
	newnode->next = first;
	first->prev = newnode;
	phead->next = newnode;
	newnode->prev=phead;
}
 
//头删
void DLPopFront(DL* phead)
{
	assert(phead);
	assert(phead->next != phead);
 
	DL* first = phead->next;
	DL* second = first->next;
 
	phead->next = second;
	second->prev = phead;
 
	free(first);
	first = NULL;
}
 
 
//查找
DL* DLFind(DL* phead,DLType x)
{
	assert(phead);
 
	DL* cur = phead->next;
	while ( cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
 
 
 
//pos位置插入数据
void DLInsert(DL* pos,DLType x)
{
	assert(pos);
 
	DL* newnode = BuyNewNode(x);
	DL* prev = pos->prev;
    
	prev->next = newnode;
	newnode->prev = prev;
 
    newnode->next = pos;
	pos->prev = newnode;
}
 
//pos位置之后插入数据
void DLInsertAfter(DL* pos, DLType x)
{
	assert(pos);
 
	DL* newnode = BuyNewNode(x);
	DL* next = pos->next;
 
	newnode->next = next;
	next->prev = newnode;
	pos->next = newnode;
	newnode->prev = pos;
}
 
//删除
void  DLErase(DL* pos)
{
	assert(pos);
 
	DL* next = pos->next;
	DL* prev = pos->prev;
 
	prev->next = next;
	next->prev = prev;
 
	free(pos);
	pos = NULL;
}
 
//销毁链表
void DLDesdroy(DL* phead)
{
	assert(phead);
	DL* tail =phead->next;
 
	while (tail != phead)
	{
		DL* next = tail->next;
		free(tail); 
		tail= next;
	}
	free(phead);
	phead = NULL;
}

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

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

相关文章

Django QuerySet对象，filter()方法

Django QuerySet对象，filter()方法

filter()方法 用于实现数据过滤功能&#xff0c;相当于sql语句中的where子句。 filter(字段名__exact10) 或 filter(字段名10)类似sql 中的 10 filter(字段名__gt10) 类似SQL中的 >10 filter(price__lt29.99) 类似sql中的 <29.99 filter(字段名__gte10, 字段名__lte20…
阅读更多...
LightGlue: Local Feature Matching at Light Speed【文献阅读】

LightGlue: Local Feature Matching at Light Speed【文献阅读】

论文&#xff1a;LightGlue: Local Feature Matching at Light Speed 代码&#xff1a;https://github.com/cvg/LightGlue 作者&#xff1a;1 ETH Zurich__2 Microsoft Mixed Reality & AI Lab Abstract 提出的LightGlue是一个深度神经网络用于学习图像间的局部特征匹配。…
阅读更多...
基于AOP的数据字典实现：实现前端下拉框的可配置更新

基于AOP的数据字典实现：实现前端下拉框的可配置更新

作者&#xff1a;后端小肥肠 创作不易&#xff0c;未经允许严禁转载。 目录 1. 前言 2. 数据字典 2.1. 数据字典简介 2.2. 数据字典如何管理各模块的下拉框 3. 数据字典核心内容解读 3.1. 表结构 3.2. 核心代码 3.2.1. 根据实体类名称获取下属数据字典 3.2.2. 数据字…
阅读更多...
python库（6）：Pygments库

python库（6）：Pygments库

1 Pygments介绍 在软件开发和文档编写中&#xff0c;代码的可读性是至关重要的一环。无论是在博客文章、技术文档还是教程中&#xff0c;通过代码高亮可以使程序代码更加清晰和易于理解。而在Python世界中&#xff0c;Pygments库就是这样一个强大的工具&#xff0c;它能够将各…
阅读更多...
【YOLOv9教程】如何使用YOLOv9进行图像与视频检测

【YOLOv9教程】如何使用YOLOv9进行图像与视频检测

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…
阅读更多...
【论文阅读】AsyncDiff: Parallelizing Diffusion Models by Asynchronous Denoising

【论文阅读】AsyncDiff: Parallelizing Diffusion Models by Asynchronous Denoising

论文&#xff1a;2406.06911 (arxiv.org) 代码&#xff1a;czg1225/AsyncDiff: Official implementation of "AsyncDiff: Parallelizing Diffusion Models by Asynchronous Denoising" (github.com) 简介 异步去噪并行化扩散模型。提出了一种新的扩散模型分布式加…
阅读更多...
python脚本“文档”撰写——“诱骗”ai撰写“火火的动态”python“自动”脚本文档

python脚本“文档”撰写——“诱骗”ai撰写“火火的动态”python“自动”脚本文档

“火火的动态”python“自动”脚本文档&#xff0c;又从ai学习搭子那儿“套”来&#xff0c;可谓良心质量&#x1f44d;&#x1f44d;。 (笔记模板由python脚本于2024年07月07日 15:15:33创建&#xff0c;本篇笔记适合喜欢钻研python和页面源码的coder翻阅) 【学习的细节是欢悦…
阅读更多...
001uboot体验

001uboot体验

1.uboot的作用&#xff1a; 上电->uboot启动->关闭看门狗、初始化时钟、sdram、uart等外设->把内核文件从flash读取到SDRAM->引导内核启动->挂载根文件系统->启动根文件系统的应用程序 2.uboot编译 uboot是一个通用的裸机程序&#xff0c;为了适应各种芯片&…
阅读更多...
盘点8款国内顶尖局域网监控软件（2024年国产局域网监控软件排名）

盘点8款国内顶尖局域网监控软件（2024年国产局域网监控软件排名）

局域网监控软件对于企业网络管理至关重要&#xff0c;它们可以帮助IT部门维护网络安全&#xff0c;优化网络性能&#xff0c;同时监控和控制内部员工的网络使用行为。以下是八款备受推崇的局域网监控软件&#xff0c;每一款都有其独特的优势和适用场景。 1.安企神软件 试用版领…
阅读更多...
【数据结构】（C语言）：二叉搜索树（不使用递归）

【数据结构】（C语言）：二叉搜索树（不使用递归）

二叉搜索树&#xff1a; 非线性的&#xff0c;树是层级结构。基本单位是节点&#xff0c;每个节点最多2个子节点。有序。每个节点&#xff0c;其左子节点都比它小&#xff0c;其右子节点都比它大。每个子树都是一个二叉搜索树。每个节点及其所有子节点形成子树。可以是空树。 …
阅读更多...
Report Design Analysis报告之logic level详解

Report Design Analysis报告之logic level详解

目录 一、前言 二、Logic Level distribution 2.1 logic level配置 2.2 Logic Level Distribution报告 2.3 Logic Level 报告详情查看 2.4 Route Distributions 报告详情查看 2.5 示例代码 一、前言 ​在工程设计中&#xff0c;如果需要了解路径的逻辑级数&#xff0c;可…
阅读更多...
赚钱小思路，送给没有背景的辛辛苦苦努力的我们！

赚钱小思路，送给没有背景的辛辛苦苦努力的我们！

我是一个没有背景的普通人&#xff0c;主要靠勤奋和一股钻劲&#xff0c;这十几年来我的日常作息铁打不变&#xff0c;除了睡觉&#xff0c;不是在搞钱&#xff0c;就是在琢磨怎么搞钱。 ​ 可以说打拼了十几年&#xff0c;各种小生意都做过&#xff0c;以前一直是很乐观的&…
阅读更多...
绘唐3最新版本哪里下载

绘唐3最新版本哪里下载

绘唐3最新版本哪里下载 绘唐最新版本下载地址 推文视频创作设计是一种通过视频和文字的形式来进行推广的方式&#xff0c;可以通过一些专业的工具来进行制作。 以下是一些常用的小说推文视频创作设计工具&#xff1a; 视频剪辑软件&#xff1a;如Adobe Premiere Pro、Fina…
阅读更多...
人工智能系列-Pandas基础

人工智能系列-Pandas基础

&#x1f308;个人主页&#xff1a;羽晨同学 &#x1f4ab;个人格言:“成为自己未来的主人~” Pandas简介 Pandas是Python语言的拓展程序库&#xff0c;用于数据分析。 Pandas是一个开放源码&#xff0c;BSD许可的库&#xff0c;提供高性能&#xff0c;易于使用的数据结…
阅读更多...
SSM养老院管理系统-计算机毕业设计源码02221

SSM养老院管理系统-计算机毕业设计源码02221

摘要 本篇论文旨在设计和实现一个基于SSM的养老院管理系统&#xff0c;旨在提供高效、便捷的养老院管理服务。该系统将包括老人档案信息管理、护工人员管理、房间信息管理、费用管理等功能模块&#xff0c;以满足养老院管理者和居民的不同需求。 通过引入SSM框架&#x…
阅读更多...
ChatGPT对话：Scratch编程中一个单词，如balloon，每个字母行为一致，如何优化编程

ChatGPT对话：Scratch编程中一个单词，如balloon，每个字母行为一致，如何优化编程

【编者按】balloon 7个字母具有相同的行为&#xff0c;根据ChatGPT提供的方法&#xff0c;优化了代码&#xff0c;方便代码维护与复用。初学者可以使用7个字母精灵&#xff0c;复制代码到不同精灵&#xff0c;也能完成这个功能&#xff0c;但不是优化方法&#xff0c;也没有提高…
阅读更多...
微信小程序毕业设计-医院挂号预约系统项目开发实战(附源码+论文)

微信小程序毕业设计-医院挂号预约系统项目开发实战(附源码+论文)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;微信小程序毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计…
阅读更多...
高考志愿填报，选专业是看兴趣还是看就业？

高考志愿填报，选专业是看兴趣还是看就业？

对于结束高考的学生来说&#xff0c;选择专业的确是一个非常让人头疼的事情。因为很多人都不知道&#xff0c;选专业的时候究竟是应该看一下个人兴趣&#xff0c;还是看未来的就业方向&#xff0c;这也是让不少人都相当纠结的问题。这里分析一下关于专业选择的问题&#xff0c;…
阅读更多...
动手学深度学习（Pytorch版）代码实践 -循环神经网络-54循环神经网络概述

动手学深度学习（Pytorch版）代码实践 -循环神经网络-54循环神经网络概述

54循环神经网络概述 1.潜变量自回归模型 使用潜变量h_t总结过去信息 2.循环神经网络概述 ​ 循环神经网络&#xff08;recurrent neural network&#xff0c;简称RNN&#xff09;源自于1982年由Saratha Sathasivam 提出的霍普菲尔德网络。循环神经网络&#xff0c;是指在全…
阅读更多...
字符串——string类的常用接口

字符串——string类的常用接口

一、string类对象的常见构造 二、string类对象的容量操作 三、string类对象的访问及遍历操作 四、string类对象的修改操作 一、string类对象的常见构造 1.string() ——构造空的string类对象&#xff0c;也就是空字符串 2.string(const char* s) ——用字符串来初始化stri…
阅读更多...
最新文章

Copyright @ 2022~2023