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

Question

嗯。。我很难递归地打印。。有人能修改我的代码吗？很难理解如何打印城市的所有方向，因为下一个城市也有所有方向。

cityHead将是所有城市的中心(可以在中间或其他位置(，数组的指针在创建citynode后用于存储城市。所以我现在想要的是递归打印。首先是主中心城市打印，它将检查其他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: %sn",cityHead->w->name);
printcity(cityHead->w,1,0,0,0);
}else{
printf("--");
printf("West: Nonen");
}
if(cityHead->e != NULL && e != 1){
printf("--");
printf("East: %sn",cityHead->e->name);
printcity(cityHead->e,0,1,0,0);
}else{
printf("--");
printf("East: Nonen");
}
if(cityHead->s != NULL && s != 1){
printf("--");
printf("South: %sn",cityHead->s->name);
printcity(cityHead->s,0,0,0,1);
}else{
printf("--");
printf("South: Nonen");
}
if(cityHead->n != NULL && n != 1){
printf("--");
printf("North: %sn",cityHead->n->name);
printcity(cityHead->s,0,0,1,0);
}else{
printf("--");
printf("North: Nonen");
}
}
}
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

很可能是城市的合理定义(更好的名称是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: %sn", cityHead->name, cityHead->w->name);
printcity(cityHead->w,1,0,0,0);
}else{
printf("--");
printf("%s West: Nonen", 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: %sn", cityHead->name, cityHead->w->name);
printcity(cityHead->w,1,0,0,0);
}else{
printf("--");
printf("%s West: Nonen", cityHead->name);
}

w显然用于不进入无穷大，但它也会阻止printf

所以让我们修改它，使其具有：

if(cityHead->w != NULL){
printf("--");
printf("%s West: %sn", cityHead->name, cityHead->w->name);
if (w != 1)
printcity(cityHead->w,1,0,0,0);
}else{
printf("--");
printf("%s West: Nonen", 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: %sn", cityHead->name, cityHead->w->name);
if (w != 1)
printcity(cityHead->w,1,0,0,0);
}else{
printf("--");
printf("%s West: Nonen", cityHead->name);
}
if(cityHead->e != NULL){
printf("--");
printf("%s East: %sn", cityHead->name,cityHead->e->name);
if (e != 1)
printcity(cityHead->e,0,1,0,0);
}else{
printf("--");
printf("%s East: Nonen", cityHead->name);
}
if(cityHead->s != NULL){
printf("--");
printf("%s South: %sn", cityHead->name,cityHead->s->name);
if (s != 1)
printcity(cityHead->s,0,0,0,1);
}else{
printf("--");
printf("%s South: Nonen", cityHead->name);
}
if(cityHead->n != NULL){
printf("--");
printf("%s North: %sn", cityHead->name,cityHead->n->name);
if (n != 1)
printcity(cityHead->n,0,0,1,0);
}else{
printf("--");
printf("%s North: Nonen", 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);
}

执行之前写了很长一段时间的verrrrry，在过多的递归和过大的堆栈之后停止。

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

一种解决方法是在结构中添加一个字段，以标记该城市是否已被管理。但是，在修改结构时，该结构在末尾请求再次遍历图形以清除标记。

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

#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: %sn", cityHead->name, cityHead->w->name);
printcity(cityHead->w, l);
}else{
printf("--");
printf("%s West: Nonen", cityHead->name);
}
if(cityHead->e != NULL){
printf("--");
printf("%s East: %sn", cityHead->name,cityHead->e->name);
printcity(cityHead->e, l);
}else{
printf("--");
printf("%s East: Nonen", cityHead->name);
}
if(cityHead->s != NULL){
printf("--");
printf("%s South: %sn", cityHead->name,cityHead->s->name);
printcity(cityHead->s, l);
}else{
printf("--");
printf("%s South: Nonen", cityHead->name);
}
if(cityHead->n != NULL){
printf("--");
printf("%s North: %sn", cityHead->name,cityHead->n->name);
printcity(cityHead->n, l);
}else{
printf("--");
printf("%s North: Nonen", 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 $ 

---

请注意，您对新城的定义是危险的，因为线

strcpy(temp->name,name);

如果名称太长，您可以在城市的名称字段外写入，从而产生未定义的行为