Язык Си - руководство для начинающих - M. УЭИТ
Шрифт:
Интервал:
Закладка:
Проверьте вашу программу и посмотрите, работает ли она так, как должна. Самое простое - предположить, что limit равен 1 и пройти по программе шаг за шагом.
Сортировка данных
Рассмотрим еще раз функцию main( ):
main( )
{
int numbers[MAXSIZE]; /* массив для ввода */
int size; /* количество введенных элементов */
size = getarray(numbers, MAXSIZE); /* помещает ввод в массив */
sort(numbers, size); /* сортировка массива */
printf(numbers, size); /* печать отсортированного массива */
}
Мы видим, что функция sort() имеет на входе массив целых чисел, предназначенных для сортировки, и счетчик количества элементов, подлежащих сортировке. На выходе получается массив, содержащий отсортированные числа. Мы все еще не решили, как выполнять сортировку, поэтому мы должны дополнительно уточнить это описание.
Очевидно, в начале трудно определить направление сортировки. Собираемся ли мы вести сортировку от большего к меньшему, или наоборот? Мы свободны в выборе и допустим, что хотим сортировать от большего к меньшему. (Можно сделать программу, работающую любым из этих методов, но тогда нам нужно придумать способ сообщить ей о своем выборе.)
Рассмотрим теперь метод, который будем использовать для сортировки. В настоящее время разработано много алгоритмов сортировки; возьмем один из самых простых.
Вот наш план на псевдокоде:
от n = первому элементу до n = ближайшему - к- последнему элементу находим самое большое из оставшихся чисел и помещаем его в n-ю позицию.
Он выполняется примерно так. Сначала пусть n = 1. Мы просматриваем весь массив, находим самое большое число и помещаем его в первый элемент. Затем n = 2, и мы опять просматриваем весь массив, кроме первого элемента, находим самое большое из оставшихся чисел и помещаем его во второй элемент. Продолжаем этот процесс до тех пор, пока не достигнем ближайшего - к - последнему элементу. Теперь осталось только два элемента. Мы сравниваем эти числа и помещаем большее в элемент, ближайший - к - последнему. Оставшееся самое меньшее из всех чисел помещаем в последний элемент.
Это выглядит очень похоже на задачу с циклом 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(" %dn", 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( ), которую можно использовать в других программах. Если посмотреть с педагогической точки зрения, то мы проиллюстрировали несколько основных принципов и концепций, полезных при создании программ.
Следует обратить внимание на самый существенный момент:
программы нужно проектировать, а не создавать их методом проб и ошибок. Вы должны внимательно подумать о форме и содержании ввода и вывода для программы. Необходимо разделить программу на хорошо определенные задачи, затем раздельно запрограммировать, принимая во внимание взаимодействие их друг с другом. Идея заключается в достижении модульности. Если необходимо, разбивайте модули на еще более мелкие модули. Используйте функции для повышения степени модульности и простоты программы.
При проектировании программы, попытайтесь предвидеть, что может идти неправильно и программируйте, исходя из этого. Используйте локализацию ошибок, чтобы контролировать действия в местах потенциальных затруднений, или по крайней мере предупреждать пользователя, что может возникнуть осложнение. Гораздо лучше дать пользователю еще одну возможность ввести данные, чем продолжать выполнять программу и прийти к аварийной ситуации.
Если создается функция, сначала определите, как она будет взаимодействовать с вызывающей программой. Решите также, какая информация будет входить в нее, а какая выходить. Какими должны быть аргументы? Хотите ли вы использовать указатели, или возврат, или то и другое? Если вы примете во внимание все эти параметры, то можете обратить внимание на работу самой функции.
