0

I have to read a file, allocate an array of size k and store the k largest numbers in the array. I know how to scan and read the file and sort it but I don't know how to link them together. I will be really glad if someone could help me out with this issue!

I have tried to strlen, sizeof, counting loops of fscanf but none of them worked. The part with ??? is where I don know what to put. Generally I would put a amount of elements but in this case amount of elements in the file is unknown. 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
int main(int argc, char *argv[])//
{

    FILE *iFile;
    int k = atoi(argv[1]);//convert strings into int
    int i = 0, j = 0, n = 0, temp = 0;
    int *arr = (int *)malloc(k * sizeof(int));//allocate size k in an array

    iFile = fopen("a.txt", "r");

    if (iFile == NULL)
        return -1;
    while (feof(iFile) <= 0)
    {
        fscanf(iFile, "%d", arr);
        //find number of elements since I have to compare all the numbers with each other


    }
    //reverse
    for (i = 0; i < ??? - 1; i++)                     //Loop for descending ordering
    {
        for (j = 1; j <= ??? - 1; j++)             //Loop for comparing other values
        {
            if (arr[j] < arr[i])                //Comparing other array elements
            {
                temp = arr[i];         //Using temporary variable for storing last temp
                arr[i] = arr[j];            //replacing temp
                arr[j] = temp;             //storing last temp
            }
        }
    }

     for (i = 0; i < k; i++)                     //Loop for printing array 
     data after sorting
     {
printf("%d\n", arr[i]);                   //Printing data
     }

    free(arr);
    fclose(iFile);

    return 0;
}
serene
  • 19
  • 3
  • It is complete overkill to sort the whole file. Read it element by element and only keep them, if they are amongst the top-5. Discard elements, which are pushed out. – Ctx Mar 29 '19 at 12:42
  • 2
    First please read what [`feof`](https://en.cppreference.com/w/c/io/feof) returns. Then read [Why is “while (!feof(file))” always wrong?](https://stackoverflow.com/questions/5431941/why-is-while-feoffile-always-wrong) – Some programmer dude Mar 29 '19 at 12:42
  • 1
    Furthermore, in your reading loop, you *always* read into `arr[0]`, no other element will be set. – Some programmer dude Mar 29 '19 at 12:43
  • What is `while (feof(iFile) <= 0)` supposed to do? – Thomas Jager Mar 29 '19 at 12:43
  • 1
    Lastly, you might be interested in the [`qsort`](https://en.cppreference.com/w/c/algorithm/qsort) function (unless you use the method mentioned by @Ctx). – Some programmer dude Mar 29 '19 at 12:45
  • Oh and a last-second addendum, *never* use a string from `argv` without first checking `argc`. – Some programmer dude Mar 29 '19 at 12:46
  • @Someprogrammerdude Thank you for sending the link! My professor always uses feof so that's why I used it. I am still pretty new at C I don't really get what that thread is talking about!... The prototype for int main was given by the professor and argv takes 5 as the parameter for now since I am trying so trying print the top 5 largest elements. – serene Mar 29 '19 at 12:46
  • @ThomasJager it reads till the end of the file. If it hits -1 it breaks. – serene Mar 29 '19 at 12:49
  • @Ctx but to find the largest number won't I have to read the whole thing??? What do you mean by push out??? – serene Mar 29 '19 at 12:52
  • @serene read, yes. sort, no. Ok, maybe the naive approach is sufficient, just read all numbers in a single array and do a qsort. You have to use malloc()/realloc() to manage the memory for the array if there is no fixed upper bound for the number of values. – Ctx Mar 29 '19 at 12:52
  • @Ctx I am really sorry but I don't understand the algorithm or pseudocode for that. This is my first assignment where I am reading a file. – serene Mar 29 '19 at 12:55
  • This look very similar to this question: https://stackoverflow.com/questions/55390137/for-my-c-code-where-i-am-reading-a-file-and-sorting-it-is-giving-me-garbage-out?noredirect=1#comment97548430_55390137 Not only the task, but also the code is very close. – Gerhardh Mar 29 '19 at 13:07
  • @serene Imagine drawing numbers from a hat and only keeping the biggest 5 numbers. If you draw a number bigger than the smallest number you kept, keep it and instead discard the smallest number. – Ctx Mar 29 '19 at 13:12
  • @Gerhardh yeah that was my code. – serene Mar 30 '19 at 00:05
  • @serene you are not interested by the answer ? I delete it ? – bruno Apr 01 '19 at 13:26
  • @bruno I can't upvote or save your answer because I have less than 15 reputations. If I could I would have . – serene Apr 01 '19 at 23:29

1 Answers1

0

Here a proposal, as you I use a sorted array, in my case in ascending order because this seems more 'natural' (to use a descending order change almost nothing).

To sort the 'k' first values I use qsort from the stdlib, and the function comp to do the required comparisons.

The main is he function insert, because the array is sorted it is possible to first search where to insert the new element with a complexity log2(k) but after it can be necessary to move the already present elements by 1 position to create the place for the new element, so I prefered to do the search and the move at the same time.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

/* for qsort */
int comp(const void * p1, const void * p2)
{
  return (*((int *) p1) - *((int *) p2));
}

/* insert v in arr having sz elts */
void insert(int * arr, int v, int sz)
{
  if (v > arr[0]) {
    /* search and move elts to let a hole for the new elt */
    for (int i = 1; i != sz; ++i) {
      if (v <= arr[i]) {
        /* place it in the hole */
        arr[i - 1] = v;
        return;
      }
      arr[i - 1] = arr[i];
    }

    /* v is the greater value */
    arr[sz - 1] = v;
  }
}

int main(int argc, char *argv[])
{
  int k;
  FILE * iFile;
  int * arr;

  if ((argc != 3) || (sscanf(argv[1], "%d", &k) != 1))
    fprintf(stderr, "Usage: %s <number of value> <file>\n", *argv);
  else if (k < 1)
    fprintf(stderr, "<number of value> must be greater than 0\n");
  else if ((iFile = fopen(argv[2], "r")) == NULL)
    fprintf(stderr, "cannot open '%s'\n", argv[2]);
  else if ((arr = malloc(k * sizeof(int))) == NULL)
    fprintf(stderr, "cannot allocate an array of %d in\n", k);
  else {
    /* read first 'k' values */
    int i;

    for (i = 0; i != k; ++i) {
      if (fscanf(iFile, "%d", &arr[i]) != 1) {
        fprintf(stderr, "invalid file or too few values in\n");
        fclose(iFile);
        return -1;
      }
    }

    /* sort them */
    qsort(arr, k, sizeof(int), comp);

    /* manage all the next values */
    int v;

    while (fscanf(iFile, "%d", &v) == 1)
      insert(arr, v, k);

    fclose(iFile);

    /* print result */
    for (i = 0; i != k; ++i)
      printf("%d ", arr[i]);
    putchar('\n');
    free(arr);
    return 0;
  }

  return -1;
}

Compilation and execution :

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra -Wall k.c
pi@raspberrypi:/tmp $ cat a.txt 
12 78 6 2 9 56 3 45 21 0 1 56 0
pi@raspberrypi:/tmp $ ./a.out 10 a.txt 
2 3 6 9 12 21 45 56 56 78 
pi@raspberrypi:/tmp $ ./a.out 3 a.txt 
56 56 78 
pi@raspberrypi:/tmp $ ./a.out 1 a.txt 
78

Execution under valgrind :

pi@raspberrypi:/tmp $ valgrind ./a.out 10 a.txt 
==2217== Memcheck, a memory error detector
==2217== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2217== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2217== Command: ./a.out 10 a.txt
==2217== 
2 3 6 9 12 21 45 56 56 78 
==2217== 
==2217== HEAP SUMMARY:
==2217==     in use at exit: 0 bytes in 0 blocks
==2217==   total heap usage: 4 allocs, 4 frees, 5,512 bytes allocated
==2217== 
==2217== All heap blocks were freed -- no leaks are possible
==2217== 
==2217== For counts of detected and suppressed errors, rerun with: -v
==2217== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)
bruno
  • 32,421
  • 7
  • 25
  • 37