|
Читайте также: |
Рассмотрим, как с помощью записей и массивов можно организовать стеки, очереди и списки, - структуры данных, играющих фундаментальную роль в программировании. Списки, и как частный их случай стеки и очереди, лежат в основе построения многих быстрых алгоритмом сортировки и поиска. Благодаря своим свойствам, они нашли широкое применение в программах информационного поиска, при моделировании различных процессов и других важных приложениях.
Здесь мы познакомимся с наиболее общими операциями над списками, стеками и очередями: их созданием, вставкой и удалением элементов, выводом на экран и некоторыми другими.
Стеком называется линейный список с одной точкой доступа, называемой вершиной (top). Элементы в стек могут добавляться или из него удаляться только через вершину (подобно тарелкам в стопке или патронам в «магазине» автомата Калашникова). Стек часто называют структурой LIFO (сокращение от last in – first out: последний вошел – первый вышел). Такое сокращение позволяет легко запомнить механизм работы стека.
Рассмотрим реализацию стека посредством массива. Напишем в виде процедур наиболее характерные операции при работе со стеками:
Хотя, учитывая устройство стека, эти процедуры будут работать только с первым его элементом, все другие элементы стека должны смещаться соответственно на одну позицию. Чтобы более рационально приспособить массивы для реализации стеков зафиксируем «дно» стека в самом низу массива, в ячейке с наибольшим индексом maxlength.
1-й элемент массива
2-й элемент массива
…….
Вершина стека
top 1-й элемент стека
2-й элемент стека
……
Последний эл-т массива
|
Пусть элементы массива имеют тип elementtype – это могут быть символы, строки, целые, вещественные числа и другие базовые типы. Выберем пока целый тип элементов массива. Определим тип данных Stack, как запись, имеющую два поля.
const maxlength =100;
type elementtype = integer;
stack = record
elements: array[1..maxlength] of elementtype;
top: integer
end;
var rs: stack;
procedure Push(x:elementtype; var S:stack);
begin
with S do
if top =1 then begin writeln(‘Стек полон’); Exit end
else begin
top:=top-1;
elements[top]:=x
end
end;
В качестве отладки разрабатываемой нами программы заполним стек десятью нечетными числами, начиная с единицы. Для организации ввода данных удобно записать еще одну процедуру MakeNull(S), создающую пустой стек. Она может быть полезна и в других подпрограммах, когда возникнет необходимость в обновлении содержимого стека.
procedure MakeNull(var S:stack);
begin
S.top:= maxlength + 1
end;
procedure Data(var S:stack);
var k:integer;
begin
MakeNull(s);
for k:=1 to 10 do Push(2*k-1,s)
end;
Еще одна функция будет полезна при написании процедуры удаления элемента из вершины стека Pop(S). Логическая функция Empty(S) возвращает значение true, если стек S пустой, и значение false, в противном случае (empty –пустой).
function Empty (S:stack):boolean;
begin
if S.top > maxlength then Empty:= true
else Empty:= false
end;
procedure Pop(var S:stack);
begin
if Empty(S) then
begin writeln(‘ Стек пустой ’); Exit end
else S.top:= S.top +1
end;
Для организации вывода данных запишем еще одну функцию, которая будет возвращать элемент из вершины стека.
function TopS (S:stack): elementtype;
begin
if Empty(S) then
begin writeln(‘ Стек пустой ’); Exit end
else TopS:= S.elements[S.top]
end;
procedure OutData(S:stack);
begin
while not(Empty(S)) do
begin write(TopS(S):3,’ ’); Pop(S) end;
writeln
end;
Begin Data(rs); OutData(rs) End.
Дата добавления: 2015-07-19; просмотров: 50 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Введение. | | | Организация очереди |