数据结构-2.9.双链表
一.双链表与单链表的对比：
二.双链表的初始化(带头结点)：
1.图解：
2.代码演示：
#include<stdio.h>
#include<stdlib.h>
//定义双链表结构体
typedef struct DNode
{int data;struct DNode *prior;//前驱指针即指向前面数据的指针 struct DNode *next;//后继指针即指向后面数据的指针
}DNode,*DLinklist; //DLinklist与DNode *等价，DLinklist强调链表，DNode *强调结点
//初始化双链表
bool InitDLinkList(DLinklist &L)
{L = (DNode *)malloc( sizeof(DNode) );//分配一个头结点if( L==NULL ) //内存不足，分配失败 {return false;} L->prior = NULL;//头结点的prior(前驱)永远指向NULLL->next = NULL;//头结点之后(后继)暂时还没有结点 return true;
}
//判断双链表是否为空(带头结点)->只需要看第一个结点是否为空即可
bool Empty(DLinklist L)
{if( L->next == NULL )//代表双链表第一个结点为空，是空双链表{return true;}else{return false;//代表双链表第一个结点不为空，不是空双链表 }
}
int main()
{//初始化双链表 DLinklist L;InitDLinkList(L);//后续代码。。。 return 0;
}三.双链表的插入：
图解：
此时要p结点之后插入s结点，起初p->next指向y，先把p的下一个结点即y和要插入的结点即s的指向下一个结点的指针对接即s->next = p->next：
之后还需要把p结点的后继结点即p->next的前向指针p->next->prior指向s即p->next->prior = s:
再把要插入的结点即s结点的前驱指针指向p结点即 s->prior = p：
最后把p结点的后继结点指向s即p->next = s：
但对于上述代码，有一个bug，当p结点是最后一个结点时，p->next->prior = s就会报空指针的错，因为
p结点是最后一个结点时p->next指向NULL，因此，严谨的代码如下：对p->next进行空指针判断
-
按位序插入：找到要插入的位序的前驱结点，在该结点实现后插操作即可
-
前插操作：由于双链表的特性，可以很方便的找到给定结点的前驱结点，再对前驱结点进行后插操作即可
四.双链表的删除：
图解：
此时要删除p结点的后继结点q，因此要把q结点的下一个结点和p结点连接，即p->next = q->next：
再把要删除的q结点的后继结点即q->next的前驱结点即q->next->prior指向p即q->next->prior = p：
最后再释放要删除的q结点即free(q)：free函数要用到头文件#include<stdlib.h>
但上述代码也有bug，如果此时要删除的q结点为双链表最后一个结点，那么q->next就指向NULL，q->next->prior就会报空指针错误，因此对q->next进行空指针判断以增加严谨性：
销毁双链表：每一次删除头结点的后继结点即可
因为比如第一次删除头结点的后继结点即第一个结点，第二次删除时第二个结点就来了第一个位置，相当于头结点的后继结点，删除即可，以此类推，可销毁双链表：
五.双链表的遍历：
1.对于前向遍历(跳过头结点)的循环条件当p->prior == NULL时，说明此时p结点指向的就已经是头结点了，此时跳出循
环，不操作头结点了；
2.对于按位查找，只需要添加一个计数器，用于记录此时指向的哪个位置的元素，当位置和要找的位置匹配时打印即可；
3.对于按值查找，只需要对当前指向的结点和要找的值对比即可，找到了就打印即可；
4.双链表没有随机存取的特性，所以按位查找，按值查找的时间复杂度为O(n)，因为只能用循环的方式一个一个对比依次
往后找。
六.总结：
