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

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

Программа = Алгоритм + Структуры данных.

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

Алгоритмы представляют собой объекты систематического исследования специальной науки – теории алгоритмов, которая находится на стыке двух других наук - математики и информатики.

Сам термин «алгоритм» произошел от латинской формы записи имени великого математика IX в. аль-Хорезми - «Algorithmi». Именно он первым сформулировал правила выполнения арифметических действий. Изначально алгоритмом называли только правила выполнения четырех арифметических действий над многозначными числами.

В настоящее время люди постоянно сталкиваются с решением различных практических задач: приготовление супа, проезд в общественном транспорте, решение квадратного уравнения, поиск слова в словаре и т. д. При этом человек выполняет заранее продуманные (им или кем-то еще) предписания: какие действия и в какой последовательности должны быть выполнены. Эта последовательность действий может рассматриваться как алгоритм решения соответствующей задачи [4].

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

Актуальность рассматриваемой темы очевидна - структуры данных являются необходимыми компонентами любой компьютерной программы или программного комплекса. Следовательно, знание теории структур данных и, в частности, методов представления данных на различных уровнях, а также возможных операций над этими структурами, необходимо для глубокого изучения и уяснения таких разделов, как автоматизированные системы управления, компиляторы языков программирования, операционные системы, а также системы программного имитационного моделирования, управления базами данных, искусственного интеллекта и т.д. [13]

Объект исследования данной работы - структуры хранения данных в языках программирования высокого уровня, с помощью которых и реализуются программы.

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

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

Для достижения поставленной цели необходимо решить ряд задач:

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

При написании работы в качестве опорных источников использовались: Е.А. Кумагина – «Введение в структуры данных» и А.А. Ключарев – «Структуры и алгоритмы обработки данных».

1. СТРУКТУРЫ ДАННЫХ

1.1. Основные понятия

Алгоритмом принято называть точное предписание, определяющее вычислительный процесс, который за конечное число итераций приводит к искомому результату [1].

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

Независимо от сложности и содержания все данные в компьютере представляются в виде последовательности двоичных разрядов – битов. Такие данные слабо структурированы. Кроме того, подобное представление данных очень неудобно для человека. Более крупные и содержательные блоки данных называются структурами данных [16].

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

1.2. Классификация

Классификация структур данных приведена на рисунке 1 [6].

Понятие «физическая структура данных» характеризует способ физического размещен данных в памяти компьютера. Синонимы данного термина:

структура хранения;
внутренняя структура;
структура памяти.

Рисунок 1 – Классификация структур данных

Абстрактная (логическая) логическая структура – структура данных без учета ее представления в памяти компьютера. В общем случае логическая и физическая структуры отличаются. Степень данного отличия определяется самой структурой и особенностями той среды, где она должна быть отражена. Данный факт является причиной существования особых процедур, осуществляющих отображение логической структуры данных в физическую, и наоборот. Эти процедуры обеспечивают доступ к физическим структурам и выполнение над ними различных операций, каждая из которых рассматривается применительно к физической или логической структуре данных. Кроме того, в зависимости от размещения физических структур, а следовательно, и доступа к ним, принято различать внешние (хранящиеся на внешних устройствах) и внутренние (расположенные в оперативной памяти) структуры данных.

Внутренние структуры данных бывают двух видов:

элементарные (простые) – такие структуры данных, которые не могут быть разделены на составные части, большие, чем биты. С точки зрения компьютерного представления важно отметить, что каждая конкретная машинная архитектура с конкретной системой программирования всегда однозначно определяет размер элементарных данных и способ их размещения в памяти. С логической точки зрения элементарные данные – это неделимые единицы;
составные (сложные) – такие структуры данных, которые состоят из элементарных или составных структур. Эти структуры определяются программистами при помощи специальных средств, предоставляемых языками программирования. Характерным признаком составной структуры является упорядоченность ее элементов. По этому признаку структуры делятся на линейные и нелинейные [5].

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

Тип данных определяет:

структуру хранения данных – выделение памяти, способ представления данных, методы доступа;
область допустимых значений;
набор допустимых операций, применимых к данным [7].

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

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

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

К динамическим структурам относят:

односвязные (однонаправленные списки);
двусвязные (двунаправленные списки);
циклические списки;
стек;
дек;
очередь;
бинарные деревья [19].

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

2. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

2.1 Связный список

Если в рамках программы требуется хранить неупорядоченное множество элементов, число которых заранее известно, в таких случаях применяются массивы данных. Однако если количество элементов постоянно меняется, то в таких случаях для хранения используются динамические структуры [2].

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

односвязные;
двусвязные;
XOR-связные;
кольцевые.

В односвязном списке полем связки является поле «next», указывающее на следующий элемент списка (поле содержит адрес следующего элемента). Такой элемент называется ссылочным и определяет ссылочный тип списка. Эти списки также называются однонаправленными. Двусвязные списки используют еще дно поле – «prev», указывающее на предыдущий элемент списка.

Если элемент списка не связан ни с каким другим элементов, в поле указателя хранится значение NULL.

Указатель на первый элемент списка - особый элемент, называемый головой списка («head»).

Структура односвязного линейного списка приведена на рисунке 2.

Рисунок 2 – Структура односвязного линейного списка

Структура односвязного кольцевого списка приведена на рисунке 3.

Рисунок 3 – Структура односвязного кольцевого списка

Структура двусвязного линейного списка приведена на рисунке 4.

XOR-связный список представляет собой структуру данных, похожую на обычный двусвязный список. Основное отличие заключается в том, что в каждом элементе хранится только один адрес – результат выполнения операции XOR (исключающее или, сложение по модулю два) над адресами предыдущего и следующего элементов списка (см. рисунок 5).

Рисунок 4 - Структура двусвязного линейного списка

Рисунок 5 – Структура XOR списка

При инициализации XOR списка необходимо создавать два пустых элемента - текущий и предыдущий, чтобы при добавлении первого элемента вычислить его адрес [12].

Для добавления элемента в односвязный линейный список необходимо выполнить ряд шагов:

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

Самый простой вариант добавления элемента – в начало списка. В данном случае «next» нового элемента ссылается на существующий элемент головы, после чего указатель головы списка переносится на вновь созданный элемент (см. рисунок 6).

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

Второй вариант – добавление элемента в конец списка. В этом случае необходимо просмотреть весь список, найти его последний элемент и изменить ссылку со значения NULL на вновь созданный элемент. При этом ссылка «next» нового элемента будет равна NULL (см. рисунок 7).

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

Схема добавления элемента в середину списка приведена на рисунке 8. Данный алгоритм предполагает выполнение следующих шагов:

поле «next» нового элемента сослать на элемент, перед которым реализуется вставка;
поле «next» элемента, после которого реализуется вставка, сослать на вновь созданный элемент [18].

Рисунок 8 – Добавление элемента в середину списка

Операция удаления элементов также представляет собой последовательность нескольких шагов: