一.雙向鏈表的結(jié)構(gòu)
注意：這里的“帶頭”跟前面我們說(shuō)的“頭節(jié)點(diǎn)”是兩個(gè)概念，實(shí)際前面的在單鏈表階段稱呼不嚴(yán)
謹(jǐn)，但是為了同學(xué)們更好的理解就直接稱為單鏈表的頭節(jié)點(diǎn)。
帶頭鏈表里的頭節(jié)點(diǎn)，實(shí)際為“哨兵位”，哨兵位節(jié)點(diǎn)不存儲(chǔ)任何有效元素，只是站在這里“放哨
的”
“哨兵位”存在的意義：
遍歷循環(huán)鏈表避免死循環(huán)。
二. 雙向鏈表的實(shí)現(xiàn)
2.1 頭文件 ——雙向鏈表的創(chuàng)建及功能函數(shù)的定義
List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDatatype;
//鏈表的結(jié)構(gòu)創(chuàng)建
typedef struct ListNode
{
LTDatatype data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
//打印
void LTPrint(LTNode* phead);
//雙鏈表的初始化//銷毀
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//銷毀
//void LTDestroy(LTNode** pphead);
void LTDestroy(LTNode* phead);
//頭部/尾部/插入/刪除
//尾插
void LTPushBack(LTNode* phead, LTDatatype x);
//頭插
void LTPushFront(LTNode* phead, LTDatatype x);
//尾刪
void LTPopBack(LTNode* phead);
//頭刪
void LTPopFront(LTNode* phead);
//再pos位置之后插入/刪除
void LTInsrt(LTNode* pos, LTDatatype x);
void LTErase(LTNode* pos);
//查找pos
LTNode* LTFind(LTNode* phead, LTDatatype x);
2.2 源文件 ——雙向鏈表的功能函數(shù)的實(shí)現(xiàn)
List.c
#include"List.h"
//初始化
//二級(jí)指針初始化
//前提是我們需要傳入一個(gè)頭節(jié)點(diǎn)
//void LTInit(LTNode** pphead)
//{
// *pphead = (LTNode*)malloc(sizeof(LTNode));
// if (*pphead == NULL)
// {
// perror("malloc error");
// return;
// }
// (*pphead)->data = -1;//哨兵位
// (*pphead)->next = (*pphead)->prev = *pphead;
//
//}
//一級(jí)指針初始化
//不需要傳參，只需要返回一個(gè)地址即可
LTNode* LTInit()
{
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
if (phead == NULL)
{
perror("malloc error");
return;
}
phead->data = -1;
phead->next = phead->prev = phead;
return phead;
}
//鏈表的銷毀
//參數(shù)是二級(jí)指針
//void LTDestroy(LTNode** pphead)
//{
// assert(pphead && *pphead);
// LTNode* cur = (*pphead)->next;
// while(cur!=(*pphead))
// {
// LTNode* next = cur->next;
// free(cur);
// cur = next;
// }
// free(*pphead);
// *pphead = NULL;
//}
//參數(shù)是一級(jí)指針
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;
}
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("\n");
}
LTNode* LTBuyNode(LTDatatype x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
node->data = x;
node->next = node->prev = NULL;
return node;
}
//尾插
void LTPushBack(LTNode* phead, LTDatatype x)
{
LTNode* node = LTBuyNode(x);
//先處理插入的節(jié)點(diǎn)的前驅(qū)和后繼指針
node->next = phead;
node->prev = phead->prev;
//然后考慮哨兵位的前驅(qū)和尾節(jié)點(diǎn)的后繼指針
phead->prev->next = node;
phead->prev = node;
}
//頭插
void LTPushFront(LTNode* phead, LTDatatype x)
{
assert(phead);
LTNode* node = LTBuyNode(x);
//先處理插入節(jié)點(diǎn)的前驅(qū)和后繼的指針
node->next = phead->next;
node->prev = phead;
//然后處理phead,phead->next
phead->next->prev = node;
phead->next = node;
}
//尾刪
void LTPopBack(LTNode* phead)
{
assert(phead);
//鏈表不能為空，鏈表中只有一個(gè)哨兵位節(jié)點(diǎn)
assert(phead->next != phead);
LTNode* del = phead->prev;
//先處理 del->prev
del->prev->next = phead;
//接著處理phead
phead->prev = del->prev;
free(del);
del = NULL;
}
//頭刪
void LTPopFront(LTNode* phead)
{
assert(phead && phead->next != phead);
LTNode* del = phead->next;
//先處理del->next
del->next->prev = phead;
//接著處理phead
phead->next = del->next;
free(del);
del = NULL;
}
//在pos位置之后插入
void LTInsrt(LTNode* pos, LTDatatype x)
{
LTNode* node = LTBuyNode(x);
//先處理node的前驅(qū)和后繼
node->next = pos->next;
node->prev = pos;
//接著處理pos->next,pos->next->prev
pos->next = node;
pos->next->prev = node;
}
//刪除pos位置的數(shù)據(jù)
void LTErase(LTNode* pos)
{
assert(pos);
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}
//查找pos
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;
}
2.3 源文件 ——雙向鏈表功能的測(cè)試
test.c
#include"List.h"
void ListTest()
{
/*LTNode* plist = NULL;
LTInit(&plist);*/
//初始化
LTNode* plist = LTInit();
//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
//頭插
/*LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);*/
//尾刪
/*LTPopBack(plist);
LTPopBack(plist);*/
//頭刪
/*LTPopFront(plist);
LTPopFront(plist);*/
LTNode* find = LTFind(plist, 4);
//在pos位置之后插入
/*LTInsrt(find, 5);*/
//刪除pos位置的數(shù)據(jù)
LTErase(find);
LTPrint(plist);
//銷毀鏈表
//LTDestroy(&plist);
//一級(jí)指針?shù)N毀需要手動(dòng)將plist置空
LTDestroy(plist);
plist = NULL;
}
int main()
{
ListTest();
return 0;
}
2.4 雙向鏈表各項(xiàng)功能測(cè)試運(yùn)行展示
2.4.1 雙向鏈表的初始化 ——（以調(diào)試窗口展示）
//初始化
LTNode* plist = LTInit();
2.4.2 雙向鏈表的尾插 ——（以打印展示）
//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
2.4.3 雙向鏈表的頭插 ——（以打印展示）
//頭插
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
2.4.4 雙向鏈表的尾刪 ——（以打印展示）
//尾刪
LTPopBack(plist);
LTPopBack(plist);
2.4.5 雙向鏈表的頭刪 ——（以打印展示）
//頭刪
LTPopFront(plist);
LTPopFront(plist);
2.4.6 雙向鏈表的查找指定位置及在指定位置之后插入 ——（以打印展示）
//查找指定位置pos
LTNode* find = LTFind(plist, 4);
//在pos位置之后插入
LTInsrt(find, 5);
2.4.7 雙向鏈表的查找指定位置及刪除指定位置的數(shù)據(jù) ——（以打印展示）
// //查找指定位置pos
LTNode* find = LTFind(plist, 4);
//刪除pos位置的數(shù)據(jù)
LTErase(find);
2.4.8 雙向鏈表的銷毀 ——（以調(diào)試窗口展示）
//銷毀鏈表
//LTDestroy(&plist);
//一級(jí)指針?shù)N毀需要手動(dòng)將plist置空
LTDestroy(plist);
plist = NULL;
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-737114.html
三.順序表和雙向鏈表的優(yōu)缺點(diǎn)分析
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-737114.html
到了這里，關(guān)于【（數(shù)據(jù)結(jié)構(gòu)）— 雙向鏈表的實(shí)現(xiàn)】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
