Глава 2. Динамические структуры данных

Большинство задач, рассмотренных в предыдущих главах, требовали работы со статическими переменными, - переменными, которые создаются в момент определения и уничтожаются автоматически при выходе программы из области их действия. Статические переменные и структуры данных характеризуются фиксированным размером выделенной для них памяти. Например, если описан массив int a[100] под него будет выдела sizeof(int)*100 байт, хотя в самой программе может реально использоваться лишь несколько первых элементов массива. Существуют задачи, которые исключают использование структур данных фиксированного размера и требуют введения динамических структур данных, способных увеличиваться в размерах в процессе работы программы. Если до начала работы с данными невозможно определить, сколько памяти потребуется для их хранения, то память должна выделять по мере необходимости отельными блоками, связанными друг с другом указателями. Динамическая структура может занимать несмежные участки оперативной памяти.

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

Для реализации элементов динамической структуры данных в С++ используют тип данных, называемый структура (struct). (В многих языках программирования такой тип данных называют записью).

Структура - это поименованная совокупность поименованных элементов, имеющих в общем случае разный тип, и расположенных в памяти компьютера последовательно. Каждая структура включает в себя один или несколько объектов, называемых элементами структуры. Элементы структуры также называют полями структуры.

Формат описания структуры:

struct [имя типа]

{

тип1 имя_элемента1;

тип2 имя_элемента 2;

…

тип n имя_элемента n;

}[список определителей];

Элементы структуры могут иметь любой тип, кроме типа этой же структуры.

Например, опишем структуру с тремя полями:

struct student

{

char fio[30];

int group;

int mark;

} s1, *s2;

Такое определение вводит новый тип данных student, который может быть использован при определении программных объектов. Например, создадим структурированный объект и массив структурированных объектов.

student s3,s4[10];

Структурированные объекты можно определять сразу после описания структуры - в списке определений. В нашем случае в списке определений определен объект s1, и указатель на структурированный объект s2.

Для обращения к объектам, входящим в качестве элементов в конкретную структуру, обычно используют уточненные имена, то есть конструкцию вида

имя_структуры.имя_элемента_структуры

Например,

s1.group= 121;

s1.mark=5;

Если определен указатель на структуру, то для обращения к элементам структуры можно использовать операцию выбора компонентов структурного объекта ->

имя указателя->имя элемента структуры

Например,

student *st;

st->group= 222; //это равносильно (*st).group=222;

Инициализировать конкретную структуру можно только при описании перечислением ее элементов в скобках {} в порядке их описания, например

student s4= {“Fedorov”, 122, 4};

Для переменных одного и того же структурного типа определена операция присваивания, то есть поэлементное копирование, например s3=s1;

Часто в качестве поля структуры используют объединения. Объединение представляет собой частный случай структуры, все поля которой располагаются по одному и тому же адресу. Формат описания такой же, но используются ключевое слово union. Размер объединения равен наибольшему размеру из его полей.

Основное достоинство объединения – возможность разных трактовок одного и того же содержимого участка памяти.

Например,

union

{

float a;

unsigned int b;

}ab;

Если ввести ab.a=3.78, то затем можно рассматривать код его представления как беззнаковое целое cout<<ab.b;

Основное назначение объединения – обеспечить возможность доступа к одному и тому же участку памяти с помощью объектов разных типов.

Пример. Описать структуру СОТРУДНИК с полями ФАМИЛИЯ, ГОД_РОЖДЕНИЯ, ПОЛ. Для женщин – указывать количество детей, для мужчин – отношение к военной службе. Ввести данные о сотруднике и вывести их на экран.

# include <iostream.h>

# include <conio.h>

main ()

{

enum sextype {male, female};

enum ranktype {not,soldier,officier};

struct

{

char fio[40];