设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › C\C++交流 › C语言求助_链表_合并有序列表(leetcode21题)
返回列表 发新帖
查看: 1824|回复: 6

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

[复制链接]
ALiowys
发表于 2020-4-2 23:45:14 | 显示全部楼层 |阅读模式

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

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

x

链表10

链表10

不明白自己的代码为什么会无限循环，一共有三个合并代码，第一个常规思路，第二个递归，第三个是谭浩强那本书的答案（看不懂），但是人家谭老的代码运行很流畅
  1. <font face="Times New Roman">#include<stdio.h>
  2. #define LEN sizeof(struct Student *)

  4. struct Student
  5. {
  6.         int num;
  7.         float score;
  8.         struct Student *next;
  9. };

  11. int n;

  13. struct Student *creat()
  14. {
  15.         struct Student *head,*p1,*p2;
  16.         
  17.         p1=p2=(struct student *)malloc(LEN);
  18.         scanf("%d %f",&p1->num,&p1->score);
  19.         head=NULL;
  20.         n=0;
  21.         while(p1->num!=0)
  22.         {
  23.                 n++;
  24.                 if(n==1) head=p1;
  25.                 else p2->next=p1;
  26.                 p2=p1;
  27.                 p1=(struct student *)malloc(LEN);
  28.                 scanf("%d %f",&p1->num,&p1->score);
  29.         }
  30.         p2->next=NULL;
  31.         return head;
  32. }

  34. void print(struct Student *p)
  35. {
  36.         while(p!=NULL)
  37.         {
  38.                 printf("%-8d%-8.2f\n",p->num,p->score);
  39.                 p=p->next;
  40.         }
  41. }
  42. #if(0)
  43. struct Student *combine(struct Student *a,struct Student *b)
  44. {
  45.         struct Student *res,*p;
  46.         res=p;
  47.         while(a!=NULL&&b!=NULL)
  48.         {
  49.                 if(a->num>b->num)
  50.                 {
  51.                         p->next=b;
  52.                         b=b->next;
  53.                 }
  54.                 else
  55.                 {
  56.                         p->next=a;
  57.                         a=a->next;
  58.                 }
  59.                 p=p->next;
  60.         }
  61.         if(a==NULL) p->next=b;
  62.         if(b==NULL) p->next=a;
  63.         
  64.         return res->next;
  65. }
  66. #endif
  67. #if(0)
  68. struct Student *combine(struct Student *a,struct Student *b)
  69. {
  70.         struct Student *res;
  71.         if(a==NULL) return b;
  72.         if(b==NULL) return a;
  73.         
  74.         if(a->num<b->num)
  75.         {
  76.                 res=a;
  77.                 res->next=combine(a->next,b);
  78.         }
  79.         else
  80.         {
  81.                 res=a;
  82.                 res->next=combine(a,b->next);
  83.         }
  84.         
  85.         return res;
  86. }
  87. #endif
  88. #if(1)
  89. struct Student *combine(struct Student *ah,struct Student *bh)
  90. {
  91.         struct Student *pa1,*pa2,*pb1,*pb2;

  93.         pa1=pa2=ah;
  94.         pb1=pb2=bh;
  95.         
  96.         do
  97.         {
  98.                 while((pb1->num>pa1->num)&&(pa1->next!=NULL))
  99.                 {
  100.                         pa2=pa1;
  101.                         pa1=pa1->next;
  102.                 }
  103.                 if(pb1->num<=pa1->num)
  104.                 {
  105.                         if(ah==pa1) ah=pb1;
  106.                         else pa2->next=pb1;
  107.                         pb1=pb1->next;
  108.                         pb2->next=pa1;
  109.                         pa2=pb2;
  110.                         pb2=pb1;
  111.                 }
  112.         }while((pa1->next!=NULL)||(pa1==NULL&&pb1!=NULL));
  113.         if((pb1!=NULL)&&(pb1->num>pa1->num)&&pa1->next==NULL) pa1->next=pb1;
  114.         return ah;
  115. }
  116. #endif
  117. int main()
  118. {
  119.         struct Student *a,*b,*pt;
  120.         
  121.         printf("请输入链表a：\n");
  122.         a=creat();
  123.         printf("请输入链表b：\n");
  124.         b=creat();
  125.         
  126.         pt=combine(a,b);
  127.         print(pt);
  128.         return 0;
  129. }</font>
复制代码
最佳答案
月排行榜 / 总排行榜
百里狂生
2020-4-3 12:00:07
1，你自己的代码呢，都忘了给指针分配内存了。
  1. res=p=(struct student *)malloc(n);
复制代码
另外你这样排序不了了，和冒泡排序相比少了个循环。
2，谭浩强代码解释看图，它排序的前提是两个链表已经是排序好的。
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

ALiowys
 楼主| 发表于 2020-4-2 23:52:36 | 显示全部楼层
