Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

Один из способов избежать получения вытянутых деревьев — применять более тщательный подход к их построению. Если дерево или поддерево начинает становиться слишком перекошенным в одну из сторон, необходимо реорганизовать узлы для улучшения сбалансированности дерева. Аналогично реорганизация дерева может требоваться после удаления узлов. Математики Г.М. Адельсон-Вельский и Е.М. Ландис разработали для этого алгоритм. Деревья, построенные их методом, называют АВД-деревьями (от начальных букв их фамилий). Построение сбалансированного дерева занимает больше времени, т.к. должны предприниматься дополнительные действия по реструктуризации, но тем самым обеспечивается максимальная или близкая к максимальной эффективность поиска.

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

Для ознакомления с еще одним возможным вариантом дерева, мы снова обратимся к примеру с клубом Nelville Pet Club. В этом примере сортировка дерева осуществлялась как по кличкам, так и по видам животных. Поэтому оно могло бы содержать кота Сэма в одном узле, собаку Сэма — во втором и хомяка Сэма — в третьем. Тем не менее, в дереве не могло быть двух котов с кличкой Сэм. Еще один возможный под-

Расширенное представление данных 787

ход заключается в упорядочении дерева только по кличкам животных. Само по себе это изменение разрешило бы существование только одного Сэма, независимо от вида, но затем можно было бы определить Item как список структур, а не как одиночную структуру. Тогда при первом появлении животного с кличкой Салли программа создала бы новый узел, затем новый список, после чего добавила бы Салли и ее вид в этот список. Следующее животное Салли было бы направлено в этот же узел и добавлено в список.

Дополнительные библиотеки

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

Другие направления

В этой книге были раскрыты важные функциональные возможности языка С, но мы лишь вскользь затронули библиотеку. Библиотека ANSI С содержит множество полезных функций. Большинство реализаций также предоставляют обширные библиотеки, специфичные для конкретных систем. Компиляторы для Windows поддерживают графический интерфейс Windows. Компиляторы С для Macintosh предлагают функции для доступа к инструментальному набору Macintosh, облегчающему создание программ со стандартным интерфейсом Macintosh или программ для систем iOS, таких как iPhone и iPad. Аналогично имеются инструменты для построения программ Linux с графическими интерфейсами. Найдите время для исследования возможностей, которые поддерживает ваша система. Если того, что вам нужно, в системе отсутствует, создайте собственные функции. Возможность их создания — неотъемлемая часть С. Если вы думаете, что можете создать, скажем, более совершенную функцию ввода — сделайте это! И по мере совершенствования и оттачивания своих навыков программирования вы сможете перейти от написания простого кода С к получению блестящего кода С.

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

После освоения языка С можете заняться изучением C++, Objective С или Java. Эти объектно-ориентированные языки произрастают из С. Язык С уже содержит объекты данных, варьирующиеся по сложности от простой переменной типа char до крупных и сложных структур. Объектно-ориентированные языки развивают идею объектов еще больше. Например, свойства объекта определяют не только то, какие виды информации он может хранить, но также и разновидности операций, которые могут над ним выполняться. Описанные в настоящей главе абстрактные типы данных соответствуют этому подходу. Кроме того, объекты могут наследовать свойства от других объектов. Объектно-ориентированное программирование переносит концепцию модульности на более высокий уровень абстракции, чем это имеет место в языке С, и применяется при разработке больших программ.

788 Глава 17

Перечень дополнительных книг, которые могут вас заинтересовать, приведен в разделе I приложения Б.

Ключевые понятия

Тип данных характеризуется способами структурирования и хранения данных, а также возможными операциями над ними. Абстрактный тип данных (abstract data type — ADT) абстрактным образом определяет свойства и операции, характеризующие тип. Концептуально тип ADT можно преобразовать в код на конкретном языке программирования в два этапа. Первый этап связан с определением программного интерфейса. На языке С это можно сделать за счет использования заголовочного файла для определения имен типов и объявления прототипов функций, соответствующих допустимым операциям. Второй этап состоит в реализации интерфейса. На языке С это можно сделать в виде файла исходного кода, который предоставляет определения функций, соответствующих прототипам.

Резюме

Список, очередь и двоичное дерево являются примерами абстрактных типов данных, обычно применяемых в программировании. Их часто реализуют посредством динамического выделения памяти и связанных структур, но иногда их лучше реализовать с помощью массивов.

Если в программе используется конкретный тип (скажем, очередь или дерево), ее следует писать в терминах интерфейса типа. Это позволит модифицировать и совершенствовать реализацию типа, не изменяя программы, в которых применяется интерфейс типа.

вопросы для самоконтроля