#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    3
    Rep Power
    0

    Need help with trees in C.


    Hello i would like some help with an exercise that i am trying to solve for days and i can not do it.

    Given a text file with a name a surname and an age in each line(there are 10 lines) i must create an ordinated tree in base of increasing age and if the age is the same in base of alphabetical order of the surname. After i must create a function called ShowNext to show the next person on the ordinated tree.

    Here is my code that does not work:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXPER 30
    
    typedef struct
    {
    	char nome[30];
    	char cognome[30];
    	int age;
    }
    Persona;
    
    
    int Left( int i )
    {
    	return 2*i;
    }
    
    int Right( int i )
    {
    	return 2*i + 1;
    }
    
    int Parent( int i )
    {
    	if ( i == 0) return -1;
    	return (i - 1)/2;
    }
    
    int LessThan( Persona a, Persona b )
    {
    	if ( a.age != b.age )
    		{
    			if(b.age <a.age)
    			{
    				return 1;
    			}
    			if(a.age <b.age)
    			{
    				return 0;
    			}
    		}
    	 if( a.age == b.age )
    		{
    			if(strcmp( b.cognome, a.cognome ) <= 0)
    			{
    				return 1;
    			}
    			if(strcmp( b.cognome, a.cognome ) > 0)
    			{
    				return 0;
    			}
    		}
    }
    
    
    void Swap( Persona *a, Persona *b )
    {
    	Persona t = *a;
    	*a = *b;
    	*b = t;
    }
    
    void Heapify( Persona heap[], int dim, int i )
    {
    	int min = i;
    	if ( i > dim ) return;
    
    	if ( Left(i) <= dim && LessThan( heap[i],heap[ Left(i) ] ) )
    	{
    		min = Left(i);		
    	}
    	if ( Right(i) <= dim && LessThan( heap[i],heap[ Right(i) ] ) )
    	{
    		min = Right(i);
    	}
    	
    	if ( min != i )
    	{
    		Swap( &heap[min], &heap[ i ] );
    		Heapify( heap, dim, min );
    	}
    
    }
    
    void heapsort( Persona heap[], int dim) {
    int i=0, heap_size =dim;
    for ( i = dim; i >= 2;i-- ) 
    {
    Swap( &heap[1], &heap[i] );
    Heapify( heap, 1,-- dim );
    }
    
    void BuildHeap( Persona heap[], int dim )
    {
    	int i;
    
    	for ( i=(dim-1)/2; i>=0; i-- )
    	{
    		Heapify( heap, dim, i );
    	}
    }
    
    void ShowNext( Persona heap[], int dim )
    {
    	printf("Next to Serve : %s %s %d\n", heap[1].cognome, heap[1].nome, heap[1].age );
    }
    
    void Insert( Persona heap[], int *dim )
    {
    	Persona p;
    	int i;
    
    	printf("Insert the name : ");
    	scanf( "%s", p.nome );
    	printf("Insert the surname : ");
    	scanf( "%s", p.cognome );
    	printf("Insert the age' : ");
    	scanf( "%d", &p.age );
    	fflush(stdin);
    
    	heap[*dim] = heap[ Parent(*dim) ];
    	heap[ Parent(*dim) ] = p;
    	
    	(*dim)++;
    
    	for ( i=Parent(*dim - 1); i>=0; i=Parent(i) )
    	{
    		Heapify( heap, *dim, i );
    	}
    
    	ShowNext( heap, *dim );
    	
    }
    
    void CaricaPersone( Persona persone[], int *dim )
    {
    	FILE *file;
    
    	file = fopen("persone.txt", "r");
    	if(file==NULL)
    	{
    		fprintf(stderr,"Error");
    		exit(1);
    	}
    
    	*dim = 0;
    	while( !feof( file ) )
    	{
    		fscanf( file, "%s %s %d\n", persone[*dim].nome, persone[*dim].cognome, &persone[*dim].age );
    		(*dim)++;
    		
    	}
    	fclose(file);
    
    }
    
    void PrintHeap( Persona heap[], int dim )
    {
    	int i;
    	printf("\n");
    	for (i=0; i<dim; i++)
    	{
    		printf( "%s %s %d\n", heap[i].cognome, heap[i].nome, heap[i].age );
    	}
    	printf("\n");
    }
    
    int main()
    {
    	Persona persone[MAXPER];
    	int dim=0;
    
    	CaricaPersone( persone, &dim );
    	BuildHeap( persone, dim );
    	heapsort(persone,dim);
    	PrintHeap( persone, dim );
    
    	Insert( persone, &dim );
    
    	PrintHeap( persone, dim );
    
    	getchar();
    }
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,387
    Rep Power
    1871
    First of all, it doesn't compile, it's missing a closing brace for heapsort()
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXPER 30
    
    typedef struct {
      char nome[30];
      char cognome[30];
      int age;
    } Persona;
    
    
    int Left(int i)
    {
      return 2 * i;
    }
    
    int Right(int i)
    {
      return 2 * i + 1;
    }
    
    int Parent(int i)
    {
      if (i == 0)
        return -1;
      return (i - 1) / 2;
    }
    
    int LessThan(Persona a, Persona b)
    {
      if (a.age != b.age) {
        if (b.age < a.age) {
          return 1;
        }
        if (a.age < b.age) {
          return 0;
        }
      }
      if (a.age == b.age) {
        if (strcmp(b.cognome, a.cognome) <= 0) {
          return 1;
        }
        if (strcmp(b.cognome, a.cognome) > 0) {
          return 0;
        }
      }
    }
    
    
    void Swap(Persona * a, Persona * b)
    {
      Persona t = *a;
      *a = *b;
      *b = t;
    }
    
    void Heapify(Persona heap[], int dim, int i)
    {
      int min = i;
      if (i > dim)
        return;
    
      if (Left(i) <= dim && LessThan(heap[i], heap[Left(i)])) {
        min = Left(i);
      }
      if (Right(i) <= dim && LessThan(heap[i], heap[Right(i)])) {
        min = Right(i);
      }
    
      if (min != i) {
        Swap(&heap[min], &heap[i]);
        Heapify(heap, dim, min);
      }
    
    }
    
    void heapsort(Persona heap[], int dim)
    {
      int i = 0, heap_size = dim;
      for (i = dim; i >= 2; i--) {
        Swap(&heap[1], &heap[i]);
        Heapify(heap, 1, --dim);
      }
    }  //!! MISSING !!!
    
    void BuildHeap(Persona heap[], int dim)
    {
      int i;
    
      for (i = (dim - 1) / 2; i >= 0; i--) {
        Heapify(heap, dim, i);
      }
    }
    
    void ShowNext(Persona heap[], int dim)
    {
      printf("Next to Serve : %s %s %d\n", heap[1].cognome, heap[1].nome, heap[1].age);
    }
    
    void Insert(Persona heap[], int *dim)
    {
      Persona p;
      int i;
    
      printf("Insert the name : ");
      scanf("%s", p.nome);
      printf("Insert the surname : ");
      scanf("%s", p.cognome);
      printf("Insert the age' : ");
      scanf("%d", &p.age);
      //!! this is undefined behaviour fflush(stdin);
    
      heap[*dim] = heap[Parent(*dim)];
      heap[Parent(*dim)] = p;
    
      (*dim)++;
    
      for (i = Parent(*dim - 1); i >= 0; i = Parent(i)) {
        Heapify(heap, *dim, i);
      }
    
      ShowNext(heap, *dim);
    
    }
    
    void CaricaPersone(Persona persone[], int *dim)
    {
      FILE *file;
    
      file = fopen("foo.txt", "r");
      if (file == NULL) {
        fprintf(stderr, "Error");
        exit(1);
      }
    
      *dim = 0;
      //!! feof() doesn't do what you think it does.
    //   while( !feof( file ) )
    //   {
    //     fscanf( file, "%s %s %d\n", persone[*dim].nome, persone[*dim].cognome, &persone[*dim].age );
      while (fscanf(file, "%s %s %d\n", persone[*dim].nome, persone[*dim].cognome, &persone[*dim].age)
             == 3) {
        (*dim)++;
      }
      fclose(file);
    
    }
    
    void PrintHeap(Persona heap[], int dim)
    {
      int i;
      printf("\n");
      for (i = 0; i < dim; i++) {
        printf("%s %s %d\n", heap[i].cognome, heap[i].nome, heap[i].age);
      }
      printf("\n");
    }
    
    int main()
    {
      Persona persone[MAXPER];
      int dim = 0;
    
      CaricaPersone(persone, &dim);
      BuildHeap(persone, dim);
      heapsort(persone, dim);
      PrintHeap(persone, dim);
    
      Insert(persone, &dim);
    
      PrintHeap(persone, dim);
    
      getchar();
    }
    Then you mis-use feof(). You MUST check the actual file reading function (in this case, fscanf) for success.

    Also, remove the fflush(stdin), it's undefined behaviour.

    Finally, some error messages for you to fix.
    Code:
    $ gcc -Wall foo.c
    foo.c: In function ‘heapsort’:
    foo.c:80:14: warning: unused variable ‘heap_size’ [-Wunused-variable]
    foo.c: In function ‘main’:
    foo.c:174:1: warning: control reaches end of non-void function [-Wreturn-type]
    foo.c: In function ‘LessThan’:
    foo.c:48:1: warning: control reaches end of non-void function [-Wreturn-type]
    Falling off the end of a function with a garbage value isn't likely to produce correct results.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    3
    Rep Power
    0
    Originally Posted by salem
    First of all, it doesn't compile, it's missing a closing brace for heapsort()
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXPER 30
    
    typedef struct {
      char nome[30];
      char cognome[30];
      int age;
    } Persona;
    
    
    int Left(int i)
    {
      return 2 * i;
    }
    
    int Right(int i)
    {
      return 2 * i + 1;
    }
    
    int Parent(int i)
    {
      if (i == 0)
        return -1;
      return (i - 1) / 2;
    }
    
    int LessThan(Persona a, Persona b)
    {
      if (a.age != b.age) {
        if (b.age < a.age) {
          return 1;
        }
        if (a.age < b.age) {
          return 0;
        }
      }
      if (a.age == b.age) {
        if (strcmp(b.cognome, a.cognome) <= 0) {
          return 1;
        }
        if (strcmp(b.cognome, a.cognome) > 0) {
          return 0;
        }
      }
    }
    
    
    void Swap(Persona * a, Persona * b)
    {
      Persona t = *a;
      *a = *b;
      *b = t;
    }
    
    void Heapify(Persona heap[], int dim, int i)
    {
      int min = i;
      if (i > dim)
        return;
    
      if (Left(i) <= dim && LessThan(heap[i], heap[Left(i)])) {
        min = Left(i);
      }
      if (Right(i) <= dim && LessThan(heap[i], heap[Right(i)])) {
        min = Right(i);
      }
    
      if (min != i) {
        Swap(&heap[min], &heap[i]);
        Heapify(heap, dim, min);
      }
    
    }
    
    void heapsort(Persona heap[], int dim)
    {
      int i = 0, heap_size = dim;
      for (i = dim; i >= 2; i--) {
        Swap(&heap[1], &heap[i]);
        Heapify(heap, 1, --dim);
      }
    }  //!! MISSING !!!
    
    void BuildHeap(Persona heap[], int dim)
    {
      int i;
    
      for (i = (dim - 1) / 2; i >= 0; i--) {
        Heapify(heap, dim, i);
      }
    }
    
    void ShowNext(Persona heap[], int dim)
    {
      printf("Next to Serve : %s %s %d\n", heap[1].cognome, heap[1].nome, heap[1].age);
    }
    
    void Insert(Persona heap[], int *dim)
    {
      Persona p;
      int i;
    
      printf("Insert the name : ");
      scanf("%s", p.nome);
      printf("Insert the surname : ");
      scanf("%s", p.cognome);
      printf("Insert the age' : ");
      scanf("%d", &p.age);
      //!! this is undefined behaviour fflush(stdin);
    
      heap[*dim] = heap[Parent(*dim)];
      heap[Parent(*dim)] = p;
    
      (*dim)++;
    
      for (i = Parent(*dim - 1); i >= 0; i = Parent(i)) {
        Heapify(heap, *dim, i);
      }
    
      ShowNext(heap, *dim);
    
    }
    
    void CaricaPersone(Persona persone[], int *dim)
    {
      FILE *file;
    
      file = fopen("foo.txt", "r");
      if (file == NULL) {
        fprintf(stderr, "Error");
        exit(1);
      }
    
      *dim = 0;
      //!! feof() doesn't do what you think it does.
    //   while( !feof( file ) )
    //   {
    //     fscanf( file, "%s %s %d\n", persone[*dim].nome, persone[*dim].cognome, &persone[*dim].age );
      while (fscanf(file, "%s %s %d\n", persone[*dim].nome, persone[*dim].cognome, &persone[*dim].age)
             == 3) {
        (*dim)++;
      }
      fclose(file);
    
    }
    
    void PrintHeap(Persona heap[], int dim)
    {
      int i;
      printf("\n");
      for (i = 0; i < dim; i++) {
        printf("%s %s %d\n", heap[i].cognome, heap[i].nome, heap[i].age);
      }
      printf("\n");
    }
    
    int main()
    {
      Persona persone[MAXPER];
      int dim = 0;
    
      CaricaPersone(persone, &dim);
      BuildHeap(persone, dim);
      heapsort(persone, dim);
      PrintHeap(persone, dim);
    
      Insert(persone, &dim);
    
      PrintHeap(persone, dim);
    
      getchar();
    }
    Then you mis-use feof(). You MUST check the actual file reading function (in this case, fscanf) for success.

    Also, remove the fflush(stdin), it's undefined behaviour.

    Finally, some error messages for you to fix.
    Code:
    $ gcc -Wall foo.c
    foo.c: In function ‘heapsort’:
    foo.c:80:14: warning: unused variable ‘heap_size’ [-Wunused-variable]
    foo.c: In function ‘main’:
    foo.c:174:1: warning: control reaches end of non-void function [-Wreturn-type]
    foo.c: In function ‘LessThan’:
    foo.c:48:1: warning: control reaches end of non-void function [-Wreturn-type]
    Falling off the end of a function with a garbage value isn't likely to produce correct results.
    Thank you very much for your help, i cleared the garbage values but the program is still not giving me the wanted results
    here is the code i have so far i think i have some error of logic on the function LessThan but i can not figure it out.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXPER 30
    
    typedef struct
    {
    	char nome[30];
    	char cognome[30];
    	int eta;
    }
    Persona;
    
    
    int Left( int i )
    {
    	return 2*i;
    }
    
    int Right( int i )
    {
    	return 2*i + 1;
    }
    
    int Parent( int i )
    {
    	if ( i == 0) return -1;
    	return (i - 1)/2;
    }
    
    int LessThan( Persona a, Persona b )
    {
    	if ( a.eta != b.eta )
    		{
    			if(b.eta <a.eta)
    			{
    				return 1;
    			}
    			else
    			{
    				return 0;
    			}
    		}
    	else
    		{
    			if(strcmp( b.cognome, a.cognome ) <= 0)
    			{
    				return 1;
    			}
    			if(strcmp( b.cognome, a.cognome ) > 0)
    			{
    				return 0;
    			}
    		}
    }
    
    
    void Swap( Persona *a, Persona *b )
    {
    	Persona t = *a;
    	*a = *b;
    	*b = t;
    }
    
    void Heapify( Persona heap[], int dim, int i )
    {
    	int min = i;
    	if ( i > dim ) return;
    
    	if ( Left(i) <= dim && LessThan( heap[min],heap[ Left(i) ] ) )
    	{
    		min = Left(i);
    	}
    	if ( Right(i) <= dim && LessThan( heap[min],heap[ Right(i) ] ) )
    	{
    		min = Right(i);
    	}
    	
    	if ( min != i )
    	{
    		Swap( &heap[min], &heap[ i ] );
    		Heapify( heap, dim, min );
    	}
    
    }
    
    void BuildHeap( Persona heap[], int dim )
    {
    	int i;
    
    	for ( i=(dim-1)/2; i>=0; i-- )
    	{
    		Heapify( heap, dim, i );
    	}
    }
    
    void ShowNext( Persona heap[], int dim )
    {
    	printf("Prossima da servire : %s %s %d\n", heap[0].cognome, heap[0].nome, heap[0].eta );
    }
    
    void Insert( Persona heap[], int *dim )
    {
    	Persona p;
    	int i;
    
    	printf("Inserire il nome : ");
    	scanf( "%s", p.nome );
    	printf("Inserire il cognome : ");
    	scanf( "%s", p.cognome );
    	printf("Inserire l'eta' : ");
    	scanf( "%d", &p.eta );
    	fflush(stdin);
    
    	heap[*dim] = heap[ Parent(*dim) ];
    	heap[ Parent(*dim) ] = p;
    	
    	(*dim)++;
    
    	for ( i=Parent(*dim - 1); i>=0; i=Parent(i) )
    	{
    		Heapify( heap, *dim, i );
    	}
    
    	ShowNext( heap, *dim );
    	
    }
    
    void CaricaPersone( Persona persone[], int *dim )
    {
    	FILE *file;
    
    	file = fopen("persone.txt", "r");
    	if(file==NULL)
    	{
    		fprintf(stderr,"Error");
    		exit(1);
    	}
    
    	*dim = 0;
    	while( !feof( file ) )
    	{
    		fscanf( file, "%s %s %d\n", persone[*dim].nome, persone[*dim].cognome, &persone[*dim].eta );
    		(*dim)++;
    		
    	}
    	fclose(file);
    
    }
    
    void PrintHeap( Persona heap[], int dim )
    {
    	int i;
    	printf("\n");
    	for (i=0; i<dim; i++)
    	{
    		printf( "%s %s %d\n", heap[i].cognome, heap[i].nome, heap[i].eta );
    	}
    	printf("\n");
    }
    
    int main()
    {
    	Persona persone[MAXPER];
    	int dim=0;
    
    	CaricaPersone( persone, &dim );
    	BuildHeap( persone, dim );
    	PrintHeap( persone, dim );
    
    	Insert( persone, &dim );
    
    	PrintHeap( persone, dim );
    	system("PAUSE");
    	return 0;
    }
  6. #4
  7. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,387
    Rep Power
    1871
    It contains the same repeated mistakes I've already pointed out.
    I see no point in wasting any more time if you're not going to listen to anybody.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    3
    Rep Power
    0
    Ok i believe i cleared the errors of the fflush,fof and the unused value on heapsort also i made the main return 0 to close the program but i am having trouble still with my LessThan function.
    I thank you very much for helping me until now.

    here is the code

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXPER 30
    
    typedef struct
    {
    	char nome[30];
    	char cognome[30];
    	int eta;
    }
    Persona;
    
    
    int Left( int i )
    {
    	return 2*i;
    }
    
    int Right( int i )
    {
    	return 2*i + 1;
    }
    
    int Parent( int i )
    {
    	if ( i == 0) return -1;
    	return (i - 1)/2;
    }
    
    int LessThan( Persona a, Persona b )
    {
    	if ( a.eta != b.eta )
    		{
    			if(b.eta <a.eta)
    			{
    				return 1;
    			}
    			else
    			{
    				return 0;
    			}
    		}
    	else
    		{
    			if(strcmp( b.cognome, a.cognome ) <= 0)
    			{
    				return 1;
    			}
    			if(strcmp( b.cognome, a.cognome ) > 0)
    			{
    				return 0;
    			}
    		}
    }
    
    
    void Swap( Persona *a, Persona *b )
    {
    	Persona t = *a;
    	*a = *b;
    	*b = t;
    }
    
    void Heapify( Persona heap[], int dim, int i )
    {
    	int min = i;
    	if ( i > dim ) return;
    
    	if ( Left(i) <= dim && LessThan( heap[min],heap[ Left(i) ] ) )
    	{
    		min = Left(i);
    	}
    	if ( Right(i) <= dim && LessThan( heap[min],heap[ Right(i) ] ) )
    	{
    		min = Right(i);
    	}
    	
    	if ( min != i )
    	{
    		Swap( &heap[min], &heap[ i ] );
    		Heapify( heap, dim, min );
    	}
    
    }
    
    void BuildHeap( Persona heap[], int dim )
    {
    	int i;
    
    	for ( i=(dim-1)/2; i>=0; i-- )
    	{
    		Heapify( heap, dim, i );
    	}
    }
    
    void ShowNext( Persona heap[], int dim )
    {
    	printf("Prossima da servire : %s %s %d\n", heap[0].cognome, heap[0].nome, heap[0].eta );
    }
    
    void Insert( Persona heap[], int *dim )
    {
    	Persona p;
    	int i;
    
    	printf("Inserire il nome : ");
    	scanf( "%s", p.nome );
    	printf("Inserire il cognome : ");
    	scanf( "%s", p.cognome );
    	printf("Inserire l'eta' : ");
    	scanf( "%d", &p.eta );
    	
    
    	heap[*dim] = heap[ Parent(*dim) ];
    	heap[ Parent(*dim) ] = p;
    	
    	(*dim)++;
    
    	for ( i=Parent(*dim - 1); i>=0; i=Parent(i) )
    	{
    		Heapify( heap, *dim, i );
    	}
    
    	ShowNext( heap, *dim );
    	
    }
    
    void CaricaPersone( Persona persone[], int *dim )
    {
    	FILE *file;
    
    	file = fopen("persone.txt", "r");
    	if(file==NULL)
    	{
    		fprintf(stderr,"Error");
    		exit(1);
    	}
    
    	*dim = 0;
    	while (fscanf(file, "%s %s %d\n", persone[*dim].nome, persone[*dim].cognome, &persone[*dim].eta)== 3) 
    	{
    		(*dim)++;
    	}
    	fclose(file);
    
    }
    
    void PrintHeap( Persona heap[], int dim )
    {
    	int i;
    	printf("\n");
    	for (i=0; i<dim; i++)
    	{
    		printf( "%s %s %d\n", heap[i].cognome, heap[i].nome, heap[i].eta );
    	}
    	printf("\n");
    }
    
    int main()
    {
    	Persona persone[MAXPER];
    	int dim=0;
    
    	CaricaPersone( persone, &dim );
    	BuildHeap( persone, dim );
    	PrintHeap( persone, dim );
    
    	Insert( persone, &dim );
    
    	PrintHeap( persone, dim );
    	system("PAUSE");
    	return 0;
    }
  10. #6
  11. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,162
    Rep Power
    2222
    How is LessThan() supposed to work? What do the return values mean? If you are comparing fields in a and b and returning "true" when one is less than the other, then which is it, a<b or b<a?

    int LessThan( Persona a, Persona b )

    Reading the prototype naďvely, I would assume this:
    returns 1 (true) if a<b
    else returns 0 (false).

    Reading the code, I find this:
    return 1 if b<a
    else returns 0.

    So what does the rest of your program expect LessThan() to do?

    PS
    I would humbly suggest that this is a prime instance where readability would be very greatly enhanced by brief comments before each function stating what the function does and what the return values mean.

    That can be (and will often be) more for your own benefit than for ours.
    Last edited by dwise1_aol; July 18th, 2013 at 10:44 AM.

IMN logo majestic logo threadwatch logo seochat tools logo