首页 > 编程入门 文章详情

数据结构与算法—双向链表

编程入门 行业动态 更新时间:2024-10-21 12:52:08

<a href=https://www.elefans.com/category/jswz/34/1769880.html style=数据结构与算法—双向链表"/>

数据结构与算法—双向链表

目录

一、链表的分类

二、双向链表原理

三、实现双向链表 

1、声明链表结构体 

2、初始化链表

3、创建新节点

4、打印链表

5、头插&尾插

头插 

尾插

6、头删&尾删

头删

尾删

7、 查找节点

8、指定节点前插入

9、删除指定节点

10、销毁链表

完整版

Lisy.h 声明

List.c函数

text.c测试代码

一、链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构： 1. 单向或者双向 2. 带头或者不带头（头又叫哨兵位） 3. 循环或者非循环 虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
1. 无头单向非循环链表 ：结构简单，一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结构 ，如 哈希桶、图的邻接表 等等。另外这种结构在 笔试面试 中出现很多。 2. 带头双向循环链表 ：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多 优势 ，实现反而 简单了 ，后面我们代码实现了就知道了。

二、双向链表原理

 我们来对比单向链表的结构体，看一下与双向链表的结构体有什么区别：（左单向，右双向）

  1. 我们可以看出双向链表比单向链表多了一个结构体指针prev，它的作用是存储前一个结点的地址。
  2. 双向链表的每个节点既可以找到前一个节点，也可以找到后一个节点，
  3. 此外头节点和尾节点比较特殊，头节点的prev指向尾节点，尾节点的next指向头节点。
  4. 如果链表只有头节点（也叫哨兵位），那么它的prev和next都指向自己。 

三、实现双向链表 

1、声明链表结构体 

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;
  • 首先构建链表结构体，将链表结点的data数据类型设置别名LTDataType，方便后续修改。
  • 定义结构体名称的别名为LTNode。 
  • 指针next指向该节点的下一个节点，
  • 指针prev指向该节点的前一个节点。
  • LTDataType类型的data用于存值。

2、初始化链表

LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->prev = phead;phead->next = phead;return phead;
}
  • 函数的目的是创建一个空的双向链表并返回指向链表头部的指针。
  • 通过BuyLTNode( )函数为头节点开辟空间，头节点的data值为-1。（后续讲解）
  • 初始化时，prev和next均指向头节点。
  • 返回值为指针phead。

创建结构体指针，将初始化函数的返回值赋值给结构体指针，即为初始化完成，代码如下：

LTNode* plist = LTInit();

  这里也可以用二级指针接收链表地址初始化链表。

void LTInit(LTNode** phead)
{assert(phead);* phead = BuyLTNode(-1);(*phead)->prev = *phead;(*phead)->next = *phead;(*phead)->data = 0;
}

使用该函数初始化时，使用方法也有变化：

LTNode* plist;
LTInit(&plist);

3、创建新节点

LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL) {perror("malloc fail");return NULL;}newnode->data = x;newnode->prev = NULL;newnode->next = NULL;return newnode;
}
  •  使用malloc为新节点newnode开辟结构体LTNode大小的空间。
  • 开辟失败perror打印错误信息，函数提前结束。
  • 为新节点的data赋值为参数x的值，prev、next置空。
  • 返回新节点指针。

4、打印链表

void LTPrint(LTNode* phead)
{assert(phead);printf("guard<==>");LTNode* cur = phead->next;while (cur != phead) {if(cur!=phead->prev)printf("%d<==>", cur->data);elseprintf("%d\n", cur->data);cur = cur->next;}
}
  • assert检查链表是否为空，为空则报错。
  • 打印字符串 "guard<==>"，用于表示链表的头节点。
  • 指针cur指向头节点下一个节点，也就是第一个节点。
  • while循环的结束条件为cur指向头节点，双向链表尾部不为空，则循环遍历结束条件为尾结点的next指向头节点时。
  • 当cur不指向最后一个节点，打印节点之间的连接符号<==>。

5、头插&尾插

《头插&尾插 和 头删&尾删》我们都可以通过后续的指定位置前插入函数和删除函数实现， 这里进行讲解为了更好得熟悉理解双向链表。

