Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

Рис. 11.6. Сортировка указателей на страки

Символьные строки и строковые функции 465

Алгоритм сортировки выбором

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

Давайте более подробно рассмотрим сортировку выбором. Ниже показан ее набросок в псевдокоде:

для n = первый до n = предпоследний элемент

найти наибольшее из оставшихся чисел и поместить его в n-й элемент

Это работает следующим образом. Начините с n = 0. Просмотрите весь массив, найдите наибольшее число и поменяйте его и первый элемент местами. Далее установите n = 1 и просмотрите все элементы массива кроме первого. Найдите наибольший из оставшихся элементов и поменяйте его и второй элемент местами. Продолжайте этот процесс до тех пор, пока не достигнете предпоследнего элемента. Теперь остались только два элемента. Сравните их и поместите больший в позицию предпоследнего элемента. В итоге наименьший элемент занял свою окончательную позицию.

Выглядит так, что это задача для цикла for, но мы еще должны более подробно описать процесс “найти и поместить”. Один из способов выбора наибольшего значения из числа оставшихся предполагает сравнение первого и второго элементов в оставшейся части массива. Если второй элемент больше первого, выполните обмен их значениями. Далее сравните первый элемент с третьим. Если третий элемент больше, произведите обмен их значениями. Каждый обмен приводит к перемещению большего элемента ближе к началу списка. Продолжайте действовать в подобной манере до тех пор, пока не произойдет сравнение первого элемента с последним. После завершения наибольшее значение окажется в первом элементе оставшегося массива. Итак, вы отсортировали массив для первого элемента, однако остальные элементы находятся в беспорядке. Вот как можно представить процедуру с помощью псевдокода:

для n = предпредпоследний элемент

сравнить n-й элемент с первым элементом;

если n-й элемент больше, выполнить обмен их значениями

Этот процесс выглядит как еще один цикл for. Он должен быть вложен в первый цикл for. Внешний цикл указывает, какой элемент массива должен быть заполнен, а внутренний цикл находит значение, которое в него следует поместить. Объединив вместе обе части псевдокода и переведя его на С, мы получаем функцию, показанную в листинге 11.29. Кстати, в библиотеке С имеется более совершенная функция сортировки по имени qsort(). Помимо прочего она принимает указатель на функцию, выполняющую сравнение при сортировке. Ее работа будет продемонстрирована в главе 16.

Символьные функции ctype.h и строки

В главе 7 было представлено семейство функций обработки символов ctype.h. Эти функции не могут быть применены к строке как единому целому, но могут использоваться с отдельными символами в строке. В листинге 11.30 определена функ-

466 глава 11 ция, которая применяет toupper() к каждому символу строки, преобразуя символы всей строки в верхний регистр. В нем также определена функция, которая использует ispunct() для подсчета знаков препинания в строке. Наконец, здесь применяется функция strchr(), как было описано ранее, для обработки символа новой строки, если таковой присутствует, в строке, прочитанной с помощью fgets().

Листинг 11.30. Программа mod str.с

Цикл while (* str) обрабатывает каждый символ в строке, на которую указывает str, пока не будет достигнут нулевой символ. В этот момент *str становится равным 0 (код нулевого символа), или ложному значению, и цикл прекращается.

Символьные строки и строковые функции 467

Вот результаты пробного запуска:

Введите строку:

Спокойно, спокойно. За дело берусь я. Заседание продолжается.

СПОКОЙНО, СПОКОЙНО. ЗА ДЕЛО БЕРУСЬ Я. ЗАСЕДАНИЕ ПРОДОЛЖАЕТСЯ.

Эта строка содержит 4 знаков препинания.

Функция ToUpper() применяет toupper() к каждому символу строки. (Поскольку в С делается различие между символами верхнего и нижнего регистра, эти имена функций считаются разными.) Как определено в стандарте ANSI С, функция toupper() изменяет только символы, представленные в нижнем регистре. Тем не менее, в очень старых реализациях С эта проверка не выполнялась автоматически, так что в раннем коде обычно поступали следующим образом:

if (islower(*stг) ) /* до выхода стандарта ANSI С -

проверка перед преобразованием */

*str = toupper(*str);

Кстати, функции из ctype.h обычно реализованы как макросы. Они представляют собой конструкции препроцессора С, которые действуют подобно функциям, но имеют несколько важных отличий. Мы раскроем макросы в главе 16.

В этой программе используется сочетание функций fgets() и strchr() для чтения строки ввода и замены символа новой строки нулевым символом. Главное отличие между этим подходом и применением функции s_gets() заключается в том, что s_gets() отбрасывает оставшиеся символы строки ввода (если они есть), подготавливая программу к обработке следующего оператора ввода. В данном случае существует только один оператор ввода, поэтому такой дополнительный щаг не нужен.

Давайте восполним еще один пробел в наших знаниях и рассмотрим void внутри круглых скобок в функции main().

Аргументы командной строки

До появления современного графического интерфейса существовал интерфейс командной строки. Примерами могут служить DOS и Unix, к тому же терминал Linux предоставляет Unix-подобиую среду командной строки. Командная строка — это место, где вы вводите с клавиатуры информацию для запуска своей программы в среде командной строки. Предположим, что программа хранится в файле по имени fuss. Тогда командная строка для ее запуска в среде Unix может выглядеть так:

$ fuss

А вот ее вид для режима командной строки Windows:

С> fuss

Аргументы командной строки — это дополнительные элементы в той же самой строке, например:

$ fuss -r Ginger

Программа на С может считывать эти дополнительные элементы для собственных целей (рис. 11.7).