[已解决]关于递归的问题，请大佬进来看看

壳970527

1. #include <stdio.h>
   
2. 
   
3. struct cityLN {
   
4.   char name[20];
   
5.   int population;
   
6.   struct cityLN *next;
   
7. };
   
8. 
   
9. void printCities(struct cityLN *ct);
   
10. struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt);
    
11. 
    
12. int main(){
    
13.         struct cityLN c1 = {"Hiratsuka", 258, NULL},
    
14.                 c2 = {"Odawara", 190, NULL},
    
15.                 c3 = {"Yokosuka", 396, NULL},
    
16.                 c4 = {"Kamakura", 172, NULL},
    
17.                 c5 = {"Chigasaki", 242, NULL},
    
18.                 c6 = {"Fujisawa", 434, NULL};
    
19.         struct cityLN *head = NULL;
    
20.         head = &c1; c1.next = &c2;  c2.next = &c3; c3.next = &c4; c4.next = &c5; c5.next = &c6;
    
21.         printf("Original: \n");
    
22.         printCities(head);
    
23.         printf("reverse: \n");
    
24.         head = reverseCitiesRecursive(head, NULL);
    
25.         printCities(head);
    
26.         return 0;
    
27. }
    
28. void printCities(struct cityLN *ct){
    
29.         if (ct != NULL) {
    
30.                 printf("(%-10s: population = %3d)", ct->name, ct->population);
    
31.                 printf("%s", (ct->next != NULL) ? " ->\n" : "");
    
32.                 printCities(ct->next);
    
33.         }
    
34.         else
    
35.                 putchar('\n');
    
36. }
    
37. struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt){
    
38. 
    
39.        
    
40. }

复制代码

最后一行的reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt)函数设计，他原来的顺序是c1->c2->c3->c4->c5->c6这样依次打印出来，而这个函数的作用是让他变成c6->c5->c4->c3->c2->c1
但是问题就出在于必须使用递归，他的输入值时head，head是c1，如果把c1->next更改为NULL，那么这个递归就无法继续下去。卡在这里想了好久都不知道怎么解。我也思考了很多比如先倒过来但是不知道怎么下手，下面的图片是完成后运行代码的输出内容，请问下这个函数应该如何设计。

最佳答案

月排行榜 / 总排行榜

jhq999

2022-12-8 10:23:46

壳970527 发表于 2022-12-8 09:47
大佬这个函数存在问题，第一个的时候dt是NULL，就执行不下去了- -

1. //当时考虑不周
   
2. struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt){
   
3.     if (dt == NULL) {
   
4.             return ct;
   
5. 
   
6.         }
   
7. 
   
8.         struct cityLN * tmp=dt->next;
   
9.         dt->next=ct;
   
10.         return reverseCitiesRecursive(dt,tmp);
    
11. 
    
12. 
    
13. }
    

复制代码

跳转到最佳答案楼层

jhq999

1. #include <stdio.h>
   
2. 
   
3. struct cityLN {
   
4.   char name[20];
   
5.   int population;
   
6.   struct cityLN *next;
   
7. };
   
8. 
   
9. void printCities(struct cityLN *ct);
   
10. struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt);
    
11. 
    
12. int main(){
    
13.         struct cityLN c1 = {"Hiratsuka", 258, NULL},
    
14.                 c2 = {"Odawara", 190, NULL},
    
15.                 c3 = {"Yokosuka", 396, NULL},
    
16.                 c4 = {"Kamakura", 172, NULL},
    
17.                 c5 = {"Chigasaki", 242, NULL},
    
18.                 c6 = {"Fujisawa", 434, NULL};
    
19.         struct cityLN *head = NULL;
    
20.         head = &c1; c1.next = &c2;  c2.next = &c3; c3.next = &c4; c4.next = &c5; c5.next = &c6;
    
21.         printf("Original: \n");
    
22.         printCities(head);
    
23.         printf("reverse: \n");
    
24.         struct cityLN * tmp=head;
    
25.         head = reverseCitiesRecursive(head, head->next);
    
26.         tmp->next=NULL;
    
27.         printCities(head);
    
28.         return 0;
    
29. }
    
30. void printCities(struct cityLN *ct){
    
31.         if (ct != NULL) {
    
32.                 printf("(%-10s: population = %3d)", ct->name, ct->population);
    
33.                 printf("%s", (ct->next != NULL) ? " ->\n" : "");
    
34.                 printCities(ct->next);
    
35.         }
    
36.         else
    
37.                 putchar('\n');
    
38. }
    
39. struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt){
    
40.     if (dt->next == NULL) {
    
41.             dt->next=ct;
    
42.             return dt;
    
43. 
    
44.         }
    
45. 
    
46.         struct cityLN * tmp=dt->next;
    
47.         dt->next=ct;
    
48.         return reverseCitiesRecursive(dt,tmp);
    
49. 
    
50. 
    
51. }
    

复制代码

1. struct cityLN * reverseCitiesRecursive(struct cityLN *head){
   
2.     struct cityLN *p=head->next,*tmp;
   
3.     head->next=NULL;
   
4.     while(p->next)
   
5.     {
   
6.         tmp=p->next;
   
7.         p->next=head;
   
8.         head=p;
   
9.         p=tmp;
   
10.     }
    
11.     p->next=head;
    
12.     return p;
    
13. 
    
14. }

复制代码

Sagiri

函数形式一定要这样吗？ struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt);
-----------
取巧了

1. struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt = nullptr){  
   
2.         if (ct->next == nullptr) return ct;
   
3.         cityLN *lastCity = reverseCitiesRecursive(ct->next);
   
4.         ct->next->next = ct;
   
5.         ct->next = nullptr;
   
6.         return lastCity;
   
7. }

复制代码

壳970527

jhq999 发表于 2022-12-6 19:27

1. struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt){
   
2.     if (dt->next == NULL) {
   
3.             dt->next=ct;
   
4.             return dt;
   
5. 
   
6.         }
   
7. 
   
8.         struct cityLN * tmp=dt->next;
   
9.         dt->next=ct;
   
10.         return reverseCitiesRecursive(dt,tmp);
    
11. 
    
12. 
    
13. }

复制代码

大佬这个函数存在问题，第一个的时候dt是NULL，就执行不下去了- -

壳970527

Sagiri 发表于 2022-12-6 20:18
函数形式一定要这样吗？ struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt); ...

大佬，不能更改- -就好像考试总不能吧题目改了吧，我到现在还是不知道怎么做

jhq999

壳970527 发表于 2022-12-8 09:47
大佬这个函数存在问题，第一个的时候dt是NULL，就执行不下去了- -

1. //当时考虑不周
   
2. struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt){
   
3.     if (dt == NULL) {
   
4.             return ct;
   
5. 
   
6.         }
   
7. 
   
8.         struct cityLN * tmp=dt->next;
   
9.         dt->next=ct;
   
10.         return reverseCitiesRecursive(dt,tmp);
    
11. 
    
12. 
    
13. }
    

复制代码

壳970527

jhq999 发表于 2022-12-8 10:23

感谢大佬，真的我想了好久，感觉怎么想都是有点祖父悖论的感觉

jhq999

壳970527 发表于 2022-12-8 10:30
感谢大佬，真的我想了好久，感觉怎么想都是有点祖父悖论的感觉

我把三楼的改了改，应该是你要的

1. 
   
2. #include <stdio.h>
   
3. 
   
4. struct cityLN {
   
5.   char name[20];
   
6.   int population;
   
7.   struct cityLN *next;
   
8. };
   
9. 
   
10. void printCities(struct cityLN *ct);
    
11. struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt);
    
12. 
    
13. int main(){
    
14.         struct cityLN c1 = {"Hiratsuka", 258, NULL},
    
15.                 c2 = {"Odawara", 190, NULL},
    
16.                 c3 = {"Yokosuka", 396, NULL},
    
17.                 c4 = {"Kamakura", 172, NULL},
    
18.                 c5 = {"Chigasaki", 242, NULL},
    
19.                 c6 = {"Fujisawa", 434, NULL};
    
20.         struct cityLN *head = NULL;
    
21.         head = &c1; c1.next = &c2;  c2.next = &c3; c3.next = &c4; c4.next = &c5; c5.next = &c6;
    
22.         printf("Original: \n");
    
23.         printCities(head);
    
24.         printf("reverse: \n");
    
25.         head = reverseCitiesRecursive(head, NULL);
    
26.         printCities(head);
    
27.         return 0;
    
28. }
    
29. void printCities(struct cityLN *ct){
    
30.         if (ct != NULL) {
    
31.                 printf("(%-10s: population = %3d)", ct->name, ct->population);
    
32.                 printf("%s", (ct->next != NULL) ? " ->\n" : "");
    
33.                 printCities(ct->next);
    
34.         }
    
35.         else
    
36.                 putchar('\n');
    
37. }
    
38. struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt ){
    
39.         if (ct== NULL) return dt;
    
40.         struct cityLN *lastCity = reverseCitiesRecursive(ct->next,ct);
    
41.         ct->next=dt;
    
42.         return lastCity;
    
43. }

复制代码