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

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

Описание данных односвязного списка

type

p_elem = ^element;

element = record

data: string[15];

next: p_elem;

end;

var

head, current, last : p_elem;

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

new(current);

current^.data:= ’данные в первом элементе списка ’;

current^.next:=nil;

Создание следующего элемента и связывание его с первым элементом

head:=current;

new(last);

last^.data:= ’данные во втором элементе списка ’;

last^.next:=nil;

current^.next:=last;

Создание списка из n элементов

head:= nil;

for i:=1 to n do

begin

new(current);

readln(current^.data);

current^.next:=nil;

if head=nil then

head:=current

else

last^.next:= current;

last:= current;

end;

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

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

dispose(current);

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

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

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

Описание двусвязного списка

type

listPtr = ^list;

list = record

number, data: integer;

next, prev: listPtr;

end;

Удобно иметь поле для хранения порядкового номера элемента (number).

5.1.4. Общие алгоритмы основных действий над линейными списками.

Получение доступа к k-му элементу списка для считывания и/или изменения его значения

• Перейти на первый элемент, он становится текущим.

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

Вставка нового элемента списка после k-го элемента

• Произвести переход на k-ый элемент.

• Сохранить адрес k-ого элемента в указатель.

• Создать новый элемент.

• Установить ссылки на новый элемент и с него на последующий.

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

Удаление k-го элемента списка

• Произвести переход на k-ый элемент.

• Переадресовать ссылки (k-1)-го – предыдущего (и (k+1)-го – последующего) элемента так, чтобы текущий элемент исключался.

• Удалить из памяти k-ый элемент.

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

Упорядочивание элементов списка

К спискам применимы все методы сортировки, применяемые к массивам.

Поиск элемента списка с данным значением

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

5.2. Циклические (кольцевые) списки

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

5.2.1. Односвязный циклический список.

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

5.2.2. Двусвязный циклический список.

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

6. Организация данных

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

6.1. Организация данных – стек.

Стек представляет собой организацию данных, из которой первым извлекается тот элемент, который был добавлен в нее последним, т. е. последовательность элементов, включение и исключение элементов из которой производится только с одного конца, т. е. доступ к элементам происходит по принципу LIFO – last in first out.

6.1.1. Представление стека в виде списка.

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

Если стек пуст, то списка не существует, и указатель стека принимает значение nil.

Операция добавления нового элемента (запись в стек) называется операцией проталкивания в стек и имеет общепринятое название Push.

Операция исключения элемента из вершины стека (удаление элемента) называется операцией выталкивания из стека и имеет общепринятое название Pop.

Для работы со стеками на основе списка необходимо иметь один основной указатель на вершину стека (Тор) и один дополнительный временный указатель (Р), который используется для выделения и освобождения памяти элементов стека.