SUWBS6
2018-10-06 09:30
采纳率: 100%
浏览 607
已采纳

数据结构的基础题,总是不能ac

两个有序链表序列的合并 (20 分)
已知两个非降序链表序列S1与S2,设计函数构造出S1与S2合并后的新的非降序链表S3。

输入格式:
输入分两行,分别在每行给出由若干个正整数构成的非降序序列,用−1表示序列的结尾(−1不属于这个序列)。数字用空格间隔。

输出格式:
在一行中输出合并后新的非降序链表,数字间用空格分开,结尾不能有多余空格;若新链表为空,输出NULL。

输入样例:
1 3 5 -1
2 4 6 8 10 -1
输出样例:
1 2 3 4 5 6 8 10
这是代码

 #include<stdio.h>
#include<stdlib.h> 
typedef struct ListNode *node;

struct ListNode {
    int num;
    node next;
};

node readlist();
node merge(node s1, node s2 );
node apply();

int main()
{
    node s1,s2,s3;
    s1 = apply();
    s2 = apply();
    s3 = apply();
    s1 = readlist();
    s2 = readlist();
    s3 = merge(s1,s2);

    while(s3!=NULL){
        printf("%d ",s3->num);
        s3=s3->next;
    }
    return 0;
}

node apply()
{
    node L;
    L=(node)malloc(sizeof(struct ListNode));
    L=NULL;
    return L;
}

node readlist()
{
    int n;
    node head,p,last;
    head=last=NULL;
    scanf("%d",&n);
    while(n!=-1){
        p=(node)malloc(sizeof(struct ListNode));
        p->num=n;
        p->next=NULL;
        if(last!=NULL)
        {
            last->next=p;
        }
        else{
            head=p;
        }
        last=p;
        scanf("%d",&n);
    }
    last->next=NULL;
    return head;
} 

node merge(node s1, node s2 )
{
    node s3,Head;
    Head=s3;
    s1=s1->next;
    s2=s2->next;
    while(s1!=NULL&&s2!=NULL){
        if(s1->num>=s2->num){
            s3->next=s2;
            s2=s2->next;
        }
        else{
            s3->next=s1;
            s1=s1->next;
        }
        s3=s3->next;
    }
    if(s1==NULL&&s2==NULL){
        return Head;
    }
    else if(s1!=NULL){
        s3->next=s1;
        return Head;
    }
    else if(s2!=NULL){
        s3->next=s2;
        return Head;
    }
}
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • 扫眉 2018-10-06 09:37
    已采纳

    可以参考一下

     #include "stdio.h"
    
    typedef struct Node
    {
        int data;
        struct Node *next;
    }Node, *linkList;
    
    void InitList(linkList *L)
    {
        (*L) = (linkList)malloc(sizeof(Node));
        (*L)->next = NULL;
    }
    
    void creat(linkList L)
    {
        Node *s, *r = L;
        int num, flag = 1;
        while(flag)
        {
            scanf("%d", &num);
            if(num >= 0) //num脢脟脪陋虏氓脠毛碌脛脭陋脣脴
            {
                s = (linkList)malloc(sizeof(Node));
                s->data = num;
                r->next = s;
                r = r->next;
            }
            else
            {
                flag = 0;
                r->next = NULL;
            }
        }
    }
    
    void print(Node * L)
    {
        Node * t = L->next;
        int firstNum = 1;
        if(t == NULL) printf("NULL\n");
        while(t != NULL)
        {
            if(firstNum)
            {
                printf("%d", t->data);
                firstNum = 0;
            }
            else
                printf(" %d", t->data);
            t = t->next;
        }
    }
    
    void sort(Node *L1, Node *L2, Node *L3)
    {
        Node *s1 = L1->next, *s2 = L2->next;
        Node *r = L3;
        while(s1 != NULL && s2 != NULL)
        {
            if(s1->data < s2->data)
            {
                r->next = s1;
                r = r->next;
                s1 = s1->next;
            }
            else
            {
                r->next = s2;
                r = r->next;
                s2 = s2->next;
            }
        }
        if(s1 != NULL)
            r->next = s1;
        else
            r->next = s2;
    
        // return s3;
    }
    
    int main(int argc, char const *argv[])
    {
        Node *L1, *L2, *L3;
        InitList(&L1);
        InitList(&L2);
        InitList(&L3);
        creat(L1);
        creat(L2);
        sort(L1, L2, L3);
        print(L3);
        return 0;
    }
    

    你的代码里apply函数是申请空间,但是会导致内存泄漏,比如L申请了空间之后,L指向了堆上的空间,但是接下来L = NULL;就是用NULL覆盖了L的地址值。这样刚才申请的空间首地址就找不到了。
    链表如果不是很熟,不建议直接去写合并排序。建议先从简单链表的创建,输出,查询,删除等等,希望对你有帮助!

    点赞 评论

相关推荐 更多相似问题