ПРИМЕРНИ ЛИНИИ ЗА СОРТИРАНЕ

М. ПОЧАКАЙ С. ПРАТА Д. МАРТИН

C език - ръководство за начинаещи

Книга: Езикът C - Ръководство за начинаещи

ПРИМЕР: СОРТИРАНЕ НА ЛИНИИ

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

/* чете редове и ги сортира */

#define SIZE 81 /* ограничение на дължината на реда, включително */

#define LIM 20 /* максимален брой редове за четене */

#define HALT " " /* нулев низ за спиране на въвеждането */

статичен символ вход [LIM][РАЗМЕР]; /* масив за съхраняване на входни низове */

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

int ct = 0; /* брояч на входни редове */

int k; /* брояч на изходни редове */

printf(" Въведете до %d реда и аз ще ги сортирам. n" , LIM);

printf(" За да спрете да пишете, натиснете клавиша [enter] в началото на реда.n");

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

низове[отгоре] = низове[търсене];

низове[търсене] = temp;

ОРИЗ. 13.4. Програма за четене и сортиране на низове.

Отпечатването на редове не е проблем, а за сортиране можете да вземете същотоалгоритъм, използван преди за числа. Сега ще приложим един хитър трик: вижте дали можете да го забележите.

Да вземем за проверка едно детско стихче.

Въведете 20 реда и аз ще ги сортирам.

За да спрете да пишете, натиснете клавиша [enter] в началото на реда.

Имало едно време един човек

И той вървеше цял век

По крив път

Тук е сортираният списък от низове

Имало едно време един човек

И той вървеше цял век

По крив път

Детските стихчета не изглеждат твърде объркани, след като ги сортирате по азбучен ред.

Номерът е, че вместо да пренаредим самите низове, ние пренаредихме указателите им. Нека да го разберем. В началото ptrst[0] се отнася до input[0] и т. н. Всеки input[ ] е масив от 81 елемента, а всеки елемент от ptrst[ ] е отделна променлива. Рутината за сортиране пренарежда ptrst, без да докосва входа. Ако, например, input[l] идва преди input[0] по азбучен ред, тогава програмата превключва ptrst указателите, така че ptrst[0] да се отнася към input[1] и ptrst[1] към input[0]. Това е много по-лесно от използването на strcpy() за размяна на два входни реда. Вижте този процес отново на фигурата.

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