双链表的基本操作

 一.双链表的初始化：

typedef struct DNode{        //定义双链表结点类型
ElemType data;               //数据域
struct DNode*prior, *next;   //前驱和后继指针
}DNode，*DLinklist;

//初始化双链表
bool InitDLinkList(DLinklist &L){
L = ( DNode *) malloc(sizeof ( DNode) ) ;     //分配一个头结点
if (L==NULL)                                 //内存不足，分配失败
return false;
L->prior = NULL;                            //头结点的prior永远指向NULL
L->next = NULL;                             //头结点之后暂时还没有节点
return true;
}
 
void testDLinkList( ) {                    //初始化双链表
DLinklist L;
InitDLinkList(L);
//后续代码........
}

tips：DLinklist  等价  DNode*

判断双链表是否为空（带头结点）

bool Empty(DLinklist L) {
    if (L->next == NULL)
       return true;
    else
       return false;
}

二.双链表的插入：

//在p结点之后插入s结点
bool InsertNextDNode ( DNode *p,DNode *s )i
    s->next=p->next;            //将结点*s插入到结点*p之后
    p->next->prior=s;
    s->prior=p;
    p->next=s;
}

如图所示：

step1:

step2:

step3: 

step4:

但是，如果p结点是双链表的最后一个结点，那么上述代码将会发生错误，下面为优化后的代码：

在p结点之后插入s结点
bool InsertNextDNode( DNode *p,DNode *s ){
    if ( p==NULL ls==NULL)      //非法参数
       return false;
s->next=p->next;
if ( p->next != NULL)         //如果p结点有后继结点
       p->next->prior=s;
s->prior=p;
p->next=s;
return true;
}

tips：在编写代码时要注意修改指针的顺序，如若语序不合理也会发生错误。 

三.双链表的删除

//删除p结点的后继结点
bool DeleteNextDNode ( DNode *p){
    if ( p==NULL)    
       return false;
    DNode *q = p->next;         //找到p的后继结点q
    if (q==NULL)return false;   //p没有后继
    p->next=q->next;
    if (q->next !=NULL)         //q结点不是最后一个结点
       q->next->prior=p;
    free(q);                    //释放结点空间
    return true;
}

step1:

step2:

step3:

销毁一个双链表：

void DestoryList(DLinklist &L){
    //循环释放各个数据结点
    while (L->next != NULL)
       DeleteNextDNode(L);
    free(L);        //释放头结点
    L=NULL;        //头指针指向NULL
}

四.双链表的遍历：

1.前向遍历：

while (p!=NULL){
    //对结点p做相应处理
    p=p->prior;
}

前向遍历（跳过头结点）：

while (p-> prior != NULL){
    //对结点p做相应处理
    p = p->prior;
}

2.后向遍历：

while (p!=NULL){
    //对结点p做相应处理，如打印
    p = p->next;
}