目錄
1.問題引入
2.結(jié)構(gòu)實(shí)現(xiàn)
2.3.1接口實(shí)現(xiàn)
2.3.2函數(shù)實(shí)現(xiàn)
3.總結(jié)
，又和大家見面了，今天要給大家分享的是雙鏈表的知識(shí)，跟著我的腳步，包學(xué)包會(huì)哦~
規(guī)矩不亂，先贊后看！
ps：（孫權(quán)勸學(xué)）
1.問題引入
前期學(xué)習(xí)了單鏈表，我們嘗到了它的甜頭，但是容易越界訪問這一個(gè)問題也是時(shí)有出現(xiàn)的，因此也是相對(duì)比較棘手的，為了解決這一個(gè)問題，特此向大家介紹帶頭雙向鏈表
帶頭雙向鏈表，顧名思義含有哨兵位，同時(shí)一個(gè)節(jié)點(diǎn)有兩個(gè)指針（next / prev），這樣的好處是讓相鄰指針的聯(lián)系更加緊密，同時(shí)將首尾節(jié)點(diǎn)相連是其能夠非常容易實(shí)現(xiàn)找尾。
話不多說(shuō)，直接上代碼！
2.結(jié)構(gòu)實(shí)現(xiàn)
2.3.1接口實(shí)現(xiàn)
先在頭文件（List.h)上進(jìn)行順序表結(jié)構(gòu)的創(chuàng)建和對(duì)各函數(shù)的聲明，目的是為了把各部分區(qū)分開，使程序便于理解，能清楚的看到各部分對(duì)于的作用和功能。
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}LTNode;
bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
LTNode* LTInit();
void LTPopFront(LTNode* phead);
void PushFront(LTNode* phead, LTDataType x);
void LTPrint(LTNode* phead);
LTNode* BuyLTNode(LTDataType x);
void LTPopBack(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDataType x);
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);
2.3.2函數(shù)實(shí)現(xiàn)
接著下來(lái)是單鏈表各函數(shù)的函數(shù)部分，我們?cè)贚ist.c中完成：
a.創(chuàng)造新節(jié)點(diǎn)
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;
}
這些步驟都是和鏈表一模一樣的。
b.初始化鏈表
LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
都是鏈表的一套固定公式
c.查找鏈表
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;
}
d.在鏈表中插入節(jié)點(diǎn)
由于有了雙鏈表，使得插入十分輕松，同時(shí)這一個(gè)函數(shù)就能簡(jiǎn)化頭插和尾插兩個(gè)函數(shù)，是相當(dāng)方便的
//在pos前插入
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;
}
e.在鏈表中刪除節(jié)點(diǎn)
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* posprev = pos->prev;
LTNode* posnext = pos->next;
posprev->next = posnext;
posnext->prev = posprev;
free(pos);
pos = NULL;
}
有了這個(gè)函數(shù)，也可以讓頭刪和尾刪變得相當(dāng)?shù)暮?jiǎn)潔。
f.判斷鏈表是否為空
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
由于頭刪尾刪會(huì)改變鏈表，因此需要一個(gè)判空函數(shù)來(lái)保證程序的安全性
g.頭插尾插
//尾插
void LTPushBack(LTNode* phead, LTDataType x)//不需要二級(jí)指針（沒有改變phead）
{
assert(phead);
//LTNode* newnode = BuyLTNode(x);
//LTNode* tail = phead->prev;
//tail->next = newnode;
//newnode->next = phead;
//newnode->prev = tail;
//phead->prev = newnode;
LTInsert(phead, x);
}
//頭插
//頭插---指的是插在頭結(jié)點(diǎn)之后，首個(gè)含數(shù)據(jù)的結(jié)點(diǎn)之前
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
//LTNode* newnode = BuyLTNode(x);
//phead->next->prev = newnode;
//newnode->next = phead->next;
//phead->next = newnode;
//newnode->prev = phead;
//
//香餑餑
LTInsert(phead->next, x);
}
注釋掉的是沒有依靠Insert和Erase函數(shù)來(lái)寫的頭插尾插，是相當(dāng)麻煩的，通過(guò)那兩個(gè)函數(shù)，能讓你不到10分鐘就能寫出雙鏈表。
h.頭刪尾刪
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;
LTErase(phead->prev);
}
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
//if (phead->next->next == NULL)
//{
// phead->next = phead;
// phead->prev = phead;
//}
//else
//{
// LTNode* cur = phead->next;
// LTNode* af = phead->next->next;
// assert(cur);
// assert(af);
// phead->next = af;
// af->prev = phead;
// free(cur);
// cur = NULL;
//}
LTErase(phead->next);
}
i.打印鏈表
?
void LTPrint(LTNode* phead)
{
assert(phead);
printf("guard<==>");
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d<==>", cur->data);
cur = cur->next;
}
printf("\n");
}
j.銷毀鏈表
程序執(zhí)行完畢后需要銷毀程序，這樣才不會(huì)出現(xiàn)內(nèi)存問題
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;
LTErase(phead->prev);
}
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
//if (phead->next->next == NULL)
//{
// phead->next = phead;
// phead->prev = phead;
//}
//else
//{
// LTNode* cur = phead->next;
// LTNode* af = phead->next->next;
// assert(cur);
// assert(af);
// phead->next = af;
// af->prev = phead;
// free(cur);
// cur = NULL;
//}
LTErase(phead->next);
}
2.3測(cè)試程序
實(shí)現(xiàn)完函數(shù)之后還需要對(duì)其進(jìn)行測(cè)試
#include"List.h"
void TestList1()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPushBack(plist, 5);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPopFront(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTDestroy(plist);
plist = NULL;
}
void TestList2()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPushBack(plist, 5);
LTPopFront(plist);
LTPrint(plist);
LTNode* pos = LTFind(plist, 3);
if (pos)
{
LTInsert(pos, 30);
}
LTPrint(plist);
LTDestroy(plist);
plist = NULL;
}
int main()
{
TestList1();
TestList2();
return 0;
}
最后在終端上運(yùn)行一遍得到結(jié)果
?結(jié)果是這樣的小伙伴就是正確掌握了的喲
如果沒有跑起來(lái)的uu們也不用擔(dān)心，細(xì)心調(diào)試一下，慢慢找錯(cuò)也是一種成長(zhǎng)。?
3.總結(jié)
鏈表的學(xué)習(xí)我認(rèn)為是一個(gè)先苦后甜的過(guò)程，把單鏈表的原理搞懂之后，再使用雙鏈表就完全是如魚得水了。學(xué)習(xí)也是一樣，先吃苦，以后才能嘗到生活的甜頭。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-842299.html
最后關(guān)于鏈表的問題，我強(qiáng)烈建議大家刷題鞏固，踏實(shí)穩(wěn)重，才能把數(shù)據(jù)結(jié)構(gòu)這個(gè)難關(guān)拿下。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-842299.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之帶頭雙向鏈表（易學(xué)版）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
