книги / Практикум по программированию на языке Си
..pdf
(new!=0), то функция swap() меняет его значение со значением элемента с индексом 0. Затем выполняется рекурсивное обращение к функции arraySort(), в котором первый параметр перемещается на начало следующего элемента массива, а второй уменьшается на 1 (уменьшилось число анализируемых элементов массива).
Великолепным примером применения рекурсивных функций является реализация алгоритмов быстрой сортировки, предложенных в 1960 г. Чарльзом Хоаром (C.A.R.Hoare). Приведем описание этого алгоритма и реализующей его функции из книги Б.Кернигана и Р.Пайка "Практика программирования" [4] (с. 59–62).
При сортировке элементов массива по величине некоторого признака (например, по возрастанию значений) массив последовательно делится на большие некоторой величины (разделитель) и меньшие этой величины элементы. Рекурсивную процедуру такого деления можно представить следующими шагами:
выбрать один элемент массива ("разделитель"); разбить оставшиеся элементы на две группы:
"маленькие", т.е. меньшие, чем разделитель; "большие", т.е. не меньшие разделителя;
рекурсивно отсортировать обе группы.
Параметрами рекурсивной функции быстрой сортировки служит указатель на начало массива сортируемых элементов и их количество. В теле функции перед рекурсивным обращением к ней же изменяется значение указателя и количество сортируемых элементов. Следует отметить, что функция все время обрабатывает один и тот же массив (точнее, его части), поэтому указатель-параметр не фиксирован на начале массива, а перемещается по нему, адресуя каждый раз начало нужного участка (начало сортируемой последовательности элементов массива). Последовательность рекурсивных обращений к функции завершается, когда количество элементов очередного участка станет равно 1 или 0. (Сортировать в этом случае нечего.)
ЗАДАЧА 08-20. На основе приведенного описания алгоритма быстрой сортировки напишите рекурсивную функцию и основную программу, демонстрирующую применение функции.
311
Следующая программа с функциями swap() и quicksort(), скопированная из книги Р.Кернигана и Р.Пайка [4], реализует алгоритм быстрой сортировки целочисленного массива.
// 08_20.c - Рекурсивная функция быстрой сортировки
#include <stdio.h>
#include <stdlib.h> /* для функции rand() */ /* поменять местами значения v[i] и v[j] */ void swap(int v[], int i, int j)
{
int temp; temp = v[i]; v[i] = v[j]; v[j] = temp;
}
/* Сортирует массив-параметр по возрастанию */ void quicksort(int v[], int n)
{
int i, last; if (n <= 1) return;
swap(v, 0, rand() % n); last = 0;
for (i = 0; i < n; i++) if (v[i] < v[0])
swap(v, ++last, i); swap(v, 0, last); quicksort(v, last);
quicksort(v+last+1, n-last-1);
}
int main()
{
int i;
int integer[]={2,4,9,2,1,3,8,6,3,5};
int sizeArray=sizeof(integer)/sizeof(integer[0]); quicksort(integer, sizeArray);
printf("Sort Array:\n"); for (i=0; i<sizeArray; i++)
printf ("[%d]=%d%c",i,integer[i],(i+1)%5?'\t':'\n');
return 0;
}
312
Результаты выполнения программы:
Sort Array: |
[2]=2 |
[3]=3 |
[4]=3 |
|
[0]=1 |
[1]=2 |
|||
[5]=4 |
[6]=5 |
[7]=6 |
[8]=8 |
[9]=9 |
Глядя на последовательность значений, инициализирующих массив integer[], и на результаты его сортировки, можно убедиться, что упорядочение проведено правильно. Но полной ясности того, как работает рекурсивный алгоритм, можно добиться только при детальном изучении программы. Приведем некоторые пояснения. Основная программа передает в функцию quicksort() два параметра – указатель на начало массива (его имя integer) и количество элементов в нем (sizeArray). В теле функции проверяется количество элементов массива-параметра. Если n<=1, то исполнение завершено. Если n>1, то случайным образом с помощью библиотечной функции rand() в массиве выбирается "пороговый" элемент (разделитель). Его индекс определяется выражением rand()%n, т.е. индекс лежит в диапазоне от 0 до n-1. Обращение к функции swap(v,0,rand()%n) меняет местами значение элемента с нулевым индексом и выбранного порогового элемента. В последующем цикле все элементы массива сравниваются с начальным (с пороговым). Если очередной элемент меньше порогового, то он переставляется в начало массива (меняется с элементом с индексом ++last). После окончания цикла начальный элемент меняется с элементом last. Теперь слева от него оказываются элементы меньше порогового, а справа – элементы больше порогового или равные ему. Рекурсивное обращение к функции quicksort() упорядочивает отдельно "левую" и "правую" части массива.
ЗАДАНИЕ. Дополните рекурсивную функцию быстрой сортировки печатью обрабатываемого массива и порогового элемента. Проследите их изменение в процессе выполнения рекурсивных вызовов.
Заданию соответствует программа 08_20_1.с, в которой используется следующая функция сортировки:
/* Сортирует массив-параметр по возрастанию */ void quicksort(int v[], int n)
313
{
int i, last; int threshold;
printf("\nQuicksort() parameters:"); printf(" array size=%d, array:\n",n); for (i=0; i < n; i++)
printf("[%d]=%d\t",i,v[i]); if (n <= 1)
{ printf("Quicksort() end."); return;
}
threshold = rand() % n;
printf("\nthreshold index=%d, threshold=%d\n", threshold,v[threshold]);
swap(v, 0, threshold); last = 0;
for (i = 0; i < n; i++) if (v[i] < v[0])
swap(v, ++last, i); swap(v, 0, last);
for (i=0; i < n; i++) printf("[%d]=%d\t",i,v[i]);
printf("\nlast=%d, v[last]=%d", last,v[last]);
quicksort(v, last); quicksort(v+last+1, n-last-1);
}
Результаты выполнения программы для массива {3, 4, 9, 1, 2, 5}:
Quicksort() parameters: array size=6, array: [0]=3 [1]=4 [2]=9 [3]=1 [4]=2 [5]=5 threshold index=0, threshold=3
[0]=2 [1]=1 [2]=3 [3]=4 [4]=9 [5]=5 last=2, v[last]=3
Quicksort() parameters: array size=2, array: [0]=2 [1]=1
threshold index=1, threshold=1 [0]=1 [1]=2
last=0, v[last]=1
Quicksort() parameters: array size=0, array: Quicksort() end.
314
Quicksort() |
parameters: array size=1, array: |
[0]=2 Quicksort() end. |
|
Quicksort() |
parameters: array size=3, array: |
[0]=4 [1]=9 |
[2]=5 |
threshold index=1, threshold=9 |
|
[0]=5 [1]=4 |
[2]=9 |
last=2, v[last]=9 |
|
Quicksort() |
parameters: array size=2, array: |
[0]=5 [1]=4 |
|
threshold index=0, threshold=5 |
|
[0]=4 [1]=5 |
|
last=1, v[last]=5 |
|
Quicksort() |
parameters: array size=1, array: |
[0]=4 Quicksort() end. |
|
Quicksort() |
parameters: array size=0, array: |
Quicksort() |
end. |
Quicksort() |
parameters: array size=0, array: |
Quicksort() |
end. |
Sort Array: |
[2]=3 [3]=4 [4]=5 [5]=9 |
[0]=1 [1]=2 |
|
Используя результаты выполнения программы, изобразим последовательность преобразования сортируемого массива (рис. 8.2).
Рис. 8.2. Схема рекурсивной сортировки массива
315
На рисунке слева указаны уровни рекурсии ("глубина" вызовов функции quicksort()). Выделены (полужирным шрифтом с затемнением) пороговые элементы, относительно которых выполняется деление элементов массива на "большие" и "меньшие". Преобразование массива-параметра внутри функции quicksort() обозначено стрелкой. Обратите внимание, что пороговый элемент очередного уровня не участвует в обработке следующего уровня, т.е. сумма длин массивов следующего уровня меньше длины массива текущего уровня. Если после деления элементов массива слева и справа от порогового оказывается не более одного элемента, то "веточка" рекурсивных вызовов завершается.
8.5. Функции с переменным количеством аргументов
Очень интересные возможности имеют функции с переменным количеством аргументов, типы которых могут быть неизвестны до момента вызова функции.
В пособии [3] рассмотрены два подхода к проектированию таких функций. Один из них предусматривает последовательное перемещение по списку параметров с помощью явно определенного в теле функции указателя. Величина перемещения определяется типом очередного аргумента. Достоинство этого подхода в его очевидности, недостаток состоит в том, что он существенно зависит от реализации. Дело в том, что Стандарт языка Си не определяет порядок и правила размещения в памяти аргументов при обращении к функции. Только конкретный компилятор "знает" как нужно изменить значение указателя, чтобы он "нацелился" на следующий аргумент.
Универсальным и стандартным средством реализации программ с переменным количеством аргументов является набор препроцессорных средств, вводимых заголовочным файлом stdarg.h. В нем определен специальный тип va_list и три макроса:
void va_start(va_list ap, paramN); type va_arg(va_list ap, type); void va_end(va_list ap;
Макросы используются в теле функции для "перемещения" по заранее неизвестному списку аргументов. Для обращения к каждому
316
из макросов необходимо определить объект (ap – argument pointer) типа va_list. При обращении к va_start() параметр paramN нужно заменить последним (самым правым) из явно использованных в заголовке функции параметров. В макросе va_arg() type – условное обозначение типа очередного аргумента, к которому выполняется обращение из тела функции.
Итак, va_start() настраивает указатель ap (объект типа va_list) на начало списка аргументов неопределенной длины. "Зная" тип (type) очередного параметра, va_arg() возвращает его значение и перемещает указатель ap на следующий аргумент. Макрос va_end() "закрывает" перебор аргументов и обеспечивает корректное окончание выполнения функции с переменным количеством аргументов.
ЗАДАЧА 08-21. Напишите функцию, вычисляющую среднее арифметическое из значений вещественных аргументов. Количество обрабатываемых аргументов задайте с помощью первого параметра функции.
Обязателен только один первый целочисленный параметр. Следующие за ним параметры должны быть вещественными. Выберем для них тип double. Прототип функции может быть таким:
double average(int number,...);
Функция возвращает значение типа double. В прототипе указан только один обязательный (всегда реально используемый при обращениях) параметр number типа int. Следующие за ним в обращениях аргументы должны иметь тип double (по условиям задачи), но этого не видно из прототипа. Решение задачи:
/* 08_21.c - среднее арифметическое значений аргументов */
#include <stdio.h> #include <stdarg.h>
#define PRINTF(EXPRESSION) \ printf(#EXPRESSION"=%f\n",EXPRESSION)
double average(int number,...)
{
va_list point; double result=0.0;
317
int i; va_start(point,number); for (i=0; i<number; i++)
result += va_arg(point,double); va_end(point);
if(number>0)
return result/number; else
{ printf("\nArgument error!"); exit(0);
}
}
int main()
{
double x=156, y=24, z=92; PRINTF(average(3,x,y,z)); PRINTF(average(4,22.0,y,1.4,7.3)); PRINTF(average(4,6.0,8.0,10.0,12.0,14.0,16.0)); PRINTF(average(-5));
return 0;
}
Результаты выполнения программы:
average(3,x,y,z)=90.666667
average(4,22.0,y,1.4,7.3)=13.675000
average(4,6.0,8.0,10.0,12.0,14.0,16.0)=9.000000
Argument error!
В программу включен заголовочный файл stdarg.h, в котором введен тип va_list и определены макросы. В теле функции определен указатель point типа va_list. С помощью макроса va_start() указатель point "настроен" на следующий за реальным параметром number возможный аргумент. Зная тип этих возможных последующих аргументов, в цикле обращаемся к макросу va_arg(). Количество обращений определяет значение параметра number. При каждом обращении макрос va_arg() возвращает значение типа double и "настраивает" указатель point на следующий аргумент. Результаты (сумма значений аргументов) "накапливаются" в переменной result. По окончании цикла макрос va_end() завершает обработку списка аргументов. Затем полученная сумма делится на количество обрабо-
318
танных значений (number), и это значение возвращается как результат. При неверном задании параметра number выдается сообщение об ошибке, и вызовом функции exit() завершается выполнение программы.
В основной программе обращение к функции average() использовано четыре раза в качестве параметра макровызова PRINTF(). В первом обращении аргументами служат переменные типа double. Во втором обращении в качестве аргументов использованы константы типа double и одна переменная того же типа. В третьем обращении количество необязательных аргументов превышает значение первого параметра number. Обработаны только первые четыре из списка явно указанных необязательных аргументов. В последнем обращении задано отрицательное значение первого аргумента, результат – сообщение об ошибке.
Предложенная функция average() очень чувствительна к ошибкам в задании аргументов. Проверим это.
ЭКСПЕРИМЕНТ. Обратитесь к функции average(), используя в качестве необязательных аргументов целочисленные константы.
Например, обращение average(4,6,8,10,12,14,15) приве-
дет к получению нулевого результата (см. 08_21_1.с).
ЭКСПЕРИМЕНТ. Обратитесь к функции average(), используя в качестве первого параметра значение с типом, отличным от int.
В программе 08_21_1.с приведены сообщения об ошибках на этапе выполнения программы с таким обращением.
ЗАДАЧА 08-22. Напишите функцию, вычисляющую среднее геометрическое из значений вещественных аргументов. Окончание списка аргументов – нулевое значение очередного из них.
Задача похожа на предыдущую. Но все параметры могут быть одного типа (выберем тип double).
/* 08_22.c - среднее геометрическое значений аргументов */
#include <stdio.h>
319
#include <stdarg.h>
#include <math.h> /* Для функции pow().*/ #define PRINTF(EXPRESSION) \
printf(#EXPRESSION"=%f\n",EXPRESSION) double geoMean(double real,...)
{
va_list point; double product=1.0; double temp;
int counter=0; va_start(point,real); temp = real;
while (temp != 0.0)
{product *= temp;
temp = va_arg(point,double);
counter++;
}
va_end(point);
if(counter>0 && product > 0.0) return pow(product,1.0/counter); else
{printf("\nArgument error!"); exit(0);
}
}
int main()
{
PRINTF(geoMean(3.0,3.0,0.0));
PRINTF(geoMean(5.0,0.0));
PRINTF(geoMean(2.0,4.0,8.0,1.0,16.0,0.0));
PRINTF(geoMean(0.0)); return 0;
}
Результаты выполнения программы:
geoMean(3.0,3.0,0.0)=3.000000
geoMean(5.0,0.0)=5.000000
geoMean(2.0,4.0,8.0,1.0,16.0,0.0)=4.000000
Argument error!
320