[已解决]C语言求助_链表_合并有序列表(leetcode21题)

ALiowys · 发表于 2020-4-2 23:45:14

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

链表10

不明白自己的代码为什么会无限循环，一共有三个合并代码，第一个常规思路，第二个递归，第三个是谭浩强那本书的答案（看不懂），但是人家谭老的代码运行很流畅

<font face="Times New Roman">#include<stdio.h>
#define LEN sizeof(struct Student *)

struct Student
{
        int num;
        float score;
        struct Student *next;
};
 
 int n;
 
struct Student *creat()
{
        struct Student *head,*p1,*p2;
        
        p1=p2=(struct student *)malloc(LEN);
        scanf("%d %f",&p1->num,&p1->score);
        head=NULL;
        n=0;
        while(p1->num!=0)
        {
                n++;
                if(n==1) head=p1;
                else p2->next=p1;
                p2=p1;
                p1=(struct student *)malloc(LEN);
                scanf("%d %f",&p1->num,&p1->score);
        }
        p2->next=NULL;
        return head;
}

void print(struct Student *p)
{
        while(p!=NULL)
        {
                printf("%-8d%-8.2f\n",p->num,p->score);
                p=p->next;
        }
}
#if(0)
struct Student *combine(struct Student *a,struct Student *b)
{
        struct Student *res,*p;
        res=p;
        while(a!=NULL&&b!=NULL)
        {
                if(a->num>b->num)
                {
                        p->next=b;
                        b=b->next;
                }
                else
                {
                        p->next=a;
                        a=a->next;
                }
                p=p->next;
        }
        if(a==NULL) p->next=b;
        if(b==NULL) p->next=a;
        
        return res->next; 
}
#endif
#if(0)
struct Student *combine(struct Student *a,struct Student *b)
{
        struct Student *res;
        if(a==NULL) return b;
        if(b==NULL) return a; 
        
        if(a->num<b->num)
        {
                res=a;
                res->next=combine(a->next,b);
        }
        else
        {
                res=a;
                res->next=combine(a,b->next);
        }
        
        return res; 
}
#endif
#if(1)
struct Student *combine(struct Student *ah,struct Student *bh)
{
        struct Student *pa1,*pa2,*pb1,*pb2;

        pa1=pa2=ah;
        pb1=pb2=bh;
        
        do
        {
                while((pb1->num>pa1->num)&&(pa1->next!=NULL))
                {
                        pa2=pa1;
                        pa1=pa1->next;
                }
                if(pb1->num<=pa1->num)
                {
                        if(ah==pa1) ah=pb1;
                        else pa2->next=pb1;
                        pb1=pb1->next;
                        pb2->next=pa1;
                        pa2=pb2;
                        pb2=pb1;
                }
        }while((pa1->next!=NULL)||(pa1==NULL&&pb1!=NULL));
        if((pb1!=NULL)&&(pb1->num>pa1->num)&&pa1->next==NULL) pa1->next=pb1;
        return ah; 
}
#endif
int main()
{
        struct Student *a,*b,*pt;
        
        printf("请输入链表a：\n");
        a=creat();
        printf("请输入链表b：\n");
        b=creat();
        
        pt=combine(a,b);
        print(pt);
        return 0;
}</font>

最佳答案

月排行榜 / 总排行榜

百里狂生

2020-4-3 12:00:07

1，你自己的代码呢，都忘了给指针分配内存了。

 res=p=(struct student *)malloc(n);

另外你这样排序不了了，和冒泡排序相比少了个循环。
2，谭浩强代码解释看图，它排序的前提是两个链表已经是排序好的。

跳转到最佳答案楼层

ALiowys · 发表于 2020-4-2 23:52:36

加了一些注释

<font face="Times New Roman">#include<stdio.h>
#define LEN sizeof(struct Student *)

struct Student
{
        int num;
        float score;
        struct Student *next;
};
 
 int n;
//从键盘输入链表 
struct Student *creat()
{
        struct Student *head,*p1,*p2;
        
        p1=p2=(struct student *)malloc(LEN);
        scanf("%d %f",&p1->num,&p1->score);
        head=NULL;
        n=0;
        while(p1->num!=0)
        {
                n++;
                if(n==1) head=p1;
                else p2->next=p1;
                p2=p1;
                p1=(struct student *)malloc(LEN);
                scanf("%d %f",&p1->num,&p1->score);
        }
        p2->next=NULL;
        return head;
}
//打印输出链表 
void print(struct Student *p)
{
        while(p!=NULL)
        {
                printf("%-8d%-8.2f\n",p->num,p->score);
                p=p->next;
        }
}
//第一种方法，常规思路 
#if(0)
struct Student *combine(struct Student *a,struct Student *b)
{
        struct Student *res,*p;
        res=p;
        while(a!=NULL&&b!=NULL)
        {
                if(a->num>b->num)
                {
                        p->next=b;
                        b=b->next;
                }
                else
                {
                        p->next=a;
                        a=a->next;
                }
                p=p->next;
        }
        if(a==NULL) p->next=b;
        if(b==NULL) p->next=a;
        
