Читать книгу 📗 "Linux программирование в примерах - Роббинс Арнольд"
13 int main(int argc, char **argv)14 {15 int i;16 int errs = 0;1718 myname = argv[0];1920 if (argc == 1)21 errs = process("."); /* по умолчанию текущий каталог */22 else23 for (i = 1; i < argc; i++)24 errs += process(argv[i]);2526 return (errs != 0);27 }2829 /* nodots --- игнорирует файлы с точкой, для scandir() */3031 int32 nodots(const struct dirent *dp)33 {34 return (dp->d_name[0] != '.');35 }3637 /*38 * process --- сделать что-то с каталогом, в данном случае,39 * вывести в стандартный вывод пары индекс/имя.40 * Вернуть 0, если все нормально, в противном случае 1.41 */4243 int44 process(const char *dir)45 {46 DIR *dp;47 struct dirent **entries;48 int nents, i;4950 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 }5657 for (i = 0; i < nents; i++) {58 printf("%81d %sn", entries[i]->d_ino, entries[i]->d_name);59 free(entries[i]);60 }6162 free(entries);6364 return 0;65 }Функция
main()nodots()selectФункция
process()scandir()free()При запуске содержимое каталога в самом деле выводится в отсортированном порядке, без '
...$ ch06-sortdir /* Действия по умолчанию отображают текущий каталог */2097176 00-preface.texi2097187 01-intro.texi2097330 02-cmdline.texi2097339 03-memory.texi2097183 03-memory.texi.save2097335 04-fileio.texi2097334 05-fileinfo.texi2097332 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;}Преимуществом линейного поиска является его простота; легко с самого начала написать правильный код. Более того, он работает всегда. Даже если в конец массива добавляются элементы или они удаляются из него, нет необходимости сортировать массив.
Недостатком линейного поиска является то, что он медленный. В среднем для массива, содержащего
nelemsnelems/2nelemsВ отличие от линейного, бинарный поиск требует, чтобы входной массив был уже отсортирован. Недостатком здесь является то, что если добавляются элементы, массив перед новым поиском нужно повторно отсортировать. (Когда элементы удаляются, остальное содержимое массива все равно должно быть перетасовано. Это не так дорого, как повторная сортировка, но все равно может потребовать большого перемещения данных.)
Преимуществом бинарного поиска, и значительным, является то, что бинарный поиск умопомрачительно быстр, требуя самое большее log2(N) сравнений, где N является числом элементов в массиве. Функция
bsearch()#include <stdlib.h> /* ISO С */