加了一些注释

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

  4. struct Student
  5. {
  6.         int num;
  7.         float score;
  8.         struct Student *next;
  9. };

  11. int n;
  12. //从键盘输入链表
  13. struct Student *creat()
  14. {
  15.         struct Student *head,*p1,*p2;
  16.         
  17.         p1=p2=(struct student *)malloc(LEN);
  18.         scanf("%d %f",&p1->num,&p1->score);
  19.         head=NULL;
  20.         n=0;
  21.         while(p1->num!=0)
  22.         {
  23.                 n++;
  24.                 if(n==1) head=p1;
  25.                 else p2->next=p1;
  26.                 p2=p1;
  27.                 p1=(struct student *)malloc(LEN);
  28.                 scanf("%d %f",&p1->num,&p1->score);
  29.         }
  30.         p2->next=NULL;
  31.         return head;
  32. }
  33. //打印输出链表
  34. void print(struct Student *p)
  35. {
  36.         while(p!=NULL)
  37.         {
  38.                 printf("%-8d%-8.2f\n",p->num,p->score);
  39.                 p=p->next;
  40.         }
  41. }
  42. //第一种方法，常规思路
  43. #if(0)
  44. struct Student *combine(struct Student *a,struct Student *b)
  45. {
  46.         struct Student *res,*p;
  47.         res=p;
  48.         while(a!=NULL&&b!=NULL)
  49.         {
  50.                 if(a->num>b->num)
  51.                 {
  52.                         p->next=b;
  53.                         b=b->next;
  54.                 }
  55.                 else
  56.                 {
  57.                         p->next=a;
  58.                         a=a->next;
  59.                 }
  60.                 p=p->next;
  61.         }
  62.         if(a==NULL) p->next=b;
  63.         if(b==NULL) p->next=a;
  64.         
  65.         return res->next;
  66. }
  67. #endif
  68. //递归方法
  69. #if(0)
  70. struct Student *combine(struct Student *a,struct Student *b)
  71. {
  72.         struct Student *res;
  73.         if(a==NULL) return b;
  74.         if(b==NULL) return a;
  75.         
  76.         if(a->num<b->num)
  77.         {
  78.                 res=a;
  79.                 res->next=combine(a->next,b);
  80.         }
  81.         else
  82.         {
  83.                 res=a;
  84.                 res->next=combine(a,b->next);
  85.         }
  86.         
  87.         return res;
  88. }
  89. #endif
  90. //谭浩强代码
  91. #if(1)
  92. struct Student *combine(struct Student *ah,struct Student *bh)
  93. {
  94.         struct Student *pa1,*pa2,*pb1,*pb2;

  96.         pa1=pa2=ah;
  97.         pb1=pb2=bh;
  98.         
  99.         do
  100.         {
  101.                 while((pb1->num>pa1->num)&&(pa1->next!=NULL))
  102.                 {
  103.                         pa2=pa1;
  104.                         pa1=pa1->next;
  105.                 }
  106.                 if(pb1->num<=pa1->num)
  107.                 {
  108.                         if(ah==pa1) ah=pb1;
  109.                         else pa2->next=pb1;
  110.                         pb1=pb1->next;
  111.                         pb2->next=pa1;//到这里看不懂了
  112.                         pa2=pb2;
  113.                         pb2=pb1;
  114.                 }
  115.         }while((pa1->next!=NULL)||(pa1==NULL&&pb1!=NULL));
  116.         if((pb1!=NULL)&&(pb1->num>pa1->num)&&pa1->next==NULL) pa1->next=pb1;
  117.         return ah;
  118. }
  119. #endif
  120. int main()
  121. {
  122.         struct Student *a,*b,*pt;
  123.         
  124.         printf("请输入链表a：\n");
  125.         a=creat();
  126.         printf("请输入链表b：\n");
  127.         b=creat();
  128.         
  129.         pt=combine(a,b);//调用合并函数
  130.         print(pt);//打印结果
  131.         return 0;
  132. }</font>
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

百里狂生
发表于 2020-4-3 12:00:07 | 显示全部楼层    本楼为最佳答案   
1，你自己的代码呢，都忘了给指针分配内存了。
  1. res=p=(struct student *)malloc(n);
复制代码
另外你这样排序不了了，和冒泡排序相比少了个循环。
2，谭浩强代码解释看图，它排序的前提是两个链表已经是排序好的。
temp.png
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

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

感谢，确实昨天睡觉的时候突然想到自己没有分配内存。
图画的很清楚，现在已经理解谭老的代码了。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

ALiowys
 楼主| 发表于 2020-4-3 13:30:50 | 显示全部楼层
分配内存后第一种常规思路问题解决。

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

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


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

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

2.png
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

百里狂生
发表于 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种情况的判断放在循环体中。
  1.      do
  2.         {
  3.                 while((pb1->num>pa1->num)&&(pa1->next!=NULL))
  4.                 {
  5.                         pa2=pa1;
  6.                         pa1=pa1->next;
  7.                 }
  8.                 if(pb1->num<=pa1->num)
  9.                 {
  10.                         if(ah==pa1) ah=pb1;
  11.                         else pa2->next=pb1;
  12.                         pb1=pb1->next;
  13.                         pb2->next=pa1;
  14.                         pa2=pb2;
  15.                         pb2=pb1;
  16.                 }
  17.                 if(pb1==NULL) break;
  18.         }while(!(pa1->next==NULL && pb1->num>pa1->num));
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

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

他这里解题的前提设定应该就是“按顺序间隔错开”，
所以这里代码的精髓应该是想让我这类的初学者理解您上面用来解释链表之间比较的代码的图的逻辑。
而且我不认为不能把他这段代码改完美就不能很好理解链表。
期待与您的下次交流。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-10-31 19:18

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表