        return res->next; 
}
#endif
//递归方法 
#if(0)
struct Student *combine(struct Student *a,struct Student *b)
{
        struct Student *res;
        if(a==NULL) return b;
        if(b==NULL) return a; 
        
        if(a->num<b->num)
        {
                res=a;
                res->next=combine(a->next,b);
        }
        else
        {
                res=a;
                res->next=combine(a,b->next);
        }
        
        return res; 
}
#endif
//谭浩强代码 
#if(1)
struct Student *combine(struct Student *ah,struct Student *bh)
{
        struct Student *pa1,*pa2,*pb1,*pb2;

        pa1=pa2=ah;
        pb1=pb2=bh;
        
        do
        {
                while((pb1->num>pa1->num)&&(pa1->next!=NULL))
                {
                        pa2=pa1;
                        pa1=pa1->next;
                }
                if(pb1->num<=pa1->num)
                {
                        if(ah==pa1) ah=pb1;
                        else pa2->next=pb1;
                        pb1=pb1->next;
                        pb2->next=pa1;//到这里看不懂了 
                        pa2=pb2;
                        pb2=pb1;
                }
        }while((pa1->next!=NULL)||(pa1==NULL&&pb1!=NULL));
        if((pb1!=NULL)&&(pb1->num>pa1->num)&&pa1->next==NULL) pa1->next=pb1;
        return ah; 
}
#endif
int main()
{
        struct Student *a,*b,*pt;
        
        printf("请输入链表a：\n");
        a=creat();
        printf("请输入链表b：\n");
        b=creat();
        
        pt=combine(a,b);//调用合并函数 
        print(pt);//打印结果 
        return 0;
}</font>

百里狂生 · 发表于 2020-4-3 12:00:07

1，你自己的代码呢，都忘了给指针分配内存了。

 res=p=(struct student *)malloc(n);

另外你这样排序不了了，和冒泡排序相比少了个循环。
2，谭浩强代码解释看图，它排序的前提是两个链表已经是排序好的。

ALiowys · 发表于 2020-4-3 13:11:21

百里狂生发表于 2020-4-3 12:00
1，你自己的代码呢，都忘了给指针分配内存了。另外你这样排序不了了，和冒泡排序相比少了个循环。
2，谭浩 ...

感谢，确实昨天睡觉的时候突然想到自己没有分配内存。
图画的很清楚，现在已经理解谭老的代码了。

ALiowys · 发表于 2020-4-3 13:30:50

分配内存后第一种常规思路问题解决。

递归那里是我的代码写错了。。。。。
else里面应该是 res=b.

..................

另外，谭老师代码是有缺陷的。。。。真的觉得他的代码太鸡肋。不想改（其实是可能不会改）

附上谭老的不完美的运行情况

百里狂生 · 发表于 2020-4-3 15:57:59

ALiowys 发表于 2020-4-3 13:30
分配内存后第一种常规思路问题解决。

递归那里是我的代码写错了。。。。。

这应该是do while()的条件问题。
结束循环有两种情况：
1，pa1->next==NULL && pb1->num>pa1->num (a链表已经到最后一个元素，且此时b链表的首元素比这个元素要大)。
2，pb1 == NULL。(只可能a中存在元素比b中所有元素都大才会出现)
但是，如果pb1==NULL的话，pb1->num>pa1->num 比较就会出错。苦思无果，所以只好把第2种情况的判断放在循环体中。

     do
        {
                while((pb1->num>pa1->num)&&(pa1->next!=NULL))
                {
                        pa2=pa1;
                        pa1=pa1->next;
                }
                if(pb1->num<=pa1->num)
                {
                        if(ah==pa1) ah=pb1;
                        else pa2->next=pb1;
                        pb1=pb1->next;
                        pb2->next=pa1;
                        pa2=pb2;
                        pb2=pb1;
                }
                if(pb1==NULL) break;
        }while(!(pa1->next==NULL && pb1->num>pa1->num));

ALiowys · 发表于 2020-4-3 20:57:35

百里狂生发表于 2020-4-3 15:57
这应该是do while()的条件问题。
结束循环有两种情况：
1，pa1->next==NULL && pb1->num>pa1->num (a链 ...

他这里解题的前提设定应该就是“按顺序间隔错开”，
所以这里代码的精髓应该是想让我这类的初学者理解您上面用来解释链表之间比较的代码的图的逻辑。
而且我不认为不能把他这段代码改完美就不能很好理解链表。
期待与您的下次交流。

账号		自动登录	找回密码
密码			立即注册