【数据结构】带头节点的单链表的表示和实现

怼烎@ 2021-12-07 13:21 267阅读 0赞

#include<iostream>
    using namespace std;
    typedef struct LNode {
        int data;
        struct Node *next;
    }LNode, *LinkList;
    
    // 初始化链表，头节点数据域存放链表长度
    bool InitList(LinkList &L) {
        L = new LNode;
        L->next = NULL;
        L->data = 0;
        if (L)
            return true;
        return false;
    }
    
    // 创建链表（尾插法）
    void CreateList(LinkList &L) {
        LNode *p, *r;
        r = L;
        for (int i=0; i<10; i++, L->data++) {
            p = new Node;
            p->data = i;
            p->next = NULL;
            r->next = p;
            r = p;
        }
        r->next = NULL;
    }
    
    // 打印链表
    void PrintList(LinkList L) {
        cout<<"Head Node = "<<L<<endl;
        LNode *p = L->next;
        cout<<"Link Length = "<<L->data<<endl;
        int i = 1;
        while (p) {
            cout<<"p" <<i<< "= "<<p<<" p->data = "<<p->data<<" p->next = "<<p->next<<endl;
            p = p->next;
            i++;
        }
        cout<<endl;
    }
    
    // 根据节点位置返回节点地址
    LNode *GetElem(LinkList L, int pos) {
        if (pos < 0 || pos > L->data) {
            cout<<"Invalid Position!"<<endl;
            return NULL;
        }
        LNode *p = L;
        for (int i=0; i<pos; i++)
            p=p->next;
        return p;
    }
    
    // 根据节点数据域返回节点地址
    LNode *LocateElem(LinkList L, int data) {
        LNode *p = L->next;
        while (p) {
            if (p->data == data)
                return p;
            p = p->next;
        }
        return p;
    }
    
    // 插入节点到第pos个位置
    void InsertElem(LinkList &L, int pos, int data) {
        if (pos < 0 || pos > L->data) {
            cout<<"Invalid Position!"<<endl;
            return;
        }
        LNode *p = L->next;
        for (int i=1; i<pos-1; i++) {
            p=p->next;
        }
        LNode *n = new LNode;
        n->next = p->next;
        p->next = n;
        n->data = data;
        L->data++;
    }
    
    // 删除第pos个节点
    void DeleteElem(LinkList &L, int pos) {
        if (pos < 0 || pos > L->data) {
            cout<<"Invalid Position!"<<endl;
            return;
        }
        LNode *p = L->next;
        for (int i=1; i<pos-1; i++) {
            p=p->next;
        }
        LNode *q = p->next;
        p->next = q->next;
        delete q;
        L->data--;
    }
    
    int main() {
        LinkList L;
        InitList(L);
        CreateList(L);
        PrintList(L);
    
        cout<<"将19插入到第5个节点的位置"<<endl;
        InsertElem(L, 5, 19);
        PrintList(L);
    
        cout<<"数据域为19的节点地址为"<<LocateElem(L, 19)<<endl<<endl;
    
        cout<<"删除第6个节点"<<endl;
        DeleteElem(L, 6);
        PrintList(L);
    
        cout<<"第6个节点地址为"<<GetElem(L, 6)<<endl;
        return 0;
    }

// 测试结果
    Head Node = 0x6f7fb8
    Link Length = 10
    p1= 0x6f7fc8 p->data = 0 p->next = 0x6f7fd8
    p2= 0x6f7fd8 p->data = 1 p->next = 0x6f7f28
    p3= 0x6f7f28 p->data = 2 p->next = 0x6f7f38
    p4= 0x6f7f38 p->data = 3 p->next = 0x6f7f48
    p5= 0x6f7f48 p->data = 4 p->next = 0x6f7f58
    p6= 0x6f7f58 p->data = 5 p->next = 0x6f7ae0
    p7= 0x6f7ae0 p->data = 6 p->next = 0x6f7af0
    p8= 0x6f7af0 p->data = 7 p->next = 0x6f7b00
    p9= 0x6f7b00 p->data = 8 p->next = 0x6f7b10
    p10= 0x6f7b10 p->data = 9 p->next = 0
    
    将19插入到第5个节点的位置
    Head Node = 0x6f7fb8
    Link Length = 11
    p1= 0x6f7fc8 p->data = 0 p->next = 0x6f7fd8
    p2= 0x6f7fd8 p->data = 1 p->next = 0x6f7f28
    p3= 0x6f7f28 p->data = 2 p->next = 0x6f7f38
    p4= 0x6f7f38 p->data = 3 p->next = 0x6f7b20
    p5= 0x6f7b20 p->data = 19 p->next = 0x6f7f48
    p6= 0x6f7f48 p->data = 4 p->next = 0x6f7f58
    p7= 0x6f7f58 p->data = 5 p->next = 0x6f7ae0
    p8= 0x6f7ae0 p->data = 6 p->next = 0x6f7af0
    p9= 0x6f7af0 p->data = 7 p->next = 0x6f7b00
    p10= 0x6f7b00 p->data = 8 p->next = 0x6f7b10
    p11= 0x6f7b10 p->data = 9 p->next = 0
    
    数据域为19的节点地址为0x6f7b20
    
    删除第6个节点
    Head Node = 0x6f7fb8
    Link Length = 10
    p1= 0x6f7fc8 p->data = 0 p->next = 0x6f7fd8
    p2= 0x6f7fd8 p->data = 1 p->next = 0x6f7f28
    p3= 0x6f7f28 p->data = 2 p->next = 0x6f7f38
    p4= 0x6f7f38 p->data = 3 p->next = 0x6f7b20
    p5= 0x6f7b20 p->data = 19 p->next = 0x6f7f58
    p6= 0x6f7f58 p->data = 5 p->next = 0x6f7ae0
    p7= 0x6f7ae0 p->data = 6 p->next = 0x6f7af0
    p8= 0x6f7af0 p->data = 7 p->next = 0x6f7b00
    p9= 0x6f7b00 p->data = 8 p->next = 0x6f7b10
    p10= 0x6f7b10 p->data = 9 p->next = 0
    
    第6个节点地址为0x6f7f58