資料結構之雙向連結清單(C語言實作)
本次介紹雙向連結清單，雙向連結清單是在單連結清單的基礎上增加一個前驅指針，通過某個節點可以直接找到它的前驅和後繼，這個對于删除操作來說更加容易，不需要另外再定義一個指針來指向它的前驅。
和以前一樣，首先介紹雙向連結清單的通用操作：
1.連結清單的初始化
2.申請一個連結清單節點
3.連結清單的頭插法
4.連結清單的尾插法
5.擷取連結清單長度
6.删除連結清單節點
7.查找指定值的節點
8.銷毀連結清單(釋放連結清單所有節點的記憶體空間)
9.輸出單連結清單(輸出單連結清單所有節點的資料域)
說明：以下雙向連結清單的實作，是資料域以整型為例，而且帶有頭結點。
一、雙向連結清單
1. 連結清單的結構
typedef struct _DNode
{
int data;
struct _DNode* pre;//前驅指針
struct _DNode* next; //後繼指針
}DNode, *DList;
2.連結清單的操作
(1).連結清單的初始化(帶頭結點)
這裡的初始化隻要是指初始化頭結點的指針域
void InitList(DList plist)//初始化頭結點
{
if (NULL == plist)
return;
plist->next = NULL;
plist->pre = NULL;
}
(2).申請一個連結清單節點
從堆中申請一個節點，注意這裡是從堆中申請的記憶體，隻能通過free(p)顯式釋放記憶體。即使是局部變量，該記憶體也不會随着函數調用完成而釋放該記憶體。
DNode* BuyNode(int val)
{
DNode* pTmp = (DNode*)malloc(sizeof(DNode));
pTmp->data = val;
pTmp->next = NULL;
pTmp->pre = NULL;
return pTmp;
}
(3).連結清單頭插法
這裡的連結清單是帶有頭結點的，是以每次新插入的節點應插入頭結點後面。注意看看下面的注釋
void InsertHead(DList plist, int val)
{
DNode* pTmp = BuyNode(val);//申請一個新的節點
pTmp->next = plist->next;
pTmp->pre = plist;
if (NULL != pTmp->next)//這裡的判斷一定不能少，讀者可以試想去掉這個會發生什麼
{
pTmp->next->pre = pTmp;//後一個節點的前驅指向pTmp
}
plist->next = pTmp;
}
(4).連結清單尾接法
每次将新插入的節點插入到最後一個節點後面，是以采用尾接法插入節點時首先要找到尾節點
void InsertTail(DList plist, int val)
{
DNode* pTmp = BuyNode(val);
DNode* pCur = plist;
while (NULL != pCur->next)
{
pCur = pCur->next;
}
pTmp->pre = pCur;
pCur->next = pTmp;
}
(5).擷取連結清單長度
對連結清單進行周遊，每周遊一個節點，計數器加一。
int GetListLen(DList plist)
{
DNode* pTmp = plist->next;
int iCount = 0;
while (NULL != pTmp)
{
++iCount;
pTmp = pTmp->next;
}
return iCount;
}
(6).删除連結清單節點
删除指定值的連結清單節點時，需要周遊該連結清單，找到對應節點後想要删除該節點必須要知道該節點的前驅節點，這樣才能正确删除該節點。這裡要注意對于最後一個節點的删除要先進行判斷，讀者可以自己思考一下這樣做的原因
bool Delete(DList plist, int key)
{
DNode* pPre = plist;//前驅結點
DNode* pCur = plist->next;//後繼節點
while (NULL != pCur)
{
if (pCur->data == key)
{
if (NULL != pCur->next)//這涉及到删除最後一個節點，因為對于最後一個節點來說pCur->next為空，也即pCur->next沒有pre
{
pCur->next->pre = pCur->pre;
}
pCur->pre->next = pCur->next;
return true;
}
else
{
pPre = pCur;
pCur = pCur->next;
}
}
return false;
}
(7).查找指定值的節點
查找指定值的節點也需要從頭到尾周遊連結清單，若找到則傳回該節點，沒找到則傳回NULL。
DNode* Search(DList plist, int key)
{
DNode* pCur = plist->next;
while (NULL != pCur)
{
if (pCur->data == key)
{
return pCur;
}
pCur = pCur->next;
}
return NULL;
}
(8).銷毀連結清單
銷毀連結清單就是釋放連結清單中所有節點的記憶體。
void Destroy(DList plist)
{
DNode* pTmp = plist->next;//這裡必須從plist->next開始釋放記憶體，原因有兩個
while (NULL != pTmp) //一是頭結點不是由malloc開辟的，不能有free釋放
{ //二是一個空連結清單是指隻有頭結點的連結清單，銷毀操作就是把原連結清單置為空連結清單
plist = pTmp->next;
free(pTmp);
pTmp = plist;
}
}
(9).輸出單連結清單
輸出單連結清單的操作也比較簡單，從頭到尾周遊單連結清單，每周遊一個節點就輸出該節點的指針域
void ShowDList(DList plist)
{
DNode* pCur = plist->next;
while (NULL != pCur)
{
printf("%5d", pCur->data);
pCur = pCur->next;
}
printf("\n");
}
最後附上完整代碼和運作結果：
//DLink.h
#include#includetypedef struct _DNode
{
int data;
struct _DNode* pre;//前驅指針
struct _DNode* next; //後繼指針
}DNode, *DList;
void InitList(DList plist);
void InsertHead(DList plist, int val);
void InsertTail(DList plist, int val);
bool Delete(DList plist, int key);
DNode* Search(DList plist, int key);
int GetListLen(DList plist);
void Destroy(DList plist);
DNode* BuyNode(int val);
void ShowDList(DList plist);
//DLink.c
#include "test.h"
int main()
{
DNode head;
InitList(&head);
for (int i = 1; i < 5; ++i)
{
InsertHead(&head, i);
}
ShowDList(&head);
printf("DList length is %d \n", GetListLen(&head));
for (int i = 6; i < 10; ++i)
{
InsertTail(&head, i);
}
ShowDList(&head);
printf("DList length is %d \n", GetListLen(&head));
printf("search 第一個節點4:");
DNode* pTmp = Search(&head, 4);
printf("%d\n", pTmp->data);
printf("search 最後一個節點9:");
pTmp = Search(&head, 9);
printf("%d\n", pTmp->data);
printf("删除第一個節點4:\n");
if (Delete(&head, 4))
{
ShowDList(&head);
}
else
{
printf("Not Fount!!!\n");
}
printf("删除最後一個節點9:\n");
if (Delete(&head, 9))
{
ShowDList(&head);
}
else
{
printf("Not Fount!!!\n");
}
Destroy(&head);//銷毀連結清單
return 0;
}
void InitList(DList plist)//初始化頭結點
{
if (NULL == plist)
return;
plist->next = NULL;
plist->pre = NULL;
}
DNode* BuyNode(int val)
{
DNode* pTmp = (DNode*)malloc(sizeof(DNode));
pTmp->data = val;
pTmp->next = NULL;
pTmp->pre = NULL;
return pTmp;
}
void ShowDList(DList plist)
{
DNode* pCur = plist->next;
while (NULL != pCur)
{
printf("%5d", pCur->data);
pCur = pCur->next;
}
printf("\n");
}
void InsertHead(DList plist, int val)
{
DNode* pTmp = BuyNode(val);//申請一個新的節點
pTmp->next = plist->next;
pTmp->pre = plist;
if (NULL != pTmp->next)//這裡的判斷一定不能少，讀者可以試想去掉這個會發生什麼
{
pTmp->next->pre = pTmp;//後一個節點的前驅指向pTmp
}
plist->next = pTmp;
}
void InsertTail(DList plist, int val)
{
DNode* pTmp = BuyNode(val);
DNode* pCur = plist;
while (NULL != pCur->next)
{
pCur = pCur->next;
}
pTmp->pre = pCur;
pCur->next = pTmp;
}
bool Delete(DList plist, int key)
{
DNode* pPre = plist;//前驅結點
DNode* pCur = plist->next;//後繼節點
while (NULL != pCur)
{
if (pCur->data == key)
{
if (NULL != pCur->next)//這涉及到删除最後一個節點，因為對于最後一個節點來說pCur->next為空，也即pCur->next沒有pre
{
pCur->next->pre = pCur->pre;
}
pCur->pre->next = pCur->next;
return true;
}
else
{
pPre = pCur;
pCur = pCur->next;
}
}
return false;
}
DNode* Search(DList plist, int key)
{
DNode* pCur = plist->next;
while (NULL != pCur)
{
if (pCur->data == key)
{
return pCur;
}
pCur = pCur->next;
}
return NULL;
}
int GetListLen(DList plist)
{
DNode* pTmp = plist->next;
int iCount = 0;
while (NULL != pTmp)
{
++iCount;
pTmp = pTmp->next;
}
return iCount;
}
void Destroy(DList plist)
{
DNode* pTmp = plist->next;
while (NULL != pTmp)
{
plist = pTmp->next;
free(pTmp);
pTmp = plist;
}
}
運作結果：
