Files & Trees

Hello everyone!! I have this exercise and i want a small help to understand how the heap sorting of an array works. Actually my exercise says to make a file (input.txt) put inside some random numbers with first number of the file the length of the numbers (for example if we ask the user how many numbers wants in the file and let's say says 5 the first number will be 5 and then the random numbers ) and then take from the file these random numbers and put them in an array, sort them (with the heap sort) and print the array in another file (output.txt). I managed to do the first part of the exercise but i stuck in the part of sorting the array!!! I search it lots of times but i am little bit confused with the way of doing it.

This is my code of creating the file and put the random numbers in it. Then i take the numbers and i put them in the Array[].

Code:

---


# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
# include <time.h>

# define LIMIT 1000

void create_file(FILE *fp,int N)
{
    int i, random_number;

    if ( fp == NULL )
    {
        printf ( "The file can not be created." ) ;
        getch() ;
        exit (0) ;
    }

    srand ( time(NULL) );

    fprintf(fp, "%d ", N);
    printf("%d ", N);

    for ( i = 1; i < N; i++ )
    {
        random_number = rand()%LIMIT;
        fprintf(fp, "%d ",random_number);
        printf( "%d ", random_number) ;
    }
}

void put_inArray(FILE *fp, int *Array, int N)
{
    int i;
   
    if ( fp == NULL )
    {
        printf ( "The file can not open for reading." ) ;
        getch() ;
        exit (0) ;
    }
   
    for(i=0; i<N; i++)
    {
        fscanf(fp, "%d ", Array[i]);
    }
   
}

void heap_create(int *Array, int N)
{
      //I don't know what to put here. I just want your help   
         
}

int main()
{
    char file_name[50];
    int N;
    FILE *fp;
    int i;

    printf("Please give name of the file you want to create: ");
    scanf("%s", file_name);
    printf("Please give how many numbers you want to put in the array: ");
    scanf("%d", &N);

    int Array[N];

    fp = fopen(file_name, "w");

    create_file(fp,N);
   
    printf("Please give the name of the file you want to open: ");
    scanf("%s", file_name);
   
    fp = fopen(file_name, "r"); //I am trying to open the file to read it and take the numbers and put them in the Array[].
 
    put_inArray(fp, Array,N);
 
  // heap_create(); i am not sure for this function


return 0;
system("pause");

}

---

Every small help is exepted. Thank you :) :)

In create_file:

Code:

---

for ( i = 1; i < N; i++ )

---

This will only generate N-1 random numbers. I suggest the more common idiom of

Code:

---

for (i = 0; i < N; i++)

---

In main:

Code:

---

return 0;
system("pause");

---

You had this problem in your other thread. Seriously, pay attention to what you're doing, and to the advice people give you when you ask for it. Ignoring advice does not inspire us to help you.

Laserlight asked you to make an attempt, but all you did was use code from your last thread and put in a function prototype for heap_create. You need to make a real attempt. You know, write some actual code for the heap sort algorithm. Who cares if it's a train wreck. Show us you're serious about trying this and learning this yourself. You said you've made attempts before, so post one of those. Or, start by reading the Wikipedia article on heap sort (it's a bit technical, but thorough). Google for tutorials and sample code, there's plenty out there.

Give it a shot and post back with some specific questions, and you'll probably get more specific help.

Obviously, my friend i am not only the one here that does not pay attention to what someone said. Firstly, I said in my exercise, we are supposed to ask the user how many numbers wants in the file and this number will be the first number of the file. If the user wants 5 numbers and the first number of the file will be 5 the other 4 numbers aren't the random ones? So i don't thing i am so stupid of doing that :

for ( i = 1; i < N; i++ ) //This is only for generating the random numbers which will be N-1 that's why i am starting from 1 and not from 0 because if i=0 the number will be the N.
Secondly, a made my main function int main() not because i didn't want to do it like you said, but because the compiler prints me some warnings about this. When i make main int everything is ok and the program runs ok without any errors or warnings. So my advice to you is don't try to make conclusions before you ask for something you didn't understand i put in my code. Ask me first why i did it and then tell me what do you think about it.

Thirdly if you don't want to help me about something i asked, don't tell me at all, don't trying to find stupid things in my code and be upset with them and the only thing you understand i did was that i copied from somewhere else the code and put it here only to make you tell me how i am supposed to continue and solve all the exercise. It's not so good. It's the first time i am using files and heap sorting method (trees) so before i came here i searched every possible page but still i am confused, that's why i ask you to help me. The only thing i wanted from you was to explain me how it works and obviously not to solve me all the exercise.

I am not telling you all these to argue with you but to understand that here i am only because i want some help that i can not find in class, and not tell you to solve my exercise.

Thank you for your understanding.

I did pay attention, and I wasn't saying you were being stupid there, merely that I thought you were misunderstanding the assignment or had a typo/bug. The first number is the length/count of the random numbers. Typically this means that if the first number is 5, it is followed by 5 random numbers in the file, for a total of 6 numbers. I've never seen nor heard of it done the way you are suggesting, but perhaps your professor is unconventional :p. If you could post the exact assignment description, perhaps we could clear this all up.

As for the return 0; bit, it had nothing to do with void main vs. int main. It has to do with what Tim pointed out in the post I linked. The system("pause") command will never execute. It is below the return 0; so once the return happens, main is done, any further code is not executed. Your compiler should warn you about this, if not, try turning up the warning level. Again, I'm not looking to nitpick irrelevant issues, rather point out actual issues with what code you did provide. I know it is not the part of the program you asked about, but if I see errors in any part of any program posted anywhere on this site, I tend to point them out, to avoid any potential issues/problems that may result from it later.

On to the heap sort thing, laserlight did ask you to show your attempts. We get a lot of people who come here basically asking for free handouts, and trying to be clever about it. I've become quite jaded (and I'm guessing I'm not the only one on this forum). So if you did make several attempts, all we want is for you post one, as a show of good faith that you are attempting to do this and learn this on your own. Claiming that you did, but failing to prove it does not build a string case for you. It makes it look like you're waiting for a handout.

If you don't want to provide code, then at least tell us what you do know/understand about heaps and heap sort, and what you don't understand. Your post suggests that you know/understand nothing about heapsort and want us to teach you everything you need to know. It's impractical for us to give complete lectures on data structures. Besides, we are not here so much to teach, as we are here to supplement your learning and help you with problems you encounter along the way. Maybe you don't understand heaps at all. Maybe you're simply having problems calculating the indexes of the left and right children of a given node. Without more info from you, we don't really know where to begin helping you.

Start with this overview:

Quote:

---

Originally Posted by Wikipedia - Heapsort

Heapsort is a two step algorithm.

The first step is to build a heap out of the data.

The second step begins with removing the largest element from the heap. We insert the removed element into the sorted array. For the first element, this would be position 0 of the array. Next we reconstruct the heap and remove the next largest item, and insert it into the array. After we have removed all the objects from the heap, we have a sorted array. We can vary the direction of the sorted elements by choosing a min-heap or max-heap in step one.

Heapsort can be performed in place. The array can be split into two parts, the sorted array and the heap. The storage of heaps as arrays is diagrammed at Binary heap#Heap implementation.The heap's invariant is preserved after each extraction, so the only cost is that of extraction.

---

What do you understand from that and what don't you understand?

Here is my code i have tried and the attempt of creating some functions such us: creating a heap, and sorting a heap among with the functions of the files (create file, take_from_file and copy file).

Code:

---


# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
# include <time.h>

# define LIMIT 1000

void create_file(FILE *fp1, int N)
{
    int i, random_number;

    if ( fp1 == NULL )
    {
        printf ( "The file can not be created." ) ;
        getch() ;
        exit (0) ;
    }

    srand ( time(NULL) );

    fprintf(fp1, "%d ", N);
    printf("%d ", N);

    for ( i = 1; i < N; i++ )
    {
        random_number = rand()%LIMIT;
        fprintf(fp1, "%d ",random_number);
        printf( "%d ", random_number) ;
    }
}

void take_from_file(FILE *fp1, int *Array, int N )//This function takes everything from fp1 file and puts them in Array[]
{
    int i;

    if ( fp1 == NULL )
    {
        printf ( "The file can not be created." ) ;
        getch() ;
        exit (0) ;
    }
    for(i=0; i<N; i++)
    {
        fscanf(fp1, "%d ", Array[i]);
        printf("%d ", Array[i]);
    }
}

void heap_create(int *Array, int N)
{
    int i,j, parent,child,temp;
   
    for(i = 2; i <= N; i++)
    {
        child = i;
        parent = child/2;
       
        while(child > 1 && Array[child] > Array[parent])
        {
            temp = Array[child];
            Array[child] = Array[parent];
            Array[parent] = temp;
            child = parent;
            parent = child/2;
           
            if(parent < 1)
            {
                parent = 1;
            }
        }
    }
        printf("\n The Array in heap form is: ");
        for(j = 1; j <= N; i++)
        {
            printf(" %d", Array[i]);
        }
}

