Subheader

Programming discussions since 1842

Saturday, August 6, 2011

Challenge: Read a file of unknown size

I'm not sure this can be considered a "real world programming problem" but it is a "fun" and important challenge for any would be programmer and a good measurement of whether you have a good grasp of memory management.

The task is as follows:
You have a text file containing an unknown number of rows of plain text. You are to parse this file and read each row into a string in a two-dimensional array (aka a string matrix). At your disposal you have a statically typed language, like C. Each row may be of varying length.

As for the restrictions, you may only traverse the file once. You may not count the number of rows manually. You may not use a linked-list with strings.

Are you up for it? Grab this textfile and go!

The solution is below the jump. But you solved it yourself, right?

void readFileIntoMatrix() {
    FILE *fil;
    fil = fopen("strtest.dat","rt");
    assert(fil != NULL);
  
    char input[10];   //array used to store single words
    char **strMatrix; //pointer to the string matrix
    char **testPtr;
    int count = 0;    //number of strings read
    int matrixSize = 1;

    strMatrix = (char*) malloc(matrixSize*sizeof(char*));
    while (!feof(fil)) {
        fscanf(fil,"%s",input);
        count++;
       
        //if the matrix is full, double the size
        if (count > matrixSize) {
            testPtr = (char*) realloc(strMatrix, 2*count*sizeof(char*));
            if (testPtr == NULL) {
                free(testPtr);
                printf("Memory allocation failed!");
                exit(-1);
            }
            strMatrix = testPtr;
            matrixSize = 2*count;
        }
      
        //allocate char-units to the latest row of the matris
        strMatrix[count-1] = malloc((strlen(input)+1)*sizeof(char));
      
        //copy the input string to the first empty row
        strcpy(strMatrix[count-1],input);
    }
  
    //Trim empty rows from the matrix
    testPtr = (char*) realloc(strMatrix, count*sizeof(char*));
    if (testPtr == NULL) {
        free(testPtr);
        printf("Memory allocation failed!");
        exit(-1);
    } else {
        strMatrix = testPtr;
    }
  
    int i;
    for (i=0; i<count; i++) { //print the matrix to verify correctness
        printf("%s ",strMatrix[i]);
        free(strMatrix[i]);
    }
    free(strMatrix);
    free(testPtr);
  
    fclose(fil);
}

No comments:

Post a Comment