<Большинство задач, рассмотренных в предыдущих главах, требовали работы со статическими переменными, — переменными, которые создаются в момент определения и уничтожаются автоматически при выходе программы из области их действия. Статические avroramodels.info/cheljabinsk — досуг для мужчин переменные и структуры данных характеризуются фиксированным размером выделенной для них памяти. Например, если описан массив int a[100] под него будет выдела sizeof(int)*100 байт, хотя в самой программе может реально использоваться лишь несколько первых элементов массива. Существуют задачи, которые исключают использование структур данных фиксированного размера и требуют введения динамических структур данных, способных увеличиваться в размерах в процессе работы программы. Если до начала работы с данными невозможно определить, сколько памяти потребуется для их хранения, то память должна выделять по мере необходимости отельными блоками, связанными друг с другом указателями. Динамическая структура может занимать несмежные участки оперативной памяти.
<Динамические структуры широко применяют и для более эффективной работы с данными, размер которых известен, особенно для решения задач сортировки, поскольку упорядочивание динамических структур не требует перестановки элементов, а сводится к изменению указателей на эти элементы. Например, если в процессе выполнения программы требуется многократно упорядочивать большой массив данных, имеет смысл организовать его в виде динамической структуры.
Для реализации элементов динамической структуры данных в С++ используют тип данных, называемый структура (struct). (В многих языках программирования такой тип данных называют записью).
Структура — это поименованная совокупность поименованных элементов, имеющих в общем случае разный тип, и расположенных в памяти компьютера последовательно. Каждая структура включает в себя один или несколько объектов, называемых элементами структуры. Элементы структуры также называют полями структуры.
<Формат описания структуры:
<{
< тип1 имя_элемента1;
< тип2 имя_элемента 2;
<…
< тип n имя_элемента n;
<}[список определителей];
<Элементы структуры могут иметь любой тип, кроме типа этой же структуры.
<Например, опишем структуру с тремя полями:
<{
< char fio[30];
< int group;
< int mark;
<} s1, *s2;
<Такое определение вводит новый тип данных student, который может быть использован при определении программных объектов. Например, создадим структурированный объект и массив структурированных объектов.
<Структурированные объекты можно определять сразу после описания структуры — в списке определений. В нашем случае в списке определений определен объект s1, и указатель на структурированный объект s2.
<Для обращения к объектам, входящим в качестве элементов в конкретную структуру, обычно используют уточненные имена, то есть конструкцию вида
<имя_структуры.имя_элемента_структуры
<Например,
<s1.group= 121;
<s1.mark=5;
<Если определен указатель на структуру, то для обращения к элементам структуры можно использовать операцию выбора компонентов структурного объекта ->
<имя указателя->имя элемента структуры
<Например,
<st->group= 222; //это равносильно (*st).group=222;
<Инициализировать конкретную структуру можно только при описании перечислением ее элементов в скобках {} в порядке их описания, например
<Для переменных одного и того же структурного типа определена операция присваивания, то есть поэлементное копирование, например s3=s1;
<Часто в качестве поля структуры используют объединения. Объединение представляет собой частный случай структуры, все поля которой располагаются по одному и тому же адресу. Формат описания такой же, но используются ключевое слово union. Размер объединения равен наибольшему размеру из его полей.
<Основное достоинство объединения – возможность разных трактовок одного и того же содержимого участка памяти.
<Например,
<union
<{
< float a;
< unsigned int b;
<}ab;
<Если ввести ab.a=3.78, то затем можно рассматривать код его представления как беззнаковое целое cout<<ab.b;
<Основное назначение объединения – обеспечить возможность доступа к одному и тому же участку памяти с помощью объектов разных типов.
Пример. Описать структуру СОТРУДНИК с полями ФАМИЛИЯ, ГОД_РОЖДЕНИЯ, ПОЛ. Для женщин – указывать количество детей, для мужчин – отношение к военной службе. Ввести данные о сотруднике и вывести их на экран.
<# include <iostream.h>
<# include <conio.h>
<{
< 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), содержащую по крайней мере два поля: для хранения данных и для указателя на этуже структуру. Полей данных и указателей может быть несколько. Например, элемент списка целых чисел имеет вид
<{
< el *b;
<}
<Каждая динамическая структура характеризуется, во-первых, взаимосвязью элементов, и, во-вторых, набором типовых операций над этой структурой. В случае динамической структуры важно решить следующие вопросы:
- <каким образом может расти и сокращаться данная структура;
- <каким образом можно включить в структуру новый и удалить существующий элемент;
- <как можно обратиться к конкретному элементу структуры для выполнения над ним определенной операции. (Доступ по индексу здесь, очевидно, менее удобен, чем это было в случае массивов, так как любой элемент при изменении размеров структуры может изменить свою позицию. Поэтому обычно доступ к элементам динамической структуры относительный: найти следующий (предыдущий) элемент по отношению к текущему, найти последний элемент и т.п.)
<Из динамических структур в программах чаще всего используют линейные списки, их частные случае – стеки и очереди, а также бинарные деревья.
<Самый простой способ связать множество элементов – сделать так, чтобы каждый элемент ссылался на следующей. Такую динамическую структуру называют однонаправленным (односвязанным) линейным списком. Если каждый элемент структуры содержит ссылку как на следующий, так и не предыдущий, то говорят о двунаправленном (двусвязанном) линейном списке. Создадим однонаправленный список студентов и их оценок. Каждый элемент списка будет иметь следующий вид:
<{
< char *fio;
< int mark;
< student *next;
<}
<Для формирования списка требуется иметь по крайней мере один указатель – на начало списка (голова списка).
<и один вспомогательный указатель student *adr;.
<Опишем процедуру создания списка
<{
< int n;
< cout<< “Введите количество студентов ”;
< cin>>n;
< const int dlin=20;
< char f[dlin]; // вспомогательный массив для хранения
< // введенной фамилии студента
<{
< 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 и последний созданный элемент делая головой списка.
<{
< int n;
< cout<< “Введите количество студентов ”;
< cin>>n;
< const int dlin=20;
< char f[dlin]; // вспомогательный массив для хранения
< // введенной фамилии студента
< {
< 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;
< }
<}
<Чтобы вывести на экран элементы списка, созданного любым из предложных способов, можно использовать следующую процедуру
<{
< adr=begin;
< while (adr!=NULL)
< {
< cout<<«\n «<<(adr->fio)<<» «<<adr->mark;
< adr=adr->next;
< }
<}
<Кроме процедур создания и вывода на экран для списка обычно определяют следующие процедуры:
- <добавления элемента в конец списка;
- поиска заданного элемента;
- вставка элемента до или после заданного элемента;
- сортировка списка;
- удаления заданного элемента;
- удаление списка.