void sort_Array(FILE *fp2, int *Array, int N)
{
    int current,parent,child,i,maxnodes;
   
    for(maxnodes = N; maxnodes >= 2; maxnodes--)
    {
        current = Array[maxnodes];
        Array[maxnodes] = Array[1];
        parent = 1;
     
        if ((maxnodes-1) >= 3 && Array[3] > Array[2])
        {
          child = 3;
        }
        else
        {
          child = 2;
        }
           
        while (child <= (maxnodes-1) && Array[child] >= current)
        {
            Array[parent] = Array[child];
            parent = child;
            child = child*2;
       
            if((child+1) <= (maxnodes-1) && Array[child+1] > Array[child])
            {
                child = child + 1;
            }
        }

        Array[parent] = current;
    }
 
    printf("\n The Array sorted is: ");
    for(i = 1;i <= N; i++)
    {
        fprintf(fp2, "%d", Array[i]); //I am not sure if i have to put the sorted Array from this point or the way i have done it in the other function copy_file(). Please tell me wich way is better or if they are both wrong or wright.
        printf("%d ",Array[i]);
    }
           
    getch();
}

void copy_file(FILE *fp1, FILE *fp2)//In this function i am trying to put the data of fp1 to fp2, but i want first to bring everything into an Array and then sort this Array. Here is the step i have stuck.
{
    char ch, int counter;
   
    if ( fp1 == NULL )
    {
        printf ( "The file can't open." ) ;
        getch() ;
        exit (0) ;
    }
    if ( fp2 == NULL )
    {
        printf ( "The file can't open." ) ;
        getch() ;
        exit (0) ;
    }

    heap_create();
    take_from_file();//Here i call this function to take the elements from fp1 file and store it into the Array[]
    sort_Array();//And here i am sorting the Array[]

    while(!feof(fp1))
    {
        fputc(Array[i], fp2); //Here i am lost ... :P I don't know how to say to take the sorted Array and put it into fp2.
        counter++;
    }
 
}

int main()
{
    char file_name1[50], file_name2[50];
    int N;
    FILE *fp1, *fp2;
    int i;

    printf("Please give the name of the file you want to create: ");
    scanf("%s", file_name1);
    printf("Please give the number of numbers you want in the file: ");
    scanf("%d", &N);

    int Array[N];

    fp1 = fopen(file_name1, "w");

    create_file(fp1, N);
   
    printf("Please give the name of the source file: ");
    scanf("%s", file_name1);
   
    printf("Please give the name of the destination file: ");
    scanf("%s", file_name2);
   
    fp1 = fopen(file_name1, "r"); //I open the fp1 file for reading it
   
    take_from_file(fp1, Array, N);
    heap_create(Array, N);
    sort_Array(fp2, Array, N);
    copy_file(fp1, fp2);
   
 
system("pause");
return 0;
}

---

I except every small detail or help from you. Thank you although for your before help and advice.

P.S : I am totally sure that in the file we are suppose to have N numbers with the first one the N its self. The teacher from our class sent us an email to clarify that he wants it in that way, maybe he is wrong but i can not do it other way.

Thank you again. I will expect your answer. :) :)

Here's what I get when I compile your program:

Code:

---

