[数据结构与算法]双向链表的基本操作实现

双链表通过前驱指针与后驱指针解决了单链表无法逆向检索的问题。

?

1.注意事项

两种边界情况：
新插入结点在最后一个位置时，需特殊处理。
被删除结点是最后一个结点时，需特殊处理。

2.代码实现

// 带头结点的双向链表
#include <stdio.h>
#include <stdlib.h>

typedef struct DNode{
    int 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;
}

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

// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
    if(p == NULL || s ==NULL)
        return false;
    s->next = p->next;
    if(p->next!=NULL)
        p->next->prior = s;
    s->prior = p;
    p->next = s;
    return true;
}

// 建双链表
DLinkList CreateDList(DLinkList L){
    int x;
    scanf("%d\n",&x);
    while(x!=9999){
        DNode *s = (DNode*)malloc(sizeof(DNode));
        s->data = x;
        InsertNextDNode(L,s);
        scanf("%d\n",&x);
    }
    return L;
}

// 删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
    if(p==NULL)
        return false;
    DNode *q = p->next;
    if(q==NULL) return false;
    p->next = q->next;
    if(q->next!=NULL) //p的后继结点不是null
        q->next->prior = p;
    free(q);
    return true;
}

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

int main(){
    DLinkList L;
    InitDLinkList(L);
    CreateDList(L);

    // 后向遍历
    while(L->next!=NULL){
        L = L->next;
        printf("%d\n",L->data);
    }

    DestoryList(L);

    return 0;
}