Организация списков в динамической памяти

3. Организация списков в динамической памяти

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

Рис. 1. Пример списковой структуры

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

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

Type element=^Ptr;

Ptr=record

d:integer;

link:element;

end;

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

Пример создания списка в обратном порядке (см. рис.2):

Рис. 2. Пример создания списка в обратном порядке

Var i,n,a:integer;

tek,nach:Ptr;

Begin

tek:=nil;

readln(n);

for i:=1 to n do

begin

readln(a);

new(nach);

nach^.d:=a;

nach^.link:=tek;{цепочка присоединяется к nach}

{*} tek:=nach;

end;

end;

Обратим внимание на вызов процедуры new(nach). В результате этого вызова в динамической памяти отводится место для переменной типа record, которая в нашем случае состоит из двух полей: для хранения целочисленного значения и значения указателя, т.е. адреса. Здесь важно представлять, что после того, как переменная nach (или какая другая) создана в динамической памяти, тем самым имеем ее адрес, который сам является именем переменной, т.е. nach. Если у нас имеется другая переменная того же типа, tek, то мы знаем также и ее адрес, это tek. Поэтому, если в адресную часть переменной nach занести адрес tek, тем самым мы свяжем элементы nach и tek: nach^.link:=tek.

Алгоритм создания списка в прямом направлении:

1. Создать первый элемент nach.

Ввести nach^.d; pred:=nach;

2. Создать текущий элемент tek.

Ввести tek^.d;

Установить связь предыдущего с текущим: pred^.link:=tek;

текущий элемент становится предыдущим: pred:=tek;

3. Если не конец списка, то перейти на 2.

Обнулить адресную часть последнего элемента: tek^.link:=nil.

Рис. 3. Пример создания списка в прямом направлении

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

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

tek:=nach;{Встали на начало списка}

while tek<>nil do

begin

wtiteln(tek^.d);{Вывести информационную часть}

tek:=tek^.link; {Шаг по связи}

end;

Рассмотрим еще раз строку tek:=tek^.link; . Ее можно интерпретировать по-другому: значению адреса tek присвоить то, что хранится в адресной части элемента tek, а там хранится адрес элемента, следующего за tek. Вообще нотацию tek^.link следует различать в контексте ее нахождения: если она стоит слева от присваивания, имеется ввиду сама адресная часть элемента tek, а если справа от присваивания – то, что хранится в адресной части tek. Таким образом, например, tek^.link:=tek^.link будет означать: в адресную часть tek занести адрес элемента, следующего за tek.

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

Алгоритм добавления элемента в начало списка:

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

Ввести информационную часть nov^.d.

2. Построить связь: nov^.link:=nach.

3. Новый элемент сделать начальным: nach=nov.

Рис. 4. Добавление элемента в начало списка

Нетрудно удалить первый элемент (nach:=nach^.link). Главное - не забыть физически удалить его из памяти (процедура Dispose).

Добавление элемента в середину списка: пусть переменная tek указывает на элемент, после которого необходимо вставить в список элемент nov. Сначала нужно заполнить связь у элемента nov: nov^.link:=tek^.link; затем соединить tek и nov: tek^.link:=nov.

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

Добавление элемента в конец списка (рис.6). Пусть переменная pos указывает на последний элемент списка, nov – добавляемый элемент. Тогда операция pos^.link:=nov соединяет элементы; присваивание nov^.link:=nil обнуляет адресную часть нового элемента.

Рис. 6. Добавление элемента в конец списка

Удаление элемента из середины списка. Пусть переменная pred - элемент, предшествующий удаляемому элементу. Необходимо идти по ссылке, хранящейся в pred в поле link (адрес удаляемого элемента), затем идти по ссылке link удаляемого элемента (а это адрес следующего за удаляемым). Полученное значение записать в поле link элемента pred: pred^.link:=pred^.link^.link.

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

Исключение последнего элемента. Пусть pos - последний элемент, pred– предыдущий перед последним. Тогда присваивание pred^.link:=nil исключит последний элемент из цепи (рис. 8).

Рис. 8. Исключение последнего элемента из списка

Умова задачі

16.13. Одно из возможных представлений «длинного» текста —это разделить его на участки (строки) равной длины и создать массив ссылок на эти строки:

const d=…; {длина строки}

 n=...; {максим, число строк}

