Объединения разнотипных данных

Со структурами "в близком родстве" находятся объединения, которые вводятся с помощью служебного слова union. Чтобы пояснить "степень родства" объединений со структурами, рассмотрим приведённый ниже пример.

struct ExamStruct { long L; int K[2]; char C[4]; } STR;	union ExamUnion { long L; int K[2]; char C[4]; } UNI;
sizeof(ExamStruct) = 12	sizeof(ExamUnion) = 4
В памяти элементы структуры размещаются следующим образом:     Каждому из элементов L, K[2], C[4] отведено по четыре байта	В памяти элементы объединения размещаются следующим образом     Под все элементы L, K[2], C[4] отводится четыре байта памяти.

Итак, объединение можно рассматривать как структуру, все элементы которой при размещении в памяти имеют нулевое смещение от начала. Тем самым все элементы объединения размещаются в одном и том же участке памяти. Размер участка памяти, выделяемого для объединения, определяется максимальной из длин его элементов. В приведённом выше примере все элементы занимают в памяти четыре байта, поэтому объём памяти, занимаемый объектом UNI равен четырём байтам.

Объединения часто используются для того чтобы обеспечить доступ к одному и тому же фрагменту памяти с помощью разных форматов данных ( разными способами), так записав строчку UNI .C[1] мы получили доступ ко второму байту четырёхбайтовой переменной L и соответственно можем его модифицировать.

Приведём фрагмент кода, в котором объединение используется в качестве поля данных структурированного объекта. Этот же фрагмент является хорошим примером использования директивы препроцессора define, с помощью которой создаётся словарь терминов для абстракций из решаемой нами задачи. Так с помощью первой директивы define вводится синоним STAFF для типа данных struct sStaffType. Этот приём с одной стороны позволяет скрывать некоторые детали реализации, а с другой стороны делает наш код более читабельным и простым для понимания.

#define STAFF struct sStaffType

STAFF { // Учебно-вспомогательный персонал

int iYearsOfService; // Время работы (лет)

float fHourlyWage; // Почасовая оплата

};

# define STUDENT struct sStudentType

STUDENT{

float fGradePtAverage; // Средний рейтинг

int iLevel; // Год обучения

};

# define PROFESSOR struct sProfType

PROFESSOR {

int iDepartmentNumber; // Номер кафедры

float fAnnualSalary; // Годовая зарплата

};

# define NODE_TYPE enum eNodeType

typedef NODE_TYPE {student, professor, staff};

# define TREE struct sTree

TREE {

char sLastName[15]; // Фамилия

char sFirstName[15]; // Имя

int iAge; // Возраст

TREE *Left, *Right; // Указатели на левый и правый листья (ветви)

NODE_TYPE tag; // описатель типа узла - студент или профессор или УВП

union {

STUDENT student;

PROFESSOR professor;

STAFF staff;

} uNodeTag; // Обьединение, содержащее информацию по

}; // студенту или сотруднику университета

Итак, обратим внимание на определение структуры TREE, внутри которой есть поле данных uNodeTag, являющееся объединением структурированных типов данных STUDENT, PROFESSOR, STAFF. Предположим, что каждый объект типа TREE должен содержать запись либо о студенте, либо о профессоре, либо о преподавателе причём фамилия, имя и возраст должны присутствовать во всех трёх типах записей, а остальные поля данных у каждого типа будут свои. В записи о студенте будет хранится информация о среднем рейтинге и годе обучения, в записи о профессоре - номер кафедры и годовая зарплата, в записи о преподавателе – время работы и почасовая оплата. Для того чтобы при извлечении записи из массива или базы данных мы знали, какая информация хранится в поле uNodeTag вводится описатель типа узла tag. В соответствии с его определением в программе мы видим, что если он равен нулю, то это поле содержит информацию о студенте, если единица, то о профессоре, если двойку, то о преподавателе. (Естественно значение поля tag, как и значение всех остальных полей, мы задаём самостоятельно перед тем как поместить запись в массив, или в базу данных, или в линейный список и т.д.) Таким образом объект типа TREE с помощью объединения становится универсальным для хранения данных и о студентах, и о преподавателях , и о профессорах.

Ещё раз хочу обратить внимание на определение поля uNodeTag внутри структуры TREE:

union {

STUDENT student;

PROFESSOR professor;

STAFF staff;

} uNodeTag;

Поскольку объект типа uNodeTag необходим нам только внутри структурированного объекта типа TREE , то нет смысла засорять глобальную область и определять новый тип объединения за пределами TREE. Именно поэтому объединение определено внутри структурированного объекта TREE и не имеет имени типа. Зато сразу видно, что собой представляет объект uNodeTag. Такой приём очень распространён при программировании на Windows.

Деревья

Рассмотрим деревья – наиболее важные нелинейные структуры, которые встречаются при работе с компьютерными алгоритмами.

Формально дерево определяется как конечное множество Т одного или более узлов со следующими свойствами:

1. существует один выделенный узел, а именно – корень данного дерева Т;

2. остальные узлы (за исключением корня) распределены среди m0 непересекающихся множеств Т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/x² приводит к построению дерева вида:

Обход в обратном порядке. Узлы посещаются «снизу-вверх». Для корня дерева рекурсивно вызывается следующая процедура: обойти левое поддерево; обойти правое поддерево; посетить узел. Для того чтобы правильно найти значение выражения y=3ln(x+1) – a/x² какраз такой обход и нужен.

Обход в прямом порядке. Каждый узел посещается до того, как посещены его потомки. Для корня дерева рекурсивно вызывается следующая процедура: посетить узел; обойти левое поддерево; обойти правое поддерево.

Симметричный обход. Посещаем сначало левое поддерево, затем узел, затем - правое поддерево. Для корня дерева рекурсивно вызывается следующая процедура: обойти левое поддерево; посетить узел; обойти правое поддерево;