### Thread: Need help with trees in C.

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. 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.
3. 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;
}```
4. 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.
5. 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;
}```
6. 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.