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

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

     Возьмем реальную задачу сортировки строк в алфавитном порядке. Эта задача может возникнуть при подготовке списка фамилий, при создании алфавитного указателя и во многих других ситуациях. В такой программе одним из главных инструментов является функция 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( ).

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

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

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

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;};Мы могли бы написать функцию для сортировки сотрудников по


Сортировка

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

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


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

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

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


Сортировка

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

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


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

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

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


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

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

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


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

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

Пример 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. Старая, добрая: "Пузырьковая" сортировка

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

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


Сортировка

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

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


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

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

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