С++ для начинающих




Параметры и тип возврата


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

int sort( string*, string*,

          int (*)( const string &, const string & ) );

И в этом случае директива typedef помогает сделать объявление sort() более понятным:

// Использование директивы typedef делает

// объявление sort() более понятным

typedef int ( *PFI2S )( const string &, const string & );

int sort( string*, string*, PFI2S );

Поскольку в большинстве случаев употребляется функция lexicoCompare, можно использовать значение параметра по умолчанию:

// значение по умолчанию для третьего параметра

int lexicoCompare( const string &, const string & );

int sort( string*, string*, PFI2S = lexicoCompare );

Определение sort() выглядит следующим образом:

1 void sort( string *sl, string *s2,

2            PFI2S compare = lexicoCompare )

3 {

4     // условие окончания рекурсии

5     if ( si < s2 ) {

6         string elem = *s1;

7         string *1ow = s1;

8         string *high = s2 + 1;

9

10        for (;;) {

11            while ( compare ( *++1ow, elem ) < 0 && low < s2) ;

12            while ( compare( elem, *--high ) < 0 && high > s1)

14            if ( low < high )

15                1ow->swap(*high);

16            else break;

17        } // end, for(;;)

18

19        s1->swap(*high);

20        sort( s1, high - 1 );

21        sort( high +1, s2 );

22    } // end, if ( si < s2 )

23 }

sort() реализует алгоритм быстрой сортировки Хоара (C.A.R.Hoare). Рассмотрим ее определение детально. Она сортирует элементы массива от s1 до s2. Это рекурсивная функция, которая вызывает сама себя для последовательно уменьшающихся подмассивов. Рекурсия окончится тогда, когда s1 и s2 укажут на один и тот же элемент или s1 будет располагаться после s2 (строка 5).

elem (строка 6) является разделяющим элементом. Все элементы, меньшие чем elem, перемещаются влево от него, а большие– вправо. Теперь массив разбит на две части. sort() рекурсивно вызывается для каждой из них (строки 20-21).




Содержание  Назад  Вперед