$ make heapsort
gcc -Wall -Wunreachable-code -g -std=c99 -pedantic  -lm -lpthread  heapsort.c  -o heapsort
heapsort.c:2:20: error: conio.h: No such file or directory
heapsort.c: In function ‘create_file’:
heapsort.c:15: warning: implicit declaration of function ‘getch’
heapsort.c: In function ‘take_from_file’:
heapsort.c:40: error: ‘i’ undeclared (first use in this function)
heapsort.c:40: error: (Each undeclared identifier is reported only once
heapsort.c:40: error: for each function it appears in.)
heapsort.c: In function ‘heap_create’:
heapsort.c:71: error: ‘n’ undeclared (first use in this function)
heapsort.c:49: warning: unused variable ‘j’
heapsort.c: In function ‘sort_Array’:
heapsort.c:114: error: incompatible type for argument 1 of ‘fprintf’
/usr/include/stdio.h:333: note: expected ‘struct FILE * restrict’ but argument is of type ‘FILE’
heapsort.c: In function ‘copy_file’:
heapsort.c:123: error: expected identifier or ‘(’ before ‘int’
heapsort.c:138: error: too few arguments to function ‘heap_create’
heapsort.c:139: error: too few arguments to function ‘take_from_file’
heapsort.c:140: error: too few arguments to function ‘sort_Array’
heapsort.c:144: error: ‘Array’ undeclared (first use in this function)
heapsort.c:144: error: ‘i’ undeclared (first use in this function)
heapsort.c:145: error: ‘counter’ undeclared (first use in this function)
heapsort.c:123: warning: unused variable ‘ch’
heapsort.c: In function ‘main’:
heapsort.c:158: error: ‘file_name’ undeclared (first use in this function)
heapsort.c:164: error: ‘fp’ undeclared (first use in this function)
heapsort.c:178: error: incompatible type for argument 1 of ‘sort_Array’
heapsort.c:77: note: expected ‘FILE’ but argument is of type ‘struct FILE *’
heapsort.c:155: warning: unused variable ‘i’
make: *** [heapsort] Error 1

---

Eek! Don't worry though, they're (mostly) easy ones.

• Lines 2, 15, 37, 118, 128, 134: conio.h is an outdated header, and not very portable. getch is only available in conio.h. Unless you really need it's features for some legacy code, I suggest removing the #include and replacing getch() with the standard function getchar(), provided by stdio.h.
• Lines 40, 71, 144, 145, 158, 164: You forgot to declare these variables, or other errors made it appear as though they weren't declared. Easy fix: declare them if need be, or fix typos/capitilization in the case of line 71. Fixing some of the other errors should take care of line 145.
• Lines 49, 123, 155: Remove the unused variables.
• Lines 114, 77, 178: You should only using FILE pointers (i.e. FILE *). I think you just forgot a * in the sort_Array function designator.
• Line 123: You have a comma where you should have a semicolon. This will become a non-issue when you remove the unneeded ch variable.
• Lines 138, 139, 140: This will go away when you figure out what to pass to the functions.

Fixing all that brought up one more little error on line 42 (this line number may be a bit different after you fix the above errors). In take_from_file:

Code:

---

fscanf(fp1, "%d ", &Array[i]);

---

Note the &, since fscanf needs the address of the spot in the array where it will store the data it read.

If I wanted a text-type file that is human readable, I would generally use fscanf to read an integer from a file, and always use fprintf to print an integer to a file. However, if I wanted to make an copy that preserves all the white space, etc, I would use fgetc to read a single character, and fputc to write it out.

That should keep you busy for a while. I have to run to class, then I have plans for the evening. I might get back to this tonight, or if not, tomorrow morning. Somebody else may come along and pick up the ball before then, however.

Oh, and the exact assignment specification would be helpful, I'm not sure if you're making it more complicated than it needs to be, with all the files you're using (it could be done with only one file for input -- or zero files really, but we know you need at least one).

I don't see where you are closing file_name1 before trying to open it again in read mode.

Here i am again... I have tried to correct the errors but i don't understand why the program don't run. The function create file is ok but when i tried to run the other functions too it crashes. Please my friend i don't what else to do to make it work and my compiler doesn't print me any more errors. It says 0 errors and 0 warnings.

Code:

---


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

# define LIMIT 1000

void create_file(FILE *fp1, int N)
{
    int i, random_number;

    if ( fp1 == NULL )
    {
        printf ( "The file can not be created." ) ;
        getch() ;
        exit (0) ;
    }

    srand ( time(NULL) );

    fprintf(fp1, "%d ", N);
    printf("%d ", N);

    for ( i = 1; i < N; i++ )
    {
        random_number = rand()%LIMIT;
        fprintf(fp1, "%d ",random_number);
        printf( "%d ", random_number) ;
    }
    printf("\n");
}

void take_from_file(FILE *fp1, int *Array, int N )
{
    int i;

    if ( fp1 == NULL )
    {
        printf("The file can not be created");
        getch() ;
        exit (0) ;
    }
    for(i=0; i<N; i++)
    {
        fscanf(fp1, "%d ", &Array[i]);
        printf("%d ", Array[i]);
    }
}

void heap_create(int *Array, int N)
{
    int i,j, parent,child,temp;

    for(i = 2; i <= N; i++)
    {
        child = i;
        parent = child/2;

        while(child > 1 && Array[child] > Array[parent])
        {
            temp = Array[child];
            Array[child] = Array[parent];
            Array[parent] = temp;
            child = parent;
            parent = child/2;

            if(parent < 1)
            {
                parent = 1;
            }
        }
    }
        printf("\nThe Aray in heap form is: ");
        for(j = 1; j <= N; i++)
        {
            printf(" %d", Array[i]);
        }
}

void sort_Array(FILE *fp2, int *Array, int N)
{
    int current,parent,child,i,maxnodes;

    for(maxnodes = N; maxnodes >= 2; maxnodes--)
    {
        current = Array[maxnodes];;
        Array[maxnodes] = Array[1];
        parent = 1;

        if ((maxnodes-1) >= 3 && Array[3] > Array[2])
        {
          child = 3;
        }
        else
        {
          child = 2;
        }

        while (child <= (maxnodes-1) && Array[child] >= current)
        {
            Array[parent] = Array[child];
            parent = child;
            child = child*2;

            if((child+1) <= (maxnodes-1) && Array[child+1] > Array[child])
            {
                child = child + 1;
            }
        }

        Array[parent] = current;
    }

    printf("\nThe Aray sorted is: ");
    for(i = 1; i <= N; i++)
    {
        fprintf(fp2, "%d", Array[i]);
        printf("%d ",Array[i]);
    }

    getch();
}

/*void copy_file(FILE *fp1, FILE *fp2)//I put everything in comments here because i don't know if i should put this function at all, so i would like you to tell me if can.

{
  char ch;
    int counter;

  if ( fp1 == NULL )
  {
      printf ( "The file can't open." ) ;
      getch() ;
      exit (0) ;
  }
  if ( fp2 == NULL )
  {
      printf ( "The file can't open." ) ;
      getch() ;
      exit (0) ;
  }

  heap_create();
  take_from_file();

  sort_Array();


  while(!feof(fp1))
  {
      fputc(Array[i], fp2);

      counter++;
  }

}*/

int main()
{
    char file_name1[50], file_name2[50];
    int N;
    FILE *fp1, *fp2;

    printf("Please give the name of the file you wnat to crate: ");
    scanf("%s", file_name1);
    printf("Please give me the number of numbers you want to put in your file: ");
    scanf("%d", &N);
    printf("\n");

    int Array[N];

    fp1 = fopen(file_name1, "w");

    create_file(fp1,N);
    fclose(fp1);

    printf("Please give the name of the source file: ");
    scanf("%s", file_name1);
    printf("Please give the name of the destination file: ");
    scanf("%s", file_name2);

    fp1 = fopen(file_name1, "r");
    //copy_file(fp1, file_name1, file_name2);

    heap_create(Array, N);

    fp2 = fopen(file_name2, "w");
    sort_Array(fp2, Array, N);

    fclose(fp1);
    fclose(fp2);


system("pause");
return 0;
}

---

I will appreciate if you tell me if anything in the code of sorting the array and creating the heap is false.

Thank you!!

For the library conio.h i don't get any error when i compile the program in my computer. But there you said to me to remove the #include and replacing getch() with the standard function getchar(). I don't really understands what that means... :)

