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

 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: %s\n", myname,
 53 strerror(errno));
 54 return 1;
 55 }
 56
 57 for (i = 0; i < nents; i++) {
 58 printf("%81d %s\n", entries[i]->d_ino, entries[i]->d_name);
 59 free(entries[i]);
 60 }
 61
 62 free(entries);
 63
 64 return 0;
 65 }

Функция main программы (строки 1–27) следует стандартному шаблону, который мы использовали до этого. Функция nodots (строки 31–35) действует как параметр select, выбирая лишь имена файлов, которые не начинаются с точки.

Функция process (строки 43–65) довольно проста, причем scandir делает большую часть работы. Обратите внимание, как каждый элемент отдельно освобождается с помощью free (строка 59) и как освобождается также весь массив (строка 62).

При запуске содержимое каталога в самом деле выводится в отсортированном порядке, без '.' и '..'.

 $ ch06-sortdir /* Действия по умолчанию отображают текущий каталог */
 2097176 00-preface.texi
 2097187 01-intro.texi
 2097330 02-cmdline.texi
 2097339 03-memory.texi
 2097183 03-memory.texi.save
 2097335 04-fileio.texi
 2097334 05-fileinfo.texi
 2097332 06-generall.texi
 ...

6.2.2. Бинарный поиск: bsearch

Линейный поиск в значительной степени похож на свое название: вы начинаете в начале и проходите искомый массив, пока не встретите то, что нужно. Для чего-нибудь простого, типа поиска целых, это обычно принимает форму цикла for. Рассмотрите эту функцию:

 /* ifind --- линейный поиск, возвращает найденный индекс или -1 */
 int ifind(int x, const int array[], size_t nelems) {
  size_t i;
  for (i = 0; i < nelems; i++)
  if (array(i) == x) /* найдено */
  return i;
  return -1;
 }

Преимуществом линейного поиска является его простота; легко с самого начала написать правильный код. Более того, он работает всегда. Даже если в конец массива добавляются элементы или они удаляются из него, нет необходимости сортировать массив.

Недостатком линейного поиска является то, что он медленный. В среднем для массива, содержащего nelems элементов, при линейном поиске случайного элемента требуется 'nelems/2' сравнений, прежде чем найдется нужный элемент. Это становится чрезмерно дорогим даже на современных высокопроизводительных системах, когда nelems принимает большие значения. Поэтому линейный поиск следует использовать лишь с небольшими массивами.

В отличие от линейного, бинарный поиск требует, чтобы входной массив был уже отсортирован. Недостатком здесь является то, что если добавляются элементы, массив перед новым поиском нужно повторно отсортировать. (Когда элементы удаляются, остальное содержимое массива все равно должно быть перетасовано. Это не так дорого, как повторная сортировка, но все равно может потребовать большого перемещения данных.)

Преимуществом бинарного поиска, и значительным, является то, что бинарный поиск умопомрачительно быстр, требуя самое большее log₂(N) сравнений, где N является числом элементов в массиве. Функция bsearch объявлена следующим образом:

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

 void *bsearch(const void *key, const void *base, size_t nmemb,
  size_t size, int (*compare)(const void*, const void*));

Параметры и их назначение сходны с таковыми для qsort:

 const void *key

Объект, который ищется в массиве.

 const void *base

Начало массива.

 size_t nmemb

Число элементов в массиве.

 size_t size

Размер каждого элемента, полученный с помощью sizeof.

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

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