ГЛАВА 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];

int year;

sextype sex;

union

{

int children;

ranktype rang;

};

}s1;

cout<<"Enter fio ";

cin.getline(s1.fio,40);

cout<<"Enter sex ";

cin>>int(s1.sex);

switch(s1.sex)

{

case male: { cout<< "Enter rank ";

cin>>int (s1.rang);

cout<<"\n"<<s1.fio;

cout<< " male, rank="<<s1.rang;

break;

}

case female:{cout<< "Enter number of children ";

cin>>s1.children;

cout<<"\n"<<s1.fio;

cout<< " female, children ="<<s1.children;

break;

}

}

getch();

}

Вернемся к рассмотрению динамических структур данных. Элемент любой динамической структуры данных представляет собой структуру (в смысле struct), содержащую по крайней мере два поля: для хранения данных и для указателя на этуже структуру. Полей данных и указателей может быть несколько. Например, элемент списка целых чисел имеет вид

struct el

{

int a;

el *b;

}

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

- каким образом может расти и сокращаться данная структура;

- каким образом можно включить в структуру новый и удалить существующий элемент;

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

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

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

struct student

{

char *fio;

int mark;

student *next;

}

Для формирования списка требуется иметь по крайней мере один указатель – на начало списка (голова списка).

student * begin=NULL;

и один вспомогательный указатель student *adr;.

Опишем процедуру создания списка

void vvod ()

{

int n;

cout<< “Введите количество студентов ”;

cin>>n;

const int dlin=20;

char f[dlin]; // вспомогательный массив для хранения введенной фамилии студента

for (int i=1;i<=n; i++)

{

if (begin==NULL) // выделение памяти под первый элемент списка

{

begin=new (student);

adr=begin;

}

else // выделение памяти под очередной элемент списка

{

adr->next=new(student);

adr=adr->next;

}

//заполнение элементов списка

cout<< “Введите фамилию ”;

cin.getline(f,dlin);

adr->fio=new (char [strlen(f)+1]);

strcpy(adr->fio,.f);

cout<< “Введите оценку ”;

cin>>(adr->mark);

adr->next=NULL;

}

}

В данном случае мы создали список студентов как очередь. Очередь – это частный случай списка, добавление элементов в который выполняется в один конец, а выборка – из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Очередь реализует принцип FIFO (firs in – first out, первым пришел – первым вышел). В нашем примере указатель begin указывает на начало списка, и не изменяется во время выполнения программы. Добавление элементов происходит в конец списка. Очевидно, что обработка элементов для списка, сформированного таким образом, может происходить только с первого введенного.

Другим частным случаем однонаправленного списка является стек, добавление в который и выборка из которого выполняется с одного конца. Другие операции со стеком не определены. При выборке элемент исключается из стека. Стек реализует принцип LIFO (last in – first out, последним пришел – первым вышел). Создадим список студентов как стек, постоянно передвигая указатель begin и последний созданный элемент делая головой списка.

.

void vvod1 ()

{

int n;

cout<< “Введите количество студентов ”;

cin>>n;

const int dlin=20;

char f[dlin]; // вспомогательный массив для хранения введенной фамилии студента

for (int i=1;i<=n; i++)

{

adr=new(student);

cout<< “Введите фамилию ”;

cin.getline(f,dlin);

adr->fio=new (char [strlen(f)+1]);

strcpy(adr->fio,.f);

cout<< “Введите оценку ”;

cin>>(adr->mark);

adr->next=begin;

begin=adr;

}

}

Чтобы вывести на экран элементы списка, созданного любым из предложных способов, можно использовать следующую процедуру

void vivod()

{

adr=begin;

while (adr!=NULL)

{

cout<<"\n "<<(adr->fio)<<" "<<adr->mark;

adr=adr->next;

}

}

Кроме процедур создания и вывода на экран для списка обычно определяют следующие процедуры:

- добавления элемента в конец списка;

- поиска заданного элемента;

- вставка элемента до или после заданного элемента;

- сортировка списка;

- удаления заданного элемента;

- удаление списка.

Каждому студенту рекомендуется выполнить хотя бы одно из упражнений 1-12 заданий 1-4.