Динамические структуры данных. Решение задач. Стек. Очередь. Дек
Для решения многих практических задач используются структуры данных тАУ массив, запись, множество и так далее. Цель описания типов данных и последующего описания переменных, как относящихся к этому типу, состоит в том, чтобы зафиксировать на время выполнения программы размер значений, которые присваиваются этим переменным и, соответственно, фиксировать размер выделяемой области памяти для них. Такие переменные называются статическими.
Вследствие фиксирования размера выделенной памяти возникают определенные трудности: неэффективное использование оперативной памяти. Нам, во многих случаях, заранее не известны значения той или иной переменной, и даже факт существования этого значения. Для решения задач мы можем использовать только статические переменные, но мы не знаем значения результата и его размеры, поэтому нам бы пришлось выделять место в памяти для максимально возможного итогового значения, что приводит к нерациональному использованию памяти машины.
Созданные и не описанные заранее, переменные размещаются на свободные участки в динамической области оперативной памяти. Такой способ распределения памяти называется динамическим. Существуют множество типов динамических структур данных, среди них, такие как стек, очередь, линейные списки, деки, деревья и другие.
В некоторых случаях решение задачи эффективней при использовании стеков, в других деревьев, в-третьих, тАУ следующих. В этой работе неполный обзор стеков, очередей и деков.
1. Стек
Типичная ситуация, когда одна проблема требует решения другой, которая неразрешима без решения третьей и так далее. В этом ряду проблема, не вызвавшая новых проблем, решается нами первой, хотя оформилась последней, а исходная проблема решается в последнюю очередь. Такая дисциплина обслуживания обозначается LIFO и часто используется в программах. Ей соответствует абстрактная линейная структура, называемая стек.
Определение для стека на языке линейного списка:
стек тАУ частный случай линейного односвязного списка, для которого разрешено добавлять или удалять элементы только с одного конца списка, который называется вершиной стека.
Помещение нового элемента в стек, чтение для обработки и его удаление происходит в одном его конце тАУ верхушке. Другой конец стека неактивен. Если мы удалим элемент, в верхушке оказывается следующий, можно сравнить с действием магазина в стрелковом оружии. Включение нового элемента как бы проталкивает имеющиеся элементы в сторону дна. Порядок их следования при хранении не нарушается, как и в очередях, массивах и других структурах. Поскольку в каждый момент нужен доступ к одному, верхнему, элементу стека, индексы элементов не нужны.
Пусть Т тАУ некоторый тип. Рассмотрим тип Влстек элементов типа ТВ». Его значениями являются последовательности значений типа Т. Основные операции, которые используются при применении стека
В· Сделать пустым;
В· Добавить элемент;
В· Взять элемент;
В· Стек пуст;
В· Вершина стека: Т;
Процедура Влсделать пустымВ» делает стек пустым, то есть Влна дне стека ничего нетВ», рисунок №2. Процедура Влдобавить элементВ» добавляет элемент Х, типа Т, в конец последовательности.
Процедура Влвзять элементВ» применима, если последовательность S непустая, она забирает из неё последний элемент, который становится значением переменной т.). Выражение Влстек пустВ» истинно, если последовательность S пуста. Выражение Влвершина стекаВ» определенно, если последовательность s непустая, и равно последнему элементу последовательности s (.
Реализация стека на основе массива
Будем считать, что вершина нашего стека тАУ это первый элемент массива, тогда вершина будет находиться всегда в первой ячейке массива, а дно будет продвигаться по массиву. Для удобства договоримся пустым членам массива тАУ свободному стеку присваивать тАУ 1000.
Заметно, что стек ограничен по размерам: в него можно записать ограниченное количество элементов
Раздел объявления переменных и констант на языке программирования Паскаль выглядит следующим образом:
Const n=10;
туре typeelem=Integer; {объявление типа переменного}
Stack=Array Of typeelem;
Var s: stack;
Х:typeelem
I: Integer
Стек можно моделировать с помощью двух переменных:
1. S тАУ стек.
2. Х тАУ переменная для содержимого вершины.
Для того чтобы не было недоразумений и ошибок нужно распечатывать содержимое стека. Эта процедура выводит на экран содержимое стека в виде столбика, на верху которой будет выводиться вершина. В самом нижнем положении будет находиться первый занесённый элемент.
Procedurelist; {процедура распечатки содержания стека}
Var i: Integer;
Begin
Writeln;
I: =1; {указатель вершины ставится на вершину стека}
While And Do Begin
Writeln;
Inc
End
End; {list}
Для добавления элемента в стек надо, чтобы этот элемент был типа элемента стека. Процедуру добавления можно описать следующим образом:
Procedurepush
Vari: Integer;ВаВаВаВаВаВаВаВаВаВаВаВаВаВа {процедура вставки}
Begin
For i: =n Downto 2 Do s: =s;
S: =x
End; {push}
Процедура добавления: сначала мы должны освободить место под новый элемент, для этого сдвигаем все элементы стека по массиву вправо и только после добавляем новый в свободную ячейку.
Функция Влвзять элементВ» в переменную заключена в том, чтобы считать элемент в переменную и удалить его из стека. Функции мы присваиваем значение вершины стека, после чего сдвигаем весь стек на одну ячейку влево. В цикле присваиваем I тАУ тому I+1 значение. Последнему члену массива тАУ ВлдноВ» стека присваиваем тАУ1000.
Functionpop: typeelem; {считывание с удалением}
Var i: Integer;
Begin
Pop: =s;
For i: =1 To n-1 Do s: =s;
S: =-1000
End{pop}
Функция вершина стека: значению функции присваиваем значение вершины стека.
Functionstacktop: typeelem; {считывание без удаления}
Begin
Stacktop: =s
End; {stacktop}
Функция стек пуст: если значение вершины стека не равняется тАУ1000, то функции присваиваем значение логической переменной FALSE.
Function empty: Boolean; {проверканапустоту}
Begin
If s <> -1000 empty: =false;
End; {empty}
В основной программе используются выше указанные процедуры, например:
init; {процедура инициализации}
list; {распечатка содержимого стека}
For i: =1 To 3 Do
push; {вставкавстек}
Writeln;
list; {распечатка содержимого стека}
Writeln);
х:=stacktop; {считывание без удаления}
Writeln;
Writeln;
List;
For i: =1 To 2 Do Begin
х:=pop; {считывание с удалением}
Writeln
End;
Writeln;
List;
х:=pop;
Writeln;
Writeln;
list;
Writeln);
Недостаток реализации стека на основе массива тАУ это его ограниченность в длине, для преодоления этого недостатка используют стек на основе линейного списка.
2. Очередь
Очередь тАУ частный случай линейного односвязного списка, для которого разрешены только два действия: добавление элемента в конец очереди и удаление элемента из начала очереди. Для создания и работы с ней необходимо иметь как минимум два указателя:
В· На начало очереди.
В· На конец очереди.
Очередь можно представить в виде звеньев, каждая из которых состоит из двух полей: первое тАУ поле элемента, второе тАУ поле ссылки на следующий элемент очереди.
Для очередей применимы следующие операции:
В· Сделать пустой.
В· Добавить в очередь.
В· Взять из очереди.
В· Очередь пуста.
В· Очередной элемент.
Реализация очереди на основе линейного списка
Описание типа переменных для реализации очереди: пользуемся рекурсивным описанием полей:
Type typeelem=Integer; типэлементаочереди
connect=^data; рекурсивное определение указателя
data=Record
elem:typeelem; тип информационной ячейки
next:connect тип указателя
End;
В этом случае каждое звено содержится в указателе предыдущего звена.
Процедура инициализации очереди включает в себя выделение памяти для создания новой ячейки, указатели присваиваются равными новой ячейке, указатель на следующее звено равно nil:
Процедура распечатки содержимого очереди: независимой переменной присваиваем значение указателя начала, задаем цикл, до того момента как указатель не будет равен 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:=
создается новое звено, указатель которого равен nil, информационной ячейке придается какое-то значение, и указатель конца передвигается к этому звену.
Очередной элемент очереди: функции присваивается значение первого элемента, указатель начала передвигается на одно звено.
Remove= Sn^. Elem;
Sn: =Sn^. Next
Sk
Для того чтобы не было заполнение памяти ненужной информацией, используют процедуру dispose, которая освобождает память.
P: =Sn;
Remove= Sn^. Elem;
Sn: =Sn^. Next;
Dispose;
Тема №3: деки.
Дек как динамическая структура данных включает в себя характерные особенности очереди и стека. Перемещение в очереди осуществляется от ее левого конца к правому, то есть от первого к последнему элементу. В стеке движение также идет в одну сторону, но порядок прохождения элементов обратный тАУ от последнего элемента к первому. Дек же является двунаправленным списком, где движение может осуществляться в обе стороны. Дек, как и очередь, определяется ссылками на свои два конца, однако, в отличие от очереди, можно обрабатывать элементы в начале, в конце и в середине.
Дек можно представить в виде звеньев, каждый из которых состоит из трех полей: первое поле тАУ поле элемента, второе тАУ поле ссылки на последующий элемент, третье тАУ поле ссылки на предыдущий. В схеме имеются две ссылки nil, каждая из которых ограничивает движение по деку на его концах. Способ описания используемых типов данных, сравним с очередями, но здесь уже имеются три поля.
UsesCRT;Ва {описание переменных}
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:=
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:=
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. Дан стек заполненный случайным образом, из целых чисел. Удалить из него все отрицательные элементы, используя второй стек и одну переменную.
Вместе с этим смотрят:
РЖнварiантнi пiдпростори. Власнi вектори i власнi значення лiнiйного оператора
РЖнтерполювання функцiй
Автокорреляционная функция. Примеры расчётов
Актуальные проблемы квантовой механики
Алгебра и алгебраические системы