【数据结构】双向链表的插入和删除操作

亦凉 2021-12-03 11:34 194阅读 0赞

#include<iostream>
    using namespace std;
    typedef struct DNode {
        int data;
        struct DNode *prior;
        struct DNode *next;
    }DNode, *DLinkList;
    
    bool InitDList(DLinkList &DL) {
        DL = new DNode;
        DL->prior = NULL;
        DL->next = NULL;
        DL->data = 0;
        if (DL)
            return true;
        return false;
    }
    
    void CreateDList(DLinkList &DL) {
        DNode *p, *r = DL;
        for (int i=0; i<10; i++, DL->data++) {
            p = new DNode;
            p->data = i;
            r->next = p;
            p->prior = r;
            p->next = NULL;
            r = p;
        }
        r->next = NULL;
    }
    
    void PrintDList(DLinkList DL) {
        cout<<"Head Node = "<<DL<<endl;
        DNode *p = DL->next;
        int i = 1;
        while (p) {
            cout<<"p" <<i<< "= "<<p<<" p->data = "<<p->data<<" p->prior = "<<p->prior<<" p->next = "<<p->next<<endl;
            p = p->next;
            i++;
        }
        cout<<endl;
    }
    
    // 删除第pos个节点
    void DeleteElem(DLinkList &DL, int pos) {
        if (pos < 0 || pos > DL->data) {
            cout<<"Invalid Position!"<<endl;
            return;
        }
        DNode *p = DL->next;
        for (int i=0; i<pos-1; i++) {
            p=p->next;
        }
        p->prior->next = p->next;
        p->next->prior = p->prior;
        delete p;
        DL->data--;
    }
    
    // 插入节点到第pos个位置
    void InsertElem(DLinkList &DL, int pos, int data) {
        if (pos < 0 || pos > DL->data) {
            cout<<"Invalid Position!"<<endl;
            return;
        }
        DNode *p = DL->next, *newNode;
        newNode = new DNode;
        newNode->data = data;
        for (int i=1; i<pos-1; i++) {
            p=p->next;
        }
        newNode->next = p->next;
        p->next->prior = newNode;
        p->next = newNode;
        newNode->prior = p;
        DL->data++;
    }
    
    int main() {
        DLinkList DL;
        InitDList(DL);
        CreateDList(DL);
        PrintDList(DL);
    
        cout<<"删除第5个节点"<<endl;
        DeleteElem(DL, 5);
        PrintDList(DL);
    
        cout<<"将19插入到第7个节点的位置"<<endl;
        InsertElem(DL, 7, 19);
        PrintDList(DL);
        return 0;
    }

// 测试结果
    Head Node = 0x757fc0
    p1= 0x757f28 p->data = 0 p->prior = 0x757fc0 p->next = 0x757f40
    p2= 0x757f40 p->data = 1 p->prior = 0x757f28 p->next = 0x757f58
    p3= 0x757f58 p->data = 2 p->prior = 0x757f40 p->next = 0x757ae0
    p4= 0x757ae0 p->data = 3 p->prior = 0x757f58 p->next = 0x757af8
    p5= 0x757af8 p->data = 4 p->prior = 0x757ae0 p->next = 0x757b10
    p6= 0x757b10 p->data = 5 p->prior = 0x757af8 p->next = 0x757b28
    p7= 0x757b28 p->data = 6 p->prior = 0x757b10 p->next = 0x757b40
    p8= 0x757b40 p->data = 7 p->prior = 0x757b28 p->next = 0x757b58
    p9= 0x757b58 p->data = 8 p->prior = 0x757b40 p->next = 0x757b70
    p10= 0x757b70 p->data = 9 p->prior = 0x757b58 p->next = 0
    
    删除第5个节点
    Head Node = 0x757fc0
    p1= 0x757f28 p->data = 0 p->prior = 0x757fc0 p->next = 0x757f40
    p2= 0x757f40 p->data = 1 p->prior = 0x757f28 p->next = 0x757f58
    p3= 0x757f58 p->data = 2 p->prior = 0x757f40 p->next = 0x757ae0
    p4= 0x757ae0 p->data = 3 p->prior = 0x757f58 p->next = 0x757b10
    p5= 0x757b10 p->data = 5 p->prior = 0x757ae0 p->next = 0x757b28
    p6= 0x757b28 p->data = 6 p->prior = 0x757b10 p->next = 0x757b40
    p7= 0x757b40 p->data = 7 p->prior = 0x757b28 p->next = 0x757b58
    p8= 0x757b58 p->data = 8 p->prior = 0x757b40 p->next = 0x757b70
    p9= 0x757b70 p->data = 9 p->prior = 0x757b58 p->next = 0
    
    将19插入到第7个节点的位置
    Head Node = 0x757fc0
    p1= 0x757f28 p->data = 0 p->prior = 0x757fc0 p->next = 0x757f40
    p2= 0x757f40 p->data = 1 p->prior = 0x757f28 p->next = 0x757f58
    p3= 0x757f58 p->data = 2 p->prior = 0x757f40 p->next = 0x757ae0
    p4= 0x757ae0 p->data = 3 p->prior = 0x757f58 p->next = 0x757b10
    p5= 0x757b10 p->data = 5 p->prior = 0x757ae0 p->next = 0x757b28
    p6= 0x757b28 p->data = 6 p->prior = 0x757b10 p->next = 0x757af8
    p7= 0x757af8 p->data = 19 p->prior = 0x757b28 p->next = 0x757b40
    p8= 0x757b40 p->data = 7 p->prior = 0x757af8 p->next = 0x757b58
    p9= 0x757b58 p->data = 8 p->prior = 0x757b40 p->next = 0x757b70
    p10= 0x757b70 p->data = 9 p->prior = 0x757b58 p->next = 0