Связанные динамические данные. Списки

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

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

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

Динамические переменные, как правило, имеют тип «ЗАПИСЬ», так как должны содержать, помимо значения (целого, вещественного), ссылку на другую динамическую переменную связанной структуры.

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

Схематично такую структуру данных можно показать следующим образом:

Соответствующие ей объявления записываются как

Type

Tptr=^Telem; {ссылка на динамическую переменную}

Telem = Record

info: integer;

next: Tptr; {указатель}

End;

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

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

р

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

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

1) добавление элемента в начало;

2) добавление элемента в конец (хвост) списка (частный случай вставки);

3) вставка элемента между двумя любыми другими элементами;

4) исключение элемента (удаление любого, как крайнего, так и среднего элемента списка).

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

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

Program spis0b; {файл spis0b.pas с адресами}

Type sv = ^struct;

Struct = record

key: integer; {ключевое поле}

next: sv {указатель на следующий элемент}

end;

Var p,t,q: sv;

x: integer;

BEGIN

p:= nil; { указатель на начало}

q:= nil; { указатель на конец}

writeln('Введите элемент (Число больше 999 - признак конца)');

read(x); {ввод первого элемента}

while x<=999 do

begin

new(t); {создание нового элемента списка, t - текущее значение указателя}

t^.key:=x; {заполнение ключевого поля}

if (p=nil) then q:=t; {признак конца}

t^.next:=p;

writeln(' ', longint(t^.next)); { вывод адреса}

p:=t; { writeln(ptr(сегмент,смещение)); p-через Wath }

read(x); {ввод очередного элемента}

end;

writeln('элемент - адрес');

while t<>nil{не пусто} do

begin

writeln(t^.key:6,' / ', longint(t^.next)); { dispose(t);}

t:=t^.next; { \ нельзя печатать сам указатель}

end;

END.

Пример 2. Подсчитать число вхождений буквы 't' в заданное слово, завершающееся точкой.

Program spis1atp; {spis1a.pas +}

Type

sv{связь}= ^zv; {звено строки}

Zv = record

info: char; {Информационное поле}

next: sv {Указатель на следующий элемент}

end;

Var P {Указатель на начало}, t {Указатель на текущее звено}: sv;

sym: char;

k: integer;

BEGIN {Формирование заглавного звена}

new(p);

t:=p;

p^.next:=nil; {резервирование памяти}

read(sym); {Чтение первого символа}

Write('Введи остальные символы и точку ');

while sym<>'.' do {Цикл обработки последовательных литер строки}

begin

new(t^.next);

t:=t^.next; {адрес следующего}

t^.info:=sym;

t^.next:=nil;

read(sym)

end; {Исходное слово представлено в виде цепочки}

k:=0; t:=p; {Подсчет}

while t<>nil do

begin

t:=t^.next;

if t^.info='t' then k:=K+1;

end;

Writeln;

Writeln('Буква t входит в слово ',k,' раз');

END.

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

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

Для вставки элемента необходимо:

а) создать новый динамический объект, которым будет представлено новое звено;

б) в ключевое поле key внести значение (литеру),

в) в поле next занести ссылку, взятую из поля next того звена, за которым должно следовать вставляемое;

г) в поле next звена, за которым следует вставка, занести ссылку на это вставляемое звено.

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

Для работы со связными структурами были разработаны 3 основных динамических структуры, объединенные под общим термином списки.

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

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

начало списка конец списка

р

q

элементы списка

Обязательно должен быть указатель на заглавное звено.

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

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

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

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

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

Дата добавления: 2015-09-05