带哨兵的双向循环链表的C语言实现

欢迎访问我的新博客：http://www.milkcu.com/blog/

原文地址：http://www.milkcu.com/blog/archives/1370911920.html

标题：带哨兵的双向循环链表的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函数为测试函数，且均省略了对上溢和下溢的检验！

（全文完）