柚子快報邀請碼778899分享：數(shù)據(jù)結(jié)構(gòu) 帶頭雙向循環(huán)鏈表
柚子快報邀請碼778899分享：數(shù)據(jù)結(jié)構(gòu) 帶頭雙向循環(huán)鏈表
文章目錄
帶頭雙向循環(huán)鏈表定義雙向鏈表的功能雙向鏈表的功能實現(xiàn)初始化代碼實現(xiàn)
創(chuàng)建新節(jié)點打印鏈表代碼實現(xiàn)
頭插代碼實現(xiàn)
尾插代碼實現(xiàn)
頭刪代碼實現(xiàn)
尾刪代碼實現(xiàn)
銷毀鏈表代碼實現(xiàn)
查找下標代碼實現(xiàn)
在任意位置之前插入數(shù)據(jù)代碼實現(xiàn)
刪除任意位置的數(shù)據(jù)代碼實現(xiàn)
源碼List.hList.ctest.c
前言：當我們想要挪動大量數(shù)據(jù)的時候，單鏈表的效率就很低了，比如尾插，要找到尾，通過遍歷的時間復雜度最壞情況是O(N),所以我們引進結(jié)構(gòu)復雜但效率高的雙向帶頭循環(huán)鏈表
帶頭雙向循環(huán)鏈表
帶頭雙向循環(huán)鏈表指得是什么呢？就是既存儲了上一個節(jié)點的地址，又存儲了下一個節(jié)點的地址，帶有哨兵位，加上哨兵位的頭指向了鏈表的尾，鏈表的尾的下一個指向了哨兵位的頭
定義
和單鏈表一樣，有指針域和數(shù)據(jù)域，不過比單鏈表多了一個存儲上一個節(jié)點的指針
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
雙向鏈表的功能
和單鏈表大差不差
頭插 尾插 頭刪 尾刪 找到某個位置的下標 在任意位置插入 刪除任意位置的數(shù)據(jù) 銷毀鏈表
標明：我們先實現(xiàn)每個函數(shù)的接口，插入和刪除用這兩個函數(shù)(在任意位置插入 ，刪除任意位置的數(shù)據(jù))復用效率會快好多
雙向鏈表的功能實現(xiàn)
初始化
初始化需要傳二級指針，因為初始化需要改變結(jié)構(gòu)體指針，也就是要對頭進行初始化，讓頭指向自己，如果傳一級，就相當于傳值調(diào)用，形參的改變并不會影響實參，而后面的函數(shù)接口都不用二級，因為改變的是結(jié)構(gòu)體，也就是“箭頭”的指向 注：你可以返回結(jié)構(gòu)體指針，也可以傳二級指針，我們這里采用的是返回結(jié)構(gòu)體指針
代碼實現(xiàn)
ListNode* ListInit()
{
ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
phead->prev = phead;
phead->next = phead;
return phead;
}
創(chuàng)建新節(jié)點
ListNode* BuyListNode(LTDataType x)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->data = x;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
打印鏈表
代碼實現(xiàn)
void ListPrint(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
頭插
首先創(chuàng)建個哨兵，也就是新節(jié)點，一定要先斷言鏈表不為空哦
代碼實現(xiàn)
void ListPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
ListNode* next = phead->next;
phead->next = newNode;
newNode->prev = phead;
newNode->next = next;
next->prev = newNode;
}
尾插
先定義一個尾指針，使代碼清晰易懂，不用像單鏈表一樣考慮一個節(jié)點，兩個節(jié)點，多個節(jié)點的問題
代碼實現(xiàn)
void ListPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
ListNode* tail = phead->prev;
newNode->prev = tail;
tail->next = newNode;
newNode->next = phead;
phead->prev = newNode;
//ListInsert(phead, x);
}
頭刪
當刪到只剩哨兵位的話就不能刪了
代碼實現(xiàn)
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* next = phead->next;
phead->next = next->next;
next->next->prev = phead;
ListNode* nextNext = next->next;
phead->next = nextNext;
nextNext->prev = phead;
free(next);
//ListErase(phead->next);
}
尾刪
刪到最后只剩哨兵位，就不要刪了，鏈表為空，再去解引用就會報錯
代碼實現(xiàn)
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* tail = phead->prev;
ListNode* tailprev = tail->prev;
free(tail);
phead->prev = tailprev;
tailprev->next = phead;
//ListErase(phead->prev);
}
銷毀鏈表
循環(huán)結(jié)束的條件是當遍歷到等于哨兵位時，說明已經(jīng)銷毀完數(shù)據(jù)了，再把哨兵位free掉就好
代碼實現(xiàn)
void ListDestroy(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur->next != phead)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}
查找下標
代碼實現(xiàn)
ListNode* ListFind(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
在任意位置之前插入數(shù)據(jù)
代碼實現(xiàn)
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newNode = BuyListNode(x);
ListNode* posPrev = pos->prev;
posPrev->next = newNode;
newNode->prev = posPrev;
newNode->next = pos;
pos->prev = newNode;
}
刪除任意位置的數(shù)據(jù)
代碼實現(xiàn)
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* posPre = pos->prev;
ListNode* posNext = pos->next;
posPre->next = posNext;
posNext->prev = posPre;
free(pos);
pos = NULL;
}
源碼
List.h
#pragma once
#include
#include
#include
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
ListNode* ListInit();
void ListPushBack(ListNode* phead, LTDataType x);
void ListPrint(ListNode* phead);
void ListPopBack(ListNode* phead);
void ListPopFront(ListNode* phead);
void ListPushFront(ListNode* phead,LTDataType x);
ListNode* ListFind(ListNode* phead, LTDataType x);
void ListInsert(ListNode* pos, LTDataType x);
void ListErase(ListNode* pos);
void ListDestroy(ListNode* phead);
List.c
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
ListNode* ListInit()
{
ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
phead->prev = phead;
phead->next = phead;
return phead;
}
ListNode* BuyListNode(LTDataType x)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->data = x;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
void ListPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
ListNode* tail = phead->prev;
newNode->prev = tail;
tail->next = newNode;
newNode->next = phead;
phead->prev = newNode;
也處理了空鏈表的問題，不用像單鏈表一樣考慮一個節(jié)點，兩個節(jié)點，多個節(jié)點的問題
//ListInsert(phead, x);
}
void ListPrint(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);//刪到最后只剩哨兵位，就不要刪了，鏈表為空，再去解引用就會報錯
/*ListNode* tail = phead->prev;
ListNode* tailprev = tail->prev;
free(tail);
phead->prev = tailprev;
tailprev->next = phead;*/
ListErase(phead->prev);
}
void ListPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
ListNode* next = phead->next;
phead->next = newNode;
newNode->prev = phead;
newNode->next = next;
next->prev = newNode;
//ListInsert(phead->next, x);
}
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* next = phead->next;
phead->next = next->next;
next->next->prev = phead;
ListNode* nextNext = next->next;
phead->next = nextNext;
nextNext->prev = phead;
free(next);
//ListErase(phead->next);
}
ListNode* ListFind(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//在pos位置之前插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newNode = BuyListNode(x);
ListNode* posPrev = pos->prev;
posPrev->next = newNode;
newNode->prev = posPrev;
newNode->next = pos;
pos->prev = newNode;
}
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* posPre = pos->prev;
ListNode* posNext = pos->next;
posPre->next = posNext;
posNext->prev = posPre;
free(pos);
pos = NULL;
}
void ListDestroy(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur->next != phead)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void test2()
{
ListNode* plist = ListInit();
//尾插
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPrint(plist);
//頭插
ListPushFront(plist, 10);
ListPushFront(plist, 18);
ListPushFront(plist, 17);
ListPushFront(plist, 16);
ListPushFront(plist, 15);
ListPrint(plist);
/*
//在pos位置前插入
ListNode* pos1 = ListFind(plist, 3);
if(pos1)
{
ListInsert(pos1,30);
}
ListPrint(plist);
*/
/* //刪除pos位置的數(shù)據(jù)
ListNode* pos = ListFind(plist, 2);
if(pos)
{
ListErase(pos);
}
ListPrint(plist);
*/
頭刪
//ListPopFront(plist);
//ListPopFront(plist);
//ListPrint(plist);
尾刪
//ListPopBack(plist);
//ListPrint(plist);
//ListPopBack(plist);
//ListPrint(plist);
//銷毀
ListDestroy(plist);
plist = NULL;
}
int main()
{
//test1();
test2();
return 0;
}
柚子快報邀請碼778899分享：數(shù)據(jù)結(jié)構(gòu) 帶頭雙向循環(huán)鏈表
參考文章
本文內(nèi)容根據(jù)網(wǎng)絡資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Megamarket外貿(mào)巨型市
