doublyinkedlist.h
代码语言：javascript复制#ifndef DOUBLYLINKEDLIST_H
#define DOUBLYLINKEDLIST_H
typedef struct node *link;
struct node
{
unsigned char item;
link prev, next;
};
link make_node(unsigned char item);
void free_node(link p);
link search(unsigned char key);
void insert(link p);
void delete(link p);
void traverse(void (*visit)(link));
void destroy(void);
void enqueue(link p);
link dequeue(void);
#endifdoublylinkedlist.c
代码语言：javascript复制#include <stdlib.h>
#include "doublylinkedlist.h"
struct node tailsentinel;
struct node headsentinel = {0, NULL, &tailsentinel};
struct node tailsentinel = {0, &headsentinel, NULL};
static link head = &headsentinel;
static link tail = &tailsentinel;
link make_node(unsigned char item)//创建结点
{
link p = malloc(sizeof *p);
p->item = item;
p->prev = p->next = NULL;
return p;
}
void free_node(link p)//释放结点
{
free(p);
}
link search(unsigned char key)//查询
{
link p;
for (p = head->next; p != tail; p = p->next)
{
if (p->item == key)
return p;
}
return NULL;
}
void insert(link p)//插入结点
{
p->next = head->next;
head->next->prev = p;
head->next = p;
p->prev = head;
}
void delete(link p)//删除结点
{
p->prev->next = p->next;
p->next->prev = p->prev;
}
void traverse(void (*visit)(link))//遍历链表
{
link p;
for (p = head->next; p != tail; p = p->next)
{
visit(p);
}
}
void destroy(void)//销毁链表
{
link q, p = head->next;
head->next = tail;
tail->prev = head;
while (p != tail)
{
q = p;
p = p->next;
free_node(q);
}
}
void enqueue(link p)//入队
{
insert(p);
}
link dequeue(void)//出队
{
if (tail->prev == head)
{
return NULL;
}
else
{
link p = tail->prev;
delete(p);
return p;
}
}main.c
代码语言：javascript复制#include <stdio.h>
#include "doublylinkedlist.h"
void print_item(link p)
{
printf("%dn", p->item);
}
int main(void)
{
link p = make_node(10);
insert(p);
p = make_node(5);
insert(p);
p = make_node(90);
insert(p);
p = search(5);
delete(p);
free_node(p);
traverse(print_item);
destroy();
p = make_node(100);
enqueue(p);
p = make_node(200);
enqueue(p);
p = make_node(250);
enqueue(p);
while (p = dequeue())
{
print_item(p);
free_node(p);
}
return 0;
}
