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

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

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

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

x

#include <stdio.h>

struct cityLN {
  char name[20];
  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，那么这个递归就无法继续下去。卡在这里想了好久都不知道怎么解。我也思考了很多比如先倒过来但是不知道怎么下手，下面的图片是完成后运行代码的输出内容，请问下这个函数应该如何设计。
截屏2022-12-06 18.09.15.png

最佳答案

月排行榜 / 总排行榜

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);


}

跳转到最佳答案楼层

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

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

#include <stdio.h>

struct cityLN {
  char name[20];
  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);
-----------
取巧了

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

这个最佳答案由 jhq999 给出，感谢 jhq999 的回答。

单击隐藏图章

壳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[20];
  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;
}

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