3
\$\begingroup\$

Yesterday, I asked this question because I was asked to implement a software that used variably sized matrices with C89's limitation, so I had to practise dynamic pointer-to-pointer allocation. After the useful answers I got, I started working on a solution to a problem that I was assigned as an exercise.

Here's the assignment specification:

Implement a C program that does the following:

  1. Get from stdinput the size of two matrices of integers, and fill them with user-given data
  2. Find which one is the smaller matrix. This is going to be called A and the bigger matrix is B. Find if every integer in A is also present in B. If A occurs n times in A, it has to occur at least n times in B.
  3. If this condition isn't met, print "NO" and abort the execution of the program.
  4. If this condition is met, scan the smaller array, and for each column check if it satisfies this condition: There is a row after which, all the numbers of following rows and the given column are less than 0
  5. Print all the columns that satisfy this question, but in reverse order vertically (e.g. you print the last number of the first column that satisfies the condition, then the second-to-last, ... up to the first, then you move onto the second column that satisfies the condition and begin all over again).

I'll provide you with the code of my implementation and example inputs and outputs. My question to you is: according to the standards for good code, implementation, algorithms, optimization, and so on, is this a good program? How can I improve it and become a better programmer?

Any advice is welcome, and thank you for your time!

Code:

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

struct num {
    int val;
    int occurrences;
    struct num *nextPtr;
};

typedef struct num Num;

void getArrSize(int *rows, int *cols) {
    while(scanf("%d%d", rows, cols) != 2 || *rows < 1 || *cols < 1) {
        puts("Incorrect input.");
    }
}

int **allocateArr(int rows, int cols) {
    if(!rows) {
        return NULL;
    }
    int **arr = malloc(sizeof *arr *rows); // allocate 'rows' pointers to int pointers
    assert(arr != NULL);

    for(size_t i = 0; i < rows; i++) { // for each row, allocate 'cols' pointers to int
        arr[i] = malloc(sizeof *arr[i] * cols);
        assert(arr[i] != NULL);
    }

    return arr;
}

void deallocateList(Num **hPtr) {
    Num *currPtr = *hPtr;
    while(currPtr != NULL) {
        Num *tempPtr = currPtr;
        currPtr = currPtr->nextPtr;
        free(tempPtr);
    }
}

void deallocateArr(int **arr, int rows) {
    for(size_t i = 0; i < rows; i++) {
        free(arr[i]);
    }
    free(arr);
}

void insertOccurrence(Num **lPtr, int v) {
    Num *currPtr = *lPtr;
    if(currPtr == NULL) { // insert at head of the list
        Num *newPtr = malloc(sizeof(Num));
        assert(newPtr != NULL);
        newPtr->val = v;
        newPtr->occurrences = 1;
        newPtr->nextPtr = NULL;

        *lPtr = newPtr;
        return;
    }

    Num *prevPtr = NULL;
    while(currPtr != NULL && v > currPtr->val) { // keep scrolling through the list as long as the given value is less than or equal to the current node's value
        prevPtr = currPtr;
        currPtr = currPtr->nextPtr;
    }

    if(currPtr != NULL && v == currPtr->val) { // the value is already present in the list
        currPtr->occurrences = currPtr->occurrences + 1;
        return;
    }

    // value not found; create a new node   
    Num *newPtr = malloc(sizeof(Num));
    assert(newPtr != NULL);
    newPtr->val = v;
    newPtr->occurrences = 1;
    if(prevPtr == NULL) { // insert at head of the list
        newPtr->nextPtr = currPtr;
        *lPtr = newPtr;
        return;
    }
    newPtr->nextPtr = currPtr;

    prevPtr->nextPtr = newPtr;

}

void fillArr(int **arr, int rows, int cols, Num **occList) {
    for(size_t i = 0; i < rows; i++) {
        for(size_t j = 0; j < cols; j++) {
            scanf("%d", &arr[i][j]); // insert the given number into its spot in the array
            insertOccurrence(occList, arr[i][j]); // insert the occurrence of this number in the sorted occurrences list
        }
    }
}

