Стивен Прата - Язык программирования 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

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

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

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