【课程设计｜C++】实现两个链表的合并

• 前言
• 1. 实现两个链表的合并
• • 基本功能与要求
  • 测试数据
• 代码
• 实验截图
• 结语

Hello！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
 
自我介绍 ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研。
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
 
唯有努力
 

知其然 知其所以然！

（1）建立两个链表A和B，链表元素个数分别为m和n个。

（2）假设元素分别为(x1,x2,…,xm)，和(y1,y2,…,yn)。把它们合并成一个线性表C：
当m>=n时，C=x1,y1,x2,y2,…,xn,yn,…,xm
当n>m时， C=y1,x1,y2,x2,…,ym,xm,…,yn；

（3）输出线性表C。

（4）用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。

（1） A表（30，41，15，12，56，80）
B表（23，56，78，23，12，33，79，90，55）

（2） A表（30，41，15，12，56，80，23，12，34）
B表（23，56，78，23，12）

#include 
using namespace std;

template 
class node
{
public:
    t data;
    node *next;
    node(node *ptr = NULL) { next = ptr; }
    node(t a, node *ptr = NULL)
    {
        data = a;
        next = ptr;
    }
};

template 
class linklist
{
public:
    void merge(linklist &l1, linklist &l2)
    {
        int m = l1.length();
        int n = l2.length();
        node *r;
        node *s;
        r = first;
        node *p = l1.first->next;
        cout << p->data << endl;
        node *q = l2.first->next;
        if (m >= n)
        {
            while (p != NULL && q != NULL)
            {
                s = new node(p->data);
                r->next = s;
                r = s;
                s = new node(q->data);
                r->next = s;
                r = s;
                p = p->next;
                q = q->next;
            }
            r->next = p;
        }
        else
        {
            while (p != NULL && q != NULL)
            {
                s = new node(q->data);
                r->next = s;
                r = s;
                s = new node(p->data);
                r->next = s;
                r = s;
                p = p->next;
                q = q->next;
            }
            r->next = q;
        }
    }
    void sort()
    {
        node *L = first->next;
        node *p, *q, *pre;
        p = L->next->next;
        L->next->next = NULL;
        while (p)
        {
            q = p->next;
            pre = L;
            while (pre->next != NULL && pre->next->data < p->data)
                pre = pre->next;
            p->next = pre->next;
            pre->next = p;
            p = q;
        }
        // first = L
        // node *r;
        // node *p = l.first->next;
        // r = first;
        // node *newNode = new node(p->data);
        // r->next = newNode;
        // r = newNode;
        // p = p->next;
        // while(p != NULL) {
        //     t num = r->data;
        //     newNode = new node(p->data);
        //     if(p->data > num) {
        //         // newNode = new node(p->data);
        //         r->next = newNode;
        //         r = newNode;
        //     } else {

        //     }
        //     p = p->next;
        // }
    }
    void rel()
    {
        node *p;
        node *s;
        p = first->next;
        s = p->next;
        first->next = NULL;
        while (p != NULL)

        {
            p->next = first->next;
            first->next = p;
            p = s;
            // cout<<"1"<
                s = p->next;
            }
        }
    }
    linklist() { first = new node; }
    linklist(t x) { first = new node(x); }
    void creat(t end)
    {
        node *newnode;
        t val;
        cin >> val;
        while (val != end)
        {
            newnode = new node(val);
            newnode->next = first->next;
            first->next = newnode;
            cin >> val;
        }
    }

    void creat1(t end)
    {
        node *r;
        node *s;
        r = first;
        t val;
        cin >> val;
        while (val != end)
        {

            s = new node(val);
            r->next = s;
            r = s;
            cin >> val;
        }
        // first=new node
        r->next = NULL;
    }
    void print()
    {

        node *p = first->next;
        while (p != NULL)
        {
            cout << p->data << "--->>";
            p = p->next;
        }
        cout << "NULL" << endl;
    }

    int length()
    {
        node *p;
        p = first->next;
        int count = 0;
        while (p != NULL)
        {
            p = p->next;
            count++;
        }
        return count;
    }
    t get(int i)
    {

        node *p;
        int count = 1;
        p = first->next;

        while (p != NULL && count < i)
        {
            p = p->next;
            count++;
        }
        if (p == NULL)
            throw "位置";
        else
            return p->data;
    }

    void insert(t x, int i)
    {
        node *p;
        node *s;
        p = first;
        int count = 0;
        while (p != NULL && count < i - 1)
        {
            p = p->next;
            count++;
        }
        if (p == NULL)
            throw "位置";
        else
        {
            s = new node(x);
            s->next = p->next;
            p->next = s;
        }
    }

    int locate(t x)
    {
        node *p;
        p = first->next;
        int count = 1;
        while (p != NULL)
        {
            if (p->data == x)
                return count;
            p = p->next;
            count++;
        }
        return 0;
    }

    void del(int i)
    {
        node *p;
        node *q;
        p = first;
        int count = 0;
        while (p != NULL && count < i - 1)
        {
            p = p->next;
            count++;
        }
        if (p == NULL || p->next == NULL)
            throw "位置";
        else
        {
            q = p->next;
            p->next = q->next;
            delete q;
        }
    }

    ~linklist()
    {
        node *p;
        while (first != NULL)
        {

            p = first;
            first = first->next;
            delete p;
        }
    }

    // private:
    node *first;
};

