Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/3.线性表 -- 双链表.md

#include <cstdlib>
#include <cstdio>

typedef int ElemType;
typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

bool InitDLinkList(DLinkList &DL) {
    DL = (DNode *) malloc(sizeof(DNode));
    if (DL == NULL) {
        return false;
    }
    DL->prior = NULL;
    DL->next = NULL;
    return true;
}

DNode *GetDNode(DLinkList DL, int i) {
    if (i < 0) {
        return NULL;
    }
    DNode *p = DL;
    int j = 0;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

DNode *SearchDNode(DLinkList &DL, ElemType e) {
    DNode *p = DL;
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p;
}

bool InsertNextNode(DNode *p, ElemType e) {
    if (p == NULL) {
        return false;
    }
    DNode *s = (DNode *) malloc(sizeof(DNode));
    s->data = e;

    s->next = p->next;
    if (p->next != NULL) {
        p->next->prior = s;
    }
    s->prior = p;
    p->next = s;
    return true;
}

bool InsertPriorNode(DNode *p, ElemType e) {
    if (p == NULL) {
        return false;
    }
    DNode *s = (DNode *) malloc(sizeof(DNode));
    s->data = e;
    DNode *q = p->prior;//获取p的前节点q, 再后插
    s->next = q->next;
    q->next->prior = s;
    s->prior = q;
    q->next = s;
    return true;
}

bool DLinkListInsert(DLinkList &DL, int i, ElemType e) {
    if (i < 1) {
        return false;
    }
    DNode *p = GetDNode(DL, i - 1);
    return InsertNextNode(p, e);
}

bool DNodeDelete(DNode *p) {
    if (p == NULL) {
        return false;
    }
    p->prior->next = p->next;
    if (p->next != NULL) {
        p->next->prior = p->prior;
    }
    free(p);
    return true;
}

bool DLinkListDelete(DLinkList &DL, int i) {
    if (i < 1) {
        return false;
    }
    DNode *p = GetDNode(DL, i);
    return DNodeDelete(p);
}

bool DNodeSetElem(DLinkList &DL, int i, ElemType e) {
    if (i < 1) {
        return false;
    }
    DNode *p = GetDNode(DL, i);
    p->data = e;
    return true;
}

void PrintDLinkList(DLinkList DL) {
    DNode *p = DL->next;
    if (p == NULL) {
        printf("NULL\n");
        return;
    }
    while (p != NULL) {
        printf("%3d", p->data);
        p = p->next;
    }
    printf("\n");
}

int main() {
    DLinkList List;
    InitDLinkList(List);
    PrintDLinkList(List);
    for (int i = 0; i < 5; ++i) {
        DLinkListInsert(List, i + 1, i + 1);
    }
    PrintDLinkList(List);
    DLinkListDelete(List, 1);
    PrintDLinkList(List);
    DNode *pNode = GetDNode(List, 4);
    printf("%3d\n", pNode->data);
    printf("%3d\n", SearchDNode(List, 3)->data);
    DNodeSetElem(List, 4, 9);
    PrintDLinkList(List);
    return 0;
}