Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Организация стеков.

Связанные списки. | Введение | Текстовые файлы | Экспериментальный раздел работы. |


Читайте также:
  1. II.Организация и порядок проведения
  2. IV. Организация и порядок проведения Конкурса
  3. IV. Организация и проведения конкурса
  4. IV. Организация питания
  5. IV. Организация раннего выявления туберкулеза у взрослого населения
  6. IV. Организация учебного процесса
  7. Lt;variant>неформальная организация

Рассмотрим, как с помощью записей и массивов можно организовать стеки, очереди и списки, - структуры данных, играющих фундаментальную роль в программировании. Списки, и как частный их случай стеки и очереди, лежат в основе построения многих быстрых алгоритмом сортировки и поиска. Благодаря своим свойствам, они нашли широкое применение в программах информационного поиска, при моделировании различных процессов и других важных приложениях.

Здесь мы познакомимся с наиболее общими операциями над списками, стеками и очередями: их созданием, вставкой и удалением элементов, выводом на экран и некоторыми другими.

Стеком называется линейный список с одной точкой доступа, называемой вершиной (top). Элементы в стек могут добавляться или из него удаляться только через вершину (подобно тарелкам в стопке или патронам в «магазине» автомата Калашникова). Стек часто называют структурой LIFO (сокращение от last in – first out: последний вошел – первый вышел). Такое сокращение позволяет легко запомнить механизм работы стека.

Рассмотрим реализацию стека посредством массива. Напишем в виде процедур наиболее характерные операции при работе со стеками:

 

  1. Push(x,S) - операция добавления элемента x в стек S (от английского слова push- заталкивать);
  2. Pop(S) – операция удаления элемента из стека S (pop - выталкивать).

 

Хотя, учитывая устройство стека, эти процедуры будут работать только с первым его элементом, все другие элементы стека должны смещаться соответственно на одну позицию. Чтобы более рационально приспособить массивы для реализации стеков зафиксируем «дно» стека в самом низу массива, в ячейке с наибольшим индексом maxlength.

 

1-й элемент массива

2-й элемент массива

…….

 

Вершина стека

top 1-й элемент стека

2-й элемент стека

……

 

Последний эл-т массива

ьфдуm
maxlength

 

 

Пусть элементы массива имеют тип 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 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Введение.| Организация очереди

mybiblioteka.su - 2015-2024 год. (0.007 сек.)