Курсовая работа: Динамические структуры данных. Решение задач. Стек. Очередь. Дек
Основные процедуры:
Стек:
{Реализация стека на основе массива}
Program st;
Uses Crt;
Const n=10;
Type typeelem=Integer;
stack=Array Of typeelem;
Var s:stack; y:typeelem; i: Integer;
Procedure init; {создание стека}
Var i: Integer;
Begin
For i:=1 To n Do s:=-1000
End; {init}
Procedure list; {распечатка содержимого стека}
Var i: Integer;
Begin
Writeln;
i:=1;
While And Do Begin Writeln; Inc End
End; {list}
Procedure push; {занесение элемента в стек}
Var i: Integer;
Begin
For i:=n Downto 2 Do s:=s;
s:=x
End; {push}
Function pop:typeelem; {удаление элемента из стека}
Var i: Integer;
Begin
pop:=s;
For i:=1 To n-1 Do s:=s;
s:=-1000
End; {pop}
Function stacktop:typeelem; {считывание верхнего элемента без удаления}
Begin
stacktop:=s
End; {stacktop}
Function empty: Boolean; {проверка стека на пустоту}
Begin
empty:=false;
End; {empty}
{–}
Begin {main}
Clrscr;
init;
list; Writeln;
For i:=1 To 3 Do push;
Writeln; list;
Writeln);
y:=stacktop; Writeln; Writeln;
Writeln; list; Writeln;
For i:=1 To 2 Do Begin y:=pop; Writeln End;
Writeln; list; Writeln;
y:=pop; Writeln;
Writeln; list;
Writeln);
Readln
End. {main}
Очередь:
{pеализация очереди на основе лин списка}
Program spisok;
Uses Crt;
Type typeelem=Integer;
connect=^data;
data=Record
elem:typeelem;
next:connect
End;
Var sn, s, sk:connect; x:typeelem; i: Integer;
Procedure init;
{создание очереди}
var p:connect;
Begin
new;
p^.next:=nil;
sn:=p; sk:=p;
End; {init}
Procedure list;
{распечатка содержимого очереди}
var s:connect;
begin
s:=sn^.next;
while s<>nil do begin
write;
s:=s^.next; end;
End; {list}
Function empty: Boolean;
{проверка очереди на пустоту}
Begin
empty:=sn=sk;
End; {empty}
Procedure insert;
{занесение элемента x в очередь}
var p:connect;
Begin
new;
p^.next:=nil;
p^.elem:=x;
sk^.next:=p;
sk:=p;
End; {insert}
Function remove:typeelem;
{удаление элемента из очереди}
Begin
remove:=sn^.next^.elem;
sn:=sn^.next;
End; {remove}
{–}
Begin
ClrScr;
randomize;
init; {инициализация очереди}
for i:=1 to 5 do begin
x:=random-random;
insert; {вставка элемента в очередь}
end;
list; writeln; {распечатка содержимого очереди}
x:=remove; {удаление элемента из очереди}
list; writeln; {распечатка содержимого очереди}
Readln; End.
Дек:
{pеализация дека на основе линейного списка}
Program dek;
Uses Crt;
Type typeelem=Integer;
connect=^data;
data=Record
elem:typeelem;
next:connect;
pred:connect
End;
Var sn1, sn2, s:connect; x, y:typeelem; i: Integer;
k:string;
Procedure init;
{создание дека}
var p:connect;
Begin
new;
p^.next:=nil;
p^.pred:=nil;
p^.elem:=x;
sn1:=p;
sn2:=p;
End; {init}
Procedure listnext;
{распечатка содержимого дека в прямом порядке}
var s:connect;
begin
s:=sn1;
while s<>nil do begin
write;
s:=s^.next; end;
write;
End; {list}
Procedure listpred;
{распечатка содержимого дека в обратном порядке}
var s:connect;
begin
s:=sn2;
while s<>nil do begin
write;
s:=s^.pred; end;
write;
End; {list}
Function empty: Boolean;
{проверка дека на пустоту}
Begin
empty:=sn1=sn2;
End; {empty}
Procedure insert1;
{занесение элемента x в дек после заданного звена}
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;
Procedure insert3;
{занесение элемента x в дек до заданного звена}
var s1, s2, p:connect;
Begin
s1:=sn1;
s2:=sn2;
while s1^.next^.elem<>y do s1:=s1^.next;
while s2^.elem<>y do s2:=s2^.pred;
new;
p^.elem:=x;
p^.next:=s2;
p^.pred:=s1;
s2^.pred:=p;
s1^.next:=p;
end;
Procedure insert2;
{занесение элемента x в дек}
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}
Procedure insertnext;
{занесение элемента x в дек после заданного звена}
var s1, s2, p:connect;
Begin
s1:=sn1;
s2:=sn2;
if then insert1
else insert2
end;
Procedure insertpred;
{занесение элемента x в дек до заданного звена}
var s1, s2, p:connect;
Begin
s1:=sn1;
s2:=sn2;
if then insert3
else insert2
end;
Function remove1:typeelem;
{удаление элемента из начала}
Begin
remove1:=sn1^.elem;
sn1^.next^.pred:=nil;
sn1:=sn1^.next;
End; {remove}
Function remove2:typeelem;
{удаление элемента из конца}
Begin
remove2:=sn2^.elem;
sn2^.pred^.next:=nil;
sn2:=sn2^.pred;
End; {remove}
Function remove:typeelem;
{удаление элемента из дека}
var s1, s2, s, p:connect;
Begin
s1:=sn1; s2:=sn2;
if andthen begin
while s1^.next^.elem<>y do s1:=s1^.next;
while s2^.pred^.elem<>y do s2:=s2^.pred;
remove:=s1^.next^.elem;
s1^.next:=s1^.next^.next;
s2^.pred:=s2^.pred^.pred;
end
else if then remove:=remove2
else remove:=remove1;
End; {remove}
{–}
Begin
ClrScr;
sn1:=nil;
sn2:=nil;
k:='к';
init;
for i:=2 to 10 do
insert2;
listnext;
writeln;
listpred;
writeln;
insertnext;
listnext;
writeln;
insertpred;
listnext;
writeln;
remove1;
listnext;
writeln;
listpred;
writeln;
remove2;
listnext;
writeln;
listpred;
remove;
writeln;
listnext;
writeln;
listpred;
Readln
End.
Литература
стек дек очередь переменная
1. Информатика и образование, №5 – 1999.
2. Бабушкина И.А., Бушмелева Н.А., Окулов С.М., Черных С.Ю. Конспекты по информатике. – Киров, 1997.
3. Грэхем Р., Кнут Д., Паташник О. Конкретная информатика. – М.: Мир, 1988.
4. Вирт Н., Алгоритм + структура данных = программа.
5. Райнтли, Абстракция и структура данных.
6. Зубов В.С., Справочник программиста. – 1999.
