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

http://yzkb.51969.com/

目錄

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

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

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

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

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

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

ListNode.h

#pragma once

#include

#include

#include

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

typedef int Ltdatatype;

typedef struct ListNode

{

Ltdatatype data;

struct ListNode* prev;//指向前一個節(jié)點的指針

struct ListNode* next;//指向后一個節(jié)點的指針

}ListNode;

//雙向鏈表的初始化

ListNode* LtInit();

//尾插

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

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

//打印鏈表

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"

//申請節(jié)點

ListNode* LtBuyNode(Ltdatatype x)

{

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

if (node == NULL)

{

perror("malloc fail");

exit(1);

}

//申請成功

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é)點的指向

newnode->prev = phead->prev;

newnode->next = phead;

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

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;

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

phead->next->prev = newnode;

phead->next = newnode;

}

//尾刪

LtPopBack(ListNode* phead)

{

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

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

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

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

phead->prev = DelPrev;

DelPrev->next = phead;

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

Del = NULL;

}

//頭刪

LtPopFront(ListNode* phead)

{

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

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

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

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

phead->next = DelNext;

DelNext->prev = phead;

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

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的前一個節(jié)點

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

PosPrev->next = PosNext;

PosNext->prev = PosPrev;

free(pos);

//pos = NULL;這里就算置空了，也不會影響實參

}

//銷毀鏈表

void LtDestroy(ListNode* phead)

{

ListNode* pcur = phead->next;

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

while (pcur != phead)

{

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

free(pcur);

pcur = Next;

}

//此時pcur指向phead，而phead還沒有被銷毀

free(phead);

pcur = NULL;

}

text.c

#define _CRT_SECURE_NO_WARNINGS

#include "ListNode.h"

void LtnodeTest()

{

//測試初始化

ListNode* plist = LtInit();

//測試尾插

LtPushBack(plist,1);

LtPushBack(plist,2);

LtPushBack(plist,3);

//測試打印

LtPrint(plist);

//測試頭插

//LtPushFront(plist,4);

//LtPushFront(plist,5);

//LtPushFront(plist,6);

//LtPrint(plist);

//測試尾刪

LtPopBack(plist);

LtPrint(plist);

//測試頭刪

//LtPopFront(plist);

//LtPrint(plist);

//測試查找

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

//if (find)

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

//else

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

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

//LtInsert(find,88);

//LtPrint(plist);

//測試刪除pos位置

//LtErase(find);

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

//LtPrint(plist);

//測試銷毀鏈表

//LtDestroy(plist);

//plist = NULL;

}

int main()

{

LtnodeTest();

return 0;

}

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

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

http://yzkb.51969.com/

相關(guān)鏈接