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

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

return 0;

 else

return 1;

}

Логика здесь проста: сначала сравниваются фамилии, затем имена, а затем номера ID, если два имени совпадают. Используя для строк

strcmp

, мы автоматически получаем правильное отрицательное/нулевое/положительное значение для возвращения.

При сравнении ID сотрудников нельзя просто использовать вычитание: представьте, что

long

64-разрядный, а

int

32-разрядный, а два значения отличаются лишь в старших 32 битах (скажем,

младшие 32 бита равны нулю). В таком случае вычитание автоматически привело бы к приведению типа к

int

с отбрасыванием старших 32 битов и возвращением неверного результата.

ЗАМЕЧАНИЕ. Возможно, мы остановились при сравнении имен, в этом случае все сотрудники с совпадающими фамилиями и именами оказались бы сгруппированы, но никак не отсортированы

Это важный момент

qsort

не гарантирует стабильной сортировки. Стабильна сортировка, в которой, если два элемента равны на основе значения какого-либо ключа(-ей), они сохраняют свой первоначальный порядок друг относительно друга в конечном отсортированном массиве. Например, рассмотрите трех сотрудников с одинаковыми фамилиями и именами и с номерами 17, 42 и 81. Их порядок в первоначальном массиве. возможно, был 42, 81 и 17 (Что означает, что сотрудник 42 находится по индексу с меньшим значением, чем сотрудник 81, который, в свою очередь, находится по индексу с меньшим значением, чем сотрудник 17). После сортировки порядок может оказаться 81, 42 и 17. Если ото представляет проблему, процедура сравнения должна рассматривать все важные ключевые значения (Наша так и делает.)

Просто используя другую функцию, мы можем отсортировать сотрудников по старшинству:

int emp_seniority_compare(const void *e1p,

 const void *e2p) {

 const struct employee *e1, *e2;

 double diff;

 /* Привести указатели к нужному типу */

 e1 = (const struct employee*)e1p;

 e2 = (const struct employee*)e2p;

 /* Сравнить времена */

 diff = difftime(e1->start_date, e2->start_date);

 if (diff < 0)

return -1;

 else if (diff > 0)

return 1;

 else

return 0;

}

Для максимальной переносимости мы использовали

difftime

, которая возвращает разницу в секундах между двумя значениями

time_t

. Для данного конкретного случая приведение, такое, как

return (int)difftime(e1->start_date, e2->start_date);

должно сработать, поскольку значения

time_t

находятся в приемлемом диапазоне. Тем не менее, мы вместо этого использовали полный трехсторонний оператор

if

, просто из предосторожности.

Вот пример файла данных со списком пяти президентов США:

$ cat presdata.txt

/* Фамилия, имя, номер президента, инаугурация */

Bush George 43 980013600

Clinton William 42 727552800

Bush George 41 601322400

Reagan Ronald 40 348861600

Carter James 39 222631200

В

ch06-sortemp.c

приведена простая программа, которая считывает этот файл в массив

struct employee

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

1 /* ch06-sortemp.c --- Демонстрирует qsort с двумя функциями сравнения. */

2

3 #include <stdio.h>

4 #include <stdlib.h>

5 #include <time.h>

6

7 struct employee {

8 char lastname[30];

9 char firstname[30];

10 long emp_id;

11 time_t start_date;

12 };

13

14 /* emp_name_id_compare --- сравнение по имени, затем no ID */

15

16 int emp_name_id_compare(const void *e1p, const void *e2p)

17 {

/* ...как показано ранее, опущено для экономии места... */

39 }

40

41 /* emp_seniority_compare --- сравнение по старшинству */

42

43 int emp_seniority_compare(const void *e1p, const void *e2p)

44 {

/* ...как показано ранее, опущено для экономии места... */

58 }

59

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 %ld\n",

73 presidents[npres].lastname,

74 presidents[npres].firstname,

75 &presidents[npres].emp_id,

76 &presidents[npres].start_date);

77 }

78

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

80

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