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

В языке Паскаль имеется главное правило: прежде чем использовать какой-то объект, его нужно описать. Исключение составляют лишь указатели, которые могут иметь ссылки на еще не объявленные типы.

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

New (a); {выделяется место в памяти}

a^.Next:= nil; {указатель пустой}

a^.Inf:=3;

Продолжаем формирование списка. Для этого необходимо добавление элемента либо в конец списка, либо в его голову.

А) Добавляем элемент к голове списка. Для этого нужно выполнить следующую последовательность действий:

получение памяти для нового элемента;
помещение туда информации;
присоединение элемента к голове списка.

New(x);

Readln(x^.Inf);

x^.Next:= a;

a:= x;

Б) Добавление элементов в конец списка. Для этого вводится вспомогательная переменная, которая хранит адрес последнего элемента. Например, это будет указатель с именем hvost (хвост) (рис. 3).

x:=hvost;

Рисунок 3. Добавление элемента

New( x^. next); {выделяется память для следующего элемента}

x:=x^.next;

x^.next:=nil;

x^.inf:=5;

hvost:=x;

Просмотр списка:

While a<>nil do

Begin

Writeln (a^.inf);

a:=a^.next;

End;

Удаление элемента из списка.

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

Рисунок 4.Удаление элемента 1

x:=a;

a:=a^.next;

dispose(x);

Б) Удаление элемента из середины списка. Для этого необходимо знать адрес удаляемого элемента и адрес элемента, который стоит перед ним. Например, dig – это значение элемента, который удаляем (рис. 5).

Рисунок 5. Удаление элемента 2

x:=a;

while ( x<> nil) and ( x^. inf<> dig) do

begin

dx:=x;

x:=x^.next;

end;

dx:=x^.next:

dispose(x);

В) Удаление из конца списка. Для этого необходимо найти предпоследний элемент.

x:=a; dx:=a;

while x^.next<>nil do

begin

dx:=x; x:=x^.next;

end;

dx^.next:=nil;

dispose(x);

Прохождение списка. Существенно уметь перебирать все элементы в списке и выполнять над ними какую-то операцию. Например, нужно найти сумму всех элементов в списке:

sum:=0;

x:=a;

while x<>nil do

begin

sum:= sum+x^.inf;

x:=x^.next;

end;

Использование однонаправленного списка при решении некоторых задач может вызывать некоторые трудности. Все дело в том, что по однонаправленным спискам возможно движение только в одном направлении, от его головы к последнему элементу. Но иногда возникают необходимости произведения каких-либо операций с элементами, предшествующими элементу с заданными свойствами. Тем не менее после нахождения элемента с данными свойствами в однонаправленных списках нет возможности получения удобного и быстрого способа доступа к предыдущим элементам [12].

2.2. Двунаправленные списки

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

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

Рисунок 6. Двунаправленный список

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

Описать элемент двунаправленного списка можно следующим образом:

Type ukazatel=^P;

P=record

Inform: integer;

Next: ukazatel;

Pred: ukazatel;

End;

В динамические структуры, в нашем случае двунаправленный список, легко добавлять элементы. Для этого достаточно изменить значения адресных полей. Операция вставки реализовывается аналогично функции вставки для однонаправленного списка, только с учетом особенностей двунаправленного списка (рис. 7).

Рисунок 7. Добавление элемента в двунаправленный список

Можно удалять элементы. Данная операция удаления элемента из двунаправленного списка во многом аналогична удалению из однонаправленного списка (рис. 8.).

Рисунок 8.Удаление элемента из двунаправленного списка

Поиск элемента в двунаправленном списке ведется:

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

Таким образом, двунаправленные списки являются расширением однонаправленных списком, сохраняя при всем своем своеобразии свойства [14].

2.3. Циклические списки

Циклический список отличается тем, что в списке такого типа нет пустых указателей, отсутствует NIL (рис. 9). Как и линейные списки, циклические списки могут быть однонаправленными или двунаправленными.

Рисунок 9. Однонаправленный циклический список

В случае представленном на рисунке 9, последний элемент нашего циклического однонаправленного списка содержит в себе указатель, который связывает его с первым элементом списка. Чтобы полностью «обойти» такой список, достаточно всего лишь иметь указатель на текущий элемент [15].

Что касается двунаправленного циклическом списка, то здесь система указателей полностью аналогична работе указателей линейного двунаправленного (см. рис. 10).

Рисунок 10.Двунаправленный циклический список

Двунаправленные циклические списки позволяют нам достаточно легко осуществлять добавление и удаление элементов справа и слева от текущего элемента. Все элементы циклического списка, В отличие от линейного списка, являются по отношению друг к другу равноправными. Чтобы выделить первый элемент нужно иметь указатель на заголовок. Но все же в большинстве случаев нет такой необходимости, достаточно просто иметь указатель на текущий элемент списка [16].

2.4. Мультисписки

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

Мультисписок состоит из элементов, которые содержат то количество указателей, которое позволяет одновременно организовать их в виде нескольких разных списков. Тем самым мы не допускаем дублирование, вследствие чего более рационально используем память (рис. 11).

Рисунок 11. Объединение двух линейных списков в один мультисписок

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

2.5. Очередь и дек

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

Рисунок 12. Организация дека на основе двунаправленного линейного списка

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

Рисунок 13. Дек с ограниченным входом на основе двунаправленного списка

Рисунок 14. Дек с ограниченным выходом на основе двунаправленного линейного списка

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

Деки с ограниченными входами могут быть использованы как простые очереди или стеки [19].

2.6. Стек

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

Для такого списка достаточно хранить указатель вершины стека, который указывает на первый элемент списка. Если стек пуст, то списка не существует и указатель принимает значение NIL.

Рисунок 15. Организация стека на основе линейного списка.

Глава 3. Практическая часть

3.1. Постановка задачи

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

Задача:

Необходимо сформировать связанный однонаправленный список путем добавления последующих элементов в конец списка. Пусть элементами списка будут являться целые числа: 7, 2, 1 и 9.

3.2. Решение поставленной задачи

Для того чтобы сформировать связанный однонаправленный список сначала определим запись типа element, в котором будут находиться два поля – информационное поле, которое будет содержать в себе данные (по условию задачи это будут целые числа 7, 2, 1 и 9), и адресное поле, в нем будет находиться адрес следующего от текущего элемента списка.

type

pointer = ^element

element = record

data : integer;

next : pointer;

end;

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

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

В решении задачи будем использовать переменные:

var list_header, x: pointer;

где: list_header – указатель на первый элемент списка, его начало; x – указатель, играющий вспомогательную роль при создании следующего элемента списка.