л12дин пам06.ppt

в среде Turbo PASCAL. Базовый курс 7.0. – К.:ВЕК+,1999. –

464 с.

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

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

Type
Tptr=^Telem; {ссылка на динамическую
переменную}
Telem = Record
info:integer;
next: Tptr; {указатель}
end;

Использование динамической памяти

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

односвязным списком.

Линейные списки – это данные динамической структуры, которые представляют собой совокупность линейно-связанных однородных элементов, для которых разрешены следующие действия:
1) добавление элемента в начало;
2) добавление элемента в конец (хвост) списка (частный случай вставки);
3) вставка элемента между двумя любыми другими элементами;
4) исключение элемента (удаление любого, как крайнего, так и среднего элемента списка).

{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

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

147554 3040
4 1475 477512
2

1475477 504
1 0

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(' ', seg(t^.next),'+',ofs(t^.next));}
writeln('элемент - адрес');
while t<>nil{не пусто} do
begin {ofs() возвращает смещение адреса объекта типа WORD}
writeln(t^.key:6,' / ', longint(t^.next));
t:=t^.next; { \ нельзя печатать сам указатель}
end;
END.

слово, завершающееся точкой.
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.

next
До занесения

Занесение

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

и линейные списки, но имеющие дополнительную связь между последним и

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

Линейный двусвязный (двунаправленный)

добавлением элементов в начало (конец) списка}
Program spis2а;

{вывод не верен}
Type sv = ^struct;
struct = record
key: integer;
left: sv ; {на предыдущий}
right: sv { на следующий}
end;
Var p,t,q: sv;
x: integer;
BEGIN
p:=nil; q:=nil;
writeln('Введите элемент (Число >999-признак конца)');
read(x);

p=t

q=t

p

Ввели 1 элемент

Ввели 2 элемент

new(t); {новый элемент списка}

t^.key:=x; {заполнение ключевого списка}
t^.right:=nil; {это последний элемент, т.к. добавление в конец}
t^.left:=q; {привязывание нового элемента справа(с предыдущим) дадим ему значение признака конца}
writeln(longint(t^.right),' / ',t^.key:6,' \ ', longint(t^.left)); { dispose(t);}
if (p=nil) then p:=t {текущему 1 раз}
else q^.right:=t; {указатель текущем в правое поле}
q :=t; {установка указателя на текущий элемент (последний)}
read(x);
end;
writeln('на левый - элемент - на правый(сегмент + смещение)');
t:=q;
while t<>nil{не пусто} do
begin
writeln(longint(t^.right),' / ',t^.key:6,' / ', longint(t^.left)); { dispose(t);}t:=t^.left;
end
END.

Результаты:

0 ./ 4 / 1477378048
1477443584 ./ 3 / 1477312512
1477378048 ./ 2 / 1477246976
1477312512 ./ 1 / 0






0 ./ 1 / 1477312512
1477378048 ./ 2 / 1477246976
1477312512 ./ 5 / 0

Ввод:
Тест1: 0 ./ 1 \ 0
0 ./ 2 \ 1477246976
0 / 3 \ 1477312512
0 ./ 4 \ 1477378048
9999

Тест2: 0 ./ 5 \ 0
0 ./ 2 \ 1477246976
0 ./ 1 \ 1477312512
9999

ушел".

Val)
Program queue0; {queue0.pas + }
Uses crt;
Type

ptr=^elem;
elem=record
inf:integer;
next: ptr
end;
Var beg_p,t,end_q:ptr;
x: integer;
i: byte;
Procedure ADDEl(val:integer); {Добавление элемента}
Var pt:ptr;
Begin
new(pt);
pt^.inf:=val;
pt^.next:=nil;
if end_q = nil then Beg_p:=pt {если создается первый элемент}
else end_q^.next:=pt; {если создается очередной элемент}
End_q:=pt
End;

beg_P:=pt^.next;
if Beg_p=nil then end_q:=nil; {если удаляется последний элемент}

dispose(pt)
end;
BEGIN
clrscr;
Beg_p:=nil; end_q:=nil; {Начальная установка указателей}
for i:=1 to 10 do AddEl(i); {Создание очереди из 10 элементов}
{Удаление очереди с распечаткой значений ее элементов}
while Beg_p<>nil do
begin
GetDelEl(x);
writeln('x=',x:4)
end;
END.

Результат
x=1
x=2
x=3
x=4
x=5
x=6
x=7
x=8
x=9
x=10

первый элемент
4. Установка указателей на созданный первый элемент
nil
nil

Beg.p
End.q
t

в него информации

t
t^.inf:=5;
p^.next:=nil;
new(t)
Установка связи между последним элементом очереди и новым,

а также перемещение указателя конца на новый элемент

BegP

EndQ

t

Endq^.next:=

EndQ:=t;

первым ушел".
- ограниченный
глубина стека
- пуст
NIL:
Операции над стеком:

Занесение

Выбор

25

17

30

45

45

crt;
Type ptr=^elem; elem=record
inf:integer;
next: ptr
end;
Var
Top:ptr;
x: integer; i:byte;
Procedure

Push(val: integer); {Добавление элемента}
Var pt:ptr;
Begin new(pt); pt^.inf:=val; pt^.next:=Top; Top:=pt
End;
Procedure Pop(Var Val:integer); {Извлечение}
Var pt:ptr;
begin
val:=Top^.inf;
pt:=Top;
Top:=pt^.next; dispose(pt)
end;

10 do Push(i);{Создание стека из 10 элементов}

{Удаление стека с распечаткой значений его элементов}
while Top<>nil do
begin
Pop(x); writeln('x=',x:4)
end
END.

Результаты
x=10
x=9
x=8
x=7
x=6
x=5
x=4
x=3
x=2
x=1

Пусть имеется текст, сбалансированный по круглым скобкам. Необходимо построить таблицу, в каждой строке которой будут находится координаты соответствующих пар скобок, т.е. для текста 15 30
( ... ( ... ) ... ( ... ) ... ) таблица 45 60
0 15 30 45 60 95 0 95

"(", занести ее координату в стек; как только встретится ")", возьмем из стека верхнюю координату

конец
Взять из конца
Добавить в начало
Взять из начала
Конец
Начало
Дерево
корень
листья 1 уровня
листья

2 уровня

листья n уровня

…

…