[Solved] How to print cities correctly using recursive? [closed]

by


very probably a reasonable definition of cities (which was much better named City, no reason so have it plural) is

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

and your problem is to write all the links without entering in an infinite loop

A first thing to do is to immediately modify your program because you indicate the west etc of a city but you do not indicate for which city, so for instance :

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

and so on for the other cases

Let see with 2 cities with the change :

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

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

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

Execution :

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

and we see the program does not indicate the east of c2 is c1

The reason is simple, for instance in

 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 is clearly used to not enter in an infinite, but it also blocks the printf

So let modify it to have :

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

There is also an error when you want to manage the north, the recursive call is :

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

but it must be

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

So finaly :

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

out of that let notice the initial test

if(cityHead){

is only useful if printcity is initially called with NULL, the function itself never recur with a NULL

Now the execution is :

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

If we have 4 cities making a square :

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

the execution write a verrrrrrrry long times before to stop after too many recursions and a too large stack.

The reason is the int in parameters do not have enough extend in the graph.

A way to solve is to add a field in the struct to mark if the city was already managed. But out of modifying the struct that requests at the end to again go through the graph to clear the mark.

An other way is to save the already managed cities in a list, giving that list in parameter :

#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;
}

Execution :

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 $

Note your definition of newcity is dangerous because of the line

strcpy(temp->name,name);

where you can write out of the field name in cities in case the name is too long, producing an undefined behavior

solved How to print cities correctly using recursive? [closed]