M. УЭИТ - Язык Си - руководство для начинающих

Это выглядит очень похоже на задачу с циклом for, но мы все же должны описать процесс "найти и поместить" более детально. Как сделать так, чтобы мы находили каждый раз самое большое из оставшихся чисел? Вот один способ. Сравните первый и второй элементы оставшегося массива. Если второй больше, поменяйте их местами. Теперь сравните первый элемент с третьим. Если третий больше, поменяйте местами эти два. Каждый раз больший элемент перемещается вверх. Продолжаем таким образом, пока не сравним первый элемент с последним. Если мы дошли до конца, самое большое число теперь будет в первом элементе оставшегося массива. По существу мы имеем отсортированный массив для первого элемента, но остаток массива находится в беспорядке. На псевдокоде это можно выразить так:

для n = от второго до последнего элемента сравниваем n-й элемент с первым; если n-й больше, меняем их местами.

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

/* сортировка массива целых чисел в порядке убывания */

sortarray(array, limit)

int array[ ], limit;

{

int top, search;

for(top = 0; top < limit - 1; top++)

for(search = top + 1; search < limit; search++)

if(array [search] > array[top]

interchange(&array[search], &array[top] );

}

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

Мы использовали top в качестве индекса для элемента массива, который следует заполнить, так как он является вершиной не отсортированной части массива. Индекс searchперемещает по массиву в порядке убывания текущий элемент. Большинство текстов использует обозначения i и j для этих индексов, однако это осложняет ситуацию, если нужно посмотреть, что происходит.

Этот алгоритм иногда называют "пузырьковой сортировкой", так как самое большое значение медленно поднимется вверх. Именно теперь мы должны написать функцию рrint( ).

Эта программа достаточно проста:

/* печать массива */

print(array, limit)

int array[ ], limit;

{

int index;

for(index = 0; index <= limit; index ++)

printf(" %d\n", array[index]);

}

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

Давайте скомпилируем и протестируем нашу программу сортировки. Чтобы упростить проверку граничных условий, временно изменим MAXSIZE на 5.

В нашем первом тесте будем снабжать программу числами до тех пор, пока она не откажется их принимать.

Эта программа прекращает считывание чисел после 5 значений, или если встретился символ EOF.

12 34 54 23 67

Все 5 элементов массива заполнены.

67

54

34

23

12

Программа считала 5 чисел и отсортировала их. Теперь посмотрим, как будет выглядеть результат, если она остановится, встретив символ EOF.

Эта программа прекращает считывание чисел после 5 значений, или если встретился символ EOF.

456 928

-23 +16

Клавиша [control -z] (передает EOF в нашу систему)

928

456

16

-23

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

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

Этим завершаются наши примеры в данной главе. Давайте теперь вернемся немного назад и сделаем обзор главы.

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

Следует обратить внимание на самый существенный момент:

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

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

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

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