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

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

на обложку

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

Шрифт:

Все процедуры разделяют общий лейтмотив; данные управляются через указатели

void*

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

sort

хорошо работает для текстовых файлов; см. справочную страницу для sort(1). Сортировка двоичных файлов требует написания специальной программы.)

Поскольку ни один алгоритм не работает

одинаково хорошо для всех приложений, имеются несколько различных наборов библиотечных процедур для сопровождения искомых коллекций данных. Данная глава рассматривает лишь один простой интерфейс для поиска. Другой, более развитый интерфейс описан в разделе 14.4 «Расширенный поиск с использованием двоичных деревьев». Более того, мы намеренно не объясняем лежащие в основе алгоритмы, поскольку данная книга об API, а не об алгоритмах и структурах данных. Важно понять, что API можно рассматривать как «черные ящики», выполняющие определенную работу без необходимости понимания подробностей их работы.

6.2.1. Сортировка:

qsort

Сортировка выполняется с помощью

qsort

#include <stdlib.h> /* ISO С */

void qsort(void *base, size_t nmemb, size_t size,

int (*compare)(const void*, const void*));

Название

qsort

происходит от алгоритма машинного поиска Хоара Quicksort (C.A.R. Hoare's Quicksort algorithm), который использовался в первоначальной реализации Unix. (Ничто в стандарте POSIX не требует использования этого алгоритма для

qsort

. Реализация GLIBC использует высоко оптимизированную комбинацию Quicksort и Insertion Sort.)

qsort

сортирует массивы произвольных объектов. Она работает, перетасовывая непрозрачные участки памяти из одного места массива в другой и полагаясь на то, что вы, программист, предоставите функцию сравнения, которая позволяет определить относительное расположение одного элемента массива относительно другого. Аргументы следующие:

void *base

Адрес начала массива.

size_t nmemb

Общее число элементов в массиве.

size_t size

Размер каждого элемента массива. Лучший способ получения этого значения — оператор С

sizeof

int (*compare)(const void*, const void*)

Возможно устрашающее объявление указателя функции. Оно говорит, что «

compare

указывает на функцию, которая принимает два параметра '

const void*

' и возвращает

int

».

Большая часть работы заключается в написании соответствующей функции сравнения. Возвращаемое значение должно имитировать соответствующее значение

strcmp

: меньше нуля, если первое значение «меньше» второго, ноль, если они равны, и больше нуля, если первое значение «больше» второго. Именно функция сравнения определяет значения «больше» и «меньше» для всего, что вы сравниваете. Например, для сравнения двух значений

double

мы могли бы использовать эту функцию:

int dcomp(const void *d1p, const void *d2p) {

const double *d1, *d2;

d1 = (const double*)d1p; /*

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

d2 = (const double*)d2p;

if (*d1 < *d2) /* Сравнить и вернуть нужное значение */

return -1;

else if (*d1 > *d2)

return 1;

else if (*d1 == *d2)

return 0;

else

return -1; /* NaN сортируется до действительных чисел */

}

Это показывает общий стереотип для функций сравнения: привести тип аргументов от

void*

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

Для чисел с плавающей точкой простое вычитание, подобное '

return *d1 - *d2

', не работает, особенно если одно значение очень маленькое или одно или оба значения являются специальными значениями «не число» или «бесконечность». Поэтому нам приходится осуществлять сравнение вручную, принимая во внимание нечисловое значение (которое даже не равно самому себе!)

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;