您现在的位置是：首页 >学无止境 >来领略一下带头双向循环链表的风采吧网站首页学无止境
来领略一下带头双向循环链表的风采吧
简介来领略一下带头双向循环链表的风采吧
文章目录
?前言
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
上期阿博带友友们实现了单链表,我们可以看出单链表的尾插以及尾删都是非常复杂的，比如尾插：如果链表为空，我们就需要调用二级指针改变来接收plist的地址，因为首次尾插，plist为空，我们要让plist指向结点，需要改变plist,所以传plist的地址，但是之后，我们只需要改变结构体中的next指针，让它指向我们开辟出来的结点就可以了，此时我们改变的是结构体，就不需要传结构体地址了。再比如我们的尾删：我们需要遍历链表，找到尾结点的前一个结点，这样非常麻烦，而且效率很低，但是双向循环链表就会方便很多，我们可以直接通过尾结点的prev指针找到它的前一个结点，我们尾插的时候就不用再判断链表是否为空了，因为就算链表为空，头、尾结点也不为空，它们此时都是哨兵位，我们尾插的时候改变的一直都是结构体的next指针.
?双向循环链表
?1.链表的定义
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* prev;
struct ListNode* next;
}LTNode;
?2.链表的初始化
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;
}
LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
?误区
❌错误案例
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;
}
void LTInit(LTNode*phead)
{
phead = BuyLTNode(-1);
phead->next = phead;
phead->prev = phead;
}
⛳友友们，这里我们通过调试也可以看出plist的值并没有被改变，因为我们传的是plist的值，所以形参的改变不会影响实参，形参只是实参的一份临时拷贝，这里我们要改变的是plist，所以我们要传plist的地址，但是我们还可以通过通过返回值的方式来让plist接收newnode,这种就是值拷贝的方式返回，就是先把newnode的值拷贝给pilst,然后它又是一个局部变量，出完函数作用域就销毁了，但是我们通过plist找到那个开辟出来的结点，因为它在堆区上存放，所以出完函数作用域，那个结点并没有销毁.
?3.链表的尾插
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;
}
void PushBack(LTNode* phead, LTDataType x)
{
assert(phead); //就算链表为空，这里也一定不能为空，因为phead是带哨兵位的头结点。
LTNode* tail = phead->prev;
LTNode* newnode = BuyLTNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
//LTInsert(phead,x);
}
?4.链表的头插
1.未定义指针版
void PushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyLTNode(x);
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
?注意先后顺序
2.定义指针版
void PushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyLTNode(x);
LTNode* first = phead->next;
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
//LTInsert(phead->next,x);
}
?5.链表的打印
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("guard<==>");
while (cur != phead)
{
printf("%d<==>",cur->data);
cur = cur->next;
}
printf("
");
}
?6.链表的尾删
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
void PopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
tailPrev->next = phead;
phead->prev = tailPrev;
free(tail);
//LTErase(phead->prev);
}
所以友友们这里我们就可以定义一个布尔值，来判空，这样可以提高我们代码的可读性?.
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
友友们注意这里是个等号，不是赋值号，因为空链表是phead->next和phead相等，而不是赋值.
?7.链表的头删
void PopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* cur = phead->next;
phead->next = cur->next;
cur->next->prev = phead;
free(cur);
//LTErase(phead->next);
}
这里我们也可以定义两个指针来提高我们代码的可读性???.
?8.链表的查找
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;
}
友友们注意，这里我们让cur从phead->next处开始遍历，因为哨兵位的头结点不存储有效数据.这个函数同时兼具修改的功能，因为它可以返回结点的地址.
?9.链表任意位置的插入（在pos之前插入）
1.未定义指针版
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;
}
?注意先后顺序
2.定义指针版
友友们，当我们这个函数写好之后，我们的
头插和尾插就可以附用这个函数了，头插就可以写成LTInsert(phead->next,x),尾插就可以写成LTInsert(phead,x),⛳友友们一定要注意尾插不是LTInsert（phead->prev,x）,因为我们是在pos之前插入的，所以我们pos的位置必须是头结点.
?10.链表任意位置的删除（pos位置）
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
友友们，当我们这个函数写好之后，我们的
头删和尾删就可以附用这个函数了，头删就可以写成LTErase（phead->next）,尾删就可以写成LTErase（phead->prev）.
?11.链表的销毁
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
//cur = cur->next; 这里cur已经被释放了，不能在使用了，否则就是野指针
cur = next;
}
free(phead);
//phead = NULL; 这里置空也没用，因为phead是一级指针，形参的改变不会影响实参，就算把它置空，plist也不会被改变.
}
友友们注意，这里phead=NULL对plist是无效的，因为它们是值传递，形参只是实参的一份临时拷贝，形参的改变不会影响实参.所以我们可以在外面把plist置空，当我们头插，尾插之后一定要注意及时释放，否则就会出现内存泄露.
?List.h代码
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* prev;
struct ListNode* next;
}LTNode;
LTNode* LTInit(); //初始化链表
void LTPrint(LTNode* phead); //打印链表
void PushBack(LTNode* phead, LTDataType x); //尾插
void PushFront(LTNode* phead, LTDataType x); //头插
bool LTEmpty(LTNode* phead);
void PopFront(LTNode* phead); //头删
void PopBack(LTNode* phead); //尾删
LTNode* LTFind(LTNode* phead, LTDataType x); //链表的查找
//在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos); //删除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->next = NULL;
newnode->prev = NULL;
return newnode;
}
LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("guard<==>");
while (cur != phead)
{
printf("%d<==>",cur->data);
cur = cur->next;
}
printf("
");
}
void PushBack(LTNode* phead, LTDataType x)
{
assert(phead); //就算链表为空，这里也一定不能为空，因为phead是带哨兵位的头结点。
LTNode* tail = phead->prev;
LTNode* newnode = BuyLTNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
//LTInsert(phead,x);
}
void PushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyLTNode(x);
/*newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;*/
//这里我们也可以提前记录下一结点的地址，这样就不用在意顺序了.
LTNode* first = phead->next;
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
//LTInsert(phead->next,x);
}
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
void PopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* cur = phead->next;
phead->next = cur->next;
cur->next->prev = phead;
free(cur);
//LTErase(phead->next);
}
void PopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
tailPrev->next = phead;
phead->prev = tailPrev;
free(tail);
//LTErase(phead->prev);
}
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;
}
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)
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
//cur = cur->next; 这里cur已经被释放了，不能在使用了，否则就是野指针
cur = next;
}
free(phead);
//phead = NULL; 这里置空也没用，因为phead是一级指针，形参的改变不会影响实参，就算把它置空，plist也不会被改变.
}
?test.c代码
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void TestList1()
{
LTNode* plist = LTInit();
PushBack(plist, 1);
PushBack(plist, 2);
PushBack(plist, 3);
PushBack(plist, 4);
LTPrint(plist);
PopBack(plist);
LTPrint(plist);
PopBack(plist);
LTPrint(plist);
LTDestroy(plist);
plist = NULL;
}
void TestList2()
{
LTNode* plist = LTInit();
PushFront(plist, 1);
PushFront(plist, 2);
PushFront(plist, 3);
PushFront(plist, 4);
PopFront(plist);
LTNode* pos = LTFind(plist, 3);
if (pos)
{
LTInsert(pos, 30);
}
LTPrint(plist);
LTDestroy(plist);
plist = NULL;
}
int main()
{
TestList1();
TestList2();
return 0;
}
?代码效果展示
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述