Файл: Динамические структуры данных. Списки (Основные понятия).pdf

Стеком называется структура данных, в которой новый элемент всегда помещается в начало списка, и при чтении также берется из начала, реализуя алгоритм LIFO (Last In – Firs Out).

Схема представления стека приведено на рисунке 11.

Рисунок 11 – Стек

В основе стека лежит динамический список. С учетом того, что работа всегда ведется только с головным элементом, исчезает необходимость просмотра элементов стека.

Очередь – это структура данных, представляющая собой последовательность элементов, образованная в порядке их поступления. Данный вид структуры реализует алгоритм FIFO (First In – First Out).

Частный случай очереди – дек (двусторонняя очередь). Схема реализации очереди представлена на рисунке 12.

Рисунок 12 – Очередь

Очередь также реализуется на базе линейного списка. Важно учесть, что работа здесь ведется как с началом, так и с концом очередь, следовательно, необходимо хранить два указателя – на голову и на хвост списка [9].

2.3. Деревья

Ссылки могут использоваться не только для представления линейных списков, возможны и другие способы – например, структуры, состоящие из записей, связанных между собой системой ссылок. При этом каждая запись может содержать ссылки на несколько других записей. Подобное представление называется ориентированным графом [3].

Дерево – частный случай графа. Дерево обладает следующими свойствами:

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

Схема представления дерева приведена на рисунке 13.

Рисунок 13 – Дерево

Здесь узел А – это корень дерева. Узлы Г, Д, Е, И, К, Л – листья дерева (терминальные узлы).

Частным случаем дерева, которое наиболее часто используется в программировании, является двоичное (бинарное) дерево. Каждый узел такого дерева имеет не более двух узлов-отростков (см. рисунок 14) [20].

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

Существует несколько способов обхода дерева (просмотра всех его элементов):

обход в глубину – посетить корень дерева, обойти левое поддерево, обойти правое поддерево;
обход в ширину – данный метод основан на использовании очереди. Алгоритм обхода:

Рисунок 14 – Двоичное дерево

- изъять из очереди очередную вершину. Поместить в очередь ее дочерние вершины по порядку;
- если очередь пуста – конец обхода, иначе перейти к п.1 [11].

Таким образом, в рамках данной главы рассмотрены динамические структуры данных. Приведена их классификация по нескольким признакам. Отдельное внимание уделяется динамическим структурам данных – спискам и деревьям.

3. ПРАКТИЧЕСКАЯ ЧАСТЬ

3.1. Линейный односвязный список

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

значение элемента списка;
указатель на следующий элемент списка.

Таким образом, в разрабатываемом классе содержится всего один элемент – указатель на голову списка, а также необходимо предусмотреть методы:

конструктор;
деструктор;
добавление элемента в начало списка;
добавление элемента в конец списка;
удаление из списка последнего элемента;
поиск элемента по значению;
вывод содержимого списка на экран.

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

public: struct Node //описание узла - элемента списка

{

int value; //значение

struct Node *next; //ссылка на следующий элемент

} *head;

В данной записи head – это и есть указатель на первый элемент списка.

Методы класса:

Spisok() – конструктор без параметров;
Spisok(int val) – конструктор с параметром;
~Spisok() – деструктор;
void AddAtBegin(int val) – добавление элемента в начало списка;
void AddAtEnd(int val) – добавление элемента в конец списка;
void Delete() – удаление из списка последнего элемента;
int Search(int val) – поиск элемента по значению;
void Show() – вывод содержимого списка на экран.

Блок-схемы методов представлены на рисунках 15-21.

Рисунок 15 – Блок-схема конструктора

Рисунок 16 – Блок-схема деструктора

Рисунок 17 - Блок-схема метода добавления элемента в конец списка

Рисунок 18 - Блок-схема метода добавления элемента в начало списка

Рисунок 19 - Блок-схема метода удаления элемента из конца списка

Рисунок 20 - Блок-схема метода поиска элемента по значению

Рисунок 21 - Блок-схема метода вывода списка на экран

Для тестирования методов класса было создано приложение, исходный код которого надохится в приложении 1. Результаты тестирования программы представлены на рисунках 22-36.

Рисунок 22 – Окно запуска приложения

Рисунок 23 – Попытка просмотра пустого списка

Рисунок 24 – Попытка удаления из пустого списка

Рисунок 25 – Добавление элемента в начало списка

Рисунок 26 – Результат добавления элемента в начало списка

Рисунок 27 – Просмотр содержимого списка

Рисунок 28 – Добавление элемента в конец списка

Рисунок 29 – Результат добавления элемента в конец списка

Рисунок 30 – Просмотр содержимого списка

Рисунок 31 – Удаление последнего элемента

Рисунок 32 – Просмотр содержимого списка после удаления

Рисунок 33 – Поиск отсутствующего элемента

Рисунок 34 – Результат поиска отсутствующего элемента

Рисунок 35 – Поиск существующего элемента

Рисунок 36 – Результат поиска существующего элемента

3.2. Циклический двусвязный список

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

значение элемента списка;
указатель на следующий элемент списка;
указатель на предыдущий элемент списка.

конструктор;
деструктор;
добавление элемента в начало списка;
добавление элемента в конец списка;
удаление из списка последнего элемента;
поиск элемента по значению;
вывод содержимого списка на экран.

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

public: struct Node //описание узла - элемента списка

{

int value; //значение

struct Node *next; //ссылка на следующий элемент

struct Node *back; //ссылка на предыдущий элемент

} *head;

В данной записи head – это и есть указатель на первый элемент списка.

Методы класса:

Spisok() – конструктор без параметров;
Spisok(int val) – конструктор с параметром;
~Spisok() – деструктор;
void AddAtBegin(int val) – добавление элемента в начало списка;
void AddAtEnd(int val) – добавление элемента в конец списка;
void Delete() – удаление из списка последнего элемента;
int Search(int val) – поиск элемента по значению;
void Show() – вывод содержимого списка на экран.

Блок-схемы данных методов представлены на рисунках 37-

Рисунок 37 – Блок-схема конструктора

Рисунок 38 – Блок-схема деструктора

Рисунок 39 – Блок-схема метода добавления элемента в начало списка

Рисунок 40 – Блок-схема метода добавления элемента в конец списка

Рисунок 41 – Блок-схема метода удаления элемента из конца списка

Рисунок 42 – Блок-схема метода поиска элемента по значению

Рисунок 43 – Блок-схема метода вывода списка на экран

Для тестирования методов класса было создано приложение, исходный код которого надохится в приложении 2. Результаты тестирования программы представлены на рисунках 44-58.

Рисунок 44 – Окно запуска приложения

Рисунок 45 – Попытка просмотра пустого списка

Рисунок 46 – Попытка удаления из пустого списка

Рисунок 47 – Добавление элемента в начало списка

Рисунок 48 – Результат добавления элемента в начало списка

Рисунок 49 – Просмотр содержимого списка

Рисунок 50 – Добавление элемента в конец списка

Рисунок 51 – Результат добавления элемента в конец списка

Рисунок 52 – Просмотр содержимого списка

Рисунок 53 – Удаление последнего элемента

Рисунок 54 – Просмотр содержимого списка после удаления

Рисунок 55 – Поиск отсутствующего элемента