Динамические списковые структуры

Изучить:

ü 􀂃 Линейные списки.

ü 􀂃 Описание элемента односвязного списка.

ü 􀂃 Типовые действия со списком.

Действия со стеком(создание списка, добавление, удаление, печать элементов списка)

type

pitem=^item;

item=record { элемент стека }

data: integer; { значение элемента }

prev: pitem; { адрес предыдущего элемента }

end;

var

top,p:pitem;

n,k:integer;

procedure add(x:integer); { добавляет элемент на вершину стека }

begin

new(p); { создаем произвольный элемент р }

p^.data:=x;

p^.prev:=top;

top:=p; { устанавливаем р вершиной стека }

end;

procedure deltop; { удаляет узел с вершины стека }

begin

if top<>nil then

begin { если стек не пустой }

p:=top^.prev; { запоминаем предшествующий вершине элемент }

dispose(top);

top:=p; { устанавливаем р вершиной стека }

end;

end;

procedure writestack; { выводит стек на экран }

begin

writeln('Содержимое стека (начиная с вершины): ');

p:=top;

while p<>nil do

begin

write(p^.data,' ');

p:=p^.prev;

end;

writeln;

end;

BEGIN { начало программы }

top:=nil;

for k:=l to 10 do

add(k); { заполняем стек числами от 1 до 10 }

writestack;

writeln('Введите значение элемента для добавления в стек:'); readln(n);

add(n);

writestack;

writeln('Сколько элементов стека нужно удалить?'); readln(n);

for k:=l to n do

deltop;

writestack;

readln

END.

{ Комментарии}

Листинг 2. Вставка и удаление элементов в произвольной позиции

type

pitem=^item;

item=record

data:integer;

next:pitem;

end;

var

head,p,p1:pitem;

n,k,l:integer;

procedure add(x,i:integer);

var

j:integer;

begin

if (i>0) and (i<=n+l) then

begin

new(p);

p^.data:=x;

if i=l then

begin

p^.next:=head;

head:=p;

end

else

begin

p1:=head;

for j:=2 to i-1 do (находим i-1-й элемент }

pl:=pl^.next;

p^.next:=р1^.next;

pl^.next:=p;

end;

n:=n+l;

end;

end;

procedure delitem(i:integer);

var

k:integer;

begin

if (i>=l) and (i<=n) and (head<>nil) then

if i=l then

begin { если нужно удалить первый элемент }

р:=head^.next;

dispose(head);

head:=p;

end

else

begin

p:=head;

for к:=2 to i-1 do { находим i-1-й элемент }

p:=p^.next;

pl:=p^.next; { pl-i-й элемент }

р^.next:=р1^.next; { p^.next ссылается на i+1-й элемент }

dispose(pi);

end;

end;

procedure writelist;

begin

p1:=head;

writeln('Содержимое списка');

while p1<>nil do

begin

write(р1^.data,' ');

pl:=pl^.next;

end;

writeln;

end;

BEGIN

n:=0; head:=nil;

for k:=l to 10 do

add(k,k); { заполняем список числами от 1 до 10 }

writelist;

write('Введите значение добавляемого элемента:');

readln(k);

write('Введите позицию добавляемого элемента');

readln(l);

add(k,l);

writelist;

write('Введите номер удаляемого элемента:'); readln(k);

delitem(k); writelist;

readln

END.

{Комментарии}

Проанализировав процедуры вставки и удаления элементов в произвольное место списка, можно прийти к выводу, что сама операция добавления и удале­ния выполняется на удивление просто — достаточно лишь переставить указа­тели. Гораздо больше времени уходит на то, чтобы найти элемент с заданным номером в списке. Список — это не массив, и обратиться по индексу к элементу нельзя. Остается только один вариант — двигаться по цепочке от одного эле­мента к другому, начиная от самого первого элемента.

2. Работа с массивом ссылок

Type

ssilka=^real;

vector=array [1..100] of ssilka;

Считая, что все элементы вектора Х отличны от nil, описать функцию Negat(x), значением которой является первый из элементов вектора Х, ссылающихся на отрицательные числа или nil, если таких элементов нет.

var

v:vector;

function Negat(var x:vector):ssilka;

var

i:byte;

begin

negat:=nil;

for I:=1 to 100 do

if x[i]^<0 then {если элемент массива отрицателен}

begin

negat:=x[i]

exit {досрочный выход из функции}

end;

end;

BEGIN {тело основной программы}

randomize;

writeln(' исходный массив');

for i:=1 to 100 do {создание массива ссылок в куче заполнение случайными числами и печать массива}

begin

new(v[i]);

v[i]^:=random*10-0.2;

write(v[i]^:5:1)

end;

writeln;

if negat(v)=nil then

writeln(' ссылок на отрицательные числа нет в массиве')

else

writeln(' первое отрицательное число= ',negat(v):5:1);

for i:=1 to 100 do {высвобождение памяти в куче}

dispose(v[i])

END.