柚子快報(bào)激活碼778899分享：C語言：數(shù)據(jù)結(jié)構(gòu)（雙向鏈表）

http://yzkb.51969.com/

目錄

1、雙向鏈表的結(jié)構(gòu)2、順序表和雙向鏈表的優(yōu)缺點(diǎn)分析3、雙向鏈表的實(shí)現(xiàn)

1、雙向鏈表的結(jié)構(gòu)

注意：這?的“帶頭“跟前面我們說的“頭節(jié)點(diǎn)”是兩個(gè)概念，實(shí)際前面的在單鏈表階段稱呼不嚴(yán)謹(jǐn)，但是為了更好的理解就直接稱為單鏈表的頭節(jié)點(diǎn)。 帶頭鏈表里的頭節(jié)點(diǎn)，實(shí)際為“放哨的”，哨兵位節(jié)點(diǎn)不存儲(chǔ)任何有效元素，只是站在這里“放哨的”。 “哨兵位”存在的意義：遍歷循環(huán)鏈表避免死循環(huán)。

2、順序表和雙向鏈表的優(yōu)缺點(diǎn)分析

不同點(diǎn)順序表鏈表存儲(chǔ)空間上物理上一定連續(xù)邏輯上連續(xù)，但物理上不一定連續(xù)隨機(jī)訪問支持O(1)不支持O(N)任意位置插?或者刪除元素可能需要搬移元素，效率低只需修改指針指向插入動(dòng)態(tài)順序表，空間不夠時(shí)需要擴(kuò)容沒有容量的概念應(yīng)用場(chǎng)景元素高效存儲(chǔ)和頻繁訪問任意位置頻繁插入和刪除

3、雙向鏈表的實(shí)現(xiàn)

ListNode.h

#pragma once

#include

#include

#include

//定義雙向鏈表節(jié)點(diǎn)的結(jié)構(gòu)

typedef int Ltdatatype;

typedef struct ListNode

{

Ltdatatype data;

struct ListNode* prev;//指向前一個(gè)節(jié)點(diǎn)的指針

struct ListNode* next;//指向后一個(gè)節(jié)點(diǎn)的指針

}ListNode;

//雙向鏈表的初始化

ListNode* LtInit();

//尾插

//不改變哨兵位的地址，所以傳一級(jí)即可

void LtPushBack(ListNode* phead, Ltdatatype x);//插入數(shù)據(jù)之前，鏈表必須初始化到只有一個(gè)頭結(jié)點(diǎn)的情況

//打印鏈表

void LtPrint(ListNode* phead);

//頭插

void LtPushFront(ListNode* phead, Ltdatatype x);

//尾刪

LtPopBack(ListNode* phead);

//頭刪

LtPopFront(ListNode* phead);

//查找

ListNode* LtFind(ListNode* phead, Ltdatatype x);

//指定位置前插入

void LtInsert(ListNode* pos, Ltdatatype x);

//刪除pos位置

void LtErase(ListNode* pos);

//銷毀鏈表

void LtDestroy(ListNode* phead);

ListNode.c

#define _CRT_SECURE_NO_WARNINGS

#include "ListNode.h"

//申請(qǐng)節(jié)點(diǎn)

ListNode* LtBuyNode(Ltdatatype x)

{

ListNode* node = (ListNode*)malloc(sizeof(ListNode));

if (node == NULL)

{

perror("malloc fail");

exit(1);

}

//申請(qǐng)成功

node->data = x;

node->next = node->prev = node;

return node;

}

//雙向鏈表的初始化

ListNode* LtInit()

{

ListNode*phead = LtBuyNode(-1);

return phead;

}

//尾插

void LtPushBack(ListNode* phead, Ltdatatype x)

{

assert(phead);

ListNode* newnode = LtBuyNode(x);

//改變新節(jié)點(diǎn)的指向

newnode->prev = phead->prev;

newnode->next = phead;

//改變尾節(jié)點(diǎn)和哨兵位的指向

phead->prev->next = newnode;

phead->prev = newnode;

}

//打印鏈表

void LtPrint(ListNode* phead)

{

ListNode* pcur = phead->next;

//遍歷鏈表

while (pcur != phead)

{

printf("%d->", pcur->data);

pcur = pcur->next;

}

printf("\n");

}

//頭插

void LtPushFront(ListNode* phead,Ltdatatype x)

