目錄
前言
1. 雙向鏈表?
帶頭雙向循環(huán)鏈表的結(jié)構(gòu)
2. 鏈表的實(shí)現(xiàn)
2.1 初始化
2.2 尾插
2.3 尾刪
2.4 頭插
2.5 頭刪
2.6 在pos位置之前插入
2.7 刪除pos位置
3.雙向鏈表完整源碼
List.h
List.c
前言
在上一期中我們介紹了單鏈表，也做了一些練習(xí)題，在一些題中使用單鏈表會(huì)十分繁瑣。因?yàn)閱捂湵碇荒苷?，不能倒著走，例如：回文、逆置。本期我們將學(xué)習(xí)帶頭雙向循環(huán)鏈表。
1. 雙向鏈表?
帶頭雙向循環(huán)鏈表的結(jié)構(gòu)
?特點(diǎn)：帶頭雙向循環(huán)鏈表結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來(lái)多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡(jiǎn)單了。
2. 鏈表的實(shí)現(xiàn)
2.1 初始化
LTNode* LTInit()
{
LTNode* phead = CreateLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}2.2 尾插
帶哨兵位的鏈表尾插時(shí)不用判斷是否有節(jié)點(diǎn)，兩種情況的插入相同，而且還不用傳遞二級(jí)指針。
void LTPushBack(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* newnode = CreateLTNode(x);
phead->prev->next = newnode;
newnode->prev = phead->prev;
newnode->next = phead;
phead->prev = newnode;
}2.3 尾刪
在尾刪時(shí)我們通過(guò) assert(phead->next != phead);? 判斷鏈表是否有節(jié)點(diǎn)。同時(shí)這個(gè)代碼就有普遍性，不用單獨(dú)考慮剩一個(gè)節(jié)點(diǎn)的情況。
void LTPopBack(LTNode* phead)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* tailprev = tail->prev;
free(tail);
phead->prev = tailprev;
tailprev->next = phead;
}2.4 頭插
頭刪重要的是賦值的順序，順序錯(cuò)誤會(huì)找不到后面的節(jié)點(diǎn)，導(dǎo)致內(nèi)存泄漏。帶哨兵位的鏈表不需要傳遞二級(jí)指針，因?yàn)楦淖兊氖墙Y(jié)構(gòu)體的變量。
void LTPushFront(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* newnode = CreateLTNode(x);
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}2.5 頭刪
我們可以多定義幾個(gè)指針來(lái)保存后面節(jié)點(diǎn)的地址，這樣就不會(huì)造成節(jié)點(diǎn)的丟失，不用考慮賦值的順序，會(huì)更加方便。?
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->next;
LTNode* next = tail->next;
phead->next = next;
next->prev = phead;
free(tail);
tail = NULL;
}2.6 在pos位置之前插入
void LTInsert(LTNode* pos, LTDateType x)
{
assert(pos);
LTNode* posprev = pos->prev;
LTNode* newnode = CreateLTNode(x);
posprev->next = newnode;
newnode->prev = posprev;
newnode->next = pos;
pos->prev = newnode;
}2.7 刪除pos位置
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* posprev = pos->prev;
LTNode* posnext = pos->next;
posprev->next = posnext;
posnext->prev = posprev;
}3.雙向鏈表完整源碼
List.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDateType;
typedef struct ListNode
{
LTDateType val;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
LTNode* LTInit();
void LTPrint(LTNode* phead);
void LTPushBack(LTNode* phead, LTDateType x);
void LTPushFront(LTNode* phead, LTDateType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDateType x);
void LTInsert(LTNode* pos, LTDateType x);
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);List.c
#include"List.h"
LTNode* CreateLTNode(LTDateType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->val = x;
newnode->next = NULL;
newnode->prev = NULL;
}
LTNode* LTInit()
{
LTNode* phead = CreateLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("<=>哨兵位<=>");
while (cur != phead)
{
printf("%d<=>", cur->val);
cur = cur->next;
}
printf("\n");
}
void LTPushBack(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* newnode = CreateLTNode(x);
phead->prev->next = newnode;
newnode->prev = phead->prev;
newnode->next = phead;
phead->prev = newnode;
}
void LTPushFront(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* newnode = CreateLTNode(x);
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
void LTPopBack(LTNode* phead)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* tailprev = tail->prev;
free(tail);
phead->prev = tailprev;
tailprev->next = phead;
}
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->next;
LTNode* next = tail->next;
phead->next = next;
next->prev = phead;
free(tail);
tail = NULL;
}
LTNode* LTFind(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void LTInsert(LTNode* pos, LTDateType x)
{
assert(pos);
LTNode* posprev = pos->prev;
LTNode* newnode = CreateLTNode(x);
posprev->next = newnode;
newnode->prev = posprev;
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;
}
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}通過(guò)上面鏈表的實(shí)現(xiàn)，我們已經(jīng)感受到了帶頭雙向循環(huán)鏈表的方便和簡(jiǎn)單，它不需要去考慮鏈表是否有元素，還可以找到前一個(gè)元素，在我們使用中提供很大的便利。
本次的內(nèi)容到這里就結(jié)束啦。希望大家閱讀完可以有所收獲，同時(shí)也感謝各位讀者三連支持。文章有問(wèn)題可以在評(píng)論區(qū)留言，博主一定認(rèn)真認(rèn)真修改，以后寫出更好的文章。?文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-752789.html
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-752789.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】手撕雙向鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
