DoubleList.h
#ifndef __DOUBLELIST_H #define __DOUBLELIST_H #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<malloc.h> typedef int ElemType; //定义每一个结点的结构 typedef struct Node { struct Node *prev; //结点的前驱 ElemType data; //结点的数据域 struct Node *next; //结点的后继 }Node; //定义双向链表结构 typedef struct Doublelist { Node head; //头结点 int count; //结点数目 }Doublelist, *pDoulist; void InitDoublelist(pDoulist list); void InsertDoublelist(pDoulist list, ElemType val , int pos); void InsertHeadDoublelist (pDoulist list,ElemType val); void InsertTailDoublelist(pDoulist list,ElemType val); void DeleteDoublelist(pDoulist list,int pos); void DeleteHeadDoublelist(pDoulist list); void DeleteTailDoublelist(pDoulist list); void DestroyDoublelist(pDoulist list);//销毁 void Show1(pDoulist list); //打印输出 void Show2(pDoulist list); void Reverseshow(pDoulist list); //逆序输出 #endifDoubleList.c
#include"DoubleList.h" //初始化双向链表 void InitDoublelist(pDoulist list) { assert(list != NULL); list->head.next = NULL; //尾指针 list->head.prev = NULL; //头指针 list->count = 0; //结点个数 } //在双向链表中插入一个结点 /*1：先考虑普通情况下的结点插入 void InsertDoublelist(pDoulist list, ElemType val, int pos) { assert(list != NULL); if( pos < 0 | pos > list->count ) { printf("pos is error\n"); return ; } Node *p = &list->head; Node *s = ( Node *)malloc(sizeof(Node)); while( pos > 0) { p = p->next; pos--; } s->data = val; if( p->next != NULL) { p->next->prev = s; } s->next = p->next; s->prev = p; p->next = s; list->count++; } */ //2：考虑特殊情况的结点插入优化代码（list->count == 0 和 pos == list->count ） static Node *BuyNode(ElemType val, Node *prev, Node *next )//创建结点 { Node *s = (Node *)malloc(sizeof(Node)); assert( s != NULL); s->data = val; s->prev = prev; s->next = next; return s; } void InsertDoublelist(pDoulist list, ElemType val, int pos) { assert( list != NULL); if( (pos < 0) || (pos > list->count)) { printf("pos is error\n"); return ; } Node *p = &list->head; while( pos > 0) { p = p->next; pos --; } Node *s = BuyNode( val, p, p->next);//插入结点 if( p->next != NULL)//考虑尾插 { p->next->prev = s; } p->next = s; list->count++; } void InsertHeadDoublelist (pDoulist list,ElemType val) { InsertDoublelist(list, val, 0); } void InsertTailDoublelist(pDoulist list,ElemType val) { InsertDoublelist(list, val, list->count); } void DeleteDoublelist(pDoulist list,int pos) { assert(list != NULL); if((pos < 1) ||(pos > list->count)) { printf("pos is error\n"); return ; } Node * p = &list->head; while( pos > 0) { p = p->next; pos --; } p->prev->next = p->next; if ( p->next != NULL) { p->next->prev = p->prev; } free(p); list->count--; } void DeleteHeadDoublelist(pDoulist list) { DeleteDoublelist(list,1); } void DeleteTailDoublelist(pDoulist list) { DeleteDoublelist(list,list->count); } void Show1(pDoulist list) { assert(list != NULL); Node *p = list->head.next; while( p != NULL)//用指针遍历整个链表，指针跑一个输出一个 { printf("%3d",p->data); p = p->next; } printf("\n"); } void Show2(pDoulist list) { assert( list != NULL); Node *p = list->head.next; int tmp = list->count; while( tmp > 0) { printf("%3d",p->data); p = p->next; tmp --; } printf("\n"); } //逆序输出双向链表中的数据 void Reverseshow(pDoulist list) { assert( list != NULL); Node *p = &list->head; while( p->next != NULL)//先让指针跑到最后一个结点 { p = p->next; } while( p->prev != NULL)//指针开始往前跑，指针跑一个输出一个 { printf("%3d",p->data); p = p->prev; } printf("\n"); } void DestroyDoublelist(pDoulist list) { assert(list != NULL); while( list->count > 0) { DeleteHeadDoublelist(list); } }main.c
#include"DoubleList.h" int main() { Doublelist list; Doublelist *p = &list; InitDoublelist(&list); //初始化 printf("count3 = %d\n",p->count); for( int i = 0; i < 5; i++ ) { InsertDoublelist(&list,i * 10 ,i); //插入结点 Show1(&list); } Show1(&list); InsertTailDoublelist(&list,88); InsertHeadDoublelist (&list,99); Show2(&list); Reverseshow(&list);//逆序输出 for( int i = 4; i > 0; i--) { DeleteDoublelist(&list,i);//删除结点 Show2(&list); } Show2(&list); return 0; }