{

assert(phead);

ListNode* newnode = LtBuyNode(x);

newnode->prev = phead;

newnode->next = phead->next;

//修改哨兵位和第一個(gè)有效節(jié)點(diǎn)的指向

phead->next->prev = newnode;

phead->next = newnode;

}

//尾刪

LtPopBack(ListNode* phead)

{

//鏈表必須有效且鏈表不能為空（只有一個(gè)哨兵位）

assert(phead && phead->next != phead);

ListNode* Del = phead->prev;//尾節(jié)點(diǎn)

ListNode* DelPrev = Del->prev;//尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)

phead->prev = DelPrev;

DelPrev->next = phead;

free(Del);//刪除Del節(jié)點(diǎn)

Del = NULL;

}

//頭刪

LtPopFront(ListNode* phead)

{

//判斷鏈表是否有效和鏈表是否為空

assert(phead && phead->next != phead);

ListNode* Del = phead->next;//第一個(gè)有效節(jié)點(diǎn)

ListNode* DelNext = Del->next;//有效節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)

phead->next = DelNext;

DelNext->prev = phead;

free(Del);//刪除Del節(jié)點(diǎn)

Del = NULL;

}

//查找

ListNode* LtFind(ListNode* phead, Ltdatatype x)

{

ListNode* pcur = phead->next;

//遍歷鏈表

while (pcur != phead)

{

if (pcur->data == x)

return pcur;

pcur = pcur->next;//繼續(xù)讓pcur往下遍歷

}

return NULL;//沒有找到

}

//在pos位置之前插入數(shù)據(jù)

void LtInsert(ListNode* pos,Ltdatatype x)

{

ListNode* newnode = LtBuyNode(x);

newnode->prev = pos->prev;

newnode->next = pos;

pos->prev->next = newnode;

pos->prev = newnode;

}

//刪除pos位置

void LtErase(ListNode* pos)

{

assert(pos);

ListNode* PosPrev = pos->prev;//pos的前一個(gè)節(jié)點(diǎn)

ListNode* PosNext = pos->next;//pos的后一個(gè)節(jié)點(diǎn)

PosPrev->next = PosNext;

PosNext->prev = PosPrev;

free(pos);

//pos = NULL;這里就算置空了，也不會(huì)影響實(shí)參

}

//銷毀鏈表

void LtDestroy(ListNode* phead)

{

ListNode* pcur = phead->next;

//邊遍歷邊釋放節(jié)點(diǎn)

while (pcur != phead)

{

ListNode* Next = pcur->next;//保存要釋放掉節(jié)點(diǎn)的下一個(gè)地址

free(pcur);

pcur = Next;

}

//此時(shí)pcur指向phead，而phead還沒有被銷毀

free(phead);

pcur = NULL;

}

text.c

#define _CRT_SECURE_NO_WARNINGS

#include "ListNode.h"

void LtnodeTest()

{

//測(cè)試初始化

ListNode* plist = LtInit();

//測(cè)試尾插

LtPushBack(plist,1);

LtPushBack(plist,2);

LtPushBack(plist,3);

//測(cè)試打印

LtPrint(plist);

//測(cè)試頭插

//LtPushFront(plist,4);

//LtPushFront(plist,5);

//LtPushFront(plist,6);

//LtPrint(plist);

//測(cè)試尾刪

LtPopBack(plist);

LtPrint(plist);

//測(cè)試頭刪

//LtPopFront(plist);

//LtPrint(plist);

//測(cè)試查找

//ListNode*find = LtFind(plist,2);

//if (find)

// printf("找到了！\n");

//else

// printf("沒找到！\n");

//測(cè)試在pos位置之前插入數(shù)據(jù)

//LtInsert(find,88);

//LtPrint(plist);

//測(cè)試刪除pos位置

//LtErase(find);

//find = NULL;//形參的改變不會(huì)影響實(shí)參，所以要在函數(shù)調(diào)用結(jié)束之后置為空

//LtPrint(plist);

//測(cè)試銷毀鏈表

//LtDestroy(plist);

//plist = NULL;

}

int main()

{

LtnodeTest();

return 0;

}

如果對(duì)你有所幫助的話，別忘了一鍵三連喲，謝謝寶子們?！

柚子快報(bào)激活碼778899分享：C語言：數(shù)據(jù)結(jié)構(gòu)（雙向鏈表）

http://yzkb.51969.com/

相關(guān)鏈接