如何使用递归正确打印城市？

Question

嗯..我很难递归地做这个打印..有人可以修复我的代码吗？很难理解如何打印城市的所有方向，而下一个城市也有一个所有方向。

cityHead 将是所有城市的中心（可以在中间或其他位置）和数组指针我用它来存储 citynode 创建后的城市。所以我现在想要的是递归打印。首先是主中心城市打印，它会检查其他 4 个方向。如果第一个方向 city->west 上有 city，它将首先打印它。直到所有城市都打印出来，如果城市->西方向有任何城市，它将变为城市->西部并打印城市-西部所有4个方向..

struct cities{
    char name[100];
    cities *e,*w,*s,*n;

}*cityHead,*city[100];

    void printcity(cities *cityHead,int e,int w,int s,int n){
     if(cityHead){

        if(cityHead->w != NULL && w != 1){
            printf("--");
            printf("West: %s\n",cityHead->w->name);
            printcity(cityHead->w,1,0,0,0);
        }else{
            printf("--");
            printf("West: None\n");
        }

        if(cityHead->e != NULL && e != 1){
            printf("--");
            printf("East: %s\n",cityHead->e->name);
            printcity(cityHead->e,0,1,0,0);

        }else{
            printf("--");
            printf("East: None\n");
        }

        if(cityHead->s != NULL && s != 1){
            printf("--");
            printf("South: %s\n",cityHead->s->name);
            printcity(cityHead->s,0,0,0,1);

        }else{
            printf("--");
            printf("South: None\n");
        }

        if(cityHead->n != NULL && n != 1){
            printf("--");
            printf("North: %s\n",cityHead->n->name);
            printcity(cityHead->s,0,0,1,0);

        }else{
            printf("--");
            printf("North: None\n");
        }
    }
    }

    cities * newcity(char name[])
    {
       cities *temp = (cities)malloc(sizeof(cities));

       strcpy(temp->name,name);
       temp->e = temp->n = temp->s = temp->w = NULL;
       return temp;
     }

Answer 1

很可能 cities 的合理定义（最好命名为 City，没有理由那么复数）是

typedef struct cities {
  char name[64];
  struct cities * e;
  struct cities * n;
  struct cities * s;
  struct cities * w;
} cities;

而你的问题是在不进入无限循环的情况下编写所有链接

首先要做的是立即修改你的程序，因为你指出了一个城市的西部等，但你没有指出哪个城市，例如：

  if(cityHead->w != NULL && w != 1){
      printf("--");
      printf("%s West: %s\n", cityHead->name, cityHead->w->name);
      printcity(cityHead->w,1,0,0,0);
  }else{
      printf("--");
      printf("%s West: None\n", cityHead->name);
  }

其他情况依此类推

让我们看看 2 个城市的变化：

int main()
{
  cities * c1 = newcity("c1");
  cities * c2 = newcity("c2");

  c1->e = c2;
  c2->w = c1;

  printcity(c1, 0, 0, 0, 0);
}

执行：

pi@raspberrypi:/tmp $ ./a.out
--c1 West: None
--c1 East: c2
--c2 West: None
--c2 East: None
--c2 South: None
--c2 North: None
--c1 South: None
--c1 North: None

而我们看到程序中并没有指出c2的东边是c1

原因很简单，比如在

 if(cityHead->w != NULL && w != 1){
     printf("--");
     printf("%s West: %s\n", cityHead->name, cityHead->w->name);
     printcity(cityHead->w,1,0,0,0);
 }else{
     printf("--");
     printf("%s West: None\n", cityHead->name);
 }

w明明是用来不进无穷大的，但是也挡住了printf

所以让我们将其修改为：

  if(cityHead->w != NULL){
      printf("--");
      printf("%s West: %s\n", cityHead->name, cityHead->w->name);
      if (w != 1)
        printcity(cityHead->w,1,0,0,0);
  }else{
      printf("--");
      printf("%s West: None\n", cityHead->name);
  }

想要管理北方的时候也出现错误，递归调用为：

printcity(cityHead->s,0,0,1,0);

但必须

printcity(cityHead->n,0,0,1,0);

最后 :

void printcity(cities *cityHead,int e,int w,int s,int n){
 if(cityHead){

    if(cityHead->w != NULL){
        printf("--");
        printf("%s West: %s\n", cityHead->name, cityHead->w->name);
        if (w != 1)
          printcity(cityHead->w,1,0,0,0);
    }else{
        printf("--");
        printf("%s West: None\n", cityHead->name);
    }

    if(cityHead->e != NULL){
        printf("--");
        printf("%s East: %s\n", cityHead->name,cityHead->e->name);
        if (e != 1)
          printcity(cityHead->e,0,1,0,0);

    }else{
        printf("--");
        printf("%s East: None\n", cityHead->name);
    }

    if(cityHead->s != NULL){
        printf("--");
        printf("%s South: %s\n", cityHead->name,cityHead->s->name);
        if (s != 1)
          printcity(cityHead->s,0,0,0,1);

    }else{
        printf("--");
        printf("%s South: None\n", cityHead->name);
    }

    if(cityHead->n != NULL){
        printf("--");
        printf("%s North: %s\n", cityHead->name,cityHead->n->name);
        if (n != 1)
          printcity(cityHead->n,0,0,1,0);

    }else{
        printf("--");
        printf("%s North: None\n", cityHead->name);
    }
 }
}

除此之外，请注意初始测试

