数据结构之带头双向链表（易学版）

2024-03-19 16:20
文章标签 链表 数据结构 双向 易学 带头

本文主要是介绍数据结构之带头双向链表（易学版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1.问题引入

2.结构实现

2.3.1接口实现

2.3.2函数实现

3.总结


，又和大家见面了，今天要给大家分享的是双链表的知识，跟着我的脚步，包学包会哦~

规矩不乱，先赞后看！

ps：（孙权劝学）

1.问题引入

前期学习了单链表，我们尝到了它的甜头，但是容易越界访问这一个问题也是时有出现的，因此也是相对比较棘手的，为了解决这一个问题，特此向大家介绍带头双向链表

带头双向链表，顾名思义含有哨兵位，同时一个节点有两个指针（next / prev），这样的好处是让相邻指针的联系更加紧密，同时将首尾节点相连是其能够非常容易实现找尾。

话不多说，直接上代码！

2.结构实现

2.3.1接口实现

先在头文件（List.h)上进行顺序表结构的创建和对各函数的声明，目的是为了把各部分区分开，使程序便于理解，能清楚的看到各部分对于的作用和功能。

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>  
#include<stdbool.h>typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;}LTNode;bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
LTNode* LTInit();
void LTPopFront(LTNode* phead);
void PushFront(LTNode* phead, LTDataType x);
void LTPrint(LTNode* phead);
LTNode* BuyLTNode(LTDataType x);
void LTPopBack(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDataType x);
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);

2.3.2函数实现

接着下来是单链表各函数的函数部分，我们在List.c中完成：

a.创造新节点

LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}

这些步骤都是和链表一模一样的。

b.初始化链表

LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

都是链表的一套固定公式

c.查找链表

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}

d.在链表中插入节点

由于有了双链表，使得插入十分轻松，同时这一个函数就能简化头插和尾插两个函数，是相当方便的

//在pos前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyLTNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;}

e.在链表中删除节点

void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;posprev->next = posnext;posnext->prev = posprev;free(pos);pos = NULL;
}

有了这个函数，也可以让头删和尾删变得相当的简洁。

f.判断链表是否为空

bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

由于头删尾删会改变链表，因此需要一个判空函数来保证程序的安全性

g.头插尾插

//尾插
void LTPushBack(LTNode* phead, LTDataType x)//不需要二级指针（没有改变phead）
{assert(phead);//LTNode* newnode = BuyLTNode(x);//LTNode* tail = phead->prev;//tail->next = newnode;//newnode->next = phead;//newnode->prev = tail;//phead->prev = newnode;LTInsert(phead, x);}//头插
//头插---指的是插在头结点之后，首个含数据的结点之前
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);//LTNode* newnode = BuyLTNode(x);//phead->next->prev = newnode;//newnode->next = phead->next;//phead->next = newnode;//newnode->prev = phead;////香饽饽LTInsert(phead->next, x);
}

注释掉的是没有依靠Insert和Erase函数来写的头插尾插，是相当麻烦的，通过那两个函数，能让你不到10分钟就能写出双链表。

h.头删尾删

void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//LTNode* tail = phead->prev;//LTNode* tailprev = tail->prev;//free(tail);//tailprev->next = phead;//phead->prev = tailprev;LTErase(phead->prev);}void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//if (phead->next->next == NULL)//{//	phead->next = phead;//	phead->prev = phead;//}//else//{//	LTNode* cur = phead->next;//	LTNode* af = phead->next->next;//	assert(cur);//	assert(af);//	phead->next = af;//	af->prev = phead;//	free(cur);//	cur = NULL;//}LTErase(phead->next);}

i.打印链表

 


void LTPrint(LTNode* phead)
{assert(phead);printf("guard<==>");LTNode* cur = phead->next;while (cur != phead){printf("%d<==>", cur->data);cur = cur->next;}printf("\n");
}

j.销毁链表

程序执行完毕后需要销毁程序，这样才不会出现内存问题

void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//LTNode* tail = phead->prev;//LTNode* tailprev = tail->prev;//free(tail);//tailprev->next = phead;//phead->prev = tailprev;LTErase(phead->prev);}void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//if (phead->next->next == NULL)//{//	phead->next = phead;//	phead->prev = phead;//}//else//{//	LTNode* cur = phead->next;//	LTNode* af = phead->next->next;//	assert(cur);//	assert(af);//	phead->next = af;//	af->prev = phead;//	free(cur);//	cur = NULL;//}LTErase(phead->next);}

2.3测试程序

实现完函数之后还需要对其进行测试

#include"List.h"void TestList1()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPopFront(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTDestroy(plist);plist = NULL;}
void TestList2()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPopFront(plist);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){LTInsert(pos, 30);}LTPrint(plist);LTDestroy(plist);plist = NULL;
}int main()
{TestList1();TestList2();return 0;
}

最后在终端上运行一遍得到结果

 结果是这样的小伙伴就是正确掌握了的哟

如果没有跑起来的uu们也不用担心，细心调试一下，慢慢找错也是一种成长。 

3.总结

链表的学习我认为是一个先苦后甜的过程，把单链表的原理搞懂之后，再使用双链表就完全是如鱼得水了。学习也是一样，先吃苦，以后才能尝到生活的甜头。

最后关于链表的问题，我强烈建议大家刷题巩固，踏实稳重，才能把数据结构这个难关拿下。

这篇关于数据结构之带头双向链表（易学版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/826585。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2