?

??Yan-英杰的主頁

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

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

---

?目錄

一、什么是雙向鏈表

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

---

一、什么是雙向鏈表

?

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

二、雙向鏈表的實(shí)現(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前一個(gè)位置添加節(jié)點(diǎn)
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的實(shí)現(xiàn),我們在實(shí)現(xiàn)頭插尾插時(shí),為了更加遍歷的實(shí)現(xiàn)功能，我們創(chuàng)建了BuyListNode函數(shù)，malloc一塊新的空間，并且對其進(jìn)行初始化，返回其類型

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ù)

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

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

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

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

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

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

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

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

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ù)

??????????????? 尾插與尾刪功能，我們先對其進(jìn)行暴力檢查，通過LTInsert和LTErase函數(shù)進(jìn)行實(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ù)

???????? 頭插與頭刪功能，我們先對其進(jìn)行暴力檢查，通過LTInsert和LTErase函數(shù)進(jìn)行實(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ù)的實(shí)現(xiàn)

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

??????????????? LTDestory:當(dāng)我們退出鏈表時(shí)，對其進(jìn)行銷毀

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;
}