if(cityHead){

仅在 printcity 最初以 NULL 调用时才有用，函数本身永远不会以 NULL

重复出现

现在执行是：

pi@raspberrypi:/tmp $ ./a.out
--c1 West: None
--c1 East: c2
--c2 West: c1
--c2 East: None
--c2 South: None
--c2 North: None
--c1 South: None
--c1 North: None

如果我们有 4 个城市组成一个正方形：

int main()
{
  cities * c1 = newcity("c1");
  cities * c2 = newcity("c2");
  cities * c3 = newcity("c3");
  cities * c4 = newcity("c4");

  c1->e = c2;
  c2->w = c1;

  c1->s = c3;
  c3->n = c1;

  c2->s = c4;
  c4->n = c2;

  c4->w = c3;
  c3->e = c4;

  printcity(c1, 0, 0, 0, 0);
}

执行在递归过多和堆栈过大后长时间写入 verrrrrrrry 停止。

原因是 int 参数在图中没有足够的扩展。

一种解决方法是在struct中添加一个字段来标记城市是否已经被管理。但是由于修改了最后请求的 struct 再次遍历图形以清除标记。

另一种方法是将已管理的城市保存在列表中，在参数中给出该列表:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct cities {
  char name[64];
  struct cities * e;
  struct cities * n;
  struct cities * s;
  struct cities * w;
} cities;

typedef struct CityList {
  cities * city;
  struct CityList * next;
} CityList;

int isPresent(cities * c, CityList * l)
{
  while (l) {
    if (l->city == c)
      return 1;
    l = l->next;
  }
  return 0;
}

void add(cities * city, CityList ** l)
{
  CityList * cell = malloc(sizeof(CityList));

  cell->city = city;
  cell->next = *l;
  *l = cell;
}

void clear(CityList ** l)
{
  while (*l) {
    CityList * c = *l;

    *l = (*l)->next;
    free(c);
  }
}


void printcity(cities *cityHead, CityList ** l){
 if(cityHead && !isPresent(cityHead, *l)) {
    add(cityHead, l);
    if(cityHead->w != NULL){
        printf("--");
        printf("%s West: %s\n", cityHead->name, cityHead->w->name);
        printcity(cityHead->w, l);
    }else{
        printf("--");
        printf("%s West: None\n", cityHead->name);
    }

    if(cityHead->e != NULL){
        printf("--");
        printf("%s East: %s\n", cityHead->name,cityHead->e->name);
        printcity(cityHead->e, l);

    }else{
        printf("--");
        printf("%s East: None\n", cityHead->name);
    }

    if(cityHead->s != NULL){
        printf("--");
        printf("%s South: %s\n", cityHead->name,cityHead->s->name);
        printcity(cityHead->s, l);

    }else{
        printf("--");
        printf("%s South: None\n", cityHead->name);
    }

    if(cityHead->n != NULL){
        printf("--");
        printf("%s North: %s\n", cityHead->name,cityHead->n->name);
        printcity(cityHead->n, l);

    }else{
        printf("--");
        printf("%s North: None\n", cityHead->name);
    }
 }
}

cities * newcity(char name[])
{
   cities *temp = (cities*)malloc(sizeof(cities));

   strcpy(temp->name,name);
   temp->e = temp->n = temp->s = temp->w = NULL;
   return temp;
 } 


int main()
{
  cities * c1 = newcity("c1");
  cities * c2 = newcity("c2");
  cities * c3 = newcity("c3");
  cities * c4 = newcity("c4");
  CityList * l = NULL;

  c1->e = c2;
  c2->w = c1;

  c1->s = c3;
  c3->n = c1;

  c2->s = c4;
  c4->n = c2;

  c4->w = c3;
  c3->e = c4;

  puts("[]");
  printcity(c1, &l);
  clear(&l);

  /* to make a 8 */

  cities * c5 = newcity("c5");
  cities * c6 = newcity("c6");

  c3->s = c5;
  c5->n = c3;

  c4->s = c6;
  c6->n = c4;

  c5->e = c6;
  c6->w = c5;

  puts("8");
  printcity(c1, &l);
  clear(&l);

  free(c1);
  free(c2);
  free(c3);
  free(c4);
  free(c5);
  free(c6);

  return 0;
}

执行：

pi@raspberrypi:/tmp $ ./a.out
[]
--c1 West: None
--c1 East: c2
--c2 West: c1
--c2 East: None
--c2 South: c4
--c4 West: c3
--c3 West: None
--c3 East: c4
--c3 South: None
--c3 North: c1
--c4 East: None
--c4 South: None
--c4 North: c2
--c2 North: None
--c1 South: c3
--c1 North: None
8
--c1 West: None
--c1 East: c2
--c2 West: c1
--c2 East: None
--c2 South: c4
--c4 West: c3
--c3 West: None
--c3 East: c4
--c3 South: c5
--c5 West: None
--c5 East: c6
--c6 West: c5
--c6 East: None
--c6 South: None
--c6 North: c4
--c5 South: None
--c5 North: c3
--c3 North: c1
--c4 East: None
--c4 South: c6
--c4 North: c2
--c2 North: None
--c1 South: c3
--c1 North: None
pi@raspberrypi:/tmp $

请注意您对 newcity 的定义是危险的，因为行

strcpy(temp->name,name);

你可以在 cities 中写出字段 name 以防名称太长，产生未定义的行为

如何使用递归正确打印城市？

How to print cities correctly using recursive?

c

recursive-datastructures