前言:
之前我们已经学习了单链表,有了单链表的基础,现在开始学习带头双向循环链表~
一、介绍带头双向循环链表
1.带头双向循环链表的结构
结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单。
2.带头双向循环链表的功能
单链表可以实现对数据的增删查改,带头双向循环链表也同样能做到,而且实现起来比单链表简单得多。
二、实现带头双向循环链表
1.创建节点的结构
一个节点的结构:
存放数据:data
前指针:prev
后指针:next
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}LTNode;
2.函数的声明
//创建一个新节点
LTNode* BuyListNode(LTDataType x);
//初始化哨兵位节点
LTNode* LTInit();
//打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置前插入
void LTInsert(LTNode* pos, LTDataType x);
//在pos位置删除
void LTErase(LTNode* pos);
//销毁
void LTDestroy(LTNode* phead);
2.函数的实现
(1)创建一个新节点
这里与单链表的实现的方式是一样的,多了一个前指针(prev)。
LTNode* BuyListNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->next = NULL;
newnode->prev = NULL;
newnode->data = x;
return newnode;
}
(2)初始化哨兵位(带头)节点
刚开始给头指针初始化为哨兵位节点,方便后面可以直接连接新节点。不需要用二级指针。
LTNode* LTInit()
{
LTNode* phead = BuyListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
(3)打印链表
定义一个指针变量cur为哨兵位的下一个节点,也就是第一个节点。然后遍历链表,只要cur不是phead(哨兵位),就打印节点的数据。
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("phead<=>");
while (cur != phead)
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("\n");
}
(4)尾插
双向链表的尾插比单链表要简单多了。单链表尾插新节点要从头开始遍历找尾,双向链表的尾就是哨兵位的前一个节点。然后尾节点与新节点连接,新节点与哨兵位连接就行了。
刚开始没有节点(除了哨兵位)也是一样的
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = BuyListNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
(5)尾删
这里要多断言一句代码,哨兵位的下一个节点不能等于它自己,因为只有一个哨兵位就说明没有其他节点,不能再删了。
还是定义一个指针变量为尾节点,再定义一个为尾节点的前一个节点,free释放掉尾节点,然后尾节点的前一个节点与哨兵位连接起来。
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;
}
(6)头插
定义一个指针变量first为哨兵位的下一个节点(可能是空),然后新节点与first连接,first与哨兵位连接,思路和单链表的头插如出一辙。
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* first = phead->next;
LTNode* newnode = BuyListNode(x);
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}
(7)头删
与尾删相同,为了防止没有节点了(除了哨兵位)不能再删,所以要对哨兵位下一个节点不能为自己就行断言。
定义一个变量first为第一个节点,另一个变量second为第二个节点(如果只有一个节点,second指向的是哨兵位),free释放first,然后哨兵位与second连接。
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* first = phead->next;
LTNode* second = first->next;
free(first);
phead->next = second;
second->prev = phead;
}
(8)查找
与单链表的查找基本相同,从哨兵位的下一个节点开始找,当循环到哨兵位就停下,找到返回这个节点,否则返回NULL
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;
}
(9)在pos位置前插入
首先要对pos进行断言,判断除了哨兵位是否还有其他节点。
定义一个变量posPrev为pos的前一个节点,然后posPrev与新节点连接,新节点与pos连接。
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* posPrev = pos->prev;
posPrev->next = newnode;
newnode->prev = posPrev;
newnode->next = pos;
pos->prev = newnode;
}
(10)在pos位置删除
定义两个变量分别为pos前后的节点,free释放pos,连接两个前后节点
文章来源:https://www.toymoban.com/news/detail-689307.html
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
free(pos);
posPrev->next = posNext;
posNext->prev = posPrev;
}
(11)销毁
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
三、全部代码
1.List.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}LTNode;
//创建一个新节点
LTNode* BuyListNode(LTDataType x);
//初始化哨兵位节点
LTNode* LTInit();
//打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置前插入
void LTInsert(LTNode* pos, LTDataType x);
//在pos位置删除
void LTErase(LTNode* pos);
//销毁
void LTDestroy(LTNode* phead);
2.List.c
#include "List.h"
//创建一个新节点
LTNode* BuyListNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->next = NULL;
newnode->prev = NULL;
newnode->data = x;
return newnode;
}
//初始化哨兵位节点
LTNode* LTInit()
{
LTNode* phead = BuyListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
//打印
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("phead<=>");
while (cur != phead)
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("\n");
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = BuyListNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
//尾删
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* first = phead->next;
LTNode* newnode = BuyListNode(x);
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}
//头删
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* first = phead->next;
LTNode* second = first->next;
free(first);
phead->next = second;
second->prev = phead;
}
//查找
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;
}
//在pos位置前插入
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* posPrev = pos->prev;
posPrev->next = newnode;
newnode->prev = posPrev;
newnode->next = pos;
pos->prev = newnode;
}
//在pos位置删除
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
free(pos);
posPrev->next = posNext;
posNext->prev = posPrev;
}
//销毁
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
3.Test.c
#include "List.h"
void test()
{
LTNode* plist = LTInit();
LTPushBack(plist, 11);
LTPushBack(plist, 12);
LTPushBack(plist, 13);
LTPushBack(plist, 14);
LTPushBack(plist, 15);
LTPrint(plist);
LTPopBack(plist);
LTPopBack(plist);
LTPopBack(plist);
LTPrint(plist);
LTPushFront(plist, 99);
LTPushFront(plist, 89);
LTPushFront(plist, 79);
LTPushFront(plist, 69);
LTPushFront(plist, 59);
LTPrint(plist);
LTPopFront(plist);
LTPopFront(plist);
LTPrint(plist);
LTNode* pos1 = LTFind(plist, 11);
{
if (pos1)
{
LTInsert(pos1, 666);
}
}
LTPrint(plist);
LTNode* pos2 = LTFind(plist, 89);
{
if (pos2)
{
LTErase(pos2);
}
}
LTPrint(plist);
LTDestroy(plist);
}
int main()
{
test();
return 0;
}
感谢观看~文章来源地址https://www.toymoban.com/news/detail-689307.html
到了这里,关于【数据结构】实现带头双向循环链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!