Линейные списки. Наиболее простой способ связать некоторое множество элементов - это организовать линейный список

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

Рис. 1.1. Линейный список (связанный список)

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

type

element = record

data: string;

next: pointer;

end;

var

head: pointer;

current, last: ^element;

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

В описании переменных описаны три указателя head, last и current. Head является не типизированным указателем. Указатель current является типизированным указателем, что позволяет через него организовать доступ к полям внутри элемента, имеющего тип element. Для объявления типизированного указателя обычно используется символ ^ (карат), размещаемый непосредственно перед соответствующим типом данных. Однако описание типизированного указателя еще не означает создание элемента списка. Рассмотрим, как можно осуществить создание элементов и их объединение в список.

В системе программирования Turbo Pascal для размещения динамических переменных используется специальная область памяти (heap-область). Heap-область размещается в памяти компьютера следом за областью памяти, которую занимает программа и статические данные, и может рассматриваться как сплошной массив, состоящий из байтов.

Попробуем создать первый элемент списка. Это можно осуществить при помощи процедуры New

New(Current);

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

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

Сurrent^.next:=nil;

Значение указателя nil означает пустой указатель. Обратим внимание на разницу между присвоением значения указателю и данным, на которые он указывает. Для указателей допустимы только операции присваивания и сравнения. Указателю можно присваивать значение указателя того же типа или константу nil. Данным можно присвоить значения, соответствующие декларируемым типам данных. Для того чтобы присвоить значение данным, после указателя используется символ ^(карат). Поле Сurrent^.next само является указателем, доступ к его содержимому осуществляется через указатель Current.

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

Head:=Current;

New(last);

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

Last^.next:=nil;

Сurrent^.next:=nil;

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

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

Head:=last;

Dispose(current);

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

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

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

Приведем пример программы, которая выполняет следующие операции с двунаправленным линейным списком:

· добавление (справа и слева от текущего);

· удаление (справа и слева от текущего);

· поиск;

· вывод списка.

program;

type element = record

data:string;

last, next: pointer;

end;

var

i,n: integer;

head: pointer;

current, pnt, pnt2: ^element;

s:string;

begin

new(current);

head:=current;

current^.data:=head;

current^.next:=nil;

current^.last:=nil;

repeat

writeln('1 – сделать текущим');

writeln('2 – список элементов');

writeln('3 – добавить справа');

writeln('4 – добавить слева');

writeln('5 – удалить текущий');

writeln('6 – удалить справа от текущего');

writeln('7 – удалить слева от текущего');

writeln('0 – выход');

writeln('текущий элемент: ', current^.data);

readln(n);

if n=1 then

{Выбор нового текущего элемента}

begin

writeln(''); readln(s);

pnt:=head;

repeat

if pnt^.data=s then current:=pnt;

pnt:=pnt^.next;

until pnt=nil;

end;

if n=2 then

{Вывод всех элементов}

begin

pnt:=head; i:=1

repeat

writeln(i, ▒ √ ▒, pnt^.data);

pnt:=pnt^.next;

i:=i+1;

until pnt=nil;

end;

if n=3 then

{Добавление нового элемента справа от текущего}

begin

writeln(▒элемент▓); readln(s);

new(pnt);

pnt^.data:=s;

pnt^.last:=current;

pnt^.next:=current^.next;

pnt2:=current^.next;

if not(pnt2=nil) then pnt2^.last:=pnt;

end;

if n=4 then

{Добавление нового элемента слева от текущего}

begin

writeln(▒элемент▓); readln(s);

new(pnt);

pnt^.data:=s;

pnt^.last:=current^.last;

pnt^.next:=current;

pnt2:=current^.last;

if not(pnt2=nil) then pnt2^.next:=pnt;

end;

if n=5 and not(current=head) then

{Удаление текущего элемента}

begin

pnt:=current^.last;

pnt^.next:=current^next;

pnt2:=current^.next;

if not(pnt2=nil) then pnt2^.last:=current^.last;

dispose(current);

end;

if n=6 and not(current^.next=nil) then

{Удаление элемента справа от текущего}

begin

pnt:=current^.next;

current^.next:=pnt^next;

pnt2:=pnt^.next;

if not(pnt2=nil) then pnt2^.last:=current;

dispose(pnt);

end;

if n=7 and not(current^.last=head) and not(current^.last=nil) then

{Удаление элемента слева от текущего}

begin

pnt:=current^.last;

current^.last:=pnt^.last;

pnt2:=pnt^.last;

if not(pnt2=nil) then pnt2^.next:=current;

dispose(pnt);

end;

until n=0;

end.

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

Поиск по сайту: