一、帶頭雙向循環(huán)鏈表的定義
帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來很多優(yōu)勢。
帶頭雙向循環(huán)鏈表包括一個(gè)帶有哨兵位的頭節(jié)點(diǎn)，該節(jié)點(diǎn)既可以作為鏈表的第一個(gè)節(jié)點(diǎn)，也可以作為鏈表的最后一個(gè)節(jié)點(diǎn).
這種鏈表的特點(diǎn)是每個(gè)節(jié)點(diǎn)都有兩個(gè)指針，一個(gè)指向前一個(gè)節(jié)點(diǎn)，一個(gè)指向后一個(gè)節(jié)點(diǎn)，這樣就可以實(shí)現(xiàn)雙向遍歷。
同時(shí)，鏈表的最后一個(gè)節(jié)點(diǎn)的后繼指針指向頭節(jié)點(diǎn)，形成了循環(huán)的結(jié)構(gòu)。這樣，我們可以在任意一個(gè)節(jié)點(diǎn)上進(jìn)行前后移動(dòng)，插入和刪除操作，而不需要像單鏈表那樣遍歷整個(gè)鏈表去找到前一個(gè)節(jié)點(diǎn)。
需要注意的是，帶頭雙向循環(huán)鏈表為空并不意味著沒有一個(gè)節(jié)點(diǎn)，而是只有一個(gè)帶哨兵位的頭節(jié)點(diǎn)，所以在使用之前需要對鏈表進(jìn)行初始化。
二、帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)
2.1初始化創(chuàng)建帶頭雙向循環(huán)鏈表的節(jié)點(diǎn)
typedef struct ListNode
{
Listdatatype data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
在創(chuàng)建帶頭雙向循環(huán)鏈表的節(jié)點(diǎn)中比之前單鏈表節(jié)點(diǎn)的創(chuàng)建多了一個(gè)struct ListNode* prev;結(jié)構(gòu)體指針，目的在與存儲前一個(gè)節(jié)點(diǎn)的地址，便于將整個(gè)鏈表連在一起。
2.2申請新節(jié)點(diǎn)
//創(chuàng)建新節(jié)點(diǎn)
LTNode* BuyLTNode(Listdatatype 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;
}
動(dòng)態(tài)申請內(nèi)存結(jié)點(diǎn)，函數(shù)返回的是一個(gè)指針類型，用malloc開辟一個(gè)LTNode大小的空間，并用node指向這個(gè)空間，再判斷是否為空，如為空就perror，顯示錯(cuò)誤信息。反之則把需要存儲的數(shù)據(jù)x存到newnode指向的空間里面，并且把newnode->next,newnode->prev置為空。
2.3節(jié)點(diǎn)的初始化
LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
通過動(dòng)態(tài)內(nèi)存申請節(jié)點(diǎn)，申請了一個(gè)頭節(jié)點(diǎn)。并且將它的phead->next ，phead->prev 都置為phead,得到如下圖的頭節(jié)點(diǎn)。
2.4帶頭雙向循環(huán)鏈表的尾插
void LTPushBack(LTNode* phead, Listdatatype x)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = BuyLTNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
尾插節(jié)點(diǎn)的方法：首先通過內(nèi)存申請一個(gè)節(jié)點(diǎn)， 然后改變四個(gè)指針的指向，便可以完成帶頭雙向循環(huán)鏈表的尾插。
2.5帶頭雙向循環(huán)鏈表的頭插
void LTFrontBack(LTNode* phead, Listdatatype x)
{
assert(phead);
LTNode* newnode = BuyLTNode(x);
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
2.6判空函數(shù)
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
2.7帶頭雙向循環(huán)鏈表的打印函數(shù)
//打印
void LTPrint(LTNode* phead)
{
LTNode* cur = phead->next;
printf("guard<->");
while (cur != phead)
{
printf("%d<->", cur->data);
cur = cur->next;
}
printf("\n");
}
2.8帶頭雙向循環(huán)鏈表的尾刪
//尾刪
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;
}
2.9帶頭雙向循環(huán)鏈表的頭刪
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* first = phead->next;
LTNode* firstnext = first->next;
free(first);
phead->next = firstnext;
firstnext->prev = phead;
}
2.11帶頭雙向循環(huán)鏈表的在pos之前插入
void LTInsert(LTNode* pos, Listdatatype x)
{
assert(pos);
LTNode* newnode = BuyLTNode(x);
LTNode* posprev = pos->prev;
posprev->next = newnode;
newnode->prev = posprev;
newnode->next = pos;
pos->prev = newnode;
}
文章來源：http://www.zghlxwxcb.cn/news/detail-707060.html
2.12帶頭雙向循環(huán)鏈表的在pos位置刪除
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* posprev = pos->prev;
LTNode* posnext = pos->next;
posprev->next = posnext;
posnext->prev = posprev;
free(pos);
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-707060.html
2.14帶頭雙向循環(huán)鏈表的銷毀
//銷毀
LTNode* LTDestory(LTNode* phead)
{
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
三、完整代碼
3.1LIst.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int Listdatatype;
typedef struct ListNode
{
Listdatatype data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
//初始化
LTNode* LTInit();
//尾插
void LTPushBack(LTNode* phead, Listdatatype x);
//尾刪
void LTPopBack(LTNode* phead);
//頭插
void LTFrontBack(LTNode* phead, Listdatatype x);
//頭刪
void LTPopFront(LTNode* phead);
//打印
void LTPrint(LTNode* phead);
//判空
bool LTEmpty(LTNode* phead);
//在pos之前插入
void LTInsert(LTNode* pos, Listdatatype x);
//在pos之前刪除
void LTErase(LTNode* pos);
//尋找
LTNode* LTFind(LTNode* phead, Listdatatype x);
//銷毀
LTNode* LTDestory(LTNode* phead);
3.2List.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//創(chuàng)建新節(jié)點(diǎn)
LTNode* BuyLTNode(Listdatatype 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 LTPushBack(LTNode* phead, Listdatatype x)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = BuyLTNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
//頭插
void LTFrontBack(LTNode* phead, Listdatatype x)
{
assert(phead);
LTNode* newnode = BuyLTNode(x);
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
//判空
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
//打印
void LTPrint(LTNode* phead)
{
LTNode* cur = phead->next;
printf("guard<->");
while (cur != phead)
{
printf("%d<->", cur->data);
cur = cur->next;
}
printf("\n");
}
//尾刪
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;
}
//頭刪
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* first = phead->next;
LTNode* firstnext = first->next;
free(first);
phead->next = firstnext;
firstnext->prev = phead;
}
//尋找
LTNode* LTFind(LTNode* phead, Listdatatype 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, Listdatatype x)
{
assert(pos);
LTNode* newnode = BuyLTNode(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;
// free(posprev);
// posprev->prev->next = pos;
// pos->prev = posprev->prev;
//
//}
//在pos位置刪除
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* posprev = pos->prev;
LTNode* posnext = pos->next;
posprev->next = posnext;
posnext->prev = posprev;
free(pos);
}
//銷毀
LTNode* LTDestory(LTNode* phead)
{
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
3.3test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//void test1()
//{
// LTNode* plist = LTInit();
// LTPushBack(plist, 1);
// LTPushBack(plist, 2);
// LTPushBack(plist, 3);
// LTPushBack(plist, 4);
// LTPrint(plist);
// LTPopBack(plist);
// LTPrint(plist);
//}
void test2()
{
LTNode* plist = LTInit();
LTFrontBack(plist, 1);
LTFrontBack(plist, 2);
LTFrontBack(plist, 3);
LTFrontBack(plist, 4);
LTPrint(plist);
LTErase(3);
LTPrint(plist);
}
int main()
{
//test1();
test2();
return 0;
}
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——帶頭雙向循環(huán)鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