Anyone who knows how i have to put the elements from the array sorted with heap sort from one file to another file ????

Quote:

---

Originally Posted by ValL

Anyone who knows how i have to put the elements from the array sorted with heap sort from one file to another file ?

---

Can't you just write the array to the other file?

Quote:

---

Originally Posted by ValL

For the library conio.h i don't get any error when i compile the program in my computer. But there you said to me to remove the #include and replacing getch() with the standard function getchar(). I don't really understands what that means... :)

---

That means, everywhere in your code, you call

Code:

---

getch();

---

change it to

Code:

---

getchar();

---

That's it, just simply changing a few "words".

I have this sorted heap. Can anyone tell me if is correct?

Code:

---


void sort_Array(int *Array, int N)
{
    int current,parent,child,i,maxnodes;

    for(maxnodes = N; maxnodes >= 2; maxnodes--)
    {
        current = Array[maxnodes];
        Array[maxnodes] = Array[1];
        parent = 1;

        if ((maxnodes-1) >= 3 && Array[3] > Array[2])
        {
          child = 3;
        }
        else
        {
          child = 2;
        }

        while (child <= (maxnodes-1) && Array[child] >= current)
        {
            Array[parent] = Array[child];
            parent = child;
            child = child*2;

            if((child+1) <= (maxnodes-1) && Array[child+1] > Array[child])
            {
                child = child + 1;
            }
        }

        Array[parent] = current;
    }

    printf("\n The array sorted is : ");
    for(i = 1; i <= N; i++)
    {
        printf("%d ",Array[i]);
    }

}

---

Thank you.