Using pointers instead of 2-D array string in C

Question

I have a problem like here: Write a program to read a multiple line text file and write the 'N' longest lines to stdout. Where the file to be read is specified on the command line.

Now I wrote my program like this:

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

int main(int argc, char *argv[])
{
  int a,k,n,i=0,j;
  int part;
  char ar[1000][1000],str[1000];
  /* char file[200]; */
  /* scanf("%s",file); */
  FILE *f = fopen(argv[1],"r");
  if ( f == NULL || argc < 2)
  {
    return 0;
  }

   fscanf(f,"%d",&a);

   while (fscanf(f,"%s",str)==1)
   {
        strcpy(ar[i++],str);

      for ( k = 0 ; k < i ; k++ )
      {
        for ( j = k ; j < i ; j++)
        {
          if ( strlen(ar[k]) < strlen(ar[j]))
          {
            strcpy(str,ar[k]);
            strcpy(ar[k],ar[j]);
            strcpy(ar[j],str);
          }
        }
      }

   }

   for ( j = 0 ; j < a ; j++ )
   {
    puts(ar[j]);
  }

return 0;
}

First of all it is working well for me but on submission it is giving me runtime error. Secondly I want to do it using pointers and dynamic allocation of memory. How can I do that?

Sorry, I went to bed for some time. Can you explain me what's wrong with my code. Why it is not working. I think no one explained me where I am doing wrong. Please let me know how can I draw attention of people after a few hours from posting my question. Again thanks a lot for all of you for giving me so much time.

Answer 1

If you really want to conserve memory then you should not copy any contents of the file, but instead mmap it into your process and only save the offsets into the longest lines in your code. On longer files this should give you significantly more performance since it outsources memory management to the kernel.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <fcntl.h>
#include <sys/stat.h>


int main(int argc, char ** argv) {
    char * filename = argv[1];
    if (!filename) {
        fprintf(stderr, "Usage: %s filename\n", argv[0]);
        exit(-1);
    }

    int fd = open(filename, O_RDONLY);
    if (fd < 0) {
        perror("open");
        abort();
    }

    struct stat file_stats;
    if(fstat(fd, &file_stats)) {
        perror("fstat");
        abort();
    }

    char * file_contents = mmap(NULL    // anywhere
        , file_stats.st_size + 1        // file length + 1 byte for null terminator
        , PROT_READ                     // we only need read only
        , MAP_PRIVATE                   // this doesn't really matter since we are read only
        , fd                            // from this file descriptor
        , 0);                           // from beginning

    if (file_contents == MAP_FAILED) {
        perror("mmap");
        abort();
    }

    // optional
    // Expect page references in sequential order.
    // Hence, pages can be aggressively read ahead, and may be freed soon after they are accessed.
    madvise(file_contents, file_stats.st_size + 1, MADV_SEQUENTIAL);

    struct {
        size_t start;
        size_t end;
    } longest_lines[10]; // struct to hold ofsets for longest lines

    memset(longest_lines, 0, sizeof(longest_lines)); // initialise
    int shortest_line_id = 0;

    char * start = file_contents;
    char * next;

    // while we are not at the end
    while (start < file_contents + file_stats.st_size) {
        if (!(next = strchr(start, '\n'))) // if line ternimator wasn't found, then go to the end
            next = file_contents + file_stats.st_size;

        size_t line_length = next - start;

        // if this line is longer then our shortest
        if (line_length > longest_lines[shortest_line_id].end - longest_lines[shortest_line_id].start) {
            longest_lines[shortest_line_id].start = start - file_contents;
            longest_lines[shortest_line_id].end = next - file_contents;

            // determine new shortest line
            int i;
            for (i = 0; i < sizeof(longest_lines)/sizeof(*longest_lines); i++) {
                if (
                longest_lines[i].end - longest_lines[i].start
                <
                longest_lines[shortest_line_id].end - longest_lines[shortest_line_id].start
                )
                    shortest_line_id = i;
            }
        }
        // next line starts at this offset
        start = next + 1;
    }

    int i; // print them
    for (i = 0; i < sizeof(longest_lines)/sizeof(*longest_lines); i++) {
        printf("%.*s\n", (int)(longest_lines[i].end - longest_lines[i].start), file_contents + longest_lines[i].start);
    }

    return 0;
}

