程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 雙向鏈表（C語言）詳解及例程

雙向鏈表（C語言）詳解及例程

編輯：關於C語言

雙（向）鏈表中有兩條方向不同的鏈，即每個結點中除next域存放後繼結點地址外，還增加一個指向其直接前趨的指針域prior。雙向鏈表在查找時更方便特別是大量數據的遍歷

雙向鏈表（C語言）詳解及例程 - 海邊風 - 鴨梨柵搭

注意：
    　①雙鏈表由頭指針head惟一確定的。
    　②帶頭結點的雙鏈表的某些運算變得方便。
    　③將頭結點和尾結點鏈接起來，為雙（向）循環鏈表。

2、雙向鏈表的結點結構和形式描述
①結點結構(見上圖a)

②形式描述
    typedef struct dlistnode{
         DataType data;（數據類型按自己要求更改）
         struct dlistnode *prior,*next;
      }DListNode;
    typedef DListNode *DLinkList;
    DLinkList head;

　由於雙鏈表的對稱性，在雙鏈表能能方便地完成各種插入、刪除操作。
①雙鏈表的前插操作

雙向鏈表（C語言）詳解及例程 - 海邊風 - 鴨梨柵搭

ps：注意箭頭沒有直入框內而是整體代表指向的是整個結點包括 prior data next

    void DInsertBefore(DListNode *p,DataType x)
      {//在帶頭結點的雙鏈表中，將值為x的新結點插入*p之前，設p≠NULL
        DListNode *s=malloc(sizeof(DListNode));//①（為鏈表結點動態分配內存）
        s->data=x;//② （將數據X的值賦給s->data)
        s->prior=p->prior;//③ (將結點p的前驅的值賦給s的前驅使s的前驅指向原來p之前的結點)
        s->next=p;//④ （使s的後驅指向p 經過2.3.4步結點s各個部分賦值完畢）
        p->prior->next=s;//⑤ （原來p之前的結點的後驅指向s）
        p->prior=s;//⑥  （使p的前驅指向s）
       }

PS: 第⑤⑥步的順序不能改變，想想為什麼呢？

②雙鏈表上刪除結點*p自身的操作

雙向鏈表（C語言）詳解及例程 - 海邊風 - 鴨梨柵搭

void DDeleteNode(DListNode *p)
      {//在帶頭結點的雙鏈表中，刪除結點*p，設*p為非終端結點
          p->prior->next=p->next;//① （使p的前一個結點的後驅直接指向原來的p的後驅）
          p->next->prior=p->prior;//② （使p的後一個結點的前驅直接為原來p的前一個結點）
          free(p);//③ （釋放p的內存這個很重要特別是處理大量數據時）
      }
注意：
    　與單鏈表上的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時修改兩個方向上的指針。
    　上述兩個算法的時間復雜度均為O(1)。

雙向鏈表是一種基本的數據結構，在許多場合都會使用到。最近正在編寫一個基於Linux的GUI系統，裡邊許多地方都要使用到雙向鏈表，於是寫了一個通用的雙向鏈表。代碼如下：

