数据结构 - 双链表

单链表：无法逆向检索，有时候不太方便

双链表：可进可退，存储密度低一点点

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; // 将节点*s插入到节点*p之后
    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的后继节点
    if (q==NULL) {
        return false;    // p没有后继节点
    }
    p->next = q->next;
    if (q->next!=NULL) { // q节点不是最后一个节点
        q->next->prior = p;
    }
    free(q); // 释放q
    return true;
}

销毁双链表

// 销毁双链表
void DestoryList(DLinkList &L) {
    // 循环释放各个数据节点
    while (L->next!=NULL) {
        DeleteNextDNode(L);
    }
    free(L);   // 释放头节点
    L = NULL;  // 头指针指向NULL；
}

遍历双链表

// 双链表的遍历
void PrintDLinkList(DNode *p) {
    //DNode *p = L->next;
    while (p->prior!=NULL)
    {
        printf("%d", p->prior);
        p = p->prior;
    }
}

创建双链表

// 双链表的创建

DNode * Create(DNode *L){
    int x;
    scanf("%d", &x);
    
    while (x!=999){
        DNode *s = (DNode*)malloc(sizeof(DNode));
        s->data = x;
        InsertNextDNode(L, s);
        scanf("%d", &x);
    }
    return L;
}

版权声明：文章转载请注明来源，如有侵权请联系删除！