Смекни!
smekni.com

Динамические структуры данных. Решение задач. Стек. Очередь. Дек (стр. 4 из 4)

3. Добавить в конец очереди сумму модулей всех элементов. Очередь состоит из целых положительных и отрицательных чисел.

4. Очередь заполнена случайным образом целыми числами. Добавить в начало очереди произведение всех элементов.

5. Вычесть из всех элементов очереди число вводимое с клавиатуры.

6. Прибавить ко всем элементам число вводимое с клавиатуры. Очередь заполнена целыми числами.

7. Записать очередь в обратном порядке. Очередь заполняется с клавиатуры.

8. Дана очередь из целых чисел. Удалить из нее числа кратные заданному с клавиатуры числу.

9. Элемент из начала очереди поменять с последним элементом.

10. Дана очередь из целых чисел. Поменять в очереди первый элемент со вторым, третий с четвертым и так далее до конца очереди.

11. В начало очереди поместить элементы с четными номерами, а вконец – с нечетными.

12. Очередь состоит из целых чисел. Поместить в начало очереди четные, а вконец – нечетные элементы.

Основные процедуры:

Стек:

{Реализация стека на основе массива}

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}

Functionempty: 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}

Procedurelist;

{распечатка содержимого очереди}

var s:connect;

begin

s:=sn^.next;

while s<>nil do begin

write;

s:=s^.next; end;

End; {list}

Functionempty: Boolean;

{проверка очереди на пустоту}

Begin

empty:=sn=sk;

End; {empty}

Procedureinsert;

{занесение элемента 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}

Procedurelistnext;

{распечатка содержимого дека в прямом порядке}

var s:connect;

begin

s:=sn1;

while s<>nil do begin

write;

s:=s^.next; end;

write;

End; {list}

Procedurelistpred;

{распечатка содержимого дека в обратном порядке}

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}

Procedureinsert1;

{занесение элемента 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}

Procedureinsertnext;

{занесение элемента x в дек после заданного звена}

var s1, s2, p:connect;

Begin

s1:=sn1;

s2:=sn2;

if then insert1

else insert2

end;

Procedureinsertpred;

{занесение элемента x в дек до заданного звена}

var s1, s2, p:connect;

Begin

s1:=sn1;

s2:=sn2;

if then insert3

else insert2

end;

Functionremove1:typeelem;

{удаление элемента из начала}

Begin

remove1:=sn1^.elem;

sn1^.next^.pred:=nil;

sn1:=sn1^.next;

End; {remove}

Functionremove2: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.