飘火兽 2022-10-15 20:24 采纳率: 100%
浏览 25
已结题

数据结构题,学校oj平台上的,一样的输入内容,出现的结果每次都不一样

数据结构题,学校oj平台上的,一样的输入内容,出现的结果每次都不一样

问题描述

基于链表的两个递增有序序列的合并
描述
给定两个递增的整数序列A和B,利用链表表示序列A和B,将A和B合并为一个递增的有序序列C,序列C不允许有重复的数据。要求空间复杂度为O(1)。
输入
多组数据,每组数据有三行,第一行为序列A和B的长度n和m,第二行为序列A的n个元素,第三行为序列B的m个元素(元素之间用空格分隔)。n=0且m=0时输入结束。
输出
对于每组数据输出一行,为合并后的序列,每个数据之间用空格分隔。

题目地址http://www.bjfuacm.com/problem/225

代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define OK 1;
#define OVERFLOW -1;

typedef int Status;

typedef struct LNode{
    int data;
    struct LNode *next;
    int length;
}LNode,*LinkList;

Status InitList(LinkList &L)
{
    L=(LNode*)malloc(sizeof(LinkList));
    if(L==NULL)
        return OVERFLOW;
    L->next=NULL;
    L->length=0;
    return OK;
}

Status CreatList(LinkList &L)
{
    LinkList p=L;
    for(int i=0;i<=L->length-1;i++)
    {
        LinkList q;
        q=(LNode*)malloc(sizeof(LinkList));
        scanf("%d",&q->data);
        q->next=NULL;
        p->next=q;
        p=q;
    }
    return OK;
}

Status MergeList(LinkList &A,LinkList &B,LinkList &C)
{
    LinkList p=A;
    LinkList q=B;
    LinkList r=C;
    while(p->next!=NULL&&q->next!=NULL)
    {
        LinkList s;
        s=(LNode*)malloc(sizeof(LinkList));
        if(p->next->data==q->next->data)
        {
            s->data=p->next->data;
            p=p->next;
            q=q->next;
        }
        else
        {
            if(p->next->data<q->next->data)
            {
                s->data=p->next->data;
                p=p->next;
            }
            else
            {
                s->data=q->next->data;
                q=q->next;
            }
        }
        s->next=NULL;
        r->next=s;
        r=s;
        C->length++;
    }
    while(p->next)
    {
        LinkList s;
        s=(LNode*)malloc(sizeof(LinkList));
        s->data=p->next->data;
        s->next=NULL;
        r->next=s;
        r=s;
        C->length++;
        p=p->next;
    }
    while(q->next)
    {
        LinkList s;
        s=(LNode*)malloc(sizeof(LinkList));
        s->data=q->next->data;
        s->next=NULL;
        r->next=s;
        r=s;
        C->length++;
        q=q->next;
    }
    return OK;
}

Status OutputList(LinkList &L)
{
    LinkList p=L;
    while(p->next)
    {
        printf("%d ",p->next->data);
        p=p->next;
    }
    return OK;
}

int main()
{
    for(int i=0;;i++)
    {
        LinkList A,B;
        InitList(A);
        InitList(B);
        scanf("%d%d",&A->length,&B->length);
        if(A->length==0&&B->length==0)
            break;
        else
        {
            LinkList C;
            InitList(C);
            CreatList(A);
            CreatList(B);
            MergeList(A,B,C);
            OutputList(C);
            free(A);
            free(B);
            free(C);
            printf("\n");
        }

    }
    return 0;
}


输入:

5 5
1 3 5 7 9
2 4 6 8 10
3 4
1 5 9
1 2 5 9
0 0

正确输出:

1 2 3 4 5 6 7 8 9 10
1 2 5 9

运行结果

第一次:
1 2 3 4 5 6 7 8 9 10
第二次:
1 2 3 4 5
第三次:
1 2 3 4 5 6
……

一样的输入样例,每次出现的结果都不一样。
望各位帮一下!

  • 写回答

1条回答 默认 最新

  • honestman_ 2022-10-15 22:59
    关注
    #include <iostream>
    
    using namespace std;
    
    typedef struct LNode{
        int data;
        struct LNode *next;
    }LNode,*LinkList;
    
    void InitList(LinkList &L)  //初始化
    {
        L = new LNode;
        L->next = NULL;
    }
    
    void CreatList(LinkList &L,int n)  //尾插法建表
    {
        LinkList rear = L;
        for(int i=0;i<n;i++)
        {
            int temp;
            cin>>temp;
            LinkList h = new LNode;
            h->data = temp;
            rear->next = h;
            rear = h;
        }
        rear->next = NULL;
    }
    
    void print_list(LinkList &L)   //遍历输出表中元素
    {
        LinkList p = L->next;
        while(p!=NULL)
        {
            cout<<p->data;
            if(p->next!=NULL)
            {
                cout<<' ';
            }
            p = p->next;
        }
        cout<<endl;
    }
    
    void Merge_list(LinkList &A,LinkList &B)   //合并两个表并输出
    {
        LinkList C = new LNode;
        C->next = NULL;
        LinkList pa = A->next;
        LinkList pb = B->next;
        LinkList pc = C;
        while(pa!=NULL&&pb!=NULL)
        {
            if(pa->data>pb->data)
            {
                pc->next = pb;
                pc = pb;
                pb = pb->next;
            }
            else if(pa->data<pb->data)
            {
                pc->next = pa;
                pc = pa;
                pa = pa->next;
            }
            else
            {
                pc->next = pa;
                pc = pa;
                pa = pa->next;
                pb = pb->next;
            }
        }
        if(pa!=NULL&&pb==NULL)
        {
            pc->next = pa;
        }
        if(pb!=NULL&&pa==NULL)
        {
            pc->next = pb;
        }
        print_list(C);
    }
    
    int main()
    {
        while(true)
        {
            int n,m;
            cin>>n>>m;
            if(n==0&&m==0)
            {
                break;
            }
            LinkList A,B;
            InitList(A);
            InitList(B);
            CreatList(A,n);
            CreatList(B,m);
            Merge_list(A,B);
        }
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 10月24日
  • 已采纳回答 10月16日
  • 创建了问题 10月15日

悬赏问题

  • ¥15 调用函数时,无关变量的改变引起函数值的改变
  • ¥15 xy坐标转化为经纬度坐标
  • ¥15 一般三角模糊数的上界值和下届值取中值的多少比较合理?
  • ¥15 关于#python#的问题,请各位专家解答!
  • ¥20 Hbase启动失败,无法启动HMaster
  • ¥15 sqpingboot在父模块已经引入了mybatisplus 在子组件不写版本号还是报错
  • ¥20 Lumerical FDTD solutions 中模型的相对阻抗,有效介电常数和有效磁导率的实部和虚部的数据如何获得?
  • ¥100 sql reporting service 远程smtp服务器配置支持
  • ¥15 ppyoloe_r带角度目标检测,loss_cls没法收敛
  • ¥15 淘宝交易指数如何解读,其关联的数据指标是什么