int isSubset(Num *occA, Num *occB) {
    Num *currA = occA, *currB = occB;

    if(occA == NULL) { // is A is empty, A is a subset of B
        return 1;
    }
    if(occB == NULL) { // is B is empty and A isn't, A is not a subset of B
        return 0;
    }

    int keepGoing = 1;
    int found = 0;

    while(currA != NULL && keepGoing) { // scroll through every element of A
        while(currB != NULL && !found && currA->val >= currB->val) { // for every element of A, keep scrolling B until you find the element and it has enough occurrences, or until you find an element in B that's bigger than it, or until you get to the end of B
            if(currB->val == currA->val && currB->occurrences >= currA->occurrences) {
                found = 1;
            } else {
                currB = currB->nextPtr;
            }
        }
        if(found) { // if you found correspondence, reset array B's pointer and repeat the search for next A's element
            currB = occB;
            currA = currA->nextPtr;
            found = 0;
        } else { // if you didn't find correspondence, interrupt the search
            keepGoing = 0;
        }
    }

    return keepGoing;
}

int *checkCondition(int **arr, int rows, int cols, int *nOfGoodIdxs) {
    int goodIdxsTemp[cols];
    int gIdx = 0;

    for(size_t i = 0; i < cols; i++) {
        if(arr[rows-1][i] < 0) {
            goodIdxsTemp[gIdx++] = i; // copy the current column's index to the temporary array if the column satisfies the condition
        }
    }

    int *goodIdxs = malloc(gIdx * sizeof(int)); // create a new array, this time without memory waste as it is only as large as the number of good indexes we have determined previously
    assert(goodIdxs != NULL);
    memcpy(goodIdxs, goodIdxsTemp, gIdx*sizeof(int)); // copy the content to the new array

    *nOfGoodIdxs = gIdx;
    return goodIdxs;
}

void printGoodIndexes(int **arr, int rows, int goodIdxs[], int nOfGoodIdxs) {
    for(int i = rows-1; i >=0; i--) { // must use int here, due to size_t unsigned underflow
        for(size_t j = 0; j < nOfGoodIdxs; j++) {
            printf("%d", arr[i][goodIdxs[j]]);
            if(j < nOfGoodIdxs-1) {
                printf(";");
            }
        }
        printf("\n");
    }
}

int main() {
    int rows1, cols1, rows2, cols2;
    Num *occ1 = NULL, *occ2 = NULL;
    int **arr1, **arr2;

    printf("Array 1 dimensions: ");
    // get size of, allocate, and fill array 1
    getArrSize(&rows1, &cols1);
    arr1 = allocateArr(rows1, cols1);
    printf("Enter %d rows of %d numbers: ", rows1, cols1);
    fillArr(arr1, rows1, cols1, &occ1);

    printf("Array 2 dimensions: ");
    // get size of, allocate, and fill array 2
    getArrSize(&rows2, &cols2);
    arr2 = allocateArr(rows2, cols2);
    printf("Enter %d rows of %d numbers: ", rows2, cols2);
    fillArr(arr2, rows2, cols2, &occ2);

    int nOfGoodIdxs; // passed onto the condition-verifying function to determine how many indexes satisfy the condition

    // compare array 1's size with array 2's
    if(rows1 * cols1 > rows2 * cols2) {
        if(isSubset(occ2, occ1)) { // array 2 is the smaller one (aka A)
            int *goodIdxs = checkCondition(arr2, rows2, cols2, &nOfGoodIdxs); // check for columns that satisfy the condition in the smaller array
            printGoodIndexes(arr2, rows2, goodIdxs, nOfGoodIdxs); // print the columns the abide by the condition, in reverse vertical order
        } else {
            puts("NO");
        }
    } else {
        if(isSubset(occ1, occ2)) { // array 1 is the smaller one (aka A)
            int *goodIdxs = checkCondition(arr1, rows1, cols1, &nOfGoodIdxs); // check for columns that satisfy the condition in the smaller array
            printGoodIndexes(arr1, rows1, goodIdxs, nOfGoodIdxs); // print the columns the satisfy the condition, in reverse vertical order
        } else {
            puts("NO");
        }
    }

    deallocateList(&occ1);
    deallocateList(&occ2);
    deallocateArr(arr1, rows1);
    deallocateArr(arr2, rows2);

    return 0;
}

Example inputs/outputs:

test case 1

input:
2 2
1 1
1 1
3 4
1 1 3 4
1 2 3 4
1 2 3 4

output:


test case 2

input:
2 3
1 2 2
4 -5 -6
4 5
0 -3 2 1 -12
3 4 5 -5 -1
2 -6 2 9 0
11 22 33 44 55

