Язык Си - Уэйт, Прата, Мартин. M. уэит с. Прата д. Мартин
 Скачать 4.69 Mb.
|
|
СОРТИРОВКА ЧИСЕЛ Далее Содержание Одним из наиболее распространенных тестов для машин является сортировка. Мы хотим 213 разработать программу для сортировки целых чисел. Снова применим принцип черного ящика и подумаем в терминах ввода и вывода. Наш общий замысел, показанный на рис. 10.4, довольно прост. РИС. 10.4. Программа сортировки, рассматриваемая как черный яшик На данном этапе программа еще недостаточно определена, чтобы ее кодировать. Следующий шаг заключается в определении главных задач, которые должна выполнить программа для достижения поставленных целей. Их три: 1. Считывание чисел. 2. Сортировка чисел. 3. Печать отсортированных чисел. На рис. 10.5 показано это разделение при движении от верхнего уровня конструкции вниз к более детальному. РИС. 10.5 Программа сортировки: содержание Теперь мы имеем три черных ящика, каждый со своим входом и выходом. Можно передать каждую часть разным группам программистов, если мы уверены в том, что числа, выводимые блоком "считывание", представлены в той же самой форме, которую использует блок "сортировка" для ввода. Как вы можете видеть, делается упор на модульность. Мы разделили исходную задачу на три более мелких, но лучше управляемых. Что дальше? Теперь приложим наши усилия к каждому из трех модулей в отдельности, разделяя их на более простые элементы до тех пор, пока не достигнем момента, когда программа станет очевидной. Делая это, обратим внимание на такие важные проблемы, как выбор представления данных, локализация ошибок и передача информации. Вернемся к нашему примеру и займемся сначала задачей считывания. Считывание числовых данных Далее Содержание Многие программы включают считывание чисел, поэтому идеи, которые мы развиваем здесь, будут полезны везде. Общий вид первой части программы ясен: использовать цикл для считывания чисел до тех пор, пока все числа не будут считаны. Но в этом есть нечто большее, чем вы можете себе представить! 214 Выбор представления данных Далее Содержание Как мы представляем группу чисел? Можно использовать группу переменных, по одной на каждое число. Об этом даже страшно подумать. Можно использовать массив, по одному элементу на каждое число. Это значительно лучше, поэтому давайте использовать массив. Однако какого типа будет массив? Типа int? Типа double? Нам нужно знать, как такую программу можно будет применять. Предположим, что она должна работать с целыми числами. (А что если она должна применять и целые и нецелые числа? Это возможно, но потребуется работы больше, чем нам бы хотелось сейчас.) Будем использовать массив целых чисел для запоминания чисел, которые мы считываем. Завершение ввода Далее Содержание Как программа "узнает", сколько ей нужно считать чисел? В гл. 8 мы обсудили несколько решений этой проблемы, большинство из которых были неудовлетворительны. Однако теперь, когда есть функция getint( ), у нас нет проблем. Вот один подход: читаем число до тех пор пока не встретится символ EOF заносим число в массив и читаем следующее число, если массив не заполнен Заметим, что здесь есть два разных условия, приводящих к завершению этой части программы: символ EOF и заполнение массива. Дальнейшие рассуждения Далее Содержание Прежде чем реализовать все это на языке Си, нам нужно еще решить, что будем делать с проверкой ошибок ? Должны ли мы превратить эту часть программы в функцию? Сначала мы решим, что делать, если пользователь вводит ошибочные данные, скажем букву вместо целого числа? Без функци getint( ) мы полагались бы на "гипотезу идеального пользователя", согласно которой пользователь не делает ошибок при вводе. Однако мы считаем, что эту гипотезу нельзя применять ник одному пользователю, кроме себя. К счастью, можно использовать способность функции getint() сообщать о состоянии, кто поможет нам выйти из затруднительного положения. Теперь займемся программированием, которое можно легко реализовать в main( ). Для соблюдения модульности следует использовать разные функции для каждой из трех основных частей программы, что мы как раз и сделаем. Входом для этой функции будут числа с клавиатуры или файл, а выходом - массив, содержащий неотсортированные числа. Было бы хорошо, если бы такая функция помогла основной программе узнать, сколько было считано чисел, поэтому предусмотрим это для выхода. Вконце концов нужно подумать и о пользователе. Мы заставим фикцию печатать сообщение, указывающее ее пределы, и, осуществлять эхо-печать входной информации. 215 main( ) и getarray( ) Далее Содержание Вызовем нашу функцию getarray( ), предназначенную для считывания. Мы определили эту функцию в терминах ввода и вывода и наметили в общих чертах схему на псевдокоде. Теперь давайте напишем функцию и покажем, как она включается в основную программу: Сначала напишем main( ): /* сортировка 1 */ #define MAXSIZE 100 /* предельное количество сортируемых целых чисел */ main( ) { int numbers [MAXSIZE]; /* массив для ввода */ int size; /* количество вводимых чисел */ size = getarray(numbers, MAXSIZE); /* запись чисел в массив */ sort(numbers, size); /* сортировка массива */ print(numbers,/size); /* печать отсортированного массива */ } Это общий вид программы. Функция getarray() размещает введенное числа в массиве numbers и выдает сообщение о том, сколько значений было считано; эта величина записывается в size. Затем идя функции sоrt( ) и print( ), которые мы еще должны написать; они сортируют массив и печатают результаты. Включая в них size, мы облегчаем им работу и избавляем от необходимости выполнять самим подсчет. Мы также снабдили getarray( ) переменной MAXSIZE, которая сообщает размер массива, необходимого для запоминания. Теперь, когда мы добавили size к передаваемой информации, нужно модифицировать рисунок нашего черного ящика. См. рис. 10.6. РИС. 10.6. Программ: сортировки, дополнительные детали. Теперь рассмотрим функцию getarray( ): /* getarray( ), использующая getint( ) */ #define STOP -1 /* признак EOF */ #define NONUM 1 /* признак нецифровой строки */ #define YESNUM 0 /* признак строки цифр */ getarray(array, limit); int array[ ], limit; { int num, status; int index = 0; /* индекс массива */ printf(" Эта программа прекращает считывание чисел после %d значений. \n", limit); printf(" или если введен символ EOF.\n"); while(index < limit && (status = getint(&num)) != STOP) { /* прекращает считывание после достижения limit или EOF */ if(status == YESNUM) { array[index++] = num; printf(" число %d принято.\n", num); } else if(status == NONUM) printf(" Это было не целое число! Попытайтесь снова. \n"); 216 else printf(" Этого не может быть! Что-то неправильно. \n"); if(index == limit) /* сообщить, если массив заполнен */ printf(" Все %d элементов массива заполнены. \n ", limit); return(index); } Это значительная часть программы, и у нас есть немало замечаний. Разъяснения Далее Содержание Так как немного трудно вспомнить значение, скажем кода -1, мы используем мнемонические символические константы для представления кодов состояния. Применяя эти коды, мы создаем getarray( ) для управления каждым из возможных значений состояния. Состояние STOP вызывает прекращение цикла чтения, если getint( ) находит на своем "пути" EOF. Состояние YESNUM говорит о запоминании числа в предлагаемом массиве. Кроме того, отсылается "эхо-число" пользователю, чтобы он знал, что оно принято. Состояние NONUM предписывает пользователю попытаться выполнить задачу еще раз. (Это признак "дружелюбия"). У нас есть еще оператор else. Единственный путь достижения этого оператора возможен, если getint( ) возвращает значение, отличное от -1, 0 или 1. Однако это единственные значения, которые могут быть возвращены, поэтому else является, по-видимому бесполезным оператором. Почему он включен в программу? Мы вставили его как пример "защитного программирования", как способ защиты программы от будущей ошибки. Когда-нибудь мы (или кто-нибудь еще), может быть, решим обратиться к функции getint( ) и добавить в ее репертуар немного больше возможных значений состояния. Наиболее вероятно, что мы забудем (а они могут никогда не узнать), что getarray( ) предполагает только три возможных ответа. Поэтому мы включаем это последнее else, чтобы "поймать" любые новые ответы, которые появятся, и значительно упростить будущую отладку. Размер массива устанавливается в main(). Поэтому мы не задаем его, когда описываем аргумент-массив в getarray(). Мы ставим только квадратные скобки в оператор, чтобы указать, что аргумент является массивом. int numbers [MAXSIZE]; /* размер задается в main */ int array[ ] /* нет определения размера в вызвавшей функции */ Использование массивов в функциях обсудим в гл. 12. Мы решили применить ключевое слово return для возврата числа прочитанных элементов. Таким образом, вызов нашей функции: size = getarray(numbers); присваивает значение переменной size и дает значения массиву numbers. Вы можете спросить, почему мы не использовали указатели в вызове size = getаrray (numbers); ведь у нас функция изменяет значение чего-то (массива) в вызывающей программе? Ошибаетесь - мы использовали указатель! В языке Си имя массива является также указателем на первый элемент массива, т. е. numbers == &numbers[0] Когда функция getarray() создает массив array, то адрес элемента аrrау[0] совпадает с адресом элемента numbers[0] и т. д. для всех других индексов. Поэтому все манипуляции, которые 217 выполняет qetarray( ) с аrrау[ ], фактически выполняются с numbers[ ]. Мы будем более подробно говорить о связи между указателями и массивами в гл. 12. Теперь же нам нужно усвоить, что функция воздействует на массив в вызывающей программе, если мы используем массив в качестве аргумента функции. В функциях, содержащих счетчики и пределы, таких как getarray( ), наиболее вероятным местом появления ошибок являются "граничные условия", где значения счетчиков достигают своих пределов. Мы собираемся прочитать максимальное количество чисел, указанное в MAXSIZE, или же мы намерены ограничиться одним? Хотим обратить внимание на детали, такие, как ++index или index++ и < или <=. Мы также должны помнить, что у массивов индексы начинаются с 0, а не с 1. Проверьте вашу программу и посмотрите, работает ли она так, как должна. Самое простое - предположить, что limit равен 1 и пройти по программе шаг за шагом. Обычно наиболее трудной частью программы является обеспечение ее взаимодействия с пользователем удобным и надежным способом. Это относится и к нашей программе. Теперь, когда мы справились с getarray( ), находим, что функция sort( ) должна быть проще и print( ) - тоже. Теперь перейдем к функции sort( ). Сортировка данных Далее Содержание Рассмотрим еще раз функцию main( ): main( ) { int numbers[MAXSIZE]; /* массив для ввода */ int size; /* количество введенных элементов */ size = getarray(numbers, MAXSIZE); /* помещает ввод в массив */ sort(numbers, size); /* сортировка массива */ printf(numbers, size); /* печать отсортированного массива */ } Мы видим, что функция sort() имеет на входе массив целых чисел, предназначенных для сортировки, и счетчик количества элементов, подлежащих сортировке. На выходе получается массив, содержащий отсортированные числа. Мы все еще не решили, как выполнять сортировку, поэтому мы должны дополнительно уточнить это описание. Очевидно, в начале трудно определить направление сортировки. Собираемся ли мы вести сортировку от большего к меньшему, или наоборот? Мы свободны в выборе и допустим, что хотим сортировать от большего к меньшему. (Можно сделать программу, работающую любым из этих методов, но тогда нам нужно придумать способ сообщить ей о своем выборе.) Рассмотрим теперь метод, который будем использовать для сортировки. В настоящее время разработано много алгоритмов сортировки; возьмем один из самых простых. Вот наш план на псевдокоде: от n = первому элементу до n = ближайшему - к- последнему элементу находим самое большое из оставшихся чисел и помещаем его в n-ю позицию. 218 Он выполняется примерно так. Сначала пусть 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( ). Печать данных Далее Содержание 219 Эта программа достаточно проста: /* печать массива */ 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 Быстрее чем вы сможете сказать "экология это наука о домашнем хозяйстве", целый огромный массив отсортирован. 220 Успех! Это было не просто, но не невозможно. Разделив задачу на небольшие части и продумав, какой информацией должна обмениваться каждая из них, мы свели задачу к частям, поддающимся управлению. Кроме того, отдельные модули, которые мы создали, можно использовать как части подобных программ. Этим завершаются наши примеры в данной главе. Давайте теперь вернемся немного назад и сделаем обзор главы. ОБЗОР Далее Содержание Чего же мы достигли? Если посмотреть с практической стороны, то мы разработали генератор случайных чисел и программу сортировки целых чисел. При этом создали функцию getint( ), которую можно использовать в других программах. Если посмотреть с педагогической точки зрения, то мы проиллюстрировали несколько основных принципов и концепций, полезных при создании программ. Следует обратить внимание на самый существенный момент: программы нужно проектировать, а не создавать их методом проб и ошибок. Вы должны внимательно подумать о форме и содержании ввода и вывода для программы. Необходимо разделить программу на хорошо определенные задачи, затем раздельно запрограммировать, принимая во внимание взаимодействие их друг с другом. Идея заключается в достижении модульности. Если необходимо, разбивайте модули на еще более мелкие модули. Используйте функции для повышения степени модульности и простоты программы. При проектировании программы, попытайтесь предвидеть, что может идти неправильно и программируйте, исходя из этого. Используйте локализацию ошибок, чтобы контролировать действия в местах потенциальных затруднений, или по крайней мере предупреждать пользователя, что может возникнуть осложнение. Гораздо лучше дать пользователю еще одну возможность ввести данные, чем продолжать выполнять программу и прийти к аварийной ситуации. Если создается функция, сначала определите, как она будет взаимодействовать с вызывающей программой. Решите также, какая информация будет входить в нее, а какая выходить. Какими должны быть аргументы? Хотите ли вы использовать указатели, или возврат, или то и другое? Если вы примете во внимание все эти параметры, то можете обратить внимание на работу самой функции. 221 Используйте эти идеи, и ваша программа будет более надежной и менее подверженной аварийным ситуациям. Вы получаете тело функции, которое можете применять в других программах. Программирование в таком случае потребует меньше времени. Вообще все это похоже на хороший рецепт здорового программирования. Не забывайте о классах памяти. Переменные можно определять вне функции; в этом случае их называют внешними (или глобальными) и они доступны более чем для одной функции. Переменные, определенные внутри функции, являются локальными для нее и не известны другим функциям. Если можно, используйте автоматическую разновидность локальных переменных. Они охраняют переменные одной функции от воздействия других функций. |