双向链表,也叫双链表,是链表的一种。它的每个数据节点含有两个指针,分别指向前驱和后继。在带哨兵的双向循环链表中,我们可以方便的访问任意节点的前驱节点和后继节点。
实现下面的程序能够对双向链表实现元素的查找、插入、删除等操作,其中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函数为测试函数,且均省略了对上溢和下溢的检验!
(全文完)