王道数据结构 | 双链表

2.3.3双链表

        · 双链表中结点类型的描述

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

 1.双链表的初始化操作（带头结点）

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;         // 定义指向头结点的指针L
    InitDLinkList(L);    //申请一片空间用于存放头结点，指针L指向这个头结点
    //...
}

//判断双链表是否为空
bool Empty(DLinklist L){
    if(L->next == NULL)    //判断头结点的next指针是否为空
        return true;
    else
        return false;
}

 2.双链表的插入操作

         InsertNextDNode(DNode *s,DNode *p) :在p结点后插入s结点

       · 在双链表中p所指的结点之后插入结点*s

bool InsertNextDNode(DNode *s,DNode *p){
    if(p==null || s==null)
        return false;
    s->next = p->next;    //将结点*s插入到结点*p之后
    if(p->next!=null)
        p-next->prior=s;  //*p结点的next往前指，指到*s
    s->prior=p;           //*S结点的往前指，指到*P,即使*s前驱为*p
    p->next=s;            //*p后驱为s
    return true;
}

        · 按照位序插入：找到某一个节点的前驱结点，然后后插

        · 前插操作：找到给定结点的前驱结点，然后进行后插操作

3.双链表的删除操作

        删除p的后继节点q

p->next=q->next;
q->next->prior=p;
free (q);

        如果要删除的结点q是最后一个结点，会出现错误，故增加条件判断以提高代码健壮性

        DeleteNextDnode(DNode *p):删除p结点的后继结点

//删除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;
}

        DestroyList(DLinkList &L) :  双链表的销毁操作

//销毁一个双链表
bool DestoryList(DLinklist &L){
    //循环释放各个数据结点
    while(L->next != NULL){
        DeletNextDNode(L);  //删除头结点的后继结点
    free(L); //释放头结点
    L=NULL;  //头指针指向NULL

    }
}

4.双链表的遍历操作

        · 后向遍历

while(p!=NULL){
    //打印操作
    p = p->next;
}

        · 前向遍历

while(p!=NULL){
    //打印
    p = p->prior;
}

         · 如果不想处理头结点，跳过头结点

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

 注：欢迎大家批评指正！