type строка = array [l..d] of char,

 ссылка =^строка;

 текст = array [l..n] of ссылка;

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

Используя данное представление текста, описать:

а) функцию числострок(Т) для подсчета числа строк в тексте Т;

Алгоритм

Текст програми

program fwg;

uses crt;

const d=4;

n=40;

type stroka=array [1..d] of char;

nodepoint=^stroka;

Mas=array [1..n] of nodepoint;

Var f:text;

procedure kilkist(var k2:integer);

var ch:char;

begin

assign(f,'c:\f.txt');

reset(f);

k2:=0;

while not eof(f) do begin

read(f,ch);

k2:=k2+1;

end;

close(f);

end;

Function Kil(var cur1:mas):integer;

var i:integer;

begin

i:=1;

while (cur1[i]<>nil) and (i<>n) do begin

i:=i+1;

end;

kil:=i-1;

end;

procedure chut(var cur1:mas);

var ch:char;i,j:integer;

begin

Assign(f,'c:\f.txt');

reset(f);

for i:=1 to n do

cur1[i]:=nil;

i:=1;

while (not eof(f)) and (i<n+1) do begin

new(cur1[i]);

j:=1;

while (j<d+1) and (not eof(f)) do begin

read(f,ch);

write(ch);

Cur1[i]^[j]:=ch;

j:=j+1;

end;

i:=i+1;

end;

close(f);

end;

procedure Vuvod(cur2:mas);

var i,j,k3:integer;

begin

i:=1;

kilkist(k3);

while cur2[i]<>nil do begin

writeln;

if (cur2[i+1]=nil) and (k3 mod 4<>0) then begin

for j:=1 to (k3 mod 4) do

write(cur2[i]^[j]);

end

else begin

for j:=1 to d do

write(cur2[i]^[j]);

end;

i:=i+1;

end;

end;

Var first:mas;q:integer;cha:char;

begin

ClrScr;

Chut(first);

readln;

Vuvod(first);

writeln;

readln;

q:=kil(first);

writeln('Kilkist strok:', q);

readln;

end.

Екран результату

Контрольні розрахунки

Контрольними розрахунками містяться в самій програмі. Отримані результати легко перевірити, що підтверджує вірність роботи програми.

Умова задачі

Описать процедуру, которая вставляет:

а) в начало списка L новый элемент E;

Алгоритм розв’язку задачі

Текст програми

program Kill_Bill;

uses Crt;

type nodepoint=^node;

node=record

info:integer;

next:nodepoint;

end;

function Vvodsp(n1:integer):nodepoint;

var cur,firs:nodepoint;i:integer;

begin

if n1=0 then begin

Vvodsp:=nil;

end else

if n1=1 then begin

new(cur);

writeln('Vvedenya elementu spusku');

readln(cur^.info);

cur^.next:=nil;

Vvodsp:=cur;

end else

begin

new(cur);

write('Vvedenya elementu spusku: ');

readln(cur^.info);

cur^.next:=nil;

firs:=cur;

for i:=1 to n1-1 do begin

new(cur^.next);

write('Vvedenya elementu spusku: ');

readln(cur^.next^.info);

cur:=cur^.next;

cur^.next:=nil;

end;

Vvodsp:=firs;

end;

end;

procedure Vuvodsp(cur1:nodepoint);

begin

Writeln('Vuvedenya spusku');

while cur1<>nil do begin

writeln(cur1^.info);

cur1:=cur1^.next;

end;

end;

procedure Add_first(var cur:nodepoint;elem:integer);

var tm:nodepoint;

begin

new(tm);

tm^.info:=elem;

tm^.next:=cur;

cur:=tm;

end;

Procedure del(var cur2:nodepoint);

var cur:nodepoint;

begin

while cur2<>nil do begin

cur:=cur2^.next;

dispose(cur2);

cur2:=cur;

end;

end;

var n,E:integer;cur,L:nodepoint;

begin

ClrScr;

Write('Vedit kilkist elementiv spusku: ');

readln(n);

L:=Vvodsp(n);

writeln;

readln;

Vuvodsp(L);

writeln;

readln;

write('Enter the element which must be added to list: ');

readln(E);

Add_first(L,E);

Vuvodsp(L);

readln;

del(L);

end.

Екран результату

Умова задачі