7.4 Деревья
Рассмотрим деревья – наиболее важные нелинейные структуры, которые встречаются при работе с компьютерными алгоритмами.
Формально дерево определяется как конечное множество Т одного или более узлов со следующими свойствами:
1. существует один выделенный узел, а именно – корень данного дерева Т;
2. остальные узлы (за исключением корня) распределены среди m0 непересекающихся множеств Т1, …, Тm и каждое из этих множеств в свою очередь, является деревом; деревья Т1, …, Тm называются поддеревом данного корня.
Как видно из определения, оно является рекурсивным, и тем самым отражает рекурсивное свойство всех древовидных структур.
Способы представления дерева
a) b)
с) (A (B (H) (J) ) (C (D) (E(G)) (F) ) )
d)
Рис. 7.2 Способы изображения древовидных структур: а) обычная схема дерева; b) вложенные множества; c) список с отступами; d) вложенные скобки.
Кроме понятия дерева в литературе часто используется понятие леса. Лес – это множество содержащие несколько непересекающихся деревьев. Для примера, если исключить корневой узел А, то мы получим лес.
Важнейшим подмножеством деревьев являются так называемые бинарные деревья. Бинарное дерево это конечное множество узлов, которое может быть пустым, либо состоять из корня вместе с двумя другими бинарными деревьями. Другими словами каждый его узел может иметь 0, 1, .2 детей (но не более); мы будем различать левых и правых детей.
Решение многих алгоритмических задач приводит к необходимости работать с древовидными структурами, так например, алгоритмический анализ алгебраического выражения y=3ln(x+1) – a/x2 приводит к построению дерева вида:
Обход в прямом порядке : посетить корень первого дерева; пройти поддеревья первого дерева; пройти оставшиеся деревья.
- * 3 ln + x 1 / a ^ x 2
Обход в обратном порядке : пройти поддеревья первого дерева; посетить корень первого дерева; пройти оставшиеся деревья. 3 x 1 + ln * a x 2 ^ / -
7.5 Битовые поля структур и объединений
Внутри структур и объединений могут в качестве их компонентом (элементов) использоваться битовые поля. Каждое битовое поле представляет целое или беззнаковое целое значение, занимающее в памяти фиксированное число битов (в компиляторе ВС++ от 1 до 16 бит). Битовые поля могут быть только элементами структур, объединений (и, как увидим в дальнейшем, классов), т.е. битовые поля не могут появляться как самостоятельные объекты программ. Битовые поля не имеют адресов, т.е. для них не определена операция &, нет указателей и ссылок на битовые поля. Они не могут объединяться в массивы. Назначение битовых полей - обеспечить удобный доступ к отдельным битам данных. С помощью битовых полей можно формировать объекты с длиной внутреннего представления, не кратной байту. Это позволяет плотно "упаковывать" информацию и тем самым экономить память, например, при работе с однобитовыми флажками.
Определение структуры с битовыми полями имеет такой формат:
struct { тип_поля имя_поля: жирина_поля; тип_поля имя_поля: ширина_поля;
} имя_структуры;
Здесь тип_поля - один из базовых целых типов int, unsigned int (сокращенно unsigned), signed int (сокращенно signed), char, short, long и их знаковые и беззнаковые варианты. (В языке Си стандарт ANSI допускает только знаковый или беззнаковый вариант типа int.)
Рис. 7.3 Варианты размещения в памяти битовых полей структуры
имя_поля - идентификатор, выбираемый пользователем; ширина-поля - целое неотрицательное десятичное число, значение которого , обычно не должно превышать длины слова конкретной ЭВМ.
Таким образом, диапазон возможных значений ширины..поля существенно зависит от реализации. В компиляторах ТС++ и ВС++ ширина-поля может выбираться в диапазоне от 0 до 16. Пример определения структуры с битовыми полями:
struct { int а: 10; int b:14; } хх, *рх;
Для обращения к битовым полям используются те же конструкции, что и для обращения к обычным элементам структур:
имя_структуры.имя_поля
укаэатель_на_структуру->имя_поля
ссылка_на_структуру.имя_поля
(* указатель_на_струхтуру).имя_поля
Например, для введенной структуры хх и указателя рх допустимы такие операторы:
хх.а = 1; рх = &хх; рх->b = 48;
От реализации зависит порядок размещения полей структуры в памяти IВМ. Поля могут размещаться как справа налево, так и слева направо. Кроме того, реализация определяет, как размещаются в памяти битовые ноля, длина которых не кратна длине слова и(или) длине байта (рис. 7.3). Для компиляторов, работающих на IBM PC, поля, размещенные в начале описания структуры, имеют младшие адреса. Именно такое размещение изображено на рис. 7.3.
В компиляторах часто имеется возможность изменять размещение битовых полей, выравнивая их по границам слов или выполняя плотную упаковку. Некоторые возможности влиять на размещение битовых полей в памяти имеются и на уровне синтаксиса самого языка Си++. Во-первых, мри определении битового поля разрешается не указывать его имя. В этом случае (когда указаны только двоеточие и ширина поля) в структуру вводятся неиспользуемые (недоступные'» биты, формирующие промежуток между значимыми полями. Например
Рис. 7.4. Структура с безымянным полем
В структуре уу между полем int a: 10 и полем int Ь:14 размещаются 6 бит, не доступных для использования. Их назначение - выравнивание полей по плану программиста (рис. 7.4).
Битовые поля в объединениях используются для доступа к нужным битам того или иного объекта, входящего в объединение. Например, следующее объединение позволяет замысловатым способом сформировать код символа ‘D’ (равный 68):
union { char simb;
struct { int x:5; int y:3; ) hh; } cod;
cod.hh.x = 4; cod.hh.y = 2; cout « cod.simb; // Выведет на экран символ 'D'
Рис. 7.5 иллюстрирует формирование кода 68, соответствующего символу 'D'.
Рис. 7.5 Объединение со структурой из битовых полей
Для иллюстрации особенностей объединений и структур с битовыми полями рассмотрим следующую программу:
//Р7-05.СРР - битовые поля, структуры, объединения tinclude <iostream.h>
// Функция упаковывает в один байт остатки от деления // на 16 двух целых чисел - параметров: unsigned char cod(int a,int b) { union { unsigned char z;
struct { unsigned int x:4; // Младшие биты unsigned int y:4; // Старшие биты } hh; } un ;
un.hh.x = a % 16; un.hh.y = b % 16; return un.z;
)
// Функция изображает на экране двоичное представление
// байта-параметра:
void binar(unsigned char ch){
union { unsigned char ss;
struct { unsigned aO:l;
unsigned al:1;
unsigned a2:1;
unsigned a3:1;
unsigned a4:1;
unsigned a5:l;
unsigned аб:1;
unsigned a7:1;
} byte;
} cod;
cod.ss = ch; // Занести значение параметра в объединение // Выводим биты внутреннего кода значения параметра: cout « "\nHOMEPA БИТОВ: 76543210"; cout « "ХпЗначения битов:";
cout « "\t" « cod.byte.a7 « " " « cod.byte.аб; cout « " " « cod.byte.a5 « "• " « cod.byte.a4; cout « " " « cod.byte.a3 « " " « cod.byte.a2; cout « " " « cod.byte.al « " " « cod.byte.aO; cout « "\n";
*
void main() {
int k;
int в, n;
cout « "\nm = "; cin » m;
cout « "n = "; cin » n;
k - cod(m,n);
cout « "cod = " « k;
binar(k);
}
Возможный результат выполнения программы:
m = I <Enter>
n = 3 <Enter>
cod = 49
НОМЕРА БИТОВ: 76543210
Значения битов: 00110001
Результат еще одного выполнения программы:
m = 0 <Enter>
n = I <Enter>
cod =16
НОМЕРА БИТОВ: 76543210
Значения битов: 00010000
Комментарии в тексте программы и приведенные результаты объясняют особенности программы. В функциях cod() и binar() использованы объединения, включающие структуры с битовыми полями. В функции cod() запись данных выполняется в битовые поля структуры hh, входящей в объединение un, а результат выбирается из того же объединения un, но как числовое значение байта. В функции binary() обратное преобразование - в нее как значение параметра передается байт, содержимое которого побитово "расшифровывается" за счет обращения к отдельным полям структуры byte, входящей в объединение cod.
Одно из принципиальных отличий языка Си++ от языка Си -возможность включения в структуры и объединения не только данных, но и функций. В этом случае структурный тип или объединяющий тип становится определением класса.