?

??Yan-英杰的主頁

悟已往之不諫 知來者之可追

??? C++程序員，2024屆電子信息研究生

---

?目錄

一、什么是雙向鏈表

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

---

一、什么是雙向鏈表

?

????????雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)節(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。一般我們都構(gòu)造雙向循環(huán)鏈表。

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

????????List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;}LTNode;LTNode* LTInit();
void LTDestory(LTNode* phead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode * phead);
void LTPushBack(LTNode* phead,LTDataType x);
void LTPopBack(LTNode * phead);void LTPushFront(LTNode *phead,LTDataType x);
void LTPopFront(LTNode* phead);void LTInsert(LTNode* pos,LTDataType x);
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDataType x);

??????? List.c

????????

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("fail:malloc");exit(-1);}node->next = NULL;node->prev = NULL;node->data = x;return node;
}LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}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);printf("<=phead=>");LTNode* cur = phead->next;while (cur != phead){printf("%d<=>",cur->data);cur = cur->next;}printf("\n");
}void LTPushBack(LTNode* phead,LTDataType x)
{	assert(phead);LTInsert(phead,x);
}void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->prev);
}void LTPushFront(LTNode* phead,LTDataType x)
{assert(phead);LTInsert(phead->next,x);
}void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->next);
}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;
}//在Pos前一個位置添加節(jié)點
void LTInsert(LTNode* pos,LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyListNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}void LTErase(LTNode* pos)
{assert(pos);LTNode* p = pos->prev;LTNode* n = pos->next;p->next = n;n->prev = p;free(pos);pos = NULL;
}

?? 思路:

??????? BuyListNode函數(shù)

??????? BuyListNode的實現(xiàn),我們在實現(xiàn)頭插尾插時,為了更加遍歷的實現(xiàn)功能，我們創(chuàng)建了BuyListNode函數(shù)，malloc一塊新的空間，并且對其進行初始化，返回其類型

LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("fail:malloc");exit(-1);}node->next = NULL;node->prev = NULL;node->data = x;return node;
}

?????? LTInit函數(shù)

??????? 在實現(xiàn)該鏈表前，我們對其進行初始化，對其哨兵位的頭節(jié)點，進行循環(huán)指向

??????? 哨兵位頭節(jié)點的出現(xiàn)，使得鏈表添加與刪除效率大大提高

LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

????????LTInsert和LTErase函數(shù)

??????????????? LTInsert函數(shù)的實現(xiàn):

????????????????????????????????????????????????我們找到pos的前一個節(jié)點位置，進行操作，首先我們找到pos的前一個位置，保存該節(jié)點，創(chuàng)建新的節(jié)點，將pos前一個位置的節(jié)點next指向新節(jié)點，新節(jié)點的prev指向pos前一個位置，新節(jié)點的next指向pos，pos的前一個位置指向新節(jié)點

?????????????? LTErase函數(shù)的實現(xiàn)：

??????????????????????????????????????????????? 刪除pos位置的節(jié)點，先暴力檢查是否為空，其中只有哨兵位的頭節(jié)點，如果只有頭節(jié)點則直接報錯，保存pos位置節(jié)點的前一個節(jié)點和后一個節(jié)點，讓pos的prev和next分別指向前一個位置和后一個位置的節(jié)點

void LTInsert(LTNode* pos,LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyListNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}void LTErase(LTNode* pos)
{assert(pos);LTNode* p = pos->prev;LTNode* n = pos->next;p->next = n;n->prev = p;free(pos);pos = NULL;
}

????????LTPushBack與LTPopBack函數(shù)

??????????????? 尾插與尾刪功能，我們先對其進行暴力檢查，通過LTInsert和LTErase函數(shù)進行實現(xiàn)該功能

void LTPushBack(LTNode* phead,LTDataType x)
{	assert(phead);LTInsert(phead,x);
}void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->prev);
}

??????? LTPushFront和LTPopFront函數(shù)

???????? 頭插與頭刪功能，我們先對其進行暴力檢查，通過LTInsert和LTErase函數(shù)進行實現(xiàn)該功能

void LTPushFront(LTNode* phead,LTDataType x)
{assert(phead);LTInsert(phead->next,x);
}void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->next);
}

????????? LTDestory和LTPrint函數(shù)的實現(xiàn)

?????????????? LTPrint: 當我們功能實現(xiàn)時，LTPrint函數(shù)可在控制臺進行打印和輸出，優(yōu)先找到哨兵位頭節(jié)點的下一位，我們對其進行循環(huán)，當循環(huán)節(jié)點等于哨兵位時，停止循環(huán)

??????????????? LTDestory:當我們退出鏈表時，對其進行銷毀

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);printf("<=phead=>");LTNode* cur = phead->next;while (cur != phead){printf("%d<=>",cur->data);cur = cur->next;}printf("\n");
}

??????????????????ListTest.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
void ListTest()
{LTNode* phead = LTInit();LTPushBack(phead, 1);LTPushBack(phead, 2);LTPushBack(phead, 3);LTPrint(phead);LTPopBack(phead);LTPrint(phead);LTPushFront(phead,10);LTPrint(phead);LTPopFront(phead);LTPrint(phead);
}int main()
{ListTest();return 0;
}