内蒙古自治区住房和城乡建设厅网站长沙网站优化培训

//双链表
//单链表无法逆向检索，双链表可进可退   双链表比单链表多啦一个前驱指针
//双链表查找时间复杂度都为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;}