C - 2D peak finder in

Question

This is an implementation of a 2D peak finder from MIT's Intro to Algos.

I'm a C beginner and I would really like some feedback on coding style, documentation and any other general C bad practices. Additionally have I correctly freed the memory of the recursive calls?

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

typedef struct max_vector {
    unsigned int col_index;
    unsigned int row_index;
    int index_value;
} max_vector;


max_vector * find_col_peak(int *arr, int rows, int col){
    /* Find the peak of a column.
    
    This function treats a 2D array like a 1D array and
    traverses using some basic pointer arithmetic.

    next item = *((i * row + arr) + j)
    where:
        - i == current row number (the y axis in matrix i.e. up and down)
        - j == column number in column space (the x axis i.e left to right)
        - row == the number of items in each row
        - *arr == the first item in the array
    */

    // we want a vector to save the max number and its index
    max_vector *vector = malloc(sizeof(max_vector));
    
    if (vector) {
        // set max to the first item of the column
        vector->col_index = 0;
        vector->index_value = *(col + arr);
    
        // loop through the rest of the column
        for (int i=1; i < rows; i++){
            int next_number = *((i * rows + arr) + col);
            if (next_number > vector->index_value){
                vector->col_index = i;
                vector->index_value = next_number;
            }
        }
        printf("the max value is %d and it is at index %d\n",
            vector->index_value, vector->col_index);
        return vector;
    }
    return NULL;
}


max_vector * peak_finder(int *matrix, int rows, int first, int last){
    /* Find a local 2D peak.

    NOTE: Expects a matrix of size row x col

    A peak is defined as:
    (i, j) >= (i, j + 1), (i, j - 1), (i + 1, j) (i - 1, j)
    */

    max_vector *vector;
    
    int middle = last / 2;
    vector = find_col_peak(matrix, rows, middle);

    if (vector){
        if (middle == first || middle == last){
            vector->row_index = middle;
            return vector;
        }

        if (last > first) {
            int current = *((vector->col_index * rows) + matrix + middle);
            int one_less = *((vector->col_index * rows) + matrix + middle - 1);
            int one_more = *((vector->col_index * rows) + matrix + middle + 1);

            if (one_less <= current >= one_more) {
                vector->row_index = middle;
                return vector;
            }

            // if current is not a peak we can free the vector
            if (one_less > current){
                free(vector);
                return peak_finder(matrix, rows, first, middle - 1);
            } else {
                free(vector);
                return peak_finder(matrix, rows, middle + 1, last);
            } 
        }
        vector->row_index = middle;
        return vector;
    }
    return NULL;
}


int main(void) {
  int arr [5][5] = {
    {10, 8, 11, 10, 16},
    {14, 13, 12, 11, 24},
    {15, 9, 11, 21, 6},
    {16, 21, 19, 20, 12},
    {100, 6, 13, 19, 9},
  };

  max_vector *ptr = peak_finder(*arr, 5, 0, 5);
  printf("the local peak is at %d, %d", ptr->row_index, ptr->col_index);
  free(ptr);
  return 0;
}

G. Sliepen · Accepted Answer · 2020-06-24 15:46:20Z

Use standard array notation

When you are accessing array elements, the idiomatic way in C is to write foo[bar] instead of *(foo + bar). So instead of:

int next_number = *((i * rows + arr) + col);

Write:

int next_number = arr[i * rows + col];

It is both shorted, and now it is clear what part the array pointer is and what part the index is.

Avoid unnecessary memory allocations

It's perfectly possible in C to return a struct by value. This avoids having to call malloc() and free(), and you no longer have to worry about its memory leaking, nor have to check whether malloc() succeeded. You do it like so:

max_vector find_col_peak(int *arr, int rows, int col) {
    max_vector vector;

    // set max to the first item of the column
    vector.col_index = 0;
    vector.index_value = *(col + arr);

    ...

    return vector;
}

About recursion

With the above you don't have to worry about freeing memory for vector anymore. However, recursive calls themselves could have some memory overhead, since each call needs some amount of space on the stack. With this algorithm, you only need log2(cols) recursion levels, so that won't be an issue even for huge inputs. Also, the compiler can turn these recursive calls into tail calls.

Stack Exchange Network

C - 2D peak finder in

1 Answer 1

Use standard array notation

Avoid unnecessary memory allocations

About recursion

You must log in to answer this question.

Hot Network Questions

C - 2D peak finder in

1 Answer 1

Use standard array notation

Avoid unnecessary memory allocations

About recursion

You must log in to answer this question.

Related

Hot Network Questions