Hello，好久不見，今天我們講鏈表的雙向鏈表，這是一個很厲害的鏈表，帶頭雙向且循環(huán)，學了這個鏈表，你會發(fā)現(xiàn)順序表的頭插頭刪不再是一個麻煩問題，單鏈表的尾插尾刪也變得簡單起來了，那廢話不多說，讓我們開始我們的學習吧！
首先我們要了解它的物理和邏輯結(jié)構(gòu)，那他們的樣子是怎樣的呢，首先是一個帶頭的，那這個難道是我們的哨兵位嗎，又是雙向，且循環(huán)，那讓我們來畫圖了解它吧。
大致就是這樣的一個形狀，那我們現(xiàn)在需要這樣的一個結(jié)構(gòu)體來實現(xiàn)這樣的功能，首先應(yīng)該有一個存儲數(shù)據(jù)的，就是data，然后就是得有兩個指針，一個指向前面的節(jié)點，一個就是指向后面的節(jié)點，那我們就叫它們一個pre指向前面，一個next指向后面，我們來實現(xiàn)一下吧。
typedef int DListType;
typedef struct DList
{
struct DList* pre;
struct DList* next;
DListType data;
}DLNode;
為了方便我們寫后面的時候結(jié)構(gòu)體方便一點，我們先定義結(jié)構(gòu)體為DLNode，這樣更加方便使用。
現(xiàn)在我們要實現(xiàn)下面的各種接口來完成雙鏈表
首先最重要的就是怎么初始化
初始化的話我們先要想想這個接口函數(shù)改的參數(shù)和返回值
因為是雙向鏈表，所以得有一個head的頭節(jié)點，這樣才能鏈接后面的內(nèi)容
初始化雙鏈表
DLNode* DListInit();
接口函數(shù)的名字
這里我們分析首先我們得返回值為什么不是void，而是DLNode*
因為我們要在這里面創(chuàng)建一個頭節(jié)點，這個節(jié)點我們后面都得使用，其次還有一個原因就是這樣頭節(jié)點就不會被銷毀，當然我們也可以在外面創(chuàng)建一個節(jié)點，然后我們在傳它的指針進去，對結(jié)構(gòu)體的內(nèi)容進行修改，都可以達到相同的作用，廢話不多說，我們來實現(xiàn)吧！
DLNode* DListInit()
{
DLNode* pHead = (DLNode*)malloc(sizeof(DLNode));
assert(pHead);
pHead->next = pHead;
pHead->pre = pHead;
}
其實很簡單，這里必須指針指向自己才可以，如果不這樣的話，那我們的循環(huán)就不能實現(xiàn)了。
接下來就是怎么打印，打印很簡單，我們將它這個指針傳過去就行了。
打印雙鏈表
void DListPrint(DLNode* pHead)
{
assert(pHead);
DLNode* cur = pHead->next;
while (cur != pHead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
打印函數(shù)的想法就是我們找head后面的那個節(jié)點，然后打印，因為頭節(jié)點我們不打印，所以取cur開始，因為是循環(huán)，所以cur最后會等于pHead，這樣的話就是一個循環(huán)，所以我們找下一個就行了，然后打印后更新cur。
接下來我們要創(chuàng)建一個節(jié)點，這樣才能鏈接起來我們的節(jié)點。
DLNode* CreatNewNode(DListType x)
DLNode* CreatNewNode(DListType x)
{
DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
newnode->pre = NULL;
return newnode;
}
創(chuàng)造節(jié)點好了，接下來就是尾插一個節(jié)點進去，我們前面單鏈表尾插首先要找到尾的位置，然后再去尾插，同時要先找到尾的前一個位置，然后free尾，這樣時間復雜度就是O（N），所以效率不是特別高，那我們現(xiàn)在因為head的位置里存放的就是尾的位置，所以不用進行查找了。我們現(xiàn)在來實現(xiàn)一下吧
雙鏈表尾插
void DListPushBACK(DLNode* pHead, DListType x)
{
assert(pHead);
DLNode* newnode = CreatNewNode(x);
DLNode* pre = pHead->pre;
pHead->pre = newnode;
newnode->next = pHead;
pre->next = newnode;
newnode->pre = pre;
}
其實尾插也很簡單，我們這里先用一個指針保存位置，這樣的話下一次插入就可以找到尾的位置，而且還不用注重順序，這樣大大的提升效率
有了尾插那就肯定有頭插，一樣的辦法我們來實現(xiàn)一下
雙鏈表的頭插
void DListPushFront(DLNode* pHead, DListType x)
{
assert(pHead);
DLNode* newnode = CreatNewNode(x);
DLNode* next = pHead->next;
pHead->next = newnode;
newnode->pre = pHead;
newnode->next = next;
next->pre = newnode;
}
有了頭插這些，那肯定還有頭刪和尾刪
那我們也來實現(xiàn)一下吧
尾刪
void DListPopBack(DLNode* pHead)
{
assert(pHead);
if (pHead->next != pHead)
{
DLNode* del = pHead->pre;
del->pre->next = pHead;
pHead->pre = del->pre;
free(del);
}
}
前面寫的代碼都需要測試一下，我們先來測試三個
#include"DList.h"
void test()
{
DLNode* head = DListInit();
DListPushBack(head, 1);
DListPushBack(head, 2);
DListPushBack(head, 3);
DListPushBack(head, 4);
DListPrint(head);
DListPushFront(head, 111);
DListPushFront(head, 111);
DListPushFront(head, 111);
DListPrint(head);
DListPopBack(head);
DListPopBack(head);
DListPopBack(head);
DListPrint(head);
}
int main()
{
test();
return 0;
}
發(fā)現(xiàn)我們的程序沒有問題，我們再來實現(xiàn)一下頭刪
void DListPopFront(DLNode* pHead)
{
assert(pHead);
if (pHead->next != pHead)
{
DLNode* del = pHead->next;
pHead->next = del->next;
del->next->pre = pHead;
free(del);
}
}
接下來就是雙鏈表的查找，有了查找我們才能和在任意位置的刪除和插入連用，那我們現(xiàn)在來實現(xiàn)一下吧
DLNode* DListFind(DLNode* pHead, DListType x)
{
assert(pHead);
DLNode* cur = pHead->next;
while (cur != pHead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
隨機插入
void DListInsert(DLNode* pos, DListType x)
{
assrt(pos);
DLNode* newnode = CreatNewNode(x);
DLNode* pospre = pos->pre;
pospre->next = newnode;
newnode->pre = pospre;
newnode->next = pos;
pos->pre = newnode;
}
也不是隨機插入，是在pos位置之前插入，我們直接傳pos和x就行，然后在根據(jù)之前的想法一步一步的進行插入鏈接就行
這里可以更新一下頭插和尾插，這里就不演示了
那我們在寫一個刪除pos位置的函數(shù)
刪除pos位置
void DListPop(DLNode* pos)
{
assert(pos);
DLNode* pospre = pos->pre;
DLNode* posnext = pos->next;
pospre->next = posnext;
posnext->pre = pospre;
free(pos);
}
還有一個destory我們開辟的空間，這個遍歷一遍數(shù)組， 然后一個一個釋放就行，但是會有問題，我們釋放的時候必須看要機記住位置，可以從尾巴開始釋放，用一個指針記住前面一個的位置，然后釋放掉尾巴，然后更新前一個位置，用while控制一下就行了文章來源：http://www.zghlxwxcb.cn/news/detail-675057.html
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int DListType;
typedef struct DList
{
struct DList* pre;
struct DList* next;
DListType data;
}DLNode;
DLNode* DListInit();
void DListPrint(DLNode* pHead);
DLNode* CreatNewNode(DListType x);
void DListPushBack(DLNode* pHead, DListType x);
void DListPushFront(DLNode* pHead, DListType x);
void DListPopBack(DLNode* pHead);
void DListPopFront(DLNode* pHead);
DLNode* DListFind(DLNode* pHead, DListType x);
void DListInsert(DLNode* pos, DListType x);
void DListPop(DLNode* pos);
#include"DList.h"
DLNode* DListInit()
{
DLNode* pHead = (DLNode*)malloc(sizeof(DLNode));
pHead->next = pHead;
pHead->pre = pHead;
}
void DListPrint(DLNode* pHead)
{
assert(pHead);
DLNode* cur = pHead->next;
while (cur != pHead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
DLNode* CreatNewNode(DListType x)
{
DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
newnode->pre = NULL;
return newnode;
}
void DListPushBack(DLNode* pHead, DListType x)
{
DLNode* newnode = CreatNewNode(x);
DLNode* pre = pHead->pre;
pHead->pre = newnode;
newnode->next = pHead;
pre->next = newnode;
newnode->pre = pre;
}
void DListPushFront(DLNode* pHead, DListType x)
{
DLNode* newnode = CreatNewNode(x);
DLNode* next = pHead->next;
pHead->next = newnode;
newnode->pre = pHead;
newnode->next = next;
next->pre = newnode;
}
void DListPopBack(DLNode* pHead)
{
assert(pHead);
if (pHead->next != pHead)
{
DLNode* del = pHead->pre;
del->pre->next = pHead;
pHead->pre = del->pre;
free(del);
}
}
void DListPopFront(DLNode* pHead)
{
assert(pHead);
if (pHead->next != pHead)
{
DLNode* del = pHead->next;
pHead->next = del->next;
del->next->pre = pHead;
free(del);
}
}
DLNode* DListFind(DLNode* pHead, DListType x)
{
assert(pHead);
DLNode* cur = pHead->next;
while (cur != pHead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void DListInsert(DLNode* pos, DListType x)
{
assrt(pos);
DLNode* newnode = CreatNewNode(x);
DLNode* pospre = pos->pre;
pospre->next = newnode;
newnode->pre = pospre;
newnode->next = pos;
pos->pre = newnode;
}
void DListPop(DLNode* pos)
{
assert(pos);
DLNode* pospre = pos->pre;
DLNode* posnext = pos->next;
pospre->next = posnext;
posnext->pre = pospre;
free(pos);
}
謝謝大家，我們下期再見文章來源地址http://www.zghlxwxcb.cn/news/detail-675057.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)雙向鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
