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

60  /* main --- демонстрация сортировки */

61

62  int main(void)

63  {

64   #define NPRES 10

65   struct employee presidents[NPRES];

66   int i, npres;

67   char buf[BUFSIZ];

68

69   /* Очень простой код для чтения данных: */

70   for (npres = 0; npres < NPRES && fgets(buf, BUFSIZ, stdin) != NULL;

71    npres++) {

72    sscanf(buf, "%s %s %ld %ldn",

73     presidents[npres].lastname,

74     presidents[npres].firstname,

75     &presidents[npres].emp_id,

76     &presidents[npres].start_date);

77   }

78

79   /* npres теперь содержит число прочитанных строк. */

80

81   /* Сначала сортировка по имени */

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

83

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

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

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

87    printf("t%s %st%dt%s",

88     presidents[i].lastname,

89     presidents[i].firstname,

90     presidents[i].emp_id,

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

92

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

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

95

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

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

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

99    printf("t%s %st%dt%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() для сортировки массива указателей, получая доступ к несортированным данным через сортированные указатели.

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

ЗАМЕЧАНИЕ. Если вы являетесь программистом С++, знайте! qsort() может быть опасной для использования с массивами объектов! qsort() осуществляет простые перемещения памяти, копируя байты. Она совершенно ничего не знает о конструкциях С++, таких, как конструкторы копирования или функции operator=(). Вместо этого используйте одну из функций сортировки STL[67] или используйте методику отдельного массива указателей.

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.

scandir() читает каталог, имя которого дано в dir, создает с использованием malloc() массив указателей struct dirent и устанавливает *namelist, чтобы он указывал на начало этого массива. Как массив указателей, так и указываемые структуры struct dirent выделяются с помощью malloc(); вызывающий код должен использовать free(), чтобы избежать утечек памяти.

Для выбора нужных элементов используйте указатель функции select. Когда это значение равно NULL, все действительные элементы каталога включаются в конечный массив. В противном случае (*select)() вызывается для каждого элемента, и те элементы, для которых она возвращает ненулевое (истинное) значение, включаются в массив.

Указатель функции compare сравнивает два элемента каталога. Он передается функции qsort() для использования при сортировке.

alphasort() лексикографически сравнивает имена файлов. Она использует для сравнения функцию strcoll(). strcoll() похожа на strcmp(), но учитывает связанные с местной спецификой правила сортировки (см. раздел 13.4 «Не могли бы вы написать это для меня по буквам?»).

versionsort() является расширением GNU, которое использует для сравнения имен файлов функцию GNU strverscmp() (см. strverscmp(3).) Короче говоря, эта функция понимает обычные соглашения по версиям имен файлов и сравнивает их соответствующим образом.

В ch06-sortdir.c приведена программа, похожая на ch04-catdir.c. Однако, она использует для работы scandir() и alphasort().

1  /* ch06-sortdir.c --- Демонстрирует scandir(), alphasort(). */

2

3  #include <stdio.h> /* для printf() etc. */

4  #include <errno.h> /* для errno */

5  #include <sys/types.h> /* для системных типов */

6  #include <dirent.h> /* для функций каталогов */

7

8  char *myname;

9  int process(const char *dir);

10

11 /* main --- перечислить аргументы каталога */

12

13 int main(int argc, char **argv)

14 {

15  int i;

16  int errs = 0;

17

18  myname = argv[0];

19

20  if (argc == 1)

21   errs = process("."); /* по умолчанию текущий каталог */

22  else

23   for (i = 1; i < argc; i++)

24    errs += process(argv[i]);

25

26  return (errs != 0);

27 }

28

29 /* nodots --- игнорирует файлы с точкой, для scandir() */

30

31 int

32 nodots(const struct dirent *dp)

33 {

34  return (dp->d_name[0] != '.');

35 }

36

37 /*

38  * process --- сделать что-то с каталогом, в данном случае,

39  * вывести в стандартный вывод пары индекс/имя.

40  * Вернуть 0, если все нормально, в противном случае 1.

41  */

42

43 int

44 process(const char *dir)

45 {

46  DIR *dp;

47  struct dirent **entries;

48  int nents, i;

49

50  nents = scandir(dir, &entries, nodots, alphasort);

51  if (nents < 0) {

52   fprintf(stderr, "%s: scandir failed: %sn", myname,

53    strerror(errno));

54   return 1;

55  }

56

57  for (i = 0; i < nents; i++) {

58   printf("%81d %sn", entries[i]->d_ino, entries[i]->d_name);

59   free(entries[i]);

60  }

61

62  free(entries);

63