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

Рис. 14.3. Структура двоичного дерева

Является ли иерархическая, или древовидная, структура, показанная на рис. 14.3, более эффективной, чем массив? Рассмотрим случай дерева с 10 уровнями узлов. Оно имеет 2 10- 1, или 1023, узла, в которых можно было бы хранить вплоть до 1023 слов. Если эти слова упорядочены в соответствии с некоторым осмысленным планом, то нужное слово можно найти максимум за девять перемещений по мере того, как поиск продвигается вниз с одного уровня на следующий. Если бы слова хранились в массиве, то для нахождения искомого слова, в худшем случае пришлось бы просмотреть все 1023 элемента.

602 глава 14

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

На этом мы завершаем обзор структур в настоящей главе, но еще приведем примеры связных структур в главе 17. Далее мы обсудим три других средства С для работы с данными: объединения, перечисления и typedef.

Объединения: краткое знакомство

ОбъеДинение— это тип, который позволяет хранить данные разных типов в одном и том же месте памяти (но не одновременно). Типичным видом объединения может служить таблица, предназначенная для хранения смеси типов в определенном порядке, который не является ни регулярным, ни известным заранее. Применяя массив объединений, можно создать массив единиц одинаковых размеров, каждая из которых может содержать данные разнообразных типов.

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

union hold { int digit; double bigfl; char letter;

};

Структура с похожим объявлением способна хранить значения типов int, double и char одновременно, однако объединение может хранить значение типа int или double или char. Вот пример определения трех переменных объединения типа hold:

union hold fit; // переменная объединения типа hold

union hold save[10]; // массив из 10 переменных объединения

union hold * pu; // указатель на переменную типа hold

Первое объявление создает одиночную переменную fit. Компилятор выделяет пространство памяти, достаточное для хранения наибольшего из описанных возможностей. В данном случае наибольшим вариантом из перечисленных является тип double, который в нашей системе требует 64 бита, или 8 байтов. Второе объявление создает массив по имени save с 10 элементами, каждый из которых имеет размер 8 байтов. Третье объявление создает указатель, который может содержать адрес объединения hold.

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

union hold valA; valA.letter = 'R';

union hold valB = valA; // инициализация одного объединения другим union hold valC = (88); // инициализация члена digit объединения

union hold valD = (.bigfl = 118.2); // назначенный инициализатор

Структуры и другие формы данных 603

Использование объединений

Ниже показано, как можно использовать объединение:

fit.digit = 23; //в переменной fit хранится 23; используются 2 байта

fit.bigfl =2.0; //23 очищено, 2.0 сохранено; используются 8 байтов

fit.letter = 'h'; // 2.0 Значение.h сохранено; используется 1 байт

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

Вы можете использовать операцию -> с указателями на объединения в той же манере, как применяли ее с указателями на структуры:

pu = &fit;

х = pu->digit; // то же, что и х = fit.digit

Ниже показано, как не следует поступать:

fit.letter = 'А';

flnum = 3 . О2*fit.bigf1; // ОШИБКА!