Курсовая работа: Динамические структуры данных. Решение задач. Стек. Очередь. Дек
Процедура распечатки содержимого очереди: независимой переменной присваиваем значение указателя начала, задаем цикл, до того момента как указатель не будет равен nil; выписываем содержимое звена и указателю задаем значение следующего звена:
S: =Sn;
While s<>nil do begin
Write;
S: =s^. Next; end;
Функция проверки на пустоту очереди выглядит следующим образом:
Empty: =Sn=SK;
Функция может принимать два значения. Если начало и конец совпадают, то функция равна правде, и наоборот: не совпадают – лжи.
Процедура вставки:
new;
P^. Next: =nil;
P^. Elem: =x;
Sk^. Next: =p;
sk:=p;
создается новое звено, указатель которого равен nil, информационной ячейке придается какое-то значение, и указатель конца передвигается к этому звену.
Очередной элемент очереди: функции присваивается значение первого элемента, указатель начала передвигается на одно звено.
Remove= Sn^. Elem;
Sn: =Sn^. Next;
Sk
Для того чтобы не было заполнение памяти ненужной информацией, используют процедуру dispose, которая освобождает память.
P: =Sn;
Remove= Sn^. Elem;
Sn: =Sn^. Next;
Dispose;
Тема №3: деки.
Дек как динамическая структура данных включает в себя характерные особенности очереди и стека. Перемещение в очереди осуществляется от ее левого конца к правому, то есть от первого к последнему элементу. В стеке движение также идет в одну сторону, но порядок прохождения элементов обратный – от последнего элемента к первому. Дек же является двунаправленным списком, где движение может осуществляться в обе стороны. Дек, как и очередь, определяется ссылками на свои два конца, однако, в отличие от очереди, можно обрабатывать элементы в начале, в конце и в середине.
Дек можно представить в виде звеньев, каждый из которых состоит из трех полей: первое поле – поле элемента, второе – поле ссылки на последующий элемент, третье – поле ссылки на предыдущий. В схеме имеются две ссылки nil, каждая из которых ограничивает движение по деку на его концах. Способ описания используемых типов данных, сравним с очередями, но здесь уже имеются три поля.
Uses CRT; {описание переменных}
Type typeelem=Integer;
connect=^data;
data=Record
elem: typeelem;
Next: connect;
Pred: connect
End;
Процесс вставки звена в дек существенно отличается от ранее рассмотренных случаев. В деке, как и в динамической цепочке общего вида, новый элемент можно вставлять в любом его месте, а, кроме того, учитывая двухстороннюю связь звеньев в деке, можно поставить вопрос о вставке до или после указанного элемента. Отсюда следует, что для вставки элемента в дек необходимо иметь две процедуры: процедуру вставки элемента до заданного звена и процедуру вставки элемента после заданного звена. Вставка звена в дек также сопровождается установлением четырех связей.
Для уменьшения процедур можно использовать вспомогательные процедуры:
Procedure insert1;
{занесение элемента в дек после заданного звена}
var s1, s2, p:connect;
Begin
s1:=sn1;
s2:=sn2;
while s1^.elem<>y do s1:=s1^.next;
while s2^.pred^.elem<>y do s2:=s2^.pred;
new;
p^.elem:=x;
p^.next:=s2;
p^.pred:=s1;
s2^.pred:=p;
s1^.next:=p;
end;
{процедура Insert1 используется при вставке элемента после заданного звена при условии что это не начало или не конец дека.}
Procedure insert3;
{занесение элемента в дек до заданного звена}
var s1, s2, p:connect;
Begin
s1:=sn1;
s2:=sn2;
while s1^.next^.elem<>y do s1:=s1^.next;
while s2^.elem<>у do s2:=s2^.pred;
new;
p^.elem:=x;
p^.next:=s2;
p^.pred:=s1;
s2^.pred:=p;
s1^.next:=p;
end;
{процедура Insert3 используется при вставке элемента до заданного звена при условии что это не начало или не конец дека}
Procedure insert2;
{занесение элемента в дек}
var p:connect;
Begin
if k='к' then begin
new;
p^.next:=nil;
p^.elem:=x;
p^.pred:=sn2;
sn2^.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;
{удаление элемента из дека}
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