linklist merge(linklist &l1, linklist &l2)
{
    int m = l1.length();
    int n = l2.length();
    cout << "m =" << m << endl;
    linklist ans;
    // linklist ans;
    // cout << "((" << endl;
    node *cur = ans.first;
    cout << "((" << endl;
    // cout << ans.first->data;
    node *p = l1.first;
    node *q = l2.first;
    if (m >= n)
    {
        while (p != NULL && q != NULL)
        {
            cur->next = p;
            cur = cur->next;
            cur->next = q;
            cur = cur->next;
            p = p->next;
            q = q->next;
        }
        cur->next = p;
    }
    else
    {
        while (p != NULL && q != NULL)
        {
            cur->next = q;
            cur = cur->next;
            cur->next = p;
            cur = cur->next;
            p = p->next;
            q = q->next;
        }
        cur->next = q;
    }
    return ans;
}
int main()
{

    linklist L;
    linklist A;
    linklist B;
    linklist C;
    linklist D;
    int key = 1;
    int choice;
    int choice1;
    int choice2;
    while (key == 1)
    {
        cout << "+++++++++++++++++++++++++++++" << endl;
        cout << "+       单链表              +" << endl;
        cout << "+  1.创建单链表（头部插入） +" << endl;
        cout << "+  2. 创建单链表（尾部插入）+" << endl;
        cout << "+  3.查找第i个结点的值      +" << endl;
        cout << "+  4.查找元素x的结点位置    +" << endl;
        cout << "+  5.在第i个位置插入元素x   +" << endl;
        cout << "+  6.删除第i个位置的值      +" << endl;
        cout << "+  7.输出单链表各元素       +" << endl;
        cout << "+  8.旋转链表               +" << endl;
        cout << "+  9.新建两个链表               +" << endl;
        cout << "+  10.直接插入排序              +" << endl;
        cout << "输入你的选择：（1---10）" << endl;
        cin >> choice;
        switch (choice)
        {
        case 1:
        {
            cout << "输入需要存储的数据 以0结尾 例如 1 2 3 4 0" << endl;
            L.creat(0);
            cout << "单链表创建完成！" << endl;
        }
        break;
        case 2:
        {
            cout << "输入需要存储的数据 以0结尾 例如 1 2 3 4 0" << endl;
            L.creat1(0);
            cout << "单链表创建完成！" << endl;
        }
        break;
        case 3:
        {

            cout << "输入查找元素的位置i（第i个结点）：";
            cin >> choice1;
            cout << "第" << choice1 << "个结点的值是：";
            cout << L.get(choice1) << endl;
        }
        break;
        case 4:
        {
            cout << "输入查找元素的值：";
            cin >> choice1;

            cout << "该元素在第" << L.locate(choice1) << "个位置！" << endl;
        }
        break;
        case 5:
        {
            cout << "输入插入元素的位置（第i个） ：";
            cin >> choice1;
            cout << "输入插入元素的值：";
            cin >> choice2;
            L.insert(choice2, choice1);
            cout << "插入完成！" << endl;
        }
        break;
        case 6:
        {
            cout << "输入删除元素的位置（第i个）：" << endl;
            cin >> choice1;
            L.del(choice1);
            cout << "删除完成！" << endl;
        }
        break;
        case 7:
        {
            cout << "该链表元素的值是：" << endl;
            L.print();
        }
        break;
        case 8:
        {

            L.rel();
            // cout<<"1"<
            cout << "输入需要存储的数据 以0结尾 例如 1 2 3 4 0" << endl;
            A.creat1(0);
            cout << "单链表创建完成！" << endl;

            cout << "输入需要存储的数据 以0结尾 例如 1 2 3 4 0" << endl;
            B.creat1(0);
            cout << "单链表创建完成！" << endl;

            C.merge(A, B);

            C.print();
            // break;
        }
        break;
                case 10:
        {
            C.sort();
            C.print();
        }
        break;
        }
        cout << "是否继续？（1：继续 0：退出）" << endl;
        cin >> key;
        system("cls");
    }
    return 0;
}

菜单

合并两个链表

直接插入排序

文章仅作为个人学习笔记记录，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正