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

ВВЕДЕНИЕ



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

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

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

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

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

Современным людям необходимо постоянно решать различные практические задачи: от приготовления еды и проезда в общественном транспорте до решения сложных квадратных уравнений и программирования. Каждое из повседневных действий подчинено заранее продуманным предписаниям, а именно: определение необходимых шагов и последовательность  их выполнения. Именно такой  порядок и может быть рассмотрен как алгоритм к решению определенного задания [4].

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

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

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

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

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

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

провести анализ учебной и научной литературы по выбранной теме;

изучить и изложить основные понятия;

дать определение основным видам программных структур;

описать примеры динамических структур данных;

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

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



1.1. Основные определения

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

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

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

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

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

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

структура хранения;

внутренняя структура;

структура памяти.

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

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

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

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

Внутренние структуры классифицируют на следующие виды:

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

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

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

Тип данных характеризует:

структуры хранения данных – выделение памяти, способ представления данных, методы доступа;

область допустимых значений;

набор допустимых операций, применимых к данным [7].

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

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

поле данных;

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

Динамическими структурами являются:

односвязные (однонаправленные списки);

двусвязные (двунаправленные списки);

циклические списки;

стек;

дек;

очередь;

бинарные деревья [19].

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

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

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

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

односвязные;

двусвязные;

XOR-связные;

кольцевые. 

Односвязный список характеризуется полем связки типа «next», которое указывает на следующий элемент списка по его адресу, таким образом, они являются однонаправленными. 

Для двусвязных списков используют еще поле – «prev», которое указывает на предыдущий элемент списка по его адресу. 

Для элемента списка, который ни с каким элементом не, в поле указателя хранится значение NULL. 

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

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

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

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

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

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

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

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

Рисунок 5 – Структура XOR-связного списка



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

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

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

оформить вставку;

выполнить включение элемента в список.

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

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

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

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

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

поле «next» нового элемента должен ссылаться на элемент, перед которым выполняется вставка;

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

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

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

поиск элемента для удаления;

перестановка указателя;

удаление элемента.

Схема удаления элемента из середины списка приведена на рисунке 9.

Рисунок 9 – Удаление элемента из середины списка

Схема удаления элемента из головы списка приведена на рисунке 10 [10].

Рисунок 10 – Удаление элемента из головы списка

1.3. Стеки и очереди

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

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

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

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

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

Схема реализации очереди представлена на рисунке 12.

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

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

1.4. Деревья

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

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

подструктуры узла не связаны между собой;

наличие корня дерева;

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

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

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



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

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

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

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

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

обход в глубину – посетить корень дерева, обойти левое поддерево, обойти правое поддерево;

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

поместить в очередь корень дерева;

изъять из очереди очередную вершину. Поместить в очередь ее дочерние вершины по порядку;

если очередь пуста – конец обхода, иначе перейти к п.1 [11].

________________________________________________________________

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

Основные функции, реализуемые приложением:

вывод содержимого списка на экран;

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

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

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

поиск элемента по значению;

выход из программы [14].

ЗАКЛЮЧЕНИЕ



В рамках данной работы рассмотрена тема «Динамические структуры данных. Организация данных в списковые структуры».

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

Структура данных является неким множеством элементов данных с установленными между ними связями.

Физическая структура данных характеризуется способом физического размещения данных в компьютерной памяти.

Абстрактная (логическая) логическая структура не дает ее представления в памяти компьютера.

Динамические структуры данных – структуры, обладающие свойством изменчивости.

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

односвязные (однонаправленные списки);

двусвязные (двунаправленные списки);

циклические списки;

стек;

дек;

очередь;

бинарные деревья.

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

Основные функции, которое реализует созданное приложение:

вывод содержимого списка на экран;

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

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

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

поиск элемента по значению;

выход из программы.

















































11.......................