Читаем Язык программирования Си. Издание 3-е, исправленное полностью

    p->count++;

   for (p = keytab; p < keytab + NKEYS; p++)

    if (p->count > 0)

     printf("%4d %s\n", p->count, p->word);

 return 0;

}

/* binsearch: найти слово word в tab[0]...tab[n-1] */

struct key *binsearch(char *word, struct key *tab, int n)

{

 int cond;

 struct key *low = &tab[0];

 struct key *high = &tab[n];

 struct key *mid;

 while (low < high) {

  mid = low + (high - low) / 2;

  if ((cond = strcmp(word, mid->word)) < 0)

   high = mid;

  else if (cond > 0)

   low = mid + 1;

  else

   return mid;

 }

 return NULL;

}

Некоторые детали этой программы требуют пояснений. Во-первых, описание функции binsearch должно отражать тот факт, что она возвращает указатель на struct key, а не целое, это объявлено как в прототипе функции, так и в функции binsearch. Если binsearch находит слово, то она выдает указатель на него, в противном случае она возвращает NULL. Во-вторых, к элементам keytab доступ в нашей программе осуществляется через указатели. Это потребовало значительных изменений в binsearch. Инициализаторами для low и high теперь служат указатели на начало и на место сразу после конца массива. Вычисление положения среднего элемента с помощью формулы

mid = (low + high) / 2 /* НЕВЕРНО */

не годится, поскольку указатели нельзя складывать. Однако к ним можно применить операцию вычитания, и так как high-low есть число элементов, присваивание

mid = low + (high-low) / 2

превратит mid в указатель на элемент, лежащий посередине между low и high.

Самое важное при переходе на новый вариант программы - сделать так, чтобы не генерировались неправильные указатели и не было попыток обратиться за пределы массива. Проблема в том, что и &tab[-1], и &tab[n] находятся вне границ массива. Первый адрес определенно неверен, нельзя также осуществить доступ и по второму адресу. По правилам языка, однако, гарантируется, что адрес ячейки памяти, следующей сразу за концом массива (т. е. &tab[n]), в арифметике с указателями воспринимается правильно.

В главной программе main мы написали

for (р = keytab; р < keytab + NKEYS; р++)

Если p - это указатель на структуру, то при выполнении операций с р учитывается размер структуры. Поэтому р++ увеличит р на такую величину, чтобы выйти на следующий структурный элемент массива, а проверка условия вовремя остановит цикл.

Не следует, однако, полагать, что размер структуры равен сумме размеров ее элементов. Вследствие выравнивания объектов разной длины в структуре могут появляться безымянные "дыры". Например, если переменная типа char занимает один байт, а int - четыре байта, то для структуры

struct { 

 char с; 

 int i;

};

может потребоваться восемь байтов, а не пять. Оператор sizeof возвращает правильное значение.

Наконец, несколько слов относительно формата программы. Если функция возвращает значение сложного типа, как, например, в нашем случае она возвращает указатель на структуру:

struct key *binsearch(char *word, struct key *tab, int n)

то "высмотреть" имя функции оказывается совсем не просто. В подобных случаях иногда пишут так:

struct key *

binsearch(char *word, struct key *tab, int n)

Какой форме отдать предпочтение - дело вкуса. Выберите ту, которая больше всего вам нравится, и придерживайтесь ее.

<p>6.5 Структуры со ссылками на себя</p>

Предположим, что мы хотим решить более общую задачу - написать программу, подсчитывающую частоту встречаемости для любых слов входного потока. Так как список слов заранее не известен, мы не можем предварительно упорядочить его и применить бинарный поиск. Было бы неразумно пользоваться и линейным поиском каждого полученного слова, чтобы определять, встречалось оно ранее или нет - в этом случае программа работала бы слишком медленно. (Более точная оценка: время работы такой программы пропорционально квадрату количества слов.) Как можно организовать данные, чтобы эффективно справиться со списком произвольных слов?

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

Перейти на страницу:

Похожие книги

Основы программирования в Linux
Основы программирования в Linux

В четвертом издании популярного руководства даны основы программирования в операционной системе Linux. Рассмотрены: использование библиотек C/C++ и стан­дартных средств разработки, организация системных вызовов, файловый ввод/вывод, взаимодействие процессов, программирование средствами командной оболочки, создание графических пользовательских интерфейсов с помощью инструментальных средств GTK+ или Qt, применение сокетов и др. Описана компиляция программ, их компоновка c библиотеками и работа с терминальным вводом/выводом. Даны приемы написания приложений в средах GNOME® и KDE®, хранения данных с использованием СУБД MySQL® и отладки программ. Книга хорошо структурирована, что делает обучение легким и быстрым. Для начинающих Linux-программистов

Нейл Мэтью , Ричард Стоунс , Татьяна Коротяева

ОС и Сети / Программирование / Книги по IT
Программист-прагматик. Путь от подмастерья к мастеру
Программист-прагматик. Путь от подмастерья к мастеру

Находясь на переднем крае программирования, книга "Программист-прагматик. Путь от подмастерья к мастеру" абстрагируется от всевозрастающей специализации и технических тонкостей разработки программ на современном уровне, чтобы исследовать суть процесса – требования к работоспособной и поддерживаемой программе, приводящей пользователей в восторг. Книга охватывает различные темы – от личной ответственности и карьерного роста до архитектурных методик, придающих программам гибкость и простоту в адаптации и повторном использовании.Прочитав эту книгу, вы научитесь:Бороться с недостатками программного обеспечения;Избегать ловушек, связанных с дублированием знания;Создавать гибкие, динамичные и адаптируемые программы;Избегать программирования в расчете на совпадение;Защищать вашу программу при помощи контрактов, утверждений и исключений;Собирать реальные требования;Осуществлять безжалостное и эффективное тестирование;Приводить в восторг ваших пользователей;Формировать команды из программистов-прагматиков и с помощью автоматизации делать ваши разработки более точными.

А. Алексашин , Дэвид Томас , Эндрю Хант

Программирование / Книги по IT
97 этюдов для архитекторов программных систем
97 этюдов для архитекторов программных систем

Успешная карьера архитектора программного обеспечения требует хорошего владения как технической, так и деловой сторонами вопросов, связанных с проектированием архитектуры. В этой необычной книге ведущие архитекторы ПО со всего света обсуждают важные принципы разработки, выходящие далеко за пределы чисто технических вопросов.?Архитектор ПО выполняет роль посредника между командой разработчиков и бизнес-руководством компании, поэтому чтобы добиться успеха в этой профессии, необходимо не только овладеть различными технологиями, но и обеспечить работу над проектом в соответствии с бизнес-целями. В книге более 50 архитекторов рассказывают о том, что считают самым важным в своей работе, дают советы, как организовать общение с другими участниками проекта, как снизить сложность архитектуры, как оказывать поддержку разработчикам. Они щедро делятся множеством полезных идей и приемов, которые вынесли из своего многолетнего опыта. Авторы надеются, что книга станет источником вдохновения и руководством к действию для многих профессиональных программистов.

Билл де Ора , Майкл Хайгард , Нил Форд

Программирование, программы, базы данных / Базы данных / Программирование / Книги по IT