数据结构-线性表-双链表

#include <stdio.h>
#include <stdlib.h>

typedef struct DNode {
    int data;
    struct DNode *prior, *next;
}DNode, *DLinklist;
//DLinklist强调是个链表
//DNode *强调是个结点

//带头结点的情况
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结点
#if 0
bool InsertNextDNode(DNode *p, DNode *s){
    s->next = p->next;
    s->next->prior = s;
    s->prior = p;
    p->next = s;
}
#endif

//更加严谨的后插操作
bool InsertNextDNode(DNode *p, DNode *s){
    if(p == NULL || s == NULL) return false;  //非法参数
    s->next = p->next;
    if(p->next != NULL){  //如果p结点有后继结点
        p->next->prior = s;
    }
    s->prior = p;
    p->next = s;
    return true;
}

//双链表的删除(删除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;

}

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

//双链表的遍历
//后向遍历
#if 0
while(p != NULL){
    //对结点p做相应处理
    p = p->next;
}
#endif
//前向遍历
#if 0
while(p != NULL){
    //对结点p做相应处理
    p = p->prior;
}
#endif
//前向遍历（跳过头结点）
#if 0
while(p->prior != NULL){
    //对结点做相应处理
    p = p->prior;
}
#endif

void testDLinkList(){
    //初始化双链表
    DLinklist L;
    InitDLinkList(L);
    //后续代码...
}

int main(){
    return 0;
}