//双链表
//单链表无法逆向检索，双链表可进可退 双链表比单链表多啦一个前驱指针
//双链表查找时间复杂度都为o(n)
#include<bits/stdc++.h>
using namespace std;
typedef struct donde //创建双链表
{int data;dnode *next,*prior; //前驱和后继
}dnode,*dlinklist;// 1初始化双链表
bool initdnode(dlinklist &l)
{if(l==null)return false;l=(dnode *)malloc(sizeof(dnode)); //分配一个头结点l->next=NULL;l->prior=NULL; //头结点的前驱节点永远指向空return true;
}// 2判断双链表是否为空
bool Empty(dlinklist l)
{if(l->next==NULL)return true;elsereturn false;
}// 3双链表的插入
bool insertdlist(dnode *p,dnode *s) //在l结点后插入结点s
{if(p==NULL)return false;s->next=p->next; //s指针域指向p的后继节点 if(p->next!=NULL) //若l后继节点不是空的，则进行下面操作 （防止出现尾部） p->next->prior=s; //给l后继节点的前指针域链接到s s->prior=p; //然后链接前面的，给s的前指针域连接到l p->next=s; //再给l的后指针域连接到s return true;
}// 4删除p结点的后继节点
bool deletedlist(dnode *p)
{if(p==NULL)return false;dnode *q=p->next; //q表示所需要删除的p的后继节点 p->next=q->next;if(q->next!=NULL){q->next->prior=p;}free(q);
}
/* 5while(p!=null) //后向遍历{p=p->next;}while(p!=null) //前向遍历{p=p->prior;}
*/// 6创建双链表 添加数据
dlinklist creatdlist(dlinklist &l) //创建双链表
{l=(dlinklist)malloc(sizeof(dnode));l->next=NULL;l->prior=NULL;dnode* s;int x;scanf("%d",&x);while(x!=9999){s=(dnode*)malloc(sizeof(dnode));s->data=x;s->next=l->next;if(l->next!=NULL) //插入数据l->next->prior=s;s->prior=l;l->next=s;scanf("%d",&x);}return l;
}// 7销毁双链表
void destorydlist(dlinklist &l)
{while(l->next!=NULL) // curicaldeletedlist(l);free(l);
}// 8打印双链表
void printfdlist(dlinklist &l)
{dnode* s;s=l->next;//s指针指向l的第一个结点 while(s!=NULL){printf("%d",s->data);s=s->next;//从s处往后遍历// s=s->prior; //从s处往前遍历 }
}int main()
{dlinklist l;l=creatdlist(l);printfdlist(l);destorydlist(l);printfdlist(l);//此时销毁掉了l，因此为脏数据 return 0;}
