帶哨兵的雙向循環鏈表的C語言實現

標題：帶哨兵的雙向循環鏈表的C語言實現

內容：鏈表是一種基本的鏈式存儲結構，帶哨兵的雙向循環鏈表更是一種方便的數據結構。

作者：MilkCu

定義

雙向鏈表，也叫雙鏈表，是鏈表的一種。它的每個數據節點含有兩個指針，分別指向前驅和後繼。在帶哨兵的雙向循環鏈表中，我們可以方便的訪問任意節點的前驅節點和後繼節點。

實現

下面的程序能夠對雙向鏈表實現元素的查找、插入、刪除等操作，其中main函數為測試函數。

# include <stdio.h>
# include <stdlib.h>
# define M 100

typedef struct lnode {
 int key;
 struct lnode * prev;
 struct lnode * next;
} lnode;
lnode * nil;

lnode * listSearch(int k);
void listInsert(int k);
void listDelete(lnode * x);
void listShow(void);

int main(void)
{
 nil = (lnode * ) malloc(sizeof(lnode));
 nil->key = 0;
 nil->prev = nil;
 nil->next = nil;
 listInsert(2);
 listInsert(4);
 listInsert(6);
 listInsert(8);
 listInsert(10);
 listShow();
 putchar('\n');
 listDelete(listSearch(6));
 listShow();
 return 0;
}
lnode * listSearch(int k)
{
 lnode * x;
 x = nil->next;
 while(x != nil && x->key != k) {
  x = x->next;
 }
 return x;
}
void listInsert(int k)
{
 lnode * x;
 x = (lnode * ) malloc(sizeof(lnode));
 x->key = k;
 x->next = nil->next;
 x->prev = nil;
 nil->next->prev = x;
 nil->next = x;
}
void listDelete(lnode * x)
{
 x->next->prev = x->prev;
 x->prev->next = x->next;
 free(x);
}
void listShow(void)
{
 lnode * x;
 x = nil->next;
 while(x != nil) {
  printf("%d ", x->key);
  x = x->next;
 }
}

上面的程序中，main函數為測試函數，且均省略了對上溢和下溢的檢驗！

（全文完）