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

一、双向链表的结构

在这里插入图片描述

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

二、双向链表的实现

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;
}

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

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

相关文章

揭秘,PyArmor库让你的Python代码更安全

揭秘,PyArmor库让你的Python代码更安全

PyArmor 概述: PyArmor 是一个用于加密和保护 Python 源代码的工具,旨在防止代码被逆向工程和未经授权的使用.通过将 Python 源代码编译为加密的字节码,PyArmor 提供了一种有效的方法来保护知识产权和敏感算法. 安装 pip install pyarmor安装完成后,可以通过以下命令验证安装…
阅读更多...
LLM端侧部署系列 | 手机上运行47B大模型?上交推理框架PowerInfer-2助力AI手机端侧部署

LLM端侧部署系列 | 手机上运行47B大模型?上交推理框架PowerInfer-2助力AI手机端侧部署

0. 引言 黄梅时节家家雨&#xff0c;青草池塘处处蛙。 有约不来过夜半&#xff0c;闲敲棋子落灯花。 当下&#xff0c;在移动设备上部署大型模型的趋势是愈演愈烈。Google推出了AI Core&#xff0c;使得Gemini Nano可以在智能手机上部署。此外&#xff0c;近期传闻苹果在iOS …
阅读更多...
SQL语句（DQL）

SQL语句（DQL）

Data Query Language&#xff08;数据查询语言&#xff09;&#xff0c;用来查询数据库中表的记录 DQL-基本查询 DQL-条件查询&#xff08;WHERE&#xff09; -- 查询姓名为2个字的员工信息 select * from emp where name like __;-- 查询身份证号最后一位是X的员工信息 selec…
阅读更多...
uni-app打包小程序的一些趣事~

uni-app打包小程序的一些趣事~

前言 Huilderx版本&#xff1a;4.15 uni-app Web端版本&#xff1a;3.4.21 问题1 Web端/APP端样式好好的&#xff0c;打包微信小程序就乱了咋整&#xff1f; 使用::v-deep/::deep/deep(){}都是没用滴~~ 原因&#xff1f; 解决&#xff1a; <script lang"ts"…
阅读更多...
c语言回顾-数组（全网最详细，哈哈哈）

c语言回顾-数组（全网最详细，哈哈哈）

目录 前言&#xff0c;和小编一起感受数组的魅力&#xff01;&#xff01;&#xff01; 1.数组的概念 2.一维数组的创建和初始化 2.1数组创建 2.2数组的初始化 2.3数组的类型 3.一维数组的使用 3.1数组下标 3.2数组元素的输入输出 小结&#xff1a; 4.一维数组在内存…
阅读更多...
Python中的__init__方法：为何它如此重要

Python中的__init__方法：为何它如此重要

目录 一、__init__方法的基本概念 1.1 定义与作用 1.2 调用时机 1.3 参数传递 二、__init__方法的工作原理 2.1 初始化属性 2.2 执行其他操作 2.3 继承与多态 三、__init__方法的使用技巧 3.1 参数传递与默认值 3.2 链式初始化 3.3 继承与超类初始化 3.4 初始化方…
阅读更多...
常见锁策略之可重入锁VS不可重入锁

常见锁策略之可重入锁VS不可重入锁

可重入锁VS不可重入锁 有一个线程,针对同一把锁,连续加锁两次,如果产生了死锁,那就是不可重入锁,如果没有产生死锁,那就是可重入锁. 死锁 我们之前引入多线程的时候不是讲了一个加数字的案例么,我们今天以它来举例 当我们这样写的时候会出现什么问题? 分析:第一个synchron…
阅读更多...
Zookeeper：Zookeeper集群角色

Zookeeper：Zookeeper集群角色

文章目录 一、Leader选举二、Zookeeper集群角色 一、Leader选举 Serverid&#xff1a;服务器ID&#xff1b;比如有三台服务器&#xff0c;编号越大在选择算法中的权重越大。Zxid&#xff1a;数据ID&#xff1b;服务器中存放的最大数据ID&#xff0c;值越大说明数据越新&#x…
阅读更多...
【创作纪念日】我的CSDN1024创作纪念

【创作纪念日】我的CSDN1024创作纪念

机缘 注册CSDN是很长时间了&#xff0c;但是上学时因为专业是电气工程&#xff0c;与编程打交道比较少&#xff0c;一直都是寻求帮助&#xff0c;而非内容输出。直到考研后专业改变&#xff0c;成为了主要跟软件编程、计算机知识相关的研究后&#xff0c;才逐步开启自己的CSDN…
阅读更多...
模拟布局：为什么井、抽头和保护环至关重要

模拟布局：为什么井、抽头和保护环至关重要

其中的关键示例是井、抽头和保护环。这些结构对于任何 MOSFET 电路的工作都至关重要。 这就是为什么了解衬底在 MOSFET 电路中的作用对于创建有效的模拟设计至关重要。要做到这一点&#xff0c;首先必须了解 MOSFET 晶体管的工作原理。 让我们来看看一种类型的 MOSFET&#x…
阅读更多...
归并排序-MergeSort (C语言详解)

归并排序-MergeSort (C语言详解)

目录 前言归并排序的思想归并排序的递归法归并排序的非递归法归并排序的时间复杂度与适用场景总结 前言 好久不见, 前面我们了解到了快速排序, 那么本篇旨在介绍另外一种排序, 它和快速排序的思想雷同, 但又有区别, 这就是归并排序, 如下图, 我们对比快速排序与归并排序. 本…
阅读更多...
编译器的控制流图分析

编译器的控制流图分析

1&#xff0c;建立感性认识 1.1 源码 hello.c int x 10; int y 11; int main(){int z 12;for (int i 0;i < 10;i){z * x * y;}if(z>7.0)z1.0f;elsez 2.0f;return 0; }1.2 编译 2005 sudo apt-get install -y graphviz-doc libgraphviz-dev graphviz2034 ../ex_…
阅读更多...
Java学习高级一

Java学习高级一

修饰符 static 类变量的应用场景 成员方法的分类 成员变量的执行原理 成员方法的执行原理 Java之 main 方法 类方法的常见应用场景 代码块 设计模式 单例设计模式 饿汉式单例设计模式 懒汉式单例设计模式 继承 权限修饰符
阅读更多...
LeetCode题练习与总结：二叉树的后序遍历--145

LeetCode题练习与总结：二叉树的后序遍历--145

一、题目描述 给你一棵二叉树的根节点 root &#xff0c;返回其节点值的 后序遍历 。 示例 1&#xff1a; 输入&#xff1a;root [1,null,2,3] 输出&#xff1a;[3,2,1]示例 2&#xff1a; 输入&#xff1a;root [] 输出&#xff1a;[]示例 3&#xff1a; 输入&#xff1a…
阅读更多...
以太坊DApp交易量激增83%的背后原因解析

以太坊DApp交易量激增83%的背后原因解析

引言 最近&#xff0c;以太坊网络上的去中心化应用程序&#xff08;DApp&#xff09;交易量激增83%&#xff0c;引发了广泛关注和讨论。尽管交易费用高达2.4美元&#xff0c;但以太坊仍在DApp交易量方面遥遥领先于其他区块链网络。本文将深入探讨导致这一现象的主要原因&#…
阅读更多...
颅内感染性疾病患者就诊指南

颅内感染性疾病患者就诊指南

颅内感染性疾病&#xff0c;即病原体侵入中枢神经系统&#xff0c;导致脑部或脑膜发生炎症的疾病。这些病原体可能是细菌、病毒、真菌或寄生虫等。颅内感染不仅会对脑组织造成损害&#xff0c;还可能引发一系列严重的并发症&#xff0c;如癫痫发作、意识障碍等 颅内感染性疾病的…
阅读更多...
国产软件号称Windows系统的天花板，却被误认为是外国佬研发

国产软件号称Windows系统的天花板，却被误认为是外国佬研发

说起国产软件&#xff0c;大家总是容易给它们贴上“流氓、捆绑、满满的都是套路”这样的标签。 其实挺冤枉的&#xff0c;有些软件真的挺好用&#xff0c;也挺良心的&#xff0c;但就是因为这些刻板印象&#xff0c;老是被误以为是外国工程师搞出来的。 VeryCapture 之前小编…
阅读更多...
JavaScript之深入对象，详细讲讲构造函数与常见内置构造函数

JavaScript之深入对象，详细讲讲构造函数与常见内置构造函数

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;我是前端菜鸟的自我修养&#xff01;今天给大家详细讲讲构造函数与常见内置构造函数&#xff0c;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;原创不易&#xff0c;如果能帮助到带大家&#xff0c;欢迎…
阅读更多...
达梦数据库的系统视图v$deadlock_history

达梦数据库的系统视图v$deadlock_history

达梦数据库的系统视图v$deadlock_history 在达梦数据库&#xff08;DM Database&#xff09;中&#xff0c;V$DEADLOCK_HISTORY 视图记录了数据库中发生的死锁信息。通过查询这个视图&#xff0c;数据库管理员可以监控和诊断数据库中的死锁问题&#xff0c;从而采取相应的措施…
阅读更多...
鸿蒙认证值得考吗？

鸿蒙认证值得考吗？

鸿蒙认证值得考吗&#xff1f; 鸿蒙认证&#xff08;HarmonyOS Certification&#xff09;是华为为了培养和认证开发者在鸿蒙操作系统&#xff08;HarmonyOS&#xff09;领域的专业技能而设立的一系列认证项目。这些认证旨在帮助开发者和企业工程师提升在鸿蒙生态中的专业技能…
阅读更多...
最新文章

Copyright @ 2022~2023