头插 

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);LTNode* first = phead->next;
//下面两块代码的顺序可以颠倒，因为使用指针first储存了原来链表第一个元素的地址newnode->next = first;first->prev = newnode;phead->next = newnode;newnode->prev = phead;
}
  • assert检查链表是否为空，为空则报错。
  • 为新节点newnode开辟空间。
  • 指针first指向链表原第一个节点。
  • 将新节点的next指向原第一个节点，原第一个节点的prev指向新节点。
  • 头节点的next指向新节点，新节点的prev指向头节点。

 

 当然下面这种形式也对，只是后两个代码块不能调换顺序，具体原因大家可以画图试一下。

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);newnode->next = phead->next;phead->next->prev = newnode;newnode->prev = phead;phead->next = newnode;
}

尾插

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);LTNode* tail = phead->prev;newnode->next = phead;phead->prev = newnode;tail->next = newnode;newnode->prev = tail;
}
  • assert检查链表是否为空，为空则报错。
  • 为新节点newnode开辟空间。
  • 指针tail指向尾节点，直接通过头节点phead的prev即可找到尾节点。
  • 新节点的next指向头节点，头节点的prev指向新节点。
  • 原尾节点的next指向新节点，新节点的prev指向尾节点。

6、头删&尾删

头删

bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* first = phead->next;LTNode* second = first->next;second->prev = phead;phead->next = second;free(first);
}
  • 借助LTEmpty函数判断链表是否只有头节点，只有头节点则不进行删除。
  • 第一个assert检查链表是否为空，为空则报错。
  • 第二个assert通过LTEmpty函数返回值判断是否可以进行删除。
  • 定义两个指针first和second分别指向第一个节点和第二个节点。
  • 将第二个节点的prev指向头节点。
  • 头节点的next指向第二个节点。
  • 释放第一个节点的空间。

尾删

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;}
  • 第一个assert检查链表是否为空，为空则报错。
  • 第二个assert通过LTEmpty函数返回值判断是否可以进行删除。
  • 定义两个指针tail和tailPrev，分别指向尾节点和尾节点的前一个节点。
  • 释放尾节点的空间。
  • tailPrev的next指向头节点。
  • 头节点的prev指向tailPrev（新的尾节点）。

7、 查找节点

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;
}
  • assert检查链表是否为空，为空则报错。
  • 指针cur指向第一个节点。
  • 循环遍历链表，节点的data值为x时，返回该节点的地址。
  • 找不到则返回NULL。

8、指定节点前插入

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;
}
  • assert检查节点是否为空，为空则报错。
  • 指针prev指向pos节点的前一个节点。
  • 为新节点newnode开辟空间，节点的data值为x。
  • 将prev的next指向新节点，新节点的prev指向prev。
  • 新节点的next指向pos，pos的prev指向新节点。

9、删除指定节点

void LTErase(LTNode* pos)//可以判断phead是否等于哨兵位
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);
}
  • assert检查节点是否为空，为空则报错。
  • 定义两个指针posPrev和posNext分别指向 pos的前一个节点和 pos后一个节点。
  • 前一个节点posPrev的next指向posNext。
  • 后一个节点posNext的prev指向posPrev
  • 释放pos节点的空间。

10、销毁链表

void LTDestroy(LTNode** phead)
{assert(phead);assert(*phead);LTNode* cur = (*phead)->next;while (cur != *phead) {LTNode* next = cur->next;free(cur);cur = next;}free(*phead);*phead = NULL;
}
  • assert检查链表是否为空，为空则报错。
  • 检查链表头指针 *phead 是否为非空，为空则报错。
  • 指针cur指向第一个节点，循环内通过cur遍历每个节点。
  • next指针记录cur下一个节点，将cur的空间释放，cur更新为next，指向下一个节点。

  • 在循环结束后，链表中的所有节点都已经被销毁，最后一步是释放链表头指针 *phead 所占用的内存。

  • *phead = NULL 最后，将链表头指针设置为 NULL，以确保不再引用链表，避免悬挂指针或野指针的问题。

完整版

完整版代码我保留了注释，方便读者学习，以下代码的功能经测试没有问题，放心使用。 

Lisy.h 声明

