王道数据结构代码：双向链表的操作

双向链表的操作，带头节点的

InitDLinkList(DLinkList &L)：初始化 ,创建一个头节点 

Empty(DLinkList L){ // 判断链表是否为空

InsertNextDNode(DNode *p , DNode *s){ // 在p节点后面插入s节点 

DeleteNextDNode(DNode *p){// 删除P节点的后继节点

DestoryList(DLinkList &L){ // 销毁双链表

bianliList(DLinkList L){///遍历链表

#include
#include
#include
using namespace std;
#define ElemType int 
typedef struct DNode{
    ElemType data;
    struct DNode *prior , *next;
}DNode , *DLinkList;

bool InitDLinkList(DLinkList &L){ // 初始化 ,创建一个头节点 
    L = (DNode*)malloc(sizeof(DNode));
    L->next = NULL;
    L->prior = NULL;
    L->data = -1 ;
    return true;
}
bool Empty(DLinkList L){ // 判断链表是否为空 
    if(L->next == NULL)
        return true;
    else return false;
} 
bool InsertNextDNode(DNode *p , DNode *s){ // 在p节点后面插入s节点 
    
    if(p == NULL || s == NULL) // 
        return false;
    s->next = p->next ; 
    //如果p没有后继节点
    if(p->next != NULL) // 看一下有没有后继节点 
        p->next->prior = s;
    p->next = s ;
    s->prior = p;
    return true;    
} 
bool DeleteNextDNode(DNode *p){// 删除P节点的后继节点
    if(p == NULL)
        return false;
    DNode *s = p->next ; 
    if(s == NULL)
        return false;
    p->next = s->next;
    if(s->next != NULL) // 如果这里是指向头结点的话，也可以不要 
        s->next->prior = p;
    
    free(s);
    return true;    
} 
void DestoryList(DLinkList &L){ // 销毁双链表
    
    while(L->next != NULL){ // L 指向的是数据节点，数据节点销毁完了，就为NULL，只剩头节点了 
        DeleteNextDNode(L);
    } 
     // 销毁完数据节点后，还要销毁头节点 
    free(L);
    L = NULL;
}
void bianliList(DLinkList L){///遍历链表
// 双向链表可以双向遍历 ， 这里是后向遍历 
    DNode *p = L ;
    p = p->next ; // 过掉头节点
    while(p != NULL){
        printf("%d " , p->data);
        p = p->next ; // 前向遍历用prior 
    } 
    printf("\n");
} 

// 查找函数等，都是和单链表一样的
 

int main()
{
    /// 带头节点的 
    DLinkList L ;
    InitDLinkList(L); 
    DNode *p = L;
    printf("插入数据:\n");
    DNode *s;
    for(int i = 1 ; i <= 5 ; i++){
        s = (DNode*)malloc(sizeof(DNode));
        s->data = i ;
        s->next = NULL;
        s->prior = NULL;
        InsertNextDNode(p , s); // 用的是头插法，每次都在 p(头节点) 后插入数据
        // 如果要后插的话，加上下面这句话，每次都移动p指针，指向最后一个节点的位置 
        //p = s ;
    } 
    bianliList(L);
    
    if(Empty(L)){
        printf("链表为空\n");
    } 
    else
        printf("链表不为空\n");
    
    printf("删除指定节点的后继节点(这里指定头节点)\n");
    DNode *temp_Node = L;
    DeleteNextDNode(temp_Node);
    bianliList(L);
    printf("销毁链表\n");
    DestoryList(L);
    if(L == NULL) printf("销毁链表成功\n");
    else printf("销毁链表失败\n"); 
    
        
    return 0;
}