C语言复习第六章:双向链表

#include<stdio.h> #include<stdlib.h> typedef struct node { int data; struct node *pre; struct node *next; }node; struct node tail_sentinel; struct node head_sentinel = {0, NULL, &tail_sentinel};//创建一个头结点 struct node tail_sentinel = {0, &head_sentinel, NULL};//创建一个尾结点 static node * head = &head_sentinel;//头指针指向头节点 static node * tail = &tail_sentinel;//尾指针指向尾节点 node *mk_node(int data) { node *p = (node*)malloc(sizeof(node)); if(p == NULL) { printf("malloc fair\n" ); exit(1); } p->data = data; p->pre = NULL; p->next = NULL; return p; } //带头结点的头插 int insert(node *p) { p->next = head->next;//头插法插入到第一个元素之前 head->next->pre = p; p->pre = head;//让插入的元素和head连接起来 head->next = p;//手尾互指 } int free_node(node *p) { free(p); } int delete_node(node* p) { p->pre->next = p->next; //p的前一个指向p的后一个 p->next->pre = p->pre;//p的后一个指向p前一个 } int traverse() { node *p = NULL; for(p = head->next;p != NULL;p = p->next) { printf("%d ",p->data ); } printf("\n------------------\n"); } int destroy() { node *q = NULL; node *p = head->next; head->next = tail; tail->pre = head; while(p != tail) { q = p->next; free_node(p); p = q; } } int enqueue(int data) { insert(data); } node * dequeue(void) { if (tail->pre == head) { return NULL; } else { node *p = tail->pre; delete_node(p); return p; } } int main(int argc, char const *argv[]) { node * p = mk_node(10); insert(p); p = mk_node(5); insert(p); p = mk_node(90); insert(p); traverse(); return 0; }