#ifndef __STDLIST_H__
#define __STDLIST_H__
typedef struct tagSTDNODE STDNODE, *LPSTDNODE;
typedef struct tagSTDLIST STDLIST, *LPSTDLIST;
// 鏈表數據結構
struct tagSTDNODE {
LPSTDNODE lpPrev;
LPSTDNODE lpNext;
};
// 鏈表節點結構
struct tagSTDLIST {
LPSTDNODE lpHead;
LPSTDNODE lpTail;
};
// 用於鏈表擴展的宏
#define NODE_INITIALIZER ((STDNODE){ .lpPrev = NULL, .lpNext = NULL, })
#define LIST_INITIALIZER ((STDLIST){ .lpHead = NULL, .lpTail = NULL, })
#define DECLARELISTNODE() 　　STDNODE __snStdNode
#define INIT_LISTNODE() __snStdNode = NODE_INITIALIZER
// 初始化鏈表
STATIC INLINE
LPSTDLIST TWINAPI StdListInit(
LPSTDLIST lpList
) {
lpList->lpHead = NULL;
lpList->lpTail = NULL;
return lpList;
}
// 獲取鏈表頭部節點
STATIC INLINE
LPSTDNODE TWINAPI StdListGetHeadNode(
LPSTDLIST lpList
) {
return lpList->lpHead;
}
// 獲取鏈表尾部節點
STATIC INLINE
LPSTDNODE TWINAPI StdListGetTailNode(
LPSTDLIST lpList
) {
return lpList->lpTail;
}
// 獲取給定節點的下一個節點
STATIC INLINE
LPSTDNODE TWINAPI StdListGetNextNode(
LPSTDNODE lpNode
) {
return lpNode->lpNext;
}
// 獲取給定節點的上一個節點
STATIC INLINE
LPSTDNODE TWINAPI StdListGetPrevNode(
LPSTDNODE lpNode
) {
return lpNode->lpPrev;
}
// 在鏈表頭部插入一個節點
STATIC INLINE
VOID TWINAPI StdListPushFront(
LPSTDLIST lpList,
LPSTDNODE lpNode
) {
lpNode->lpPrev = NULL;
lpNode->lpNext = lpList->lpHead;
if(lpList->lpHead)
lpList->lpHead->lpPrev = lpNode;
else
lpList->lpTail = lpNode;
lpList->lpHead = lpNode;
}
// 在鏈表尾部插入一個節點
STATIC INLINE
VOID TWINAPI StdListPushBack(
LPSTDLIST lpList,
LPSTDNODE lpNode
) {
lpNode->lpNext = NULL;
lpNode->lpPrev = lpList->lpTail;
if(lpList->lpTail)
lpList->lpTail->lpNext = lpNode;
else
lpList->lpHead = lpNode;
lpList->lpTail = lpNode;
}
// 在指定節點後插入一個節點
STATIC INLINE
VOID TWINAPI StdListInsert(
LPSTDLIST lpList,
LPSTDNODE lpAfter,
LPSTDNODE lpNode
) {
if(lpAfter) {
if(lpAfter->lpNext)
lpAfter->lpNext->lpPrev = lpNode;
else
lpList->lpTail = lpNode;
lpNode->lpPrev = lpAfter;
lpNode->lpNext = lpAfter->lpNext;
lpAfter->lpNext = lpNode;
} else {
StdListPushFront(lpList, lpNode);
}
}
// 從鏈表頭部彈出一個節點
STATIC INLINE
LPSTDNODE TWINAPI StdListPopFront(
LPSTDLIST lpList
) {
if(lpList->lpHead) {
LPSTDNODE lpNode = lpList->lpHead;
if(lpList->lpHead->lpNext)
lpList->lpHead->lpNext->lpPrev = NULL;
else
lpList->lpTail = NULL;
lpList->lpHead = lpList->lpHead->lpNext;
lpNode->lpPrev = lpNode->lpNext = NULL;
return lpNode;
} else {
return NULL;
}
}
// 從鏈表尾部彈出一個節點
STATIC INLINE
LPSTDNODE TWINAPI StdListPopBack(
LPSTDLIST lpList
) {
if(lpList->lpTail) {
LPSTDNODE lpNode = lpList->lpTail;
if(lpList->lpTail->lpPrev)
lpList->lpTail->lpPrev->lpNext = NULL;
else
lpList->lpHead = NULL;
lpList->lpTail = lpList->lpTail->lpPrev;
lpNode->lpPrev = lpNode->lpNext = NULL;
return lpNode;
} else {
return NULL;
}
}
// 從鏈表中刪除給定節點
STATIC INLINE
LPSTDNODE TWINAPI StdListRemove(
LPSTDLIST lpList,
LPSTDNODE lpNode
) {
if(lpNode->lpPrev)
lpNode->lpPrev->lpNext = lpNode->lpNext;
else
lpList->lpHead = lpNode->lpNext;
if(lpNode->lpNext)
lpNode->lpNext->lpPrev = lpNode->lpPrev;
else
lpList->lpTail = lpNode->lpPrev;
return lpNode;
}
// 檢查鏈表是否為空
STATIC INLINE
BOOL TWINAPI StdListIsEmpty(
LPSTDLIST lpList
) {
if(lpList->lpHead || lpList->lpTail)
return FALSE;
else
return TRUE;
}
// 獲取鏈表中的節點數
STATIC INLINE
LONG TWINAPI StdListGetSize(
LPSTDLIST lpList
) {
LONG lnSize = 0;
LPSTDNODE lpNode = StdListGetHeadNode(lpList);
while(lpNode) {
++ lnSize;
lpNode = StdListGetNextNode(lpNode);
}
return lnSize;
}
// 合並兩個鏈表
STATIC INLINE
LPSTDLIST TWINAPI StdListCombine(
LPSTDLIST lpList1,
LPSTDLIST lpList2
) {
if(!StdListIsEmpty(lpList2)) {
if(!StdListIsEmpty(lpList1)) {
lpList1->lpTail->lpNext = lpList2->lpHead;
lpList2->lpHead->lpPrev = lpList1->lpTail;
lpList1->lpTail = lpList2->lpTail;
} else {
lpList1->lpHead = lpList2->lpHead;
lpList1->lpTail = lpList2->lpTail;
}
lpList2->lpHead = lpList2->lpTail = NULL;
}
return lpList1;
}
#endif//__STDLIST_H__

算法本身沒有什麼特別的地方，為什麼說這是一個通用雙向鏈表呢？奧妙就在那四個用於擴展的宏。利用這幾個宏你可以將這個雙向鏈表擴展到任意結構。

例如，我們要實現一個消息隊列，那麼我們可以這樣定義消息節點：

typedef struct tagMSGNODE {
DECLARELISTNODE();
HWND hWnd;
UINT uMsg;
WPARAM wParam;
LPARAM lParam;
} MSGNODE, *LPMSGNODE;

而消息隊列則可以直接用LISTNODE結構來表示：

STDLIST lstMsgQueue;

這樣我們就可以用剛剛定義的函數來對這個消息隊列進行操作了：

// 向消息隊列插入一個消息
LPMSGNODE lpMsgNode = MemAlloc(SIZEOF(MSGNODE));
lpMsgNode->INIT_LISTNODE();
lpMsgNode->hWnd = hWnd;
lpMsgNode->uMsg = WM_PAINT;
lpMsgNode->wParam = NULL;
lpMsgNode->lParam = NULL;
StdListPushBack(&lstMsgQueue, (LPSTDNODE)lpMsgNode);
// 從消息隊列取出一個消息
LPMSGNODE lpMsgNode = (LPMSGNODE)StdListPopFront(&lstMsgQueue);
// 刪除所有屬於hWnd的消息
LPMSGNODE lpTemp = (LPMSGNODE)StdListGetHeadNode(&lstMsgQueue);
while(lpTemp) {
LPMSGNODE lpNext = (LPMSGNODE)StdListGetNextNode(&lstMsgQueue, (LPSTDNODE)lpTemp);
if(lpTemp->hWnd == hWnd) {
StdListRemove(&lstMsgQueue, (LPSTDNODE)lpTemp);
MemFree(lpTemp);
}
lpTemp = lpNext;
}