雙向鏈表

鏈表分類 8種 (帶頭/不帶頭 單向/雙向 循環/循環)
最常用兩種 單鏈表(不帶頭單向不循環鏈表) 雙向鏈表（帶頭雙向循環鏈表）

雙鏈表有 頭節點（哨兵位） 后繼指針(next) 前驅指針(prev)

雙向鏈表為空時，為一個哨兵位

同樣采用多文件操作

1.申請節點

//申請節點
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL)//申請不成功{perror("malloc fail");exit(1);//給非0值}node->data = x;node->next = node->prev = node;return node;
}

2.鏈表初始化

void LTInit(LTNode** pphead)
{//給雙向鏈表創建一個哨兵位*pphead = LTBuyNode(-1);//隨便賦一個值
}

3.尾插

以上圖為例 尾插時 head->prev指向的就是d3

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;//也就是newnode->prev指向d3newnode->next = phead;phead->prev->next = newnode;//d3的next指針指向新節點phead->prev = newnode;
}

4.打印鏈表

讓pcur指向phead的next指針，然后遍歷鏈表，直到pcur=phead

void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

5.頭插

頭插是插到頭結點與d1之間，插在頭結點前邊跟尾插一樣(因為鏈表是雙向循環的)

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;//先改影響小的phead->next = newnode;}

6.尾刪

void LTPopBack(LTNode* phead)
{//鏈表必須有效且鏈表不能為空assert(phead && phead->next != phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;//刪除del節點free(del);del = NULL;}

7.頭刪

void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;//刪除del節點free(del);del = NULL;
}

8.查找

LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//沒有找到return NULL;
}

9.指定位置插入

10.刪除pos節點

void LTErase(LTNode* pos)//這里傳一級指針是為了保持接口的一致性 其他函數傳的都是一級指針
{//pos理論上來說不能為phead,但是參數沒有phead，所以無法增加校驗pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

11.鏈表的銷毀

void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur->next != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此時pcur指向phead,而phead還沒有被銷毀free(phead);phead = NULL;//如果不置為空 plist(保存的地址空間被釋放掉了) 若后續不再使用plist則沒問題(野指針)}

12.程序源碼

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
//定義雙向鏈表節點的結構
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;}LTNode;//聲明雙向鏈表種提供的方法//初始化
void LTInit(LTNode** pphead);
void LTPrint(LTNode* phead);
//插入數據之前，鏈表必須初始化到只有一個頭結點的情況
// 不改變哨兵位的地址，所以傳一級指針即可
//尾插
void LTPushBack(LTNode* phead,LTDataType x);
//頭插
void LTPushFront(LTNode* phead, LTDataType x);void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
//在pos位置之后插入數據
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);void LTDesTroy(LTNode* phead);

List.c

#include"List.h";void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//申請節點
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");exit(1);//給非0值}node->data = x;node->next = node->prev = node;return node;
}
void LTInit(LTNode** pphead)
{//給雙向鏈表創建一個哨兵位*pphead = LTBuyNode(-1);
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;//不能交換位置phead->prev = newnode;
}
//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;//先改影響小的phead->next = newnode;}
//尾刪
void LTPopBack(LTNode* phead)
{//鏈表必須有效且鏈表不能為空assert(phead && phead->next != phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;//刪除del節點free(del);del = NULL;}
//頭刪
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;//刪除del節點free(del);del = NULL;
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//沒有找到return NULL;
}
//指定位置插入數據
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;}
//刪除pos節點
void LTErase(LTNode* pos)//這里傳一級指針是為了保持接口的一致性 其他函數傳的都是一級指針
{//pos理論上來說不能為phead,但是參數沒有phead，所以無法增加校驗pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}
//鏈表銷毀
void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur->next != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此時pcur指向phead,而phead還沒有被銷毀free(phead);phead = NULL;//如果不置為空 plist(保存的地址空間被釋放掉了) 若后續不再使用plist則沒問題(野指針)}
//LTErase和LTDestroy參數理論上要傳二級，因為我們需要讓形參的改變影響到實參，但是為了接口的一致性才穿的一級
//傳一級存在的問題是，當形參phead置為NULL后，實參plist不會被修改為NULL,因此解決方法是 調用完方法后手動將實參置為NULL

test.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h";void ListTest01()
{LTNode* plist = NULL;LTInit(&plist);LTPushBack(plist, 1);LTPrint(plist);LTPushFront(plist, 2);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopFront(plist);LTPushFront(plist, 3);LTPrint(plist);LTNode* find = LTFind(plist, 3);{if (find == NULL){printf("找不到\n");}else{printf("找到了\n");}}LTInsert(find, 66);LTPrint(plist);LTErase(find);LTPrint(plist);}
int main()
{ListTest01();return 0;
}