Linux программирование в примерах, Роббинс Арнольд

Linux программирование в примерах

на обложку

Роббинс Арнольд

Шрифт:

82 qsort(presidents, npres, sizeof(struct employee), emp_name_id_compare);

84 /* Вывести результат */

85 printf("Sorted by name:\n");

86 for (i = 0; i < npres; i++)

87 printf("\t%s %s\t%d\t%s",

88 presidents[i].lastname,

89 presidents[i].firstname,

90 presidents[i].emp_id,

91 ctime(&presidents[i].start_date));

93 /* Теперь сортировка по старшинству */

94 qsort(presidents, npres, sizeof(struct employee), emp_seniority_compare);

96 /* И снова вывести */

97 printf("Sorted by seniority:\n");

98 for (i = 0; i < npres; i++)

99 printf("\t%s %s\t%d\t%s",

100 presidents[i].lastname,

101 presidents!i].firstname,

102 presidents[i].emp_id,

103 ctime(&presidents[i].start_date));

104 }

Строки 70–77 считывают данные. Обратите внимание, что любое использование

scanf

требует от входных данных «хорошего поведения». Если, например, какое-нибудь имя содержит более 29 символов, возникает проблема. В данном случае, мы вне опасности, но в коде изделия нужно быть гораздо более осмотрительным.

Строка 82 сортирует данные по имени и по ID сотрудника, а затем строки 84–91 выводят отсортированные данные. Сходным образом строка 94 пересортировывает данные, на этот раз по старшинству, а строки 97–103 выводят результаты. После компилирования и запуска программа выдает следующие результаты:

$ ch06-sortemp < presdata.txt

Sorted by name:

Bush George 41 Fri Jan 20 13:00:00 1989

Bush George 43 Sat Jan 20 13:00:00 2001

Carter James 39 Thu Jan 20 13:00:00 1977

Clinton William 42 Wed Jan 20 13:00:00 1993

Reagan Ronald 40 Tue Jan 20 13:00:00 1981 \

Sorted by seniority:

Carter James 39 Thu Jan 20 13:00:00 1977

Reagan Ronald 40 Tue Jan 20 13:00:00 1981

Bush George 41 Fri Jan 20 13:00:00 1989

Clinton William 42 Wed Jan 20 13:00:00 1993

Bush George 43 Sat Jan 20 13:00:00 2001

(Мы использовали 1 час пополудни как приблизительное время, когда все президенты начали работать.) [66]

Стоит заметить одну вещь:

qsort

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

qsort

для сортировки массива указателей, получая доступ к несортированным данным через сортированные указатели.

Вывод, показанный здесь, относится к US Eastern Standard Time. Вы получите различные результаты для одних и тех же программ и данных, если используете другой часовой пояс — Примеч. автора.

Платой за это является дополнительная память для размещения указателей и модификация функций сравнения для дополнительного перенаправления указателей при сравнении структур. Полученной выгодой может стать значительное ускорение работы, поскольку на каждом шаге перемещается лишь четырех- или восьмибайтный указатель вместо большой структуры. (Наша

struct employee

имеет размер по крайней мере 68 байтов. При обмене четырехбайтных указателей перемещается в 17 раз меньше данных, чем при обмене структур.) Для тысяч размещенных в памяти структур разница мажет быть существенной.

ЗАМЕЧАНИЕ. Если вы являетесь программистом С++, знайте!

qsort

может быть опасной для использования с массивами объектов!

qsort

осуществляет простые перемещения памяти, копируя байты. Она совершенно ничего не знает о конструкциях С++, таких, как конструкторы копирования или функции

operator=

. Вместо этого используйте одну из функций сортировки STL [67] или используйте методику отдельного массива указателей.

STL (Standard Template Library, стандартная библиотека шаблонов). — Примеч. науч. ред.

6.2.1.2. Пример: сортировка содержимого каталога

В разделе 5.3 «Чтение каталогов» мы продемонстрировали, как элементы каталогов возвращаются в физическом порядке каталога. В большинстве случаев гораздо полезнее иметь содержимое каталога отсортированным каким-нибудь образом, например, по имени или по времени изменения. Хотя и не стандартизованные POSIX, несколько процедур упрощают это, используя

qsort

в качестве лежащего в основе сортирующего агента:

#include <dirent.h> /* Обычный */

int scandir(const char *dir, struct dirent ***namelist,

int (*select)(const struct dirent*),

int (*compare)(const struct dirent **, const struct dirent **));

int alphasort(const void *a, const void *b);

int versionsort(const void *a, const void *b); /* GLIBC */

Функции

scandir

alphasort

были сделаны доступными в 4.2 BSD и широко поддерживаются [68] ,

versionsort

является расширением GNU.

Заметным исключением является лишь Sun Solaris, где эти две функции существуют лишь в трудной для использования библиотеке совместимости с BSD — Примеч. автора.