как найти максимум и минимум в массиве, используя структуры и рекурсии в C

Question

У меня есть следующие функции, которые находят максимум и минимум в матрице, как я могу добавить структуру с min и max, чтобы иметь возможность выполнять только функцию, которая находит минимум и максимум?

int maximum(int array[], int index, int len) 
{
    int max;

    if(index >= len-2)
    {
        if(array[index] > array[index + 1])
            return array[index];
        else
            return array[index + 1];
    }




    max = maximum(array, index + 1, len);

    if(array[index] > max)
        return array[index];
    else
        return max;
}

int minimum(int array[], int index, int len)
{
    int min;

    if(index >= len-2)
    {
        if(array[index] < array[index + 1])
            return array[index];
        else
            return array[index + 1];
    }

    min = minimum(array, index + 1, len);

    if(array[index] < min)
        return array[index];
    else
        return min;
}

Answer 1

Как отмечается в комментариях Danny-ds , если вам действительно нужно сделать это с помощью рекурсии (для дидактических целей), по крайней мере используйте технику «разделяй и властвуй», чтобы ограничить потребление стека до O (ln (n)).

Далее я создам функцию, которая принимает диапазон, определенный как указатель first на первый элемент массива (или подмассив) и указатель last наза последним последний элемент того же массива (или подмассива).Обратите внимание, что эти два указателя можно безопасно сравнить, но last не следует разыменовывать.

Эта функция возвращает структуру, которая объединяет два указателя на значения min и max.Если переданный массив пуст (когда first == last, с этим соглашением), эти указатели установлены в last, и это условие должно быть проверено перед использованием структуры.

#include <stdio.h>

typedef struct {
    int *min;
    int *max;
} min_max_t;

min_max_t min_max_element(int *first, int *last)
{
    // First check if the range is at least two elements wide, to stop the recursion.
    if ( first == last  ||  first + 1 == last )
        return (min_max_t){first, first};

    // Then apply the algorithm to two sub-range
    int *middle = first + (last - first)/2;
    min_max_t left = min_max_element(first, middle);
    min_max_t right = min_max_element(middle, last);

    // No need to compare 'right.min' with 'left.max' or 'right.max' with 'left.min'
    if ( *(right.min) < *(left.min) )
        left.min = right.min;

    if ( *(right.max) > *(left.max) )
        left.max = right.max;

    return left;
}

// Helper function to print the result. The only part which is really necessary is
// the check before accessing the resulting struct.
void print_min_max(size_t n, int *arr)
{ 
    int *arr_end = arr + n;
    min_max_t result = min_max_element(arr, arr_end);
    if (result.min != arr_end)
        printf("Min: %d\tMax: %d\n", *(result.min), *(result.max));
    else
        puts("Error: invalid array.");
}

int main(void)
{
    int a1[] = { 1, 2, 3, 4, -5 };
    print_min_max(5, a1);               // -> Min: -5   Max: 4

    int a2[] = { 4, 2, 1, 4, -2, 0 };    
    print_min_max(6, a2);               // -> Min: -2   Max: 4

    int *a3 = NULL;    
    print_min_max(0, a3);               // -> Error: invalid array.

    int a4[] = { 1 };    
    print_min_max(1, a4);               // -> Min: 1    Max: 1

    int a5[] = { 2, 2, 2, 2 };    
    print_min_max(4, a5);               // -> Min: 2    Max: 2
}

Answer 2

#include <assert.h>
#include <stddef.h>
#include <stdio.h>

typedef struct minmax_tag {
    int min;
    int max;
} minmax_t;

minmax_t get_minmax(int const *data, size_t length)
{
    assert(length);

    minmax_t minmax = { data[0], data[0] };

    for (size_t i = 1; i < length; ++i) {
        if (data[i] < minmax.min)
            minmax.min = data[i];
        if (data[i] > minmax.max)
            minmax.max = data[i];
    }

    return minmax;
}

int main(void)
{
    int foo[] = { 12, 484, 487, 1, 500 };
    minmax_t result = get_minmax(foo, sizeof(foo) / sizeof(*foo));
    printf("Min: %d\tMax: %d\n\n", result.min, result.max);
}

Sowwy, рекурсивный:

#include <assert.h>
#include <stddef.h>
#include <stdio.h>

typedef struct minmax_tag {
    int min;
    int max;
} minmax_t;

minmax_t get_minmax_impl(int const *data, size_t pos, size_t length, minmax_t previous)
{
    if (pos == length)
        return previous;

    if (data[pos] < previous.min)
        previous.min = data[pos];
    if (data[pos] > previous.max)
        previous.max = data[pos];

    return get_minmax_impl(data, pos + 1, length, previous);
}

minmax_t get_minmax(int const *data, size_t length)
{
    assert(length);

    minmax_t previous = { data[0], data[0] };
    return get_minmax_impl(data, 1, length, previous);
}

int main(void)
{
    int foo[] = { 12, 484, 487, 1, 500 };
    minmax_t result = get_minmax(foo, sizeof(foo) / sizeof(*foo));
    printf("Min: %d\tMax: %d\n\n", result.min, result.max);
}