Answer 2

Because it seems like some kind of homework or sth. I won't provide a full solution. But I will try to give you some peaces that you can start with.

You should divide your task by its responsibilities and try to create your programm a little more modular.

The several tasks seem to be:

1. Get the count of lines in your file
   • You can use a loop with fgets and a counter-variable to do this
2. Allocate a char*-Array (char**)
   • You can use malloc() with the counter-variable
3. Read all lines of your file into the allocated memory-sections and allocate memory for each line
   • You can use getline() to get a pointer to an allocated memory section
   • Really getline takes a lot work from you, but you can also combine the following functions to to the same:
     • fgets
     • malloc
     • realloc
     • strlen
4. Sort your char** by the length of your line
   • You can use strlen and some swap-function to archieve this (by simple apply sth. like bubblesort)
5. Output the first N lines of the sortet char** with printf
6. Don't forget to free all allocated memory with free()!

For Hints see the following post.

Note that the steps I provide do not optimize for memory or cpu-usage. But if your program works and you understoud what you've done this could be the next step.

Also this task shows the great benefits of modern programming languages where such a task would be a five line script. Here's the F# version that performs what you want to archieve:

open System
open System.IO
open System.Linq

[<EntryPoint>]
let main args =
  try
    let linesToPrint = Int32.Parse(args.ElementAt(0))
    let path         = @"C:\Users\XYZ\Desktop\test.txt"
    File.ReadAllLines(path).OrderByDescending(fun line -> line.Length).Take(linesToPrint).ToArray()
    |> Array.iter(printfn "%s")
  with
  | ex -> eprintfn "%s" ex.Message
  0

Note the sortness and the readability of the solution. Nevertheless it is worth to program such a task in c or maybe also in assembler to get a deeper understanding for how computers work.

Answer 3

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

int main(int argc, char *argv[]){
    int a, n=0, i;
    char **ar, str[1000];
    int *lens;

    FILE *f = fopen(argv[1],"r");

    if ( f == NULL || argc < 2){
        return 0;
    }

    fscanf(f,"%d",&a);
    if(NULL==(ar=calloc(a, sizeof(char*))) || NULL==(lens=calloc(a, sizeof(int)))){
        perror("malloc");
        return -1;
    }
    while (fscanf(f, " %999[^\n]", str)==1){
        ++n;
        int len = strlen(str);
        for(i = 0;i < a;++i){
            if(lens[i] < len){
                free(ar[a-1]);
                memmove(&lens[i+1], &lens[i], (a-i-1)*sizeof(int));
                memmove(&ar[i+1], &ar[i], (a-i-1)*sizeof(char*));
                ar[i]=strdup(str);
                lens[i]=len;
                break;
            }
        }
    }
    fclose(f);
    for (i = 0 ; i < n && i < a ; i++ ){
        puts(ar[i]);
        free(ar[i]);
    }
    free(ar);free(lens);

    return 0;
}

Answer 4

If you're happy sticking with your maximum line length of 1000 you can do:

char (*ar)[1000] = malloc(a * sizeof *ar);

if (!ar)
    // error handling....

and then use ar as you used it before.

There is a problem : fscanf(f,"%s",str). This reads a single word, and does no length checking. I guess you actually want to read a whole line, and not overflow your buffer:

fgets(str, sizeof str, f);

If you want to you can remove the newline from str after this but actually it will make no difference to your program.

There is currently a problem with your algorithm; you read every line into ar. Instead you should just make ar's size be a (I presume that a is meant to be N), take out the line strcpy(ar[i++],str);, and only insert the line if it is bigger than the current smallest member.