【数据结构】双向链表的插入和删除操作-蒲公英云

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

亦凉 2021-12-03 11:34 393阅读 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