栀觋 2022-01-15 14:21 采纳率: 100%
浏览 329
已结题

实现对两个有序表(非递减有序)进行合并:

有序表使用顺序存储结构,元素类型为int;

设两个有序顺序表分别为La和Lb,对La和Lb进行合并生成有序顺序表Lc,合并完成后,分别输出La、Lb和Lc。

【输入形式】通过键盘分别输入La表元素个数和La表所有元素,Lb表元素个数和Lb表所有元素,且保证所输入的元素是非递减的,若当前元素比前一元素小,则本元素输入无效,重新输入

【输出形式】分别输出La、Lb和合并后的Lc。
【样例输入】

5

1 3 4 3 6 8

6

2 4 5 7 9 12

【样例输出】

There are 5 elements in La,which are:1 3 4 6 8

There are 6 elements in Lb,which are:2 4 5 7 9 12

There are 11 elements in Lc,which are:1 2 3 4 4 5 6 7 8 9 12

【样例说明】

输入样例中,第1行数据表示La的元素个数;第2行数据为La的元素,其中,第4个元素输入无效,重新输入6;第3行数据表示Lb的元素个数,第4行数据为Lb的元素

输出样例中,每个数据元素占4列列宽,左对齐

  • 写回答

1条回答 默认 最新

  • 关注

    运行结果如下:

    img

    代码:

    
    #include <iostream>
    using namespace std;
    
    struct StNode 
    {
        int data;
        struct StNode* next;
    };
    
    //创建节点
    StNode* CreateNode(int d)
    {
        StNode* node = new StNode;
        node->data = d;
        node->next = 0;
        return node;
    }
    //创建链表
    StNode* CreateList()
    {
        StNode* head,*p,*t;
        int nn,i=0;
        head = 0;
        p = head;
        t = head;
        int data,dt2;
        cin >> nn; //
        while(i<nn)
        {
            cin >> data;
            if(i>0 && data <dt2)
                continue;
            dt2 = data;
            i++;
            t = CreateNode(data);
            if(head ==0)
            {
                head = t;
                p = head;
            }
            else
            {
                p->next = t;
                p = t;
            }
        }
        return head;
    }
    //打印链表
    void Display(StNode* head)
    {
        while(head)
        {
            cout << head->data << " ";
            head = head->next;
        }
        cout << endl;
    }
    
    //链表逆序
    StNode* Reverse(StNode* head)
    {
        StNode *next = NULL;
        StNode *prev = NULL;
        while (head) {
            next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
    
    //计算表长
    int Length(StNode* head)
    {
        int len = 0;
        while(head)
        {
            len++;
            head = head->next;
        }
        return len;
    }
    
    //合并链表
    StNode* Merge(StNode* h1,StNode* h2)
    {
        //因为原来的链表是非递减次序,所以需要先逆序
        StNode* list1 = Reverse(h1);
        StNode* list2 = Reverse(h2);
    
    
        //合并为非递增序列(按递减序列处理)
        StNode* head = 0;
        StNode* tmp = 0;
        StNode* pps = 0;
    
        if(list1->data >= list2->data)
        {
            head = list1;
            list1 = list1->next;
        }else 
        {
            head = list2;
            list2 = list2->next;
        }
        pps = head;
    
        while(list1 && list2 )
        {
            if(list1->data >= list2->data)
            {
                pps->next = list1;
                pps = list1;
                list1 = list1->next;
            }else 
            {
                pps->next = list2;
                pps = list2;
                list2 = list2->next;
            }
        }
        while(list1)
        {
            pps->next = list1;
            pps = list1;
            list1 = list1->next;
        }
    
        while(list2)
        {
            pps->next = list2;
            pps = list2;
            list2 = list2->next;
        }
        pps->next = 0;
    
    
        return head;
    }
    
    
    int main()
    {
        //创建两个链表:输入非递减数列(即递增序列,如1 2 3 4 5或者1 2 2 3 4 5,回车符结束)
        StNode* list1 = CreateList();
        StNode* list2 = CreateList();
        int l1,l2;
        l1 = Length(list1);
        l2 = Length(list2);
        cout << "There are "<<l1 <<" elements in La,which are:";
        Display(list1);
        cout << "There are "<<l2 <<" elements in Lb,which are:";
        Display(list2);
        //合并
        StNode* hh = Merge(list1,list2);
        //计算长度
        int len = Length(hh);
        cout << "There are "<<len <<" elements in Lc,which are:";
        //打印链表
        Display(hh);
        return 0;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录

报告相同问题?

问题事件

  • 系统已结题 1月23日
  • 已采纳回答 1月15日
  • 创建了问题 1月15日

悬赏问题

  • ¥15 cv::resize不同线程时间不同
  • ¥15 web课程,怎么做啊😭没好好听课 根本不知道怎么下手
  • ¥15 做一个关于单片机的比较难的代码,然后搞一个PPT进行解释
  • ¥15 python提取.csv文件中的链接会经常出现爬取失败
  • ¥15 数据结构中的数组地址问题
  • ¥15 maya的mel里,怎样先选择模型A,然后利用mel脚本自动选择有相同名字的模型B呢。
  • ¥15 Python题,根本不会啊
  • ¥15 会会信号与系统和python的来
  • ¥15 关于#python#的问题
  • ¥20 oracle RAC 怎么配置啊,配置