Linux программирование в примерах
вернуться

Роббинс Арнольд
Шрифт:

6.2.1.1. Пример: сортировка сотрудников

Для более сложных структур требуются более сложные функции. Например, рассмотрите следующую (довольно тривиальную)

struct employee
:

struct employee {

char lastname[30];

char firstname[30];

long emp_id;

time_t start_date;

};

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

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

 const struct employee *e1, *e2;

 int last, first;

 e1 = (const struct employee*)e1p; /* Преобразовать указатели */

 e2 = (const struct employee*)e2p;

 if ((last = strcmp(e1->lastname, e2->lastname)) != 0)

/* Сравнить фамилии */

return last; /* Фамилии различаются */

 /* фамилии совпадают, сравнить имена */

 if ((first = strcmp(e1->firstname, e2->firstname)) != 0)

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

return first; /* Имена различаются */

 /* имена совпадают, сравнить номера ID */

 if (e1->emp_id < e2->emp_id) /* Сравнить ID сотрудника */

return -1;

 else if (e1->emp_id == e2->emp_id)

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