ПРИМЕР: СОРТИРОВКА СТРОК

ПРИМЕР: СОРТИРОВКА СТРОК

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

/* считывает строки и сортирует их */

#include <stdio.h>

#define SIZE 81 /* предельная длина строки, включая */

#define LIM 20 /* максимальное количество считываемых строк */

#define HALT   " " /* нулевая строка для прекращения ввода */

main( )

{

static char input[LIM][SIZE]; /* массив для запоминания вводимых строк */

char *ptstr[LIM];  /* массив переменных типа указатель */

int ct = 0; /* счетчик вводимых строк */

int k;  /* счетчик выводимых строк */

printf(" Введите до %d строк и я их отсортирую. " , LIM);

printf(" Для прекращения ввода нажмите клавишу [ввод] в начале строки. ");

while((gets(input[ct])!= NULL) && strcmp(input[ct], HALT)

                                != 0 && ct++ < LIM)

    ptstr[ct - 1] = input[ct - 1];  /*указывает на еще не

                                       отсортированный ввод */

stsrt(ptstr, ct); /* сортировка строк */

puts(" Вот отсортированный список строк: ");

for(k = 0; k < ct; k++)

puts(ptstr[k]); /* указатели на отсортированные строки */

}

/* функция сортировки-строк-с-использованиeм-указатeлeй */

stsrt(strings, num)

char *strings[  ];

int num;

{ char *temp;

int top, seek;

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

for(seek = top + 1; seek < num; seek++)

if(strcmp(strings[top], strings[seek]) > 0)

{ temp = strings [top];

strings [top] = strings [seek];

strings [seek] = temp;

} }

РИС. 13.4. Программа чтения и сортировки строк.

     Вывод строк на печать не составляет проблемы, а для сортировки можно взять тот же алгоритм, который использовался раньше для чисел. Сейчас мы применим один хитрый трюк: посмотрим, сможете ли вы его заметить.

Для проверки возьмем детский стишок.

Введите 20 строк, и я их отсортирую.

Для прекращения ввода нажмите клавишу [ввод] в начале строки.

Жил на свете человек

Скрюченные ножки

И гулял он целый век

По скрюченной дорожке

Вот отсортированный список строк

Жил на свете человек

И гулял он целый век

По скрюченной дорожке

Скрюченные ножки

Детские стишки не кажутся слишком искаженными после сортировки их по алфавиту.

     Трюк состоит в том что вместо перегруппировки самих строк мы перегруппировали их указатели. Разберемся в этом. В начале ptrst[0] ссылается на input[0] и т. д. Каждый input[ ] является массивом из 81 элемента, а каждый элемент ptrst[ ] является отдельной переменной. Процедура сортировки перегруппировывает ptrst, нe трогая input. Если, например, input[l] стоит перед input[0] по алфавиту, то программа переключает указатели ptrst, в результате чего ptrst[0] ссылается на input[1], a ptrst[1] на input[0]. Это гораздо легче, чем, используя strcpy( ), менять местами две введенные строки. Просмотрите еще раз этот процесс на рисунке.

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

Сортировка

Из книги Использование ListView в режиме виртуального списка автора Чадов Тимофей

Сортировка Трудности? Это еще что такое? Однако бесплатный сыр сами знаете где. Дело в том, что, так как сами элементы в списке не хранятся, придется самим заботится о сортировке. Не удастся воспользоваться функцией CListCtrl::SortItems, бесполезно писать CompareItems и т.п. Все, что у вас


Сортировка

Из книги Windows Vista автора Вавилов Сергей

Сортировка В отличие от предыдущих версий в Проводнике Windows Vista заголовки столбцов, с помощью которых можно проводить сортировку объектов и другие действия, доступны при любом способе отображения значков.Щелчком кнопки мыши на заголовке любого столбца вы можете


Сортировка

Из книги C++. Сборник рецептов автора Диггинс Кристофер

Сортировка При преобразовании документа элементами xsl:for-each и xsl:apply-templates, выбранные узлы по умолчанию обрабатываются в порядке просмотра документа, который зависит от выражения, использованного в атрибуте select этих элементов. XSLT позволяет изменять этот порядок


13.5. Сортировка локализованных строк

Из книги Язык программирования Си для персонального компьютера автора Бочков C. О.

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


Поиск и сортировка

Из книги Искусство программирования на языке сценариев командной оболочки автора Купер Мендель

Поиск и сортировка Следующие библиотечные функции предназначены для поиска и сортировки в массиве: Функция Краткое описание bsearch выполняет двоичный поиск lfind выполняет линейный поиск для заданного значения lsearch выполняет линейный поиск для заданного значения,


Пример 10-27. Простой пример сравнения строк

Из книги Linux программирование в примерах автора Роббинс Арнольд

Пример 10-27. Простой пример сравнения строк #!/bin/bash# match-string.sh: простое сравнение строкmatch_string (){ MATCH=0 NOMATCH=90 PARAMS=2 # Функция требует два входных аргумента. BAD_PARAMS=91 [ $# -eq $PARAMS ] || return $BAD_PARAMS case "$1" in "$2") return $MATCH;; * ) return $NOMATCH;; esac}a=oneb=twoc=threed=twomatch_string $a # неверное число


Пример 25-6. Старая, добрая: "Пузырьковая" сортировка

Из книги Мир InterBase. Архитектура, администрирование и разработка приложений баз данных в InterBase/FireBird/Yaffil автора Ковязин Алексей Николаевич

Пример 25-6. Старая, добрая: "Пузырьковая" сортировка #!/bin/bash# bubble.sh: "Пузырьковая" сортировка.# На каждом проходе по сортируемому массиву,#+ сравниваются два смежных элемента, и, если необходимо, они меняются местами.# В конце первого прохода, самый "тяжелый" элемент


6.2.1.1. Пример: сортировка сотрудников

Из книги автора

6.2.1.1. Пример: сортировка сотрудников Для более сложных структур требуются более сложные функции. Например, рассмотрите следующую (довольно тривиальную) struct employee:struct employee {char lastname[30];char firstname[30];long emp_id;time_t start_date;};Мы могли бы написать функцию для сортировки сотрудников по


11.1.10. Сортировка с отбрасыванием повторяющихся строк

Из книги автора

11.1.10. Сортировка с отбрасыванием повторяющихся строк Иногда приходится иметь дело с файлом, содержащим повторяющиеся строки. Чтобы избавиться от них, достаточно воспользоваться командой sort с опцией — и. Ниже показан вариант тестового файла, в котором запись о фильме "Alien"


Пример: передача текстовых строк между клиентом и сервером

Из книги автора

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