论坛 › C\C++交流 › 关于递归的问题，请大佬进来看看

壳970527 发表于 2022-12-6 17:10:41

关于递归的问题，请大佬进来看看

#include <stdio.h>

struct cityLN {
char name;
int population;
struct cityLN *next;
};

void printCities(struct cityLN *ct);
struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt);

int main(){
        struct cityLN c1 = {"Hiratsuka", 258, NULL},
                c2 = {"Odawara", 190, NULL},
                c3 = {"Yokosuka", 396, NULL},
                c4 = {"Kamakura", 172, NULL},
                c5 = {"Chigasaki", 242, NULL},
                c6 = {"Fujisawa", 434, NULL};
        struct cityLN *head = NULL;
        head = &c1; c1.next = &c2;c2.next = &c3; c3.next = &c4; c4.next = &c5; c5.next = &c6;
        printf("Original: \n");
        printCities(head);
        printf("reverse: \n");
        head = reverseCitiesRecursive(head, NULL);
        printCities(head);
        return 0;
}
void printCities(struct cityLN *ct){
        if (ct != NULL) {
                printf("(%-10s: population = %3d)", ct->name, ct->population);
                printf("%s", (ct->next != NULL) ? " ->\n" : "");
                printCities(ct->next);
        }
        else
                putchar('\n');
}
struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt){

       
}
最后一行的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-6 19:27:16

本帖最后由 jhq999 于 2022-12-6 19:37 编辑

#include <stdio.h>

struct cityLN {
char name;
int population;
struct cityLN *next;
};

void printCities(struct cityLN *ct);
struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt);

int main(){
      struct cityLN c1 = {"Hiratsuka", 258, NULL},
                c2 = {"Odawara", 190, NULL},
                c3 = {"Yokosuka", 396, NULL},
                c4 = {"Kamakura", 172, NULL},
                c5 = {"Chigasaki", 242, NULL},
                c6 = {"Fujisawa", 434, NULL};
      struct cityLN *head = NULL;
      head = &c1; c1.next = &c2;c2.next = &c3; c3.next = &c4; c4.next = &c5; c5.next = &c6;
      printf("Original: \n");
      printCities(head);
      printf("reverse: \n");
      struct cityLN * tmp=head;
      head = reverseCitiesRecursive(head, head->next);
      tmp->next=NULL;
      printCities(head);
      return 0;
}
void printCities(struct cityLN *ct){
      if (ct != NULL) {
                printf("(%-10s: population = %3d)", ct->name, ct->population);
                printf("%s", (ct->next != NULL) ? " ->\n" : "");
                printCities(ct->next);
      }
      else
                putchar('\n');
}
struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt){
    if (dt->next == NULL) {
            dt->next=ct;
            return dt;

      }

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


}

struct cityLN * reverseCitiesRecursive(struct cityLN *head){
    struct cityLN *p=head->next,*tmp;
    head->next=NULL;
    while(p->next)
    {
      tmp=p->next;
      p->next=head;
      head=p;
      p=tmp;
    }
    p->next=head;
    return p;

}

Sagiri 发表于 2022-12-6 20:18:45

本帖最后由 Sagiri 于 2022-12-6 20:25 编辑

函数形式一定要这样吗？ struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt);
-----------
取巧了{:10_297:}
struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt = nullptr){
        if (ct->next == nullptr) return ct;
        cityLN *lastCity = reverseCitiesRecursive(ct->next);
        ct->next->next = ct;
        ct->next = nullptr;
        return lastCity;
}

壳970527 发表于 2022-12-8 09:47:13

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


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

      }

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


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

壳970527 发表于 2022-12-8 09:48:07

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

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

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

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

//当时考虑不周
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:30:33

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


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

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

本帖最后由 jhq999 于 2022-12-8 10:53 编辑

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

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

#include <stdio.h>

struct cityLN {
char name;
int population;
struct cityLN *next;
};

void printCities(struct cityLN *ct);
struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt);

int main(){
      struct cityLN c1 = {"Hiratsuka", 258, NULL},
                c2 = {"Odawara", 190, NULL},
                c3 = {"Yokosuka", 396, NULL},
                c4 = {"Kamakura", 172, NULL},
                c5 = {"Chigasaki", 242, NULL},
                c6 = {"Fujisawa", 434, NULL};
      struct cityLN *head = NULL;
      head = &c1; c1.next = &c2;c2.next = &c3; c3.next = &c4; c4.next = &c5; c5.next = &c6;
      printf("Original: \n");
      printCities(head);
      printf("reverse: \n");
      head = reverseCitiesRecursive(head, NULL);
      printCities(head);
      return 0;
}
void printCities(struct cityLN *ct){
      if (ct != NULL) {
                printf("(%-10s: population = %3d)", ct->name, ct->population);
                printf("%s", (ct->next != NULL) ? " ->\n" : "");
                printCities(ct->next);
      }
      else
                putchar('\n');
}
struct cityLN * reverseCitiesRecursive(struct cityLN *ct, struct cityLN *dt ){
      if (ct== NULL) return dt;
      struct cityLN *lastCity = reverseCitiesRecursive(ct->next,ct);
      ct->next=dt;
      return lastCity;
}

查看完整版本: 关于递归的问题，请大佬进来看看