output:
-5;-6
2;2

test case 3

2 2
1 1
1 1
3 4
1 2 3 4
1 2 3 4
1 2 3 4

output: 
NO

test case 4

input:
4 4
-1 -1 -1 -1
-2 -2 -2 -2
-3 -3 -3 -3
-4 -4 -4 -4
2 2
-1 -1
-2 -2

output:
-2;-2
-1;-1
\$\endgroup\$
  • 2
    \$\begingroup\$ I would change sizeof *arr *rows into sizeof(*arr) * rows just for readability. Change error handling from assert to something "more". And handle return value of that one scanf. \$\endgroup\$ – KamilCuk Jan 20 at 18:45
  • \$\begingroup\$ Thank you for the advice! However, I'm not sure what you mean by handling the return value of scanf? \$\endgroup\$ – Samuele B. Jan 20 at 19:03
  • 1
    \$\begingroup\$ scanf("%d", &arr[i][j]); // insert the -> int err = scanf("%d", &arr[i][j]); if (err != 1) return -1. I just noticed that ` int fillArr` has no return statement, which is UB \$\endgroup\$ – KamilCuk Jan 20 at 19:36
  • \$\begingroup\$ Correct. I meant it to be a void function but then for some reason I mistyped it's type. \$\endgroup\$ – Samuele B. Jan 20 at 19:43
  • 1
    \$\begingroup\$ "so I had to practise dynamic pointer-to-pointer allocation." Is that a specific requirement of the assignment or are you allowed to model the matrices using a struct? \$\endgroup\$ – Bob__ Jan 21 at 14:14
3
\$\begingroup\$

Here, we print an error message to the standard output stream:

    puts("Incorrect input.");

I'd expect to use standard error here:

fputs("Incorrect input.\n", stderr);

(Note that puts() appends a newline, but we have to provide our own for fputs().)


Don't use assert() for run-time checks. assert() compiles to nothing in non-debug builds, so we risk undefined behaviour here:

int **arr = malloc(sizeof *arr *rows);
assert(arr != NULL);

We need a real test here, as malloc() can return a null pointer:

int **arr = malloc(sizeof *arr *rows);
if (!arr) { return arr; }

The correct handling for the allocations within the loop is more complex. However, there are advantages to allocating a single array of width * height elements: not only does it simplify the memory handling, but it also improves locality of reference as it's accessed, improving code efficiency.


I'm surprised to see the return value of scanf() ignored in fillArr(), given the exemplary code in getArrSize(). What happened here?

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ re: stderr - You're right. I forgot to specify that we were asked to print everything to the standard output, because some of our programs are corrected automatically by our university's online platform, and they only check what's on the stdout. -- re: assert() - Thank you for the input. I thought that exiting the program when a malloc pointer is NULL was appropriate handling in the context of my program (which can't really work if any of the pointers are NULL). \$\endgroup\$ – Samuele B. Jan 21 at 17:53
  • \$\begingroup\$ re: handling scanf() return value in fillArr() - Your observation is good. For the purpose of this exercise we were told not to do any input checking, and we could assume every input was legal. However, before posting the program here, I decided to add a check for good practice, but apparently I forgot to do it in the other function! \$\endgroup\$ – Samuele B. Jan 21 at 17:54
2
\$\begingroup\$

Before getting into what can be improved, the good points are that there are no global variables and there are many small functions that perform small operations which makes the code easier to read, write, maintain and debug.

Prefer calloc Over malloc for Arrays

There are 3 major allocation function in the C programming language, they are void *malloc(size_t size_to_allocate), void* calloc( size_t number_of_items, size_t item_size ) and void *realloc( void *ptr, size_t new_size ). The best for initially allocating arrays is calloc because it clearly shows that you are allocating an array, and because it zeros out the memory that is being allocated.

Checking for Memory Allocation Errors

When you call malloc(), calloc() or realloc() you should always check to see if memory was actually allocated before using the mempory. If any of these functions fail to allocate memory then it returns NULL. Reference through a null pointer results in unknown behavior, which is usually a bug. The code already checks for memory allocation errors, however, it is using assert(goodIdxs != NULL); to implement the check. The problem with using assert is that it may be optimized away when the code is compiled for production using the compiler flag -O3 and the NODEBUG flag. To catch a memory allocation error in production it is better to use if statements.

    int *goodIdxs = malloc(gIdx * sizeof(int));
    if (goodIdxs == NULL)
    {
        fprintf(stderr, "Memory allocation failed for goodIdxs\n");
        exit(EXIT_FAILURE);
    }

DRY Code

There is a programming principle called the Don't Repeat Yourself Principle sometimes referred to as DRY code. If you find yourself repeating the same code mutiple times it is better to encapsulate it in a function. If it is possible to loop through the code that can reduce repetition as well. There is code in the function void insertOccurrence(Num **lPtr, int v) that repeats, specifically the code to create an num struct. It would be better to have a function that creates a num structure and fills it. There is also code in main() that is duplicated

    printf("Array 1 dimensions: ");
    // get size of, allocate, and fill array 1
    getArrSize(&rows1, &cols1);
    arr1 = allocateArr(rows1, cols1);
    printf("Enter %d rows of %d numbers: ", rows1, cols1);
    fillArr(arr1, rows1, cols1, &occ1);

This could be turned into a function called int **getMatrix() that returns a filled matrix. Among other things this would reduce the number of variables needed in main().

Readability and Possible Bug Reduction

The variables in main should be initialized when they are declared, this reduces possible future bugs in the code (using uninitialized variables). To make the code more readable it would be better if each variable was declared and initialized on it's own line:

int main() {
    int rows1 = 0;
    int cols1 = 0;
    int rows2 = 0;
    int cols2 = 0;
    Num *occ1 = NULL;
    Num *occ2 = NULL;
    int **arr1 = NULL;
    int **arr2 = NULL;

Complexity

The functions main() and insertOccurrence() are too complex (each function does too much within the function). A third function that is on the borderline of too complex is the function int isSubset(Num *occA, Num *occB). As mentioned above in DRY Code insertOccurrence() can be simplified by creating a function who's sole purpose is to allocate a num struct and fill it with the proper values. The while loop in the function isSubset() could probably be broken out into 2 functions.

As programs grow in size the use of main() should be limited to calling functions that parse the command line, calling functions that set up for processing, calling functions that execute the desired function of the program, and calling functions to clean up after the main portion of the program. As noted in the DRY Code section the complexity of main can be reduced by adding a function that creates matrices.

There is also a programming principle called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

int *checkCondition(int **arr, int rows, int cols, int *nOfGoodIdxs)

Many C compilers would have flagged the following as a syntax error because C arrays can't be created using a variable as the size. The code will have to allocate the goodIdxsTemp array instead.

int *checkCondition(int **arr, int rows, int cols, int *nOfGoodIdxs) {
    int goodIdxsTemp[cols];

It would be better if the code was:

int *safe_calloc(size_t count, size_t size, char *estring)
{
    int *allocatedArray = calloc(count, size);
    if (allocatedArray == NULL)
    {
        fprintf(stderr, "%s\n", estring);
        exit(EXIT_FAILURE);
    }

    return allocatedArray;
}

int *checkCondition(int **arr, int rows, int cols, int *nOfGoodIdxs) {
    char *estring = "In checkCondition memory allocation failed for goodIdxsTemp";
    int *goodIdxsTemp = safe_calloc(cols, sizeof(*goodIdxsTemp), estring);

    int gIdx = 0;

    for(size_t i = 0; i < cols; i++) {
        if(arr[rows-1][i] < 0) {
            goodIdxsTemp[gIdx++] = i;
        }
    }

    estring = "In checkCondition memory allocation failed for goodIdxs";
    int *goodIdxs = safe_calloc(gIdx, sizeof(*goodIdxs), estring);
    memcpy(goodIdxs, goodIdxsTemp, gIdx*sizeof(int)); // copy the content to the new array

    *nOfGoodIdxs = gIdx;
    return goodIdxs;
}

Algorithm

Another way to simplify the program would be to separate the linked list into 2 separate structure types, one to implement the linked list, and a second to implement the num structure.

typedef struct num {
    int val;
    int occurrences;
} Num;

typedef struct num_node {
    Num data;
    struct num_node *nextPtr;
} Num_Node;

This would allow for standard linked list operations such as:

  • create_node()
  • delete_node()
  • insert_node()
  • add_node()
  • a traverse list function

Other functions could then just process the num structure.

Please note that a separate typedef statement is not needed for the structures.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.