Форум

Данная тема создана мною на основе вопроса a function that works with arrays, заданного на сайте Stackoverflow.

Требуется написать рекурсивную функцию на языке C, которая находит максимальный элемент массива.

Функция в числе параметров должна принимать два указателя. Один указатель указывает на первый элемент массива, а второй указатель указывает на память, сразу следующую за последним элементом массива.

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

В противном случае функция вызывает сама себя два раза. В первом вызова функции ей передается исходный указатель на начало массива (диапазона) и указатель на середину массива. Во втором вызове функции ей передается указатель на середину массива (диапазона) и указатель на память, сразу следующую за последним элементом массива (диапазона). То есть массив (диапазон) делится пополам на две части, и для каждой части снова вызывается функция. Затем значения элементов массива, указываемые возвращаемыми указателями вызовов функции сравниваются между собой, и в итоге возвращается пользователю указатель, указывающий на максимальный элемент массива.

Для начала попробуем написать эту функцию на C++, чтобы затем в сравнении было бы проще выявить те соглашения, которым должна следовать аналогичная функция на C.

Чтобы функция могла быть использована с любыми контейнерами, которые имеют итераторы произвольного доступа (Хотя на самом деле реализация функции, которая будет показана ниже может работать и с последовательными итераторами, но она будет менее эффективна, так как нахождение середины массива имеет сложность O( n ). А также так как аналогичная C функция будет иметь дело с указателями, то речь идет об итераторах произвольного доступа), а не только с массивами, функцию следует сделать шаблонной, принимающей в качестве параметров два итератора,задающих исходный диапазон элементов следующим образом [first, last ).

Как уже было отмечено выше, функции следует возвращать итератор, указывающий на максимальный элемент, а не само значение максимального элемента, так как в общем случае переданный функции диапазон в виде двух итераторов может быть пустым. В этом случае нельзя разыменовывать возвращаемый итератор.

Ниже в демонстрационной программе приведена реализация требуемой функции на C++.

 
 #include <iostream> 
 #include <iterator> 
  
 template <typename ForwardIterator, typename Comparator> 
 ForwardIterator max_element( ForwardIterator first,  
                              ForwardIterator last, 
                              Comparator cmp ) 
 { 
     if ( first == last || std::next( first ) == last ) 
     { 
         return first;             
     } 
     else 
     { 
         auto middle = std::next( first, std::distance( first, last ) / 2 ); 
          
         auto left  = max_element( first,  middle, cmp ); 
         auto right = max_element( middle, last,   cmp ); 
          
         return cmp( *left, *right ) ? right : left; 
     } 
 } 
  
 bool cmp_double( const double &a, const double &b ) 
 { 
 	return a < b; 
 } 
  
 int main()  
 { 
     double a[] = { 4.3, 15.1, 2.2, -3.4, 18.1, 1.1, 3.0 }; 
      
     for ( double d : a ) std::cout << d << ' '; 
     std::cout << '\n'; 
  
     auto max = max_element( std::begin( a ), std::end( a ), cmp_double ); 
  
     std::cout << "Maximum element is " << *max 
               << " at position " << max - a << '\n'; 
 	           
     return 0; 
 }

Вывод программы на консоль

 
 4.3 15.1 2.2 -3.4 18.1 1.1 3  
 Maximum element is 18.1 at position 4

Теперь, имея реализацию функции на C++, можно написать соответствующую функцию на C.
Во-первых, желательно, чтобы соответствующая функция на C, могла работать с любыми типами массивов, как это делают стандартные C функции bsearch и qsort.

Следовательно, функция должна принимать два указателя типа const void *, а также требуется передать размер элемента массива и указатель на функцию сравнения элементов, которая будет задавать общий алгоритм сравнения элементов произвольных массивов.

Ниже показана, как может быть реализована соответствующая рекурсивная функция на C, которая сможет работать с массивами произвольного типа.

 
 #include <stdio.h> 
  
 void * max_element( const void *first, const void *last, size_t size, 
                     int cmp( const void *, const void * ) ) 
 { 
     if ( first == last || ( const char * )first + size == last ) 
     { 
         return ( void * )first;             
     } 
     else 
     { 
         size_t n = ( ( const char * )last - ( const char * )first ) / size / 2; 
         void *left  = max_element( first, ( const char * )first + n * size, size, cmp ); 
         void *right = max_element( ( const char * )first + n * size, last, size, cmp ); 
          
         return cmp( left, right )  < 0 ? right : left; 
     } 
 } 
  
 int cmp_double( const void *p, const void *q ) 
 { 
     double left  = *( const double * )p; 
     double right = *( const double * )q; 
      
     return ( right < left ) - ( left < right ); 
 }     
  
 int main(void)  
 { 
     double a[] = { 4.3, 15.1, 2.2, -3.4, 18.1, 1.1, 3.0 }; 
 	const size_t N = sizeof( a ) / sizeof( *a ); 
      
     for ( size_t i = 0; i < N; i++ ) printf( "%.1f ", a[ i ] ); 
     putchar( '\n' ); 
  
     double *max = max_element( a, a + N, sizeof( *a ), cmp_double ); 
      
     printf( "Maximum element is %.1f at position %zu\n",  
             *max, ( size_t )( max - a ) ); 
  
     return 0; 
 }

Вывод программы на консоль:

 
 4.3 15.1 2.2 -3.4 18.1 1.1 3.0  
 Maximum element is 18.1 at position 4

В исходном вопросе на Stackoverflow и в представленном там лучшем ответе приводится частная реализация функции для массивов типа double[].

Если потребуется. например, выполнить поставленную задачу для массивов типа int[], то придется дублировать код и писать новую функцию с новым названием так как в C нет перегрузки функций.

К тому же параметры функции следует объявить с квалификатором const, то есть они должны иметь тип const void *.

Более того функция в выбранном лучшим ответе имеет неопределенное поведение, когда заданный диапазон элементов, переданный через указатели, может быть пустым, то есть когда два указателя равны друг другу.

Кстати сказать, похожий вопрос был также ранее задан на Stackoverflow, на который там же я предоставил свой ответ. Смотрите вопрос Calculating the maximum number of an array by divide and conquer algorithm