Способы представления динамических структур в языках программирования высокого уровня. Организация динамической памяти типа стек (создание, чтение, добавление).
Динамические цепочки
Являются аналогами строк переменной длины. В строке каждый следующий элемент занимает ячейку памяти со следующим по порядку адресом. Элементы строки можно разместить произвольно, если каждый элемент снабдить явным указанием месторасположения следующего элемента. Тогда каждый элемент строки будет состоять из двух полей: литера строка и ссылка на следующий элемент.
type
Adr = ^Zveno;
Zveno = record
AdrSled: Adr;
Element: Char;
end;
Каждая такая пара называется звеном. Ссылки сцепляют звенья в цепочку. Такой способ представления упорядоченной последовательности элементов называется сцеплением. Последний элемент в цепочке равен nil.
Для работы с цепочкой должна использоваться ссылка на первое звено цепочки. Для удобства работы с цепочкой в нее обычно вводится заглавное звено. Поле AdrSled содержит адрес первого звено, а в поле Element – любую полезную информацию.
Недостаток – движение возможно только в одном направлении.
Динамические цепочки есть подвид однонаправленных списков. В общем случае элемент однонаправленных списков есть объект произвольного типа.
type
Adr1 = ^Zveno1;
Zveno1 = record
AdrSled: Adr1;
Element: <тип элемента списка>;
end;
Двунаправленные списки
Позволяют от любого звена двигаться в двух направлениях. Каждое звено содержит 2 поля ссылочного типа: ссылку на следующий и предыдущий элемент. Структура звена:
type
Adr2 = ^Zveno2
Zveno2 = record
AdrSled: Adr2;
AdrPred: Adr2;
Element: <тип элемента списка>;
end;
На основе двунаправленных списков формируются двунаправленные кольцевые списки. Здесь возможны два способа использования заглавного звена:
- заглавное звено включается в список;
- заглавное звено не включается в список.
Очереди и стеки
Очередь есть однонаправленный список, над которым определены только две операции: занесение и выборка элементов. Различают 2 вида очередей, отличающихся по дисциплине обслуживания:
- FIFO (первый пришел, первый вышел) – нормальная очередь;
- LIFO (последний пришел, первый вышел) – стек.
В очереди доступны два элемента: начало (из нее осуществляется выборка) и конец (для занесения нового элемента). В стеке эти элементы совпадают.
Наиболее быстрое выполнение операций обеспечивает представление стека в виде однонаправленного списка. Вершиной стека обычно является первое звено списка. Заглавное звено в стеке не используется. Описание структуры элемента идентично описанию элемента однонаправленного списка. Дополнительно может быть введен тип указатель, представляющий стек как единый объект.
Type
(* см. описание типа Adr1 в главе Динамические цепочки *)
Stek = Adr1;
Var
St: Stek;
В начале работы стек необходимо сделать пустым:
St:= nil;
Двоичное дерево
Реализация в виде двоичного дерева позволяет эффективно организовать все 3 операции над таблицами. Схематически оно представляется в виде набора вершин, соединенных направленными дугами. Из каждой вершины выходит не более двух ветвей. В каждую ветвь, кроме корня, входит одна ветвь. Структура элемента:
Type
PElem = ^Elem
Elem = record
Left: Pelem;
Right: Pelem;
Code: <тип ключа>;
Element: <тип элемента списка>;
End;
Виды очередей
Очередь есть однонаправленный список, над которым определены только две операции: занесение и выборка элементов. Различают 2 вида очередей, отличающихся по дисциплине обслуживания:
- FIFO (первый пришел, первый вышел) – нормальная очередь,
- LIFO (последний пришел, первый вышел) – стек.
В очереди доступны два элемента: начало (из нее осуществляется выборка) и конец (для занесения нового элемента). В стеке эти элементы совпадают.
Для организации очереди FIFO используются две ссылочные переменные типа Adr1: Left, Right. Left ― для указания начала очереди, Right ― для указания конца очереди. Добавление элементов в очередь осуществляется в соответствии со значением Right. Затем значение Right изменяется и указывает на последний занесенный элемент. Выборка элементов из очереди происходит, исходя из значения Left. Затем Left меняется и указывает на следующий элемент очереди.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
Занесение элемента в стек
Алгоритм:
1. Создание нового звена.
2. Занесение в новое звено элемента.
3. Занесение в новое звено адреса предыдущей вершины стека.
4. Созданное звено сделать вершиной стека.
Пример.
New(Q);
Q^.Element:= Elem;
Q^.AdrSled:= St;
St:= Q;
Выбор
Алгоритм:
1. Прочитать значение из вершины стека
2. Запомнить ссылку на старую вершину
3. Исключить первое звено из стека
4. Уничтожить первое звено
Пример.
A:= St^.Element;
Q:= St;
St:= St^.AdrSled;
Dispose(Q);
Создание очереди
Перед созданием очереди Left и Right устанавливаются в nil. Затем заносится первый элемент и созданный элемент сделать началом очереди.
Занесение элемента
Алгоритм:
1. Создание нового звена
2. Занесение в последнее звено адреса нового элемента
3. Занесение nil в поле AdrSled нового звена
4. Занесение элемента в новое звено
5. Созданное звено сделать концом очереди
Пример.
New(Q);
Right^.AdrSled:= Q;
Q^.AdrSled:= nil;
Q^.Element:= El;
Right:= Q;
Выбор элемента
Алгоритм:
1. Прочитать значение из начала очереди
2. Запомнить ссылку на начало очереди
3. Исключить первое звено из начала очереди
4. Уничтожить первое звено
Пример.
Elem:= Left^.Element;
Q:= Left;
Left:= Left^.AdrSled;
Dispose(Q);
СОДЕРЖАНИЕ РАБОТЫ:
Написать алгоритм и отладить программу.
| Вариант | Задание |
| №1 | Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке. Сведения о каждом автобусе содержат: ― номер автобуса; ― фамилию и инициалы водителя; ― номер маршрута. Программа должна обеспечивать следующие функциональные возможности: ― начальное формирование данных обо всех автобусах в парке в виде двоичного дерева. |
| №2 | Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке. Сведения о каждом автобусе содержат: ― номер автобуса; ― фамилию и инициалы водителя; ― номер маршрута. Программа должна обеспечивать следующие функциональные возможности: ― начальное формирование данных обо всех автобусах в парке в виде стека. |
| №3 | Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке. Сведения о каждом автобусе содержат: ― номер автобуса; ― фамилию и инициалы водителя; ― номер маршрута. Программа должна обеспечивать следующие функциональные возможности: ― начальное формирование данных обо всех автобусах в парке в виде списка. |
| №4 | Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: ― номер УДК; ― фамилию и инициалы автора; ― название; ― год издания; ― количество экземпляров данной книги в библиотеке. Программа должна обеспечивать следующие функциональные возможности: ― начальное формирование данных обо всех книгах в библиотеке в виде списка. |
| №5 | Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: ― номер УДК; ― фамилию и инициалы автора; ― название; ― год издания; ― количество экземпляров данной книги в библиотеке. Программа должна обеспечивать следующие функциональные возможности; ― начальное формирование данных обо всех книгах в библиотеке в виде стека. |
| Вариант | Задание |
| №6 | Составить программу, которая содержит текущую информацию о заявках на авиабилеты. Каждая заявка содержат: ― пункт назначения; ― номер рейса; ― фамилию и инициалы пассажира; ― желаемую дату вылета. Программа должна обеспечивать следующие функциональные возможности очереди. |
| №7 | Составить программу, которая содержит текущую информацию о заявках на авиабилеты. Каждая заявка содержат: ― пункт назначения; ― номер рейса; ― фамилию и инициалы пассажира; ― желаемую дату вылета. Программа должна обеспечивать следующие функциональные возможности; ― хранение всех заявок в виде стека. |
| №8 | Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке. Сведения о каждом автобусе содержат: ― номер автобуса; ― фамилию и инициалы водителя; ― номер маршрута. Программа должна обеспечивать следующие функциональные возможности; ― начальное формирование данных обо всех автобусах в парке в виде стека. |
| №9 | Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке. Сведения о каждом автобусе содержат: ― номер автобуса; ― фамилию и инициалы водителя; ― номер маршрута. Программа должна обеспечивать следующие функциональные возможности; ― начальное формирование данных обо всех автобусах в парке в виде списка. |
| №10 | Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: ― номер УДК; ― фамилию и инициалы автора; ― название; ― год издания; ― количество экземпляров данной книги в библиотеке. Программа должна обеспечивать следующие функциональные возможности; ― начальное формирование данных обо всех книгах в библиотеке в виде списка. |
| №11 | Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: ― номер УДК; ― фамилию и инициалы автора; ― название; ― год издания; ― количество экземпляров данной книги в библиотеке. Программа должна обеспечивать следующие функциональные возможности; ― начальное формирование данных обо всех книгах в библиотеке в виде стека. |
| Вариант | Задание |
| №12 | Составить программу, которая содержит текущую информацию о заявках на авиабилеты. Каждая заявка содержат: ― пункт назначения; ― номер рейса; ― фамилию и инициалы пассажира; ― желаемую дату вылета. Программа должна обеспечивать следующие функциональные возможности; ― хранение всех заявок в виде списка. |
| №13 | Составить программу, которая содержит текущую информацию о заявках на авиабилеты. Каждая заявка содержат: ― пункт назначения; ― номер рейса; ― фамилию и инициалы пассажира; ― желаемую дату вылета. Программа должна обеспечивать следующие функциональные возможности; ― хранение всех заявок в виде стека. |
| №14 | Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке. Сведения о каждом автобусе содержат: ― номер автобуса; ― фамилию и инициалы водителя; ― номер маршрута. Программа должна обеспечивать следующие функциональные возможности; ― начальное формирование данных обо всех автобусах в парке в виде стека. |
| №15 | Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке. Сведения о каждом автобусе содержат: ― номер автобуса; ― фамилию и инициалы водителя; ― номер маршрута. Программа должна обеспечивать следующие функциональные возможности; ― начальное формирование данных обо всех автобусах в парке в виде списка. |
| №16 | Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: ― номер УДК; ― фамилию и инициалы автора; ― название; ― год издания; ― количество экземпляров данной книги в библиотеке. Программа должна обеспечивать следующие функциональные возможности; ― начальное формирование данных обо всех книгах в библиотеке в виде списка. |
ВОПРОСЫ ВЫХОДНОГО КОНТРОЛЯ:
1. Опишите операции с указателями.
2. Приведите примеры динамических переменных.
ДОМАШНЕЕ ЗАДАНИЕ
Выучить определение указателей, их описание, динамические переменные. Изучение примеров работы с динамическими переменными.
