Курсовая работа: Динамические структуры данных. Решение задач. Стек. Очередь. Дек
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 empty do
push);
list;
6. Дан стек заполненный элементами типа typeelem. Удалить из стека предпоследний элемент.
randomize;
init;
for i:=1 to n do
begin
y:=random-random;
push;
end;
list; Writeln;
y:=pop;
pop;
push;
list; Writeln;
7. Дан стек заполненный элементами типа typeelem. Удалить из стека первый элемент и поместить его в вершину стека номер один.
randomize;
init;
init;
for i:=1 to n do
begin
y:=random-random;
push;
end;
list; Writeln;
repeat
y:=pop;
push;
until empty;
f:=pop;
repeat
y:=pop;
push;
until empty;
push;
list; Writeln;
8. Дан стек из целых чисел, заполненный случайным образом. Поместить вершину стека в дно, используя вспомогательный стек.
randomize;
init;
init;
for i:=1 to n do
begin
y:=random-random;
push;
end;
list; Writeln;
f:=pop;
repeat
y:=pop;
push;
until empty;
push;
repeat
y:=pop;
push;
until empty;
list; Writeln;
9. Дан стек заполненный случайным образом из целых чисел. Поменять в данном стеке содержимое вершины и дна.
randomize;
init;
init;
for i:=1 to n do
begin
y:=random-random;
push;
end;
list; Writeln;
f1:=pop;
repeat
y:=pop;
push;
until empty;
f2:=pop;
push;
repeat
y:=pop;
push;
until empty;
push;
list; Writeln;
10. Дан стек из целых чисел, заполненный случайными образом. Сравнить сумму положительных элементов с модулем суммы отрицательных элементов.
randomize;
init;
init;
w:=1; w1:=1;
for i:=1 to n do begin
y:=random-random;
push; end;
list;
f:=true;
while not empty do begin
y:=pop;
if y>0 then w:=w*y
else w1:=w1*abs;
push;
end;
if w<w1 then writeln
else writeln;
while not empty do begin
y:=pop;
push; end;
list;
11. Дан стек из целых чисел. Поместить в дно стека сумму модулей всех элементов.
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+abs);
push);
pop;
end;
push;
for i:=1 to n-1 do
begin
push);
pop;
end;
list;
writeln;
12. Дан стек из целых чисел. Поместить в дно стека произведение всех элементов.
randomize;
init;
init;
for i:=1 to n-1 do
begin
y:=random-random;
push;
end;
list; Writeln;
f:=1;
for i:=1 to n-1 do
begin
f:=f*abs);
push);
pop;
end;
push;
for i:=1 to n-1 do
begin
push);
pop;
end;
list;
writeln;
13. Дан стек, заполненный случайными числами. Вычесть из всех элементов стека число вводимое с клавиатуры. Используйте второй стек для хранения данных.
randomize;
init;
init;
for i:=1 to n do
begin
y:=random-random;
push;
end;
list; Writeln;
Writeln;
readln;
for i:=1 to n do
begin
y:=stacktop-f;
push;
pop;
end;
push;
for i:=1 to n do
begin
push);
pop;
end;
list;
14. Дан стек из целых чисел. Прибавить ко всем элементам число вводимое с клавиатуры.
15. В стек записаны элементы типа typeelem. Записать содержимое стека в обратном порядке в тот же стек. Используйте два вспомогательных стека.
randomize;
init;
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
push);
pop;
end;
for i:=1 to n do
begin
push);
pop;
end;
list;
16. В стек записаны элементы типа typeelem. Поменять в стеке первый элемент со вторым, третий с четвертым, и так далее. Если стек содержит нечетное количество элементов, то оставить его на месте.
init;
init;
init;
for i:=1 to n do
push;
list; Writeln;
while not emptydo begin
push);
push);
end;
while not or empty) do begin
push);
push);
end;
list;
17. Стек заполнен элементами типа typeelem. Записать в этот же стек сначала элементы с четными номерами, затем – с нечетными.
init;
init;
init;
for i:=1 to n do
push;
list; Writeln;
while not emptydo begin
push);
push);
end;
while not or empty) do
push);
while not or empty) do
push);
list;
18. Стек заполнен целыми числами случайным образом. Записать в стек сначала четные элементы, затем – нечетные. Для решения задачи используйте два дополнительных стека.
randomize;
init;
init;
init;
for i:=1 to n do
begin
y:=random;
push;
end;
list; Writeln;
while not emptydo
if stacktop mod 2=0 then push)
else push);
while not emptydo
push);
while not emptydo
push);
list;
19. Дан стек из целых чисел, заполненный случайным образом. Используя только стеки, отсортировать элементы стека по возрастанию. На дне стека минимальный элемент, в вершине – максимальный. Используйте нужное количество стеков.
randomize;
init;
init;
init;
init;
for i:=1 to n do
begin
y:=random;
push;
end;
list; Writeln;
while not emptydo begin
push);
while not emptydo begin
if stacktop>=stacktop then
begin push); push); end
else push); end;
push);
while not emptydo
push);
end;
while not emptydo
push);
list; Writeln;
20. Отсортировать стек, заполненный целыми числами, по убыванию. На дне стека должен быть максимальный элемент, в вершине – минимальный. Использовать только нужное количество стеков.
21. Дан стек, заполненный случайными целыми числами. Удалить из стека повторяющиеся элементы, оставив по одному.
randomize;
init;
init;
init;
init;
for i:=1 to n do
begin
y:=random;
push;
end;
list; Writeln;
while not emptydo begin
push);
while not emptydo
if stacktop=stacktop then pop
else push);
while not emptydo
push);
end;
while not emptydo
push);
list; Writeln;
22. Удалить из стека, который состоит из целых чисел, все числа, которые не повторяются.
23. Стек заполнен однозначными и двухзначными числами. Поместить однозначные числа в один стек, двухзначные – в другой.
randomize;
init;
init;
init;
for i:=1 to n do
begin
y:=random;
push;
end;
list; Writeln;
while not emptydo
if stacktopdiv 10=0 then push)
else push);
list; Writeln;
list; Writeln;
24. Дан стек, заполненный случайным образом целыми числами. Поместить четные элементы в один стек, нечетные – во второй.
25. Создать стек из целых чисел, в котором каждый элемент равен сумме предшествующих элементов. Первый элемент равен одному.
randomize;
init;
push;
y:=0;
for i:=2 to n do begin
y:=y+stacktop;
push; end;
list;
26. Дан стек из целых чисел. Найти минимальный элемент стека и записать его в дно стека.
randomize;
init;
init;
init;
for i:=1 to n-1 do
begin
y:=random-random;
push;
end;
list; Writeln;
push);
while not emptydo
if stacktop<=stacktop then begin push); push) end
else push);
push);
while not emptydo
push);
writeln;
list;
27. Найти в стеке, составленном из целых чисел, максимальный элемент и поместить его в дно стека.
28. В стеке, составленном из целых чисел, найти минимальный элемент и поместить его в вершину стека.
randomize;
init;
init;
init;
for i:=1 to n-1 do
begin
y:=random-random;
push;
end;
list; Writeln;
push);
while not emptydo
if stacktop<=stacktop then begin push); push) end