#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;//初始化链表
LTNode* LTInit();
//void LTInit(LTNode** phead);//打印链表
void LTPrint(LTNode* phead);//头插&尾插
void LTPushFront(LTNode* phead, LTDataType x);
void LTPushBack(LTNode* phead, LTDataType x);//头删&尾删
void LTPopFront(LTNode* phead);
void LTPopBack(LTNode* phead);//查找值为x的节点，返回节点地址
LTNode* LTFind(LTNode* phead, LTDataType x);//在指定节点前插入
void LTInsert(LTNode* pos, LTDataType x); //删除指定节点
void LTErase(LTNode* pos);//销毁链表
void LTDestroy(LTNode** phead);

List.c函数

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"//创建新节点
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL) {perror("malloc fail");return NULL;}newnode->data = x;newnode->prev = NULL;newnode->next = NULL;return newnode;
}//初始化链表
LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->prev = phead;phead->next = phead;return phead;
}
//void LTInit(LTNode** phead)
//{
//	assert(phead);
//	* phead = BuyLTNode(-1);
//	(*phead)->prev = *phead;
//	(*phead)->next = *phead;
//	(*phead)->data = 0;
//}//打印链表
void LTPrint(LTNode* phead)
{assert(phead);printf("guard<==>");LTNode* cur = phead->next;while (cur != phead) {if(cur!=phead->prev)printf("%d<==>", cur->data);elseprintf("%d\n", cur->data);cur = cur->next;}
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{LTInsert(phead->next, x);
}//void LTPushFront(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	LTNode* newnode = BuyLTNode(x);
//	LTNode* first = phead->next;
//	//下面两块代码的顺序可以颠倒，因为使用指针first储存了原来链表第一个元素的地址
//	newnode->next = first;
//	first->prev = newnode;
//
//	phead->next = newnode;
//	newnode->prev = phead;
//}//void LTPushFront(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	LTNode* newnode = BuyLTNode(x);
//
//	newnode->next = phead->next;
//	phead->next->prev = newnode;
//
//	newnode->prev = phead;
//	phead->next = newnode;
//}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTInsert(phead, x);
}
//void LTPushBack(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	LTNode* newnode = BuyLTNode(x);
//	LTNode* tail = phead->prev;
//	
//	newnode->next = phead;
//	phead->prev = newnode;
//
//	tail->next = newnode;
//	newnode->prev = tail;
//}//监测链表是否为空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->next);
}//void LTPopFront(LTNode* phead)
//{
//	assert(phead);
//	assert(!LTEmpty(phead));
//
//	LTNode* first = phead->next;
//	LTNode* second = first->next;
//
//	second->prev = phead;
//	phead->next = second;
//	free(first);
//}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->prev);
}//void LTPopBack(LTNode* phead)
//{
//	assert(phead);
//	assert(!LTEmpty(phead));
//	//LTErase(phead->prev);
//
//	LTNode* tail = phead->prev;
//	LTNode* tailPrev = tail->prev;
//
//	free(tail);
//	tailPrev->next = phead;
//	phead->prev = tailPrev;
//
//}//查找值为x的节点，返回节点地址
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;
}//在指定节点前插入，与LTFind搭配使用
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;
}// 删除指定节点
void LTErase(LTNode* pos)//可以判断phead是否等于哨兵位
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);
}//销毁链表
void LTDestroy(LTNode** phead)
{assert(phead);assert(*phead);LTNode* cur = (*phead)->next;while (cur != *phead) {LTNode* next = cur->next;free(cur);cur = next;}free(*phead);*phead = NULL;
}

text.c测试代码

#include "List.h"void test1() {/*LTNode* plist;LTInit(&plist);*/LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPushBack(plist, 888);LTPushBack(plist, 888);LTPopFront(plist);LTPopBack(plist);LTNode* pos = LTFind(plist, 888);LTInsert(pos, 999);LTErase(pos);LTPrint(plist);LTDestroy(&plist);
}int main()
{test1();return 0;
}

更多推荐

数据结构与算法—双向链表

本文发布于:2023-12-05 18:37:57，感谢您对本站的认可！
本文链接:https://www.elefans.com/category/jswz/34/1664980.html
版权声明:本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
本文标签：数据结构   双向   算法   链表

发布评论

评论列表 （有 0 条评论）

最近发表

草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍！

热门文章

标签列表