关于递归函数的问题，急需大佬解答

壳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，那么这个递归就无法继续下去。卡在这里想了好久都不知道怎么解。我也思考了很多比如先倒过来但是不知道怎么下手，下面的图片是完成后运行代码的输出内容，请问下这个函数应该如何设计。
只能设计函数，其他地方不能修改
下图为执行后的结果图

壳970527

struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt){
    if (dt == NULL) {
            return ct;

        }

        struct cityLN * tmp=dt->next;
        dt->next=ct;
        return reverseCitiesRecursive(dt,tmp);


}

两手空空儿

壳970527 发表于 2022-12-8 10:29
struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt){
    if (dt == NULL) { ...

1. head = reverseCitiesRecursive(head, NULL);

复制代码

你这个函数不对吧，调用的时候dt 就是NULL， 你这个什么也没干就 return ct了

jackz007

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

复制代码