上一次我们说过单链表，其实双链表和单链表没有什么很大的区别，只不过多了一条前向的链子而已。单链表只能从前往后找，而双链表可以向两边找，这一点是相对于单链表的优势。
这里就不再详细解释双链表的实现过程了，可以回顾一下之前写过的：
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
struct node
{
int data;
struct node* prev;
struct node*pnext;
};
//创建节点
struct node * creat_node(int data)
{
struct node*p=malloc( sizeof(struct node) );
bzero(p,sizeof(struct node) );
p->data=data;p->prev=NULL;p->pnext=NULL;
return p;
}
//头插入
void insert_head(int data,struct node * ph)
{
struct node * p;
p=creat_node(data);
if(ph->pnext==NULL)
{
ph->pnext=p;
p->prev=ph;
}
else
{
p->pnext=ph->pnext;
p->prev=ph;
ph->pnext->prev=p;
ph->pnext=p;
}
ph->data++;
}
//尾插入
void insert_tail(int data,struct node * ph)
{
struct node * pcur=ph;
struct node * p=creat_node(data);
while(pcur->pnext!=NULL)
{
pcur=pcur->pnext;
}
pcur->pnext=p;
p->prev=pcur;
ph->data++;
}
//遍历
void traverse(struct node * ph,int mode)
{
struct node * p=ph;
switch (mode)
{
case 0: //正向遍历
while(p->pnext!=NULL)
{
printf("%d\n",p->pnext->data);
p=p->pnext;
}
printf("一共有%d个数据\n",ph->data);
break;
case 1: //逆向遍历
while(p->pnext!=NULL) //找到最后一个节点
{
p=p->pnext;
}
while(p->prev!=NULL)
{
printf("%d\n",p->data);
p=p->prev;
}
printf("一共有%d个数据\n",ph->data);
break;
default:break;
}
}
//删除节点
void delete_node(int data,struct node * ph,int mode)
{
struct node * p=ph;
struct node * pback=p;
//判断有没有可删除的节点
if(ph->pnext==NULL)
{
printf("没有可删除的节点");
return;
}
pback=p->pnext;
switch(mode)
{
case 0: //删除所有含该数字的节点
while(p->pnext!=NULL)
{
while(p->pnext->data==data) //找到了数据
{
if(p->pnext->pnext==NULL) //该节点是尾节点
{
p->pnext->prev=NULL;
p->pnext=NULL;
free(pback);
ph->data--;
break;
}
else //该节点是普通节点
{
pback->pnext->prev=p;
p->pnext=pback->pnext;
pback->pnext=NULL;
pback->prev=NULL;
free(pback);
pback=p->pnext;
}
ph->data--;
}
if(p->pnext!=NULL) //判断p是否已经是尾节点
p=p->pnext;
pback=p->pnext;
}
break;
case 1: //只删除第一个找到的节点
while(p->pnext!=NULL)
{
if(p->pnext->data==data) //找到了数据
{
if(p->pnext->pnext==NULL) //该节点是尾节点
{
p->pnext->prev=NULL;
p->pnext=NULL;
free(pback);
}
else //该节点是普通节点
{
pback->pnext->prev=p;
p->pnext=pback->pnext;
pback->pnext=NULL;
pback->prev=NULL;
free(pback);
pback=p->pnext;
}
ph->data--;
break;
}
if(p->pnext!=NULL) //判断p是否已经是尾节点
p=p->pnext;
pback=p->pnext;
}
break;
default:break;
}
}
void main(void)
{
struct node *phead;
phead=creat_node(0); //头节点
insert_head(4,phead);
insert_tail(8,phead);
insert_tail(7,phead);
insert_tail(8,phead);
insert_head(5,phead);
delete_node(8,phead,1);
// printf("%d\n",phead->data);
// printf("%d\n",phead->pnext->data);
// printf("%d\n",phead->pnext->pnext->data);
traverse(phead,0);
traverse(phead,1);
}
