2 ^. next: = p;
sn2: = p;
end;
if k = 'н ' then begin
new;
p ^. pred: = nil;
p ^. elem: = x;
p ^. next: = sn1;
sn1 ^. pred: = p;
sn1: = p;
end;
End; {insert}
{ Insert2 - вставка елемента на початок або в кінець дека}
Використовуємо покажчик кінця дека: покажчику кінця дека присвоюємо значення нової ланки, покажчику останнього елемента присвоюємо значення нової ланки.
Procedure insertnext;
{занесення елемента x в дек після заданого ланки}
var s1, s2, p: connect;
Begin
s1: = sn1; s2: = sn2;
if then insert1
else insert2; end;
На противагу першого випадку, покажчику попереднього елемента присвоюємо значення нової ланки, покажчику кінця так само присвоюємо значення нової ланки.
Procedure insertpred;
{занесення елемента в дек до заданого ланки}
var s1, s2, p: connect;
Begin
s1: = sn1;
s2: = sn2;
if then insert3
else insert2
end;
Розглянуті процедури застосовні тільки для деков, що мають не менше однієї ланки, тому в якості самостійного завдання можна дати модифікацію даних процедур з урахуванням ставки ланки порожній і одноелементні деки.
Видалення ланки з дека полягає в його ізоляції від сусідніх ланок. Це означає, що посилання next попередньої ланки повинна бути переадресована на ланку, наступне за видаляється ланкою, а посилання pred - на ланку перед видаляється ланкою.
Function remove: typeelem;
{ видалення елемента з < i> дека }
var p: connect;
Begin
if andthen begin
remove: = s ^. elem;
s ^. next ^. pred: = s1 ^. pred ^. pred;
s ^. pred ^. next: = s ^. next ^. next;
end
Else begin
if s = sn1 then begin
p: = s;
remove: = s ^. elem;
s ^. next ^. pred: = nil;
sn1: = s ^. next;
dispose;
end;
if s = sn2 then begin
p: = s;
remove: = s ^. elem;
s ^. pred ^. next: = nil;
sn2: = s ^. pred;
dispose;
end;
End;
End; {remove}
Якщо ланка перше, то значенням функції присвоюємо значення першого елемента; якщо - друге, то - останнього елемента.
Висновок:
Використання динамічних структур даних ефективно застосовувати при вирішенні завдань, оскільки кожному значенню змінної виділяється якась область пам'яті, в ході чого відбувається облік ресурсів комп'ютера. При необхідності цю клітинку можна ліквідувати, якщо інформація знаходиться в цій комірці нам більше не знадобиться.
Звичайно, при вирішенні завдань за допомогою статистичних змінних обробка та доступ до інформації полегшується. При використанні статистичних структур даних відбувається нераціональне використання оперативної пам'яті, тому що для статистичних змінних виділяється фіксований розмір пам'яті.
стекового структур даних, черг і деков в середовищі В«ТУРБО ПАСКАЛЬ В»як тип змінних не існує, тому, для наочності, використовують масиви та лінійні списки.
Стек як структура даних використовується при вирішенні рекурсивних завдань, коли необхідно спочатку вирішити останню проблему, а вже за ним попередні проблеми. Рекурсивні процедури звертаються самі до себе, при цьому змінюються значення змінних, що передують значення яких складаються в стек. При виконанні початкової заданої умов, знаходиться рішення для найпростішої функції, потім більш складною.
Додаток
Стек:
1. Дан стек заповнений випадковим чином, з цілих чисел. Видалити з нього всі негативні елементи, використовуючи другий стек і одну змінну.
randomize;
init;
init;
for i: = 1 to n do
begin
y: = random-random;
push;
end;
list; Writeln;
for i: = 1 to n do
begin
push);
pop;
end;
for i: = 1 to n do
begin
if stacktop> = 0 then
push);
pop;
end;
writeln;
list;
2. Дан стек заповнений цілими числами випадковим чином. Видалити з стека всі числа не кратні заданому з клавіатури.
randomize;
init;
init;
for i: = 1 to n do
begin
y: = random-random;
push;
end;
list; Writeln;
for i: = 1 to n do
begin
push);
pop;
end;
writeln;
readln;
for i: = 1 to n do
begin
if) mod f = 0 then
push);
pop;
end;
writeln;
list;
3. Дан стек, що містить цілі числа. Використовуючи другий стек, записати в дно стека номер один суму всіх елементів.
randomize;
init;
init;
for i: = 1 to n-1 do
begin
y: = random-random;
push;
end;
list; Writeln;
f: = 0;
for i: = 1 to n-1 do
begin
f: = f + stacktop;
push);
pop;
end;
push;
for i: = 1 to n-1 do
begin
push);
pop;
end;
list;
writeln;
4. Видалити з стека, який складено з цілих чисел заданих випадковим чином, кожен другий елемент. На дні перебуває перший елемент.
randomize;
init;
init;
for i: = 1 to n do begin
y: = random;
push; end;
list; writeln;
while not emptydo begin
pop;
push);
end;
while not emptydo begin
push); end;
list; writeln;
5. Дан стек з цілих чисел, заповнений випадковим чином. З допомогою другого стека видалити останній негативний елемент.
randomize;
init;
init;
for i: = 1 to n do begin
y: = random-random;
push; end;
list;
y: = 0;
while not empty do begin
if <0) and then begin pop; y: = 1; end;
push);
end;
list;
while not e...
