双向链表
在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。
双向链表的存储结构定义如下：
typedef struct _dnode
{
int data;
struct _dnode *pre;//前向指针，指向结点左边的结点
struct _dnode *next;//后继指针，指向结点右边的结点
}dnode, *pdnode;
双向链表的结构如下图所示：
2.3.1 创建
在创建双向链表的时候，将一个新建的结点p，插入已知的双向链表中，有2种插入方法，如下图所示，一是直接插入头部，二是直接插入尾部。
//从头部插入方法创建双向链表：
dnode *create_dobulelist_head()
{
dnode *h = NULL;
while(1)
{
dnode *p=(dnode *)malloc(sizeof(dnode));
if(p==NULL)
{
return h;
}
memset(p,0,sizeof(p));
printf("Please input your data\n");
scanf_s("%d",&p->value);
p->next=p->pre=NULL;
if(h==NULL) //如果头结点指针为空，表明这是创建的第一个结点
{
h=p;
}
else
{
p->next = h;
h->pre=p;
h=p;
}
if(p->value==0)
{
break;
}
}
return h;
}
//从尾部插入创建双向链表：
dnode *create_dobulelist_tail()
{
dnode *h = NULL;
while(1)
{
dnode *p=(dnode *)malloc(sizeof(dnode));
if(p==NULL)
{
return h;
}
memset(p,0,sizeof(p));
printf("Please input your data\n");
scanf_s("%d",&p->value);
p->next=p->pre=NULL;
if(h==NULL)//如果头结点指针为空，表明这是创建的第一个结点
{
h=p;
}
else
{
dnode *q=h;
while(q->next)//需要先从头结点开始遍历到尾结点
{
q=q->next;
}
q->next = p;
p->pre=q;
p->next = NULL;
}
if(p->value==0)//创建循环退出
{
break;
}
}
return h;
}
2.3.2 插入
如图所示，将一个结点p插入到双向链表q的后面（注意，照着图分析最有效，不要死记硬背插入代码）：
2.3.3 删除
双向链表中，将一个结点p从双向链表中删除方法：
2.3.4 遍历
双向链表的遍历，和单向链表的遍历方法差不多：
void traverse_dlist_next(dnode *h)
{
dnode *p=h;
while(p)
{
printf("%d ",p->value);
p=p->next;
}
printf("\n");
}
2.3.5 销毁
双向链表的销毁，与单向链表的销毁算法类似：
void destroy_dlist(dnode *h)
{
dnode *p =h;
while(p)
{
dnode *q=p;
p=p->next;
free(q);
}
}
