【数据结构】有序单链表归并

我就是我 2021-12-07 13:29 315阅读 0赞

#include<iostream>
    using namespace std;
    typedef struct LNode {
        int data;
        struct LNode *next;
    }LNode, *LinkList;
    // 初始化链表L
    bool InitList(LinkList &L) {
        L = new LNode;
        L->next = NULL;
        L->data = 0;
        if (L)
            return true;
        return false;
    }
    // 创建链表L
    void CreateList (LinkList &L, int data[], int length) {
        LNode *p, *r = L;
        for (int i=0; i<length; i++) {
            p = new LNode;
            p->data = data[i];
            p->next = NULL;
            r->next = p;
            r = p;
        }
    }
    // 归并链表L1, L2到M
    void MergeList(LinkList L1, LinkList L2, LinkList &M) {
        LNode *p1 = L1->next;
        LNode *p2 = L2->next;
        LNode *r = M;
        while (p1 && p2) {
            if (p1->data < p2->data) {
                r->next = p1;
                p1 = p1->next;
            } else {
                r->next = p2;
                p2 = p2->next;
            }
            r = r->next;
        }
        if (p1)
            r->next = p1;
        else
            r->next = p2;
    }
    // 打印链表
    void PrintList(LinkList L) {
        cout<<"Head Node = "<<L<<endl;
        LNode *p = L->next;
        int i = 1;
        while (p) {
            cout<<"p" <<i<< "= "<<p<<" p-data = "<<p->data<<" p->next = "<<p->next<<endl;
            p = p->next;
            i++;
        }
        cout<<endl;
    }
    
    int main() {
        int data1[6] = {2, 3, 3, 6, 9, 14};
        int data2[7] = {3, 5, 7, 8, 9, 14, 18};
        int length1 = sizeof(data1)/sizeof(int);
        int length2 = sizeof(data2)/sizeof(int);
    
        LinkList L1, L2;
        InitList(L1), CreateList(L1, data1, length1);
        InitList(L2), CreateList(L2, data2, length2);
    
        cout<<"归并前L1"<<endl;
        PrintList(L1);
        cout<<"归并前L2"<<endl;
        PrintList(L2);
        LinkList M;
        InitList(M);
        MergeList(L1, L2, M);
        cout<<"归并后M"<<endl;
        PrintList(M);
        return 0;
    }

// 测试结果
    归并前L1
    Head Node = 0x6f7fb8
    p1= 0x6f7fc8 p->data = 2 p->next = 0x6f7fd8
    p2= 0x6f7fd8 p->data = 3 p->next = 0x6f7f28
    p3= 0x6f7f28 p->data = 3 p->next = 0x6f7f38
    p4= 0x6f7f38 p->data = 6 p->next = 0x6f7f48
    p5= 0x6f7f48 p->data = 9 p->next = 0x6f7f58
    p6= 0x6f7f58 p->data = 14 p->next = 0
    
    归并前L2
    Head Node = 0x6f7ae0
    p1= 0x6f7af0 p->data = 3 p->next = 0x6f7b00
    p2= 0x6f7b00 p->data = 5 p->next = 0x6f7b10
    p3= 0x6f7b10 p->data = 7 p->next = 0x6f7b20
    p4= 0x6f7b20 p->data = 8 p->next = 0x6f7b30
    p5= 0x6f7b30 p->data = 9 p->next = 0x6f7b40
    p6= 0x6f7b40 p->data = 14 p->next = 0x6f7b50
    p7= 0x6f7b50 p->data = 18 p->next = 0
    
    归并后M
    Head Node = 0x6f7b60
    p1= 0x6f7fc8 p->data = 2 p->next = 0x6f7af0
    p2= 0x6f7af0 p->data = 3 p->next = 0x6f7fd8
    p3= 0x6f7fd8 p->data = 3 p->next = 0x6f7f28
    p4= 0x6f7f28 p->data = 3 p->next = 0x6f7b00
    p5= 0x6f7b00 p->data = 5 p->next = 0x6f7f38
    p6= 0x6f7f38 p->data = 6 p->next = 0x6f7b10
    p7= 0x6f7b10 p->data = 7 p->next = 0x6f7b20
    p8= 0x6f7b20 p->data = 8 p->next = 0x6f7b30
    p9= 0x6f7b30 p->data = 9 p->next = 0x6f7f48
    p10= 0x6f7f48 p->data = 9 p->next = 0x6f7b40
    p11= 0x6f7b40 p->data = 14 p->next = 0x6f7f58
    p12= 0x6f7f58 p->data = 14 p->next = 0x6f7b50
    p13= 0x6f7b50 p->data = 18 p->next = 0