首页 > 其他分享 >数据结构-双向链表

数据结构-双向链表

时间：2024-10-21 21:49:30浏览次数：3  
标签：prev pos next 链表 LTNode phead 双向 newnode 数据结构

一 概念与结构

193ebf0e600e4762b6cc5bf515dd6a10.png

带头双向循环链表

注意：这⾥的“带头”跟前⾯我们说的“头结点”是两个概念，带头链表⾥的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这⾥“放哨的。

如果，带头的链表中，只有头节点，我们就称该链表为空链表。

二 双向链表的实现

创建一个新项目，并创建三个新文件，分别是：头文件 List.h ,源文件 List.c , test.c (测试文件）。

2.1 链表的初始化

把链表初始化为空。

前面我们提过，哨兵位不存储任何有效的元素

所以我们让链表的next指针和prev指针都指向他自己

ed6b837ff799413eb0c00145f34cf3ae.png

因为后面代码都需要用到申请一个新的节点，所以我们单独封装一个函数 buyNode 用来申请节点。

代码：

LTNode* buyNode(LTDatatype x) {
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	node->data = x;
	node->next = node->prev = node;
	return node;
}

初始化代码：

//初始化
LTNode* LTInit() {
	LTNode* phead = buyNode(-1);
	return phead;
}

便于测试，我们写一个打印链表的函数： 

代码：

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

2.2 尾插

在双向链表中，我们申请一个新的节点，就要修改它的前驱指针和 next 指针。比如，我们要在该链表的尾部插入一个新的节点99，我们要让 newnode 的 prev 指针 指向它前面的节点，newnode 的 next 指针指向哨兵位。

d47c4382a2364444a54a59c2e487a062.png

对于原链表，我们要修改哨兵位的 prev 指针和 d3 节点的 next 指针。即让 d3 的 next 指针指向 newnode ,让 phead 的 prev 指针指向 newnode 。

daca7bfb77af4804b6b29ef68c70cd8a.png

代码：

//尾插
void LTPushBack(LTNode* phead, LTDatatype x) {
	LTNode* newnode = buyNode(x);
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev->next = newnode;
	phead->prev = newnode;
}

测试结果：

62f11177ee1640ddacd2c156877d6c9f.png

2.3 头插

在第一个有效节点之前插入节点。

PS:在哨兵位之前插入节点不叫头插，是尾插。

从下图我们可以看出来，头插时受到影响的节点是 哨兵位 节点和 d1 节点。

f114bea490eb47139c4c564f1c33d1a0.png

newnode 插入之后，newnode变成第一个有效的节点，所以对于 newnode 来说，它的 next 指针要指向它的下一个节点 d1,它的prev 指针要指向 它的前一个结点，也就是 哨兵位。​​​​​对于 d1 来说，它的 prev 指针也要指向 newnode ，对于哨兵位来说，它的的 next 指针要指向 newnode 。

f6509db7573b488792a01f638db9baf3.png

代码：

//头插
void LTPushFront(LTNode* phead, LTDatatype x) {
	assert(phead);
	LTNode* newnode = buyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

 测试结果：

c878d37162764ba0b81b6ccde5009730.png

2.4 判断链表是否为空

前面已经提过 如果哨兵位的 next 指针指向自己说明链表为空

代码：

bool LTEmpty(LTNode* phead) {
	assert(phead);
	return phead->next == phead;
	//如果这个表达式为真说明链表为空 
}

2.5尾删

如果我们要删除（最后一个节点） d3 节点，那么 哨兵位 和 d2 节点会受到影响。

b94cc9fbad694d42b0bb45a4c6e7cb41.png

d2 节点的 next 指针原本是指向 d3 节点的，现在把 d3 节点删除，那么 d2 节点的 next 指针就要指向 哨兵位。原本 哨兵位 的 prev 指针是指向 d3 节点的，现在我们要把 d3 节点删除，那么 哨兵位 的 prev 指针，就要指向 d2 节点。

b2e041c59ea54de69f03e4d4c0676e4a.png

代码;

//尾删
void LTPopBack(LTNode* phead) {
	assert(!LTEmpty(phead));
	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

测试结果：

3dfd04a63a134b32ba9f3d7f233f1953.png

2.6 头删

如果我们要删除（第一个节点） d1 节点，那么 哨兵位 的 next 指针会受到影响和 d2 节点的 prev指针会受到影响。

f3d6e8e0fec641ebbc12183b734879a4.png

原本 d2 节点的 prev 指针原本是指向 d1 节点的，现在把 d1 节点删除，那么 d2 节点的 prev指针就要指向 哨兵位。 哨兵位 的 next 指针是指向 d1 节点的，现在我们要把 d1 节点删除，那么 哨兵位 的 next 指针，就要指向 d2 节点。 

b8dd658f28c2428494b99ac7c5bfbe10.png

代码:

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

测试结果：

2d058a7eb14549ebaa51a436d2afffd9.png

2.7 查找某个数据在链表中的位置

从第一个有效节点开始寻找，如果找到了，返回皮粗如，没找到就继续遍历，直到 pcur 和 phead相等，如果 pcur = phead 说明没找到，跳出循环，返回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;//没找到 返回空
}

 测试结果：

 f4fee4f1b8884788968ef818d2ec2e66.png

2.8 在pos位置之后插⼊数据在pos 位置后插入

 如果在 pos 节点后插入新的节点 newnode ，d2 的 next 指针与 d3 的 prev 指针会受到影响。

1d7a68d5c48045afb1a8fef8fa9b1dfb.png

如果在 pos 位置后插入新节点，那么 pos 的 next 指针应该指向新节点 newnode ，d3 的 prev 指针应该指向 newnode。让 newnode 的 prev 指针指向 pos ，newnode 的 next 节点指向 d3。

211f3f3e098648079521c00370c2c288.png

代码：

//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDatatype x) {
	assert(pos);
	LTNode* newnode = buyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}

测试结果：

6e800d8608274ea4a748abd9266533cc.png

2.9 删除pos位置的数据

如果我们要删除 d1 节点，那么 哨兵位 的 next 指针会受到影响和 d2 节点的 prev指针会受到影响。

d45160b2a6c448c6aec2a91f1c88e0ed.png

原本 d2 节点的 prev 指针原本是指向 d1 节点的，现在把 d1 节点删除，那么 d2 节点的 prev指针就要指向 哨兵位。原本 哨兵位 的 next 指针是指向 d1 节点的，现在我们要把 d1 节点删除，那么 哨兵位 的 next 指针，就要指向 d2 节点。 

1d0cf08ca6dc49d58aa2d1101f230db9.png

代码：

//删除pos位置的数据
void LTErase(LTNode* pos) {
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

测试结果：

15621ef94edf4136af1e221374dd160a.png

2.10 销毁链表 

 销毁链表，我们需要从头节点开始销毁，如果我们要删除 d1 ，我们需要提前把 d1 后面的节点保存下来，避免删除 d1 后，找不到后面的内容。

104c8f562c974c8193ee6eec1f4140e8.png

我们建立一个循环，当 pcur = phead 时，说明我们把链表中所有的有效节点都删除了，然后在单独释放哨兵位。由于我们传的参数是一级指针，而形参的改变不会影响实参，所以我们要在测试数据时对plist进行释放。

6a2661e8a1d94209ba8de8deec7532cc.png

代码:

//销毁链表
void LTDesTroy(LTNode* phead) {
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}

1d148277b0ae4aee8613281a5a895396.png

全部代码

List.h代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDatatype;

//定义双向链表结构
typedef struct ListNode {
	LTDatatype data;
	struct ListNode* next;//指向下一个节点的指针
	struct ListNode* prev;//指向前一个节点的指针
}LTNode;
//初始化
LTNode* LTInit();
//打印链表
void LTPrint(LTNode* phead);
//判断是否为空
bool LTEmpty(LTNode* phead);
//尾插
//因为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);
//在pos位置之后插⼊数据----pos位置之前插入代码基本是一样的（双向的）
void LTInsert(LTNode* pos, LTDatatype x);
//删除pos位置的数据
void LTErase(LTNode* pos);
//销毁链表
void LTDesTroy(LTNode* phead);

List.c代码

#include"List.h"
//添加节点
LTNode* buyNode(LTDatatype x) {
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	node->data = x;
	node->next = node->prev = node;
	return node;
}
//初始化
LTNode* LTInit() {
	LTNode* phead = buyNode(-1);
	return phead;
}
//打印链表
void LTPrint(LTNode* phead) {
	LTNode* pcur = phead->next;
	while (pcur != phead) {
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
//判断链表是否为空
bool LTEmpty(LTNode* phead) {
	assert(phead);
	return phead->next == phead;
	//如果这个表达式为真说明链表为空 
}
//尾插
void LTPushBack(LTNode* phead, LTDatatype x) {
	LTNode* newnode = buyNode(x);
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev->next = newnode;
	phead->prev = newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDatatype x) {
	assert(phead);
	LTNode* newnode = buyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}
//尾删
void LTPopBack(LTNode* phead) {
	assert(!LTEmpty(phead));
	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}
//头删
void LTPopFront(LTNode* phead) {
	assert(!LTEmpty(phead));
	LTNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	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;//没找到 返回空
}
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDatatype x) {
	assert(pos);
	LTNode* newnode = buyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}
//删除pos位置的数据
void LTErase(LTNode* pos) {
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}
//销毁链表
void LTDesTroy(LTNode* phead) {
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}

test.c代码 

#include"List.h"

void test(){
	LTNode* plist = LTInit();
	//尾插
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	//销毁链表
	LTDesTroy(&plist);
	plist = NULL;
	LTPrint(plist);

	//查找某个数据在链表中的位置
	/*LTNode* find = LTFind(plist, 2);
	if (find == NULL) {
		printf("没找到\n");
	}
	else {
		printf("找到了\n");
	}
	LTErase(find);
	LTPrint(plist);*/
	//在pos位置之后插⼊数据
	//LTInsert(find, 88);
	
	//头删
	/*LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);*/
	//尾删
	/*LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);*/
	
	//头插
	/*LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);*/
	
}
int main() {
	test();
	return 0;
}

祝大家生活愉快。 

 

标签：prev,pos,next,链表,LTNode,phead,双向,newnode,数据结构
From： https://blog.csdn.net/2303_80645930/article/details/143021379

相关文章

  • 数据结构——队列
    目录1>>导言2>>队列的结构3>>初始化4>>打印5>>入列6>>出列6.1>>判断是否为空7>>取队头和队尾数据and统计个数8>>队列销毁9>>三个文件代码queue.hqueue.ctest.c10>>总结1>>导言    在把栈学习完后，步入新的章节——队列，队列是一种特殊的线性表，队列是......
  • 【数据结构】动态规划：揭开算法优化的秘密
    在算法世界中，动态规划（DynamicProgramming,DP）无疑是一个充满魅力的思想，特别是在解决复杂的优化问题时，它展现出了极大的威力。它不仅能优化问题的求解速度，还能通过减少重复计算来提高效率。然而，对于很多初学者来说，动态规划常常显得有些晦涩难懂。本文将通过浅显的例子，帮助你......
  • 新高一暑假第一期集训恢复性训练【数据结构-并查集】（补）
    新高一暑假第一期集训恢复性训练【数据结构-并查集】（补）C.[POJ1417]TrueLiars先将题目中的好人和坏人转换一下，也即是如果\(x\)说\(y\)是好人，则他们两属于同一组，反之则不属于同一组。然后我们可以想到带权的并查集，用\(val_x\)代表\(x\)与其父节点的关系，当\(val_x\)......
  • K个节点翻转链表
    概述起因：leetcode题目25.K个一组翻转链表问题描述给你链表的头节点head，每k个节点一组进行翻转，请你返回修改后的链表。k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值......
  • 数据结构_day5（完结）
    目录7.树7.1特性7.1.1什么是树7.1.2关于树的一些术语7.2二叉树7.2.1什么是二叉树7.2.2二叉树性质（重点）7.2.3满二叉树和完全二叉树7.2.4二叉树的存储结构7.3二叉树的链式存储7.4层次遍历哈夫曼树Huffman图1.什么是图2.图的基本概念3.图的分类3.1......
  • 【趣学C语言和数据结构100例】
    【趣学C语言和数据结构100例】问题描述51.在一个递增有序的单链表中，存在重复的元素。设计算法删除重复的元素，例如(7.10.10.21.30.42.42.42.51.70)将变为(7.10.21.30.42.51.70)。52.设A和B是两个单链表(带头结点)，其中元素递增有序。设计一个算法从A和B中的公共元素产......
  • 408数据结构-折半查找，分块查找 自学知识点整理
    前置知识：查找的基本概念折半查找折半查找又称二分查找，它仅适用于有序的顺序表。因个人习惯，下文均用二分代替折半。二分查找的基本思想：首先将给定值ke......
  • 【数据结构】队列
    ......
  • c#数据结构06_队列
    说明（此系列帖子记录数据结构学习成果,如侵犯视频作者权益，立删)视频链接:离忧夏天C#数据结构本文实现队列需要用到动态数组ArrayList和单链表的相关知识，详细请看：C#数据结构专栏文章目录一：队列的基本概念二：队列的基本操作三：队列的实现1.数组队列(由动态数组实现)2.循环......
  • 数据结构与算法
    数据结构：研究数据在内存中存储的结构算法：实现增删改查的方法解决问题的实际方法算法的好坏评价标准：时间复杂度和空间复杂度时间复杂度：算法所用时间的一个映射时间复杂度得出的是一个数学问题数据总量x(x足够大)，从而消耗的执行次数y之间存在的关系LeetCode算法题......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99