Курсовая работа
«Динамические структуры данных. Решениезадач. Стек. Очередь. Дек»
Введение
Для решения многих практических задачиспользуются структуры данных – массив, запись, множество и так далее. Цельописания типов данных и последующего описания переменных, как относящихся к этомутипу, состоит в том, чтобы зафиксировать на время выполнения программы размерзначений, которые присваиваются этим переменным и, соответственно, фиксироватьразмер выделяемой области памяти для них. Такие переменные называются статическими.
Вследствиефиксирования размера выделенной памяти возникают определенные трудности:неэффективное использование оперативной памяти. Нам, во многих случаях, заранеене известны значения той или иной переменной, и даже факт существования этогозначения. Для решения задач мы можем использовать только статическиепеременные, но мы не знаем значения результата и его размеры, поэтому нам быпришлось выделять место в памяти для максимально возможного итогового значения,что приводит к нерациональному использованию памяти машины.
Созданныеи не описанные заранее, переменные размещаются на свободные участки вдинамической области оперативной памяти. Такой способ распределения памятиназывается динамическим. Существуют множество типов динамических структурданных, среди них, такие как стек, очередь, линейные списки, деки, деревья идругие.
Внекоторых случаях решение задачи эффективней при использовании стеков, в другихдеревьев, в-третьих, – следующих. В этой работе неполный обзор стеков, очередейи деков.
1. Стек
Типичнаяситуация, когда одна проблема требует решения другой, которая неразрешима безрешения третьей и так далее. В этом ряду проблема, не вызвавшая новых проблем,решается нами первой, хотя оформилась последней, а исходная проблема решается впоследнюю очередь. Такая дисциплина обслуживания обозначается LIFO и часто используется в программах.Ей соответствует абстрактная линейная структура, называемая стек.
Определениедля стека на языке линейного списка:
стек– частный случай линейногоодносвязного списка, для которого разрешено добавлять или удалять элементытолько с одного конца списка, который называется вершиной стека.
Помещениенового элемента в стек, чтение для обработки и его удаление происходит в одномего конце – верхушке. Другой конец стека неактивен. Если мы удалим элемент, вверхушке оказывается следующий, можно сравнить с действием магазина встрелковом оружии. Включение нового элемента как бы проталкивает имеющиесяэлементы в сторону дна. Порядок их следования при хранении не нарушается, как ив очередях, массивах и других структурах. Поскольку в каждый момент нужендоступ к одному, верхнему, элементу стека, индексы элементов не нужны.
Пусть Т – некоторый тип. Рассмотримтип «стек элементов типа Т». Его значениями являются последовательностизначений типа Т. Основные операции, которые используются при применениистека
· Сделать пустым;· Добавитьэлемент;· Взятьэлемент;· Стекпуст;· Вершинастека: Т;
Процедура«сделать пустым» делает стек пустым, то есть «на дне стека ничего нет», рисунок№2. Процедура «добавить элемент» добавляет элемент Х, типа Т, в конецпоследовательности.Процедура«взять элемент» применима, если последовательность S непустая, она забираетиз неё последний элемент, который становится значением переменной т.).Выражение «стек пуст» истинно, если последовательность S пуста. Выражение «вершинастека» определенно, если последовательность s непустая, и равно последнемуэлементу последовательности s (.
Реализациястека на основе массива
Будемсчитать, что вершина нашего стека – это первый элемент массива, тогда вершинабудет находиться всегда в первой ячейке массива, а дно будет продвигаться помассиву. Для удобства договоримся пустым членам массива – свободному стекуприсваивать – 1000.
Заметно, чтостек ограничен по размерам: в него можно записать ограниченное количествоэлементов
Разделобъявления переменных и констант на языке программирования Паскаль выглядитследующим образом:
Constn=10;
туреtypeelem=Integer; {объявление типа переменного}
Stack=ArrayOf typeelem;
Vars: stack;
Х:typeelem;
I: Integer;
Стек можномоделировать с помощью двух переменных:
1. S– стек.
2. Х –переменная для содержимого вершины.
Длятого чтобы не было недоразумений и ошибок нужно распечатывать содержимое стека.Эта процедура выводит на экран содержимое стека в виде столбика, на верхукоторой будет выводиться вершина. В самом нижнем положении будет находитьсяпервый занесённый элемент.
Procedurelist; {процедура распечаткисодержания стека}
Vari: Integer;
Begin
Writeln;
I: =1; {указатель вершиныставится на вершину стека}
WhileAnd Do Begin
Writeln;
Inc
End;
End; {list}
Для добавления элемента в стек надо, чтобы этот элемент былтипа элемента стека. Процедуру добавления можно описать следующим образом:
Procedurepush;
Vari: Integer; {процедура вставки}
Begin
Fori: =n Downto 2 Do s: =s;
S: =x
End; {push}
Процедурадобавления: сначала мы должны освободить место под новый элемент, для этогосдвигаем все элементы стека по массиву вправо и только после добавляем новый всвободную ячейку.
Функция «взятьэлемент» в переменную заключена в том, чтобы считать элемент в переменную иудалить его из стека. Функции мы присваиваем значение вершины стека, после чегосдвигаем весь стек на одну ячейку влево. В цикле присваиваем I – тому I+1 значение. Последнемучлену массива – «дно» стека присваиваем –1000.
Functionpop: typeelem; {считывание с удалением}
Vari: Integer;
Begin
Pop:=s;
Fori: =1 To n-1 Do s: =s;
S: =-1000
End; {pop}
Функциявершина стека: значению функции присваиваем значение вершины стека.
Functionstacktop: typeelem; {считывание без удаления}
Begin
Stacktop:=s
End;{stacktop}Функция стекпуст: если значение вершины стека не равняется –1000, то функции присваиваемзначение логической переменной FALSE.
Functionempty: Boolean; {проверканапустоту}
Begin
Ifs -1000 empty: =false;
End;{empty}
В основной программеиспользуются выше указанные процедуры, например:
init; {процедура инициализации}
list; {распечатка содержимогостека}
Fori: =1 To 3 Do
push;{вставкавстек}
Writeln;
list; {распечатка содержимогостека}
Writeln);
х:=stacktop;{считываниебез удаления}
Writeln;
Writeln;
List;
Fori: =1 To 2 Do Begin
х:=pop; {считывание судалением}
Writeln
End;
Writeln;
List;
х:=pop;
Writeln;
Writeln;
list;
Writeln);
Недостатокреализации стека на основе массива – это его ограниченность в длине, дляпреодоления этого недостатка используют стек на основе линейного списка.
2. Очередь
Очередь – частный случай линейногоодносвязного списка, для которого разрешены только два действия: добавлениеэлемента в конец очереди и удаление элемента из начала очереди.Для создания и работы с ней необходимо иметь как минимум два указателя:
· Наначало очереди.
· Наконец очереди.
Очередь можнопредставить в виде звеньев, каждая из которых состоит из двух полей: первое –поле элемента, второе – поле ссылки на следующий элемент очереди.
Дляочередей применимы следующие операции:
· Сделать пустой.
· Добавить в очередь.
· Взять из очереди.
· Очередь пуста.
· Очередной элемент.
Реализацияочереди на основе линейного спискаОписание типапеременных для реализации очереди: пользуемся рекурсивным описанием полей: Typetypeelem=Integer; типэлементаочередиconnect=^data;рекурсивноеопределение указателяdata=Recordelem:typeelem;типинформационной ячейкиnext:connectтипуказателяEnd;
Вэтом случае каждое звено содержится в указателе предыдущего звена.
Процедураинициализации очереди включает в себя выделение памяти для создания новойячейки, указатели присваиваются равными новой ячейке, указатель на следующеезвено равно nil:
Процедурараспечатки содержимого очереди: независимой переменной присваиваем значениеуказателя начала, задаем цикл, до того момента как указатель не будет равен nil; выписываем содержимоезвена и указателю задаем значение следующего звена:
S:=Sn;
Whilesnil 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, каждая из которыхограничивает движение по деку на его концах. Способ описания используемых типовданных, сравним с очередями, но здесь уже имеются три поля.
UsesCRT; {описание переменных}
Typetypeelem=Integer;
connect=^data;
data=Record
elem:typeelem;
Next:connect;
Pred: connect
End;
Процесс вставки звена в дек существенноотличается от ранее рассмотренных случаев. В деке, как и в динамической цепочкеобщего вида, новый элемент можно вставлять в любом его месте, а, кроме того, учитываядвухстороннюю связь звеньев в деке, можно поставить вопрос о вставке до или послеуказанного элемента. Отсюда следует, что для вставки элемента в дек необходимоиметь две процедуры: процедуру вставки элемента до заданного звена и процедурувставки элемента после заданного звена. Вставка звена в дек такжесопровождается установлением четырех связей.
Для уменьшения процедур можноиспользовать вспомогательные процедуры:
Procedure insert1;
{занесение элемента в дек послезаданного звена}
var s1, s2, p:connect;
Begin
s1:=sn1;
s2:=sn2;
whiles1^.elemy do s1:=s1^.next;
whiles2^.pred^.elemy 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;
whiles1^.next^.elemy do s1:=s1^.next;
whiles2^.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='к' thenbegin
new;
p^.next:=nil;
p^.elem:=x;
p^.pred:=sn2;
sn2^.next:=p;
sn2:=p;
end;
if k='н' thenbegin
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 – на звено перед удаляемым звеном.
Functionremove:typeelem;
{удалениеэлементаиздека}
varp:connect;
Begin
ifandthen begin
remove:=s^.elem;
s^.next^.pred:=s1^.pred^.pred;
s^.pred^.next:=s^.next^.next;
end
Elsebegin
ifs=sn1 then begin
p:=s;
remove:=s^.elem;
s^.next^.pred:=nil;
sn1:=s^.next;
dispose;
end;
ifs=sn2 then begin
p:=s;
remove:=s^.elem;
s^.pred^.next:=nil;
sn2:=s^.pred;
dispose;
end;
End;
End;{remove}
Если звено первое, то значению функции присваиваем значениепервого элемента; если – второе, то – последнего элемента.
Заключение:
Использование динамических структур данных эффективно применятьпри решении задач, так как каждому значению переменной выделяется какая-тообласть памяти, в ходе чего происходит учет ресурсов компьютера. Принеобходимости эту ячейку можно ликвидировать, если информация находящаяся вэтой ячейке нам больше не понадобится.
Конечно, при решении задач с помощью статистических переменныхобработка и доступ к информации облегчается. При использовании статистическихструктур данных происходит нерациональное использование оперативной памяти,потому что для статистических переменных выделяется фиксированный размер памяти.
Стековых структур данных, очередей и деков в среде «ТУРБОПАСКАЛЬ» как тип переменных не существует, поэтому, для наглядности, используютмассивы и линейные списки.
Стек как структура данных используется при решениирекурсивных задач, когда необходимо сначала решить последнюю проблему, а уже заним предыдущие проблемы. Рекурсивные процедуры обращаются сами к себе, при этомизменяются значения переменных, предшествующие значения которых складываются встек. При выполнении начальной заданной условий, находится решение дляпростейшей функции, затем более сложной.
Приложение
Стек:
1. Данстек заполненный случайным образом, из целых чисел. Удалить из него всеотрицательные элементы, используя второй стек и одну переменную.
randomize;
init;
init;
fori:=1 to n do
begin
y:=random-random;
push;
end;
list;Writeln;
fori:=1 to n do
begin
push);
pop;
end;
fori:=1 to n do
begin
ifstacktop>=0 then
push);
pop;
end;
writeln;
list;
2. Данстек заполненный целыми числами случайным образом. Удалить из стека все числане кратные заданному с клавиатуры.
randomize;
init;
init;
fori:=1 to n do
begin
y:=random-random;
push;
end;
list;Writeln;
fori:=1 to n do
begin
push);
pop;
end;
writeln;
readln;
fori:=1 to n do
begin
if)mod f=0 then
push);
pop;
end;
writeln;
list;
3. Данстек, содержащий целые числа. Используя второй стек, записать в дно стека номеродин сумму всех элементов.
randomize;
init;
init;
fori:=1 to n-1 do
begin
y:=random-random;
push;
end;
list;Writeln;
f:=0;
fori:=1 to n-1 do
begin
f:=f+stacktop;
push);
pop;
end;
push;
fori:=1 to n-1 do
begin
push);
pop;
end;
list;
writeln;
4. Удалитьиз стека, который составлен из целых чисел заданных случайным образом, каждыйвторой элемент. На дне находится первый элемент.
randomize;
init;
init;
fori:=1 to n do begin
y:=random;
push;end;
list;writeln;
whilenot emptydo begin
pop;
push);
end;
whilenot emptydo begin
push);end;
list; writeln;
5. Данстек из целых чисел, заполненный случайным образом. При помощи второго стекаудалить последний отрицательный элемент.
randomize;
init;
init;
fori:=1 to n do begin
y:=random-random;
push;end;
list;
y:=0;
whilenot empty do begin
if
push);
end;
list;
whilenot empty do
push);
list;
6. Данстек заполненный элементами типа typeelem. Удалить из стека предпоследний элемент.
randomize;
init;
fori:=1 to n do
begin
y:=random-random;
push;
end;
list;Writeln;
y:=pop;
pop;
push;
list; Writeln;
7. Данстек заполненный элементами типа typeelem. Удалить из стека первый элемент и поместить егов вершину стека номер один.
randomize;
init;
init;
fori:=1 to n do
begin
y:=random-random;
push;
end;
list;Writeln;
repeat
y:=pop;
push;
untilempty;
f:=pop;
repeat
y:=pop;
push;
untilempty;
push;
list;Writeln;
8. Данстек из целых чисел, заполненный случайным образом. Поместить вершину стека вдно, используя вспомогательный стек.
randomize;
init;
init;
fori:=1 to n do
begin
y:=random-random;
push;
end;
list;Writeln;
f:=pop;
repeat
y:=pop;
push;
untilempty;
push;
repeat
y:=pop;
push;
untilempty;
list;Writeln;
9. Данстек заполненный случайным образом из целых чисел. Поменять в данном стекесодержимое вершины и дна.
randomize;
init;
init;
fori:=1 to n do
begin
y:=random-random;
push;
end;
list;Writeln;
f1:=pop;
repeat
y:=pop;
push;
untilempty;
f2:=pop;
push;
repeat
y:=pop;
push;
untilempty;
push;
list;Writeln;
10. Данстек из целых чисел, заполненный случайными образом. Сравнить суммуположительных элементов с модулем суммы отрицательных элементов.
randomize;
init;
init;
w:=1;w1:=1;
fori:=1 to n do begin
y:=random-random;
push;end;
list;
f:=true;
whilenot empty do begin
y:=pop;
ify>0 then w:=w*y
elsew1:=w1*abs;
push;
end;
ifw
elsewriteln;
whilenot empty do begin
y:=pop;
push;end;
list;
11. Данстек из целых чисел. Поместить в дно стека сумму модулей всех элементов.
randomize;
init;
init;
fori:=1 to n-1 do
begin
y:=random-random;
push;
end;
list;Writeln;
f:=0;
fori:=1 to n-1 do
begin
f:=f+abs);
push);
pop;
end;
push;
fori:=1 to n-1 do
begin
push);
pop;
end;
list;
writeln;
12. Данстек из целых чисел. Поместить в дно стека произведение всех элементов.
randomize;
init;
init;
fori:=1 to n-1 do
begin
y:=random-random;
push;
end;
list;Writeln;
f:=1;
fori:=1 to n-1 do
begin
f:=f*abs);
push);
pop;
end;
push;
fori:=1 to n-1 do
begin
push);
pop;
end;
list;
writeln;
13. Данстек, заполненный случайными числами. Вычесть из всех элементов стека числовводимое с клавиатуры. Используйте второй стек для хранения данных.
randomize;
init;
init;
for i:=1to n do
begin
y:=random-random;
push;
end;
list;Writeln;
Writeln;
readln;
for i:=1to n do
begin
y:=stacktop-f;
push;
pop;
end;
push;
for i:=1to n do
begin
push);
pop;
end;
list;
14. Данстек из целых чисел. Прибавить ко всем элементам число вводимое с клавиатуры.
15. Встек записаны элементы типа typeelem. Записать содержимое стека в обратном порядке втот же стек. Используйте два вспомогательных стека.
randomize;
init;
init;
init;
for i:=1to n do
begin
y:=random-random;
push;
end;
list;Writeln;
for i:=1to n do
begin
push);
pop;
end;
for i:=1to n do
begin
push);
pop;
end;
for i:=1to n do
begin
push);
pop;
end;
list;
16. Встек записаны элементы типа typeelem. Поменять в стеке первый элемент со вторым,третий с четвертым, и так далее. Если стек содержит нечетное количествоэлементов, то оставить его на месте.
init;
init;
init;
fori:=1 to n do
push;
list;Writeln;
whilenot emptydo begin
push);
push);
end;
whilenot or empty) do begin
push);
push);
end;
list;
17. Стекзаполнен элементами типа typeelem. Записать в этот же стек сначала элементы счетными номерами, затем – с нечетными.
init;
init;
init;
fori:=1 to n do
push;
list;Writeln;
whilenot emptydo begin
push);
push);
end;
whilenot or empty) do
push);
whilenot or empty) do
push);
list;
18. Стекзаполнен целыми числами случайным образом. Записать в стек сначала четныеэлементы, затем – нечетные. Для решения задачи используйте два дополнительныхстека.
randomize;
init;
init;
init;
for i:=1to n do
begin
y:=random;
push;
end;
list;Writeln;
while notemptydo
ifstacktop mod 2=0 then push)
elsepush);
whilenot emptydo
push);
whilenot emptydo
push);
list;
19. Данстек из целых чисел, заполненный случайным образом. Используя только стеки,отсортировать элементы стека по возрастанию. На дне стека минимальный элемент,в вершине – максимальный. Используйте нужное количество стеков.
randomize;
init;
init;
init;
init;
fori:=1 to n do
begin
y:=random;
push;
end;
list;Writeln;
whilenot emptydo begin
push);
whilenot emptydo begin
ifstacktop>=stacktop then
beginpush); push); end
elsepush); end;
push);
whilenot emptydo
push);
end;
whilenot emptydo
push);
list;Writeln;
20. Отсортироватьстек, заполненный целыми числами, по убыванию. На дне стека должен бытьмаксимальный элемент, в вершине – минимальный. Использовать только нужноеколичество стеков.
21. Данстек, заполненный случайными целыми числами. Удалить из стека повторяющиесяэлементы, оставив по одному.
randomize;
init;
init;
init;
init;
fori:=1 to n do
begin
y:=random;
push;
end;
list;Writeln;
whilenot emptydo begin
push);
whilenot emptydo
ifstacktop=stacktop then pop
elsepush);
whilenot emptydo
push);
end;
whilenot emptydo
push);
list; Writeln;
22. Удалить из стека, который состоит из целыхчисел, все числа, которые не повторяются.
23. Стекзаполнен однозначными и двухзначными числами. Поместить однозначные числа водин стек, двухзначные – в другой.
randomize;
init;
init;
init;
fori:=1 to n do
begin
y:=random;
push;
end;
list;Writeln;
whilenot emptydo
ifstacktopdiv 10=0 then push)
elsepush);
list;Writeln;
list;Writeln;
24. Данстек, заполненный случайным образом целыми числами. Поместить четные элементы водин стек, нечетные – во второй.
25. Создатьстек из целых чисел, в котором каждый элемент равен сумме предшествующихэлементов. Первый элемент равен одному.
randomize;
init;
push;
y:=0;
fori:=2 to n do begin
y:=y+stacktop;
push;end;
list;
26. Данстек из целых чисел. Найти минимальный элемент стека и записать его в дностека.
randomize;
init;
init;
init;
fori:=1 to n-1 do
begin
y:=random-random;
push;
end;
list;Writeln;
push);
whilenot emptydo
ifstacktop
elsepush);
push);
whilenot emptydo
push);
writeln;
list;
27. Найтив стеке, составленном из целых чисел, максимальный элемент и поместить его вдно стека.
28. Встеке, составленном из целых чисел, найти минимальный элемент и поместить его ввершину стека.
randomize;
init;
init;
init;
fori:=1 to n-1 do
begin
y:=random-random;
push;
end;
list;Writeln;
push);
whilenot emptydo
ifstacktop
elsepush);
whilenot emptydo
push);
push);
writeln;
list;
29. Дан стек из целыхчисел, заполненный случайным образом. Найти в стеке максимальный элемент ипоместить его в вершину.
30. Дан стек,заполненный случайным образом целыми числами. Отыскать в данном стекемаксимальный и минимальный элементы. Переместить максимальный элемент в дностека, минимальный – в вершину.
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
else push);
while not emptydo
push);
push);
push);
while not emptydo
if stacktop>=stacktop thenbegin push); push) end
else push);
push);
while not emptydo
push);
writeln;
list;
Дек:
1. Дан дек из целых чисел, заполненныйслучайным образом. В начало дека вставить число, вводимое с клавиатуры.
2. Дек состоит из целых чисел. Вставить вэтот дек ноль после числа вводимого с клавиатуры.
3. Заполнить дек целыми положительнымичислами. Вставить в дек сегодняшнее число до элемента, который равен числувводимому с клавиатуры.
4. Заполнить дек случайным образом целымичислами. Найти максимальный элемент в образовавшемся деке и вставить до и посленего ноль.
5. Дан дек, заполненный случайным образом.До после минимального элемента вставить тысячу.
6. В деке, состоящем из целых чисел,вставить перед предыдущим элементом, равным введенному числу с клавиатуры,число равное произведению элемента и предыдущего элемента.
7. Дек заполнен случайными целыми числами.Сортировать данный дек по возрастанию.
8. Заполнить дек случайными целыми числамии отсортировать его по убыванию.
9. Найти сумму всех элементов дека,заполненного целыми числами, и поместить эту сумму в конец дека.
10. Найти сумму всех элементов дека,который состоит из целых чисел, и приписать эту сумму в начало дека.
11. Дек заполнен случайным образом целымичислами. Найти в деке максимальный и минимальный элементы и поменять ихместами.
12. Дан дек, заполненный целымиположительными и отрицательными числами. Найти в данном деке отрицательныеэлементы и удалить их.
13. Удалить четные элементы дека,заполненного случайным образом целыми числами.
14. Удалить нечетные элементы в деке,который заполнен целыми числами.
15. Найти в данном деке, заполненномслучайным образом, отрицательные элементы, удалить эти элементы и вставитьвместо них модули удаленных.
16. Дек состоит из целых отрицательных иположительных чисел, заданных случайным образом. Найти и записать вместоположительных элементов, равные им по модулю отрицательные числа.
17. Перед отрицательными элементами данногодека, который состоит из целых отрицательных и положительных чисел, вставить ихмодули.
18. После каждого элемента дека вставитьсумму всех элементов дека. Дек состоит из целых чисел.
19. Удалить из дека все двухзначные числа.Дек заполнен случайным образом целыми числами.
20. Дан дек из целых чисел, заданныхслучайным образом. Оставить в деке только двухзначные числа, все остальныеудалить.
21. Удалить из дека нечетные отрицательныечисла. Дек заполнен случайным образом целыми числами.
22. Дек заполнен целыми положительными иотрицательными числами. Удалить из дека все положительные четные числа.
23. Дек состоит из целых чисел, заданныхслучайным образом. Переписать дек в обратном порядке.
24. В деке находятся целые числа. Добавитьв дек столько элементов, чтобы он стал в два раза длиннее и симметричным, тоесть: первый элемент был равен последнему, второй – предпоследнему и так далее.
25. Дан дек из целых чисел, заданныхслучайным образом. Если дек содержит четное количество элементов, то добавить всередину дека максимальный элемент; если же дек содержит нечетное количествоэлементов, то удалить из него средний.
26. Дан дек из целых чисел, заданныхслучайным образом. Если дек содержит четное количество элементов, то добавить всередину дека минимальный элемент; если же дек содержит нечетное количествоэлементов, то удалить из него средний.
Очередь:
1. Дана очередь из целых чисел. Удалить изнее все отрицательные элементы.
2. Сравнить модули сумм положительных иотрицательных элементов очереди. Очередь заполнена целыми числами.
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; IncEnd
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 snil 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 snil do begin
write;
s:=s^.next; end;
write;
End; {list}
Procedure listpred;
{распечатка содержимого дека в обратномпорядке}
var s:connect;
begin
s:=sn2;
while snil 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^.elemy dos1:=s1^.next;
while s2^.pred^.elemy dos2:=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^.elemy dos1:=s1^.next;
while s2^.elemy dos2:=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='к' thenbegin
new;
p^.next:=nil;
p^.elem:=x;
p^.pred:=sn2;
sn2^.next:=p;
sn2:=p;
end;
if k='н' thenbegin
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^.elemy dos1:=s1^.next;
while s2^.pred^.elemy dos2:=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.