Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Стеки
Стек – структура данных, которая содержит упорядоченный набор элементов. Если в стек помещается новый элемент, он добавляется в конец упорядоченного набора (на вершину стека). При удалении элемента он тоже выбирается из конца набора (из вершины стека).
В основе реализации рекурсивной подпрограммы лежит структура данных, называемая стеком, в котором хранятся все неглобальные данные, участвующие во всех вызовах подпрограммы, при которых она еще не завершила свою работу.
Стек разбит на фрагменты, представляющие собой блоки последовательных ячеек. Каждый вызов подпрограммы использует фрагмент стека, длина которого зависит от вызывающей подпрограммы.
В общем случае при вызове процедурой А процедуры В происходит следующее:
1. В вершину стека помещается фрагмент нужного размера. В него входят следующие‚ данные:
(а) указатели фактических параметров вызова процедуры В;
(б) пустые ячейки для локальных переменных. определенных в процедуре В;
(в) адрес возврата (АВ), т.е. адрес команды в процедуре А, которую следует выполнить после того, как процедура В закончит свою работу.
Если В - функция, то во фрагмент стека для В помещается указатель ячейки во фрагменте стека для А, в которую надлежит поместить значение этой функции (адрес значения).
2. Управление передается первому оператору процедуры В.
3. При завершении работы процедуры В управление передается процедуре А с помощью следующей последовательности шагов:
(а) адрес возврата извлекается из вершины стека
(б) если В функция, то ее значение запоминается в ячейке, предписанной указателем на адрес значения;
(в) фрагмент стека процедуры В извлекается из стека, в вершину ставится фрагмент процедуры А;
(г) выполнение процедуры А возобновляется с команды, указанной в адресе возврата.
При вызове подпрограммой самой себя, т.е. в рекурсивном случае, выполняется та же самая последовательность действий.
Стек — динамическая структура данных, представляющая из себя упорядоченный набор элементов, в который добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека.
По определению, элементы извлекаются из стека в порядке, обратном их добавлению в эту структуру, т.е. действует принцип "последний пришёл — первый ушёл".
Наиболее наглядным примером организации стека служит детская пирамидка, где добавление и снятие колец осуществляется как раз согласно определению стека.
Стек является простейшей динамической структурой. При выборке элемент исключается из стека.
Говорят, что стек реализует принцип обслуживания LIFO (last in — first out, последним пришел — первым обслужен). Стек можно представить себе как узкое дупло, в которое засовывают, скажем, яблоки. Достать первое яблоко можно только после того, как вынуты все остальные.
Кстати, сегмент стека назван так именно потому, что память под локальные переменные выделяется по принципу LIFO. Стеки широко применяются в системном программном обеспечении, компиляторах, в различных рекурсивных алгоритмах.
Стек можно реализовать с помощью массива. Пусть известно, что количество его элементов не превышает n. Кроме массива элементов, соответствующих типу данных стека, дос таточно иметь одну переменную целого типа для хранения индекса элемента мас сива, являющегося вершиной стека. При помещении в стек индекс увеличивается
на единицу, а при выборке — уменьшается. Например, стек, можно описать так:
const n=100;
type node=record
d:word; { информационная }
s:string; { часть }
end;
stack=array[1 .. n] of node;
var st:stack;
top:word;
В начале работы со стеком переменная top обнуляется. Занесение в стек выгля дит примерно так:
inc(top);
if top > n then begin
writeln('переполнение стека'); exit end;
st[top].d:=d;
st[top].s:=s;
При использовании динамической памяти вместо массива описывается указа тель на массив:
var st : ^stack;
Перед использованием такого стека необходимо выделить под него память:
new(st);
Обращение к элементу стека будет содержать операцию разадресации:
st^[top].d:=d;
Реализация стека помощью линейного списка
Наиболее подходящим для реализации стека является линейный однонаправленный список.
Для такого списка достаточно хранить указатель вершины стека, который указывает на первый элемент списка. Если стек пуст, то списка не существует и указатель принимает значение nil.
Рис.1.6. Организация стека на основе линейного списка.
С помощью линейного списка можно описать стек следующим образом
Type Tptr=^TElem; {Тип указателя на элемент стека}
TElem = record {Тип элемента стека }
inf :integer; {информационная часть}
link : Tptr; {соединительная часть}
end;
Задание
Пример №1 из прошлого занятия оформить стеком.
Пример №1
Итак, списком называется структура данных, каждый элемент которой связан с предыдущим (следующим) элементом. Элемент списка — это запись, состоящая из двух частей. Первая часть содержит поле данных. Вторая часть содержит поле ссылки на предыдущий (следующий) элемент. Последний элемент списка должен содержать пустое (Nil) поле ссылки. Очередной элемент может быть добавлен в начало, в середину или в конец списка. Любой элемент может быть исключен из списка.
Сформировать список, содержащий цифры: 0, 1, 2, 3, 4 (рис. 1). Очередной элемент должен добавляться в начало списка.
Рис.1. Список цифр
Результатом работы программы должен быть вывод на экран списка цифр, начиная с 0. Программа, реализующая заданные условия, имеет вид:
Program List;
Type number=^N;
N=record{Описатель типа элемента списка}
Data:integer;{поле данных}
Next: number;{поле ссылки}
End;
Var head: number;{Указатель на начало списка}
Current:number;{Указатель на текущий элемент списка}
Digit: integer;{вводимые значения}
Begin
Repeat
Write(‘Цифра-’); {ввод цифр с клавиатуры}
Readln(Digit);
New(Current); {создать элемент списка}
Current^. data:= digit; {записать в поле данных цифру}
Current^. Next:= head; {записать в поле ссылки начало списка}
Head:= Current; {значение указателя – на начало списка }
Until Digit=0;
Write(‘****Список****’); {ввод элементов списка}
Current:= Head;
while Current<>nil do
Begin
Write(‘’, Current^. data);
Current:= Current^. Next;
End; end.
Протокол работы программы:
Цифра-4
Цифра-3
Цифра-2
Цифра-1
Цифра-0
‘****Список****
0 1 2 3 4
Тема «Работа с динамическим стеком»
Рассмотрим пример.
Пусть задано описание стека и переменных
Type Tptr = ^TElem; {Тип указателя на элемент стека}
TElem = record {Тип элемента стека}
inf : char; {информационная часть}
link : Tptr; {соединительная часть}
end;
Var top,р : tptr; {Указатели, top – вершина стека, р - вспомогательный}
value : char;
i: byte;
Типовыми операциями над стеком и его элементами являются:
добавление элемента в стек;
удаление элемента из стека;
проверка, пуст ли стек;
просмотр элемента в вершине стека без удаления;
очистка стека.
Исходное состояние:
3.Перемещение вершины стека Top на новый элемент:
1. Исходное состояние
2.Извлечение информации из информационного поля вершины стека Top в переменную Val и установка на вершину стека вспомогательного указателя P:
3. Перемещение указателя вершины стека Top на следующий элемент и освобождение памяти, занимаемой "старой" вершиной стека:
Пример 1. Разместить в стеке 10 символов и распечатать их в обратном порядке.
Hиже приводится пример программы, использующей стек. В ней используются следующие процедуры для работы со стеком:
Program Stack;
Type Tptr = ^TElem; {Тип указателя на элемент стека}
TElem = record {Тип элемента стека}
inf : char; {информационная часть}
link : Tptr; {соединительная часть}
end;
Var top : tptr; {Указатель на конец стека}
value : char;
i: byte;
Procedure Push(val : char; var Top:Tptr); {Процедура добавления элемента}
Var p : tptr; {Вспомогательный указатель}
Begin
new (p);
p^.inf:=val;
p^.link:=top;
top:=p
End;
Procedure Pop(var val : char; var Top:Tptr); {Процедура удаления элемента}
Var p : tptr; {Вспомогательный указатель}
Begin
val:=top^.inf;
p:=top;
top:=p^.link;
dispose (p)
End;
Begin
new(top); { Создание указателя на вершину стека }
top:=nil;
for i:=1 to 10 do
begin
writeln (' введите символ');
readln (value);
push(value,Top); {добавление элемента в стек}
end;
i:=10;
while top<>nil do {пока не будет достигнут конец стека}
begin
pop(value, Top); {извлечение элемента из стека}
writeln (i,'-й символ - ',value);
dec (i)
end
End.
Пример 2. Ввести с клавиатуры 8 чисел и сформировать из них два стека. В первый поместить числа, которые делятся на 2, а во второй -остальные. Распечатать оба стека.
Type Tptr=^TElem; {Тип указателя на элемент стека}
TElem = record {Тип элемента стека }
inf :integer; {информационная часть}
link : Tptr; {соединительная часть}
end;
Var top1,top2 : tptr; {Указатели на конец стеков}
value : integer;
i: byte;
Procedure Push(val : integer; var top:tptr); {Процедура добавления элемента}
Var p :tptr; {Вспомогательный указатель}
Begin
new (p);
p^.inf:=val;
p^.link:=top;
top:=p
End;
Procedure Pop(var val : integer; var top:tptr); {Процедура удаления элемента}
Var p : tptr; {Вспомогательный указатель}
Begin
val:=top^.inf; p:=top;
top:=p^.link; dispose (p)
End;
Begin
new (top1); {Создание указателя на вершину 1-го стека }
new (top2); { Создание указателя на вершину 2-го стека }
top1:=nil; top2:=nil;
for i:=1 to 8 do
begin
writeln (' введите число'); readln (value);
if value mod 2 =0 then
push(value,top1)
else
push(value,top2)
end;
writeln (' 1-й стек - числа делятся на 2 ');
while top1<>nil do
begin
pop(value,top1);
writeln (value);
end;
writeln (' 2-й стек - - числа не делятся на 2');
while top2<>nil do
begin
pop(value,top2);
writeln (value);
end
End.
Далее приводится материал для самостоятельной работы
Пример программы, реализующей стек как динамическую структуру.
Программу отладить дома.
Program stack;
type
element=record
data:string;
next:pointer;
end;
var
n: integer;
current:^element;
pnt:^element;
procedure put_element(s:string); {занесение элемента в стек}
begin
new(pnt);
x^.data:=s;
x^.next:=current;
current:=pnt;
end;
procedure get_element(var s:string); {получение элемента из стека}
begin
if current=nil then s:=▓пусто▓ else
begin
pnt:=current;
s:=pnt^.data;
current:=pnt^.next;
dispose(pnt);
end;
end;
{------------program--------------}
begin
current:=nil;
repeat
writeln(▒1 √ добавить в стек▓);
writeln(▒2 √ удалить из стека▓);
writeln(▒0 √ выход▓);
readln(n);
if n=1 then
begin
write(▒элемент ? ▓);
readln(s);
put_element(s);
end;
if n=2 then
begin
get_element(s);
writeln(s);
end;
until n=0;
end.
В программе добавление нового элемента в стек оформлено в виде процедуры put_element, а получение элемента из стека √ как процедура get_element.
Некоторые пояснения
Пусть
type pnode = ^node;
node = record { элемент стека }
----
------
End;
var
top, p : pnode; {Указатели, top - вершина стека, p - вспомогательный указатель }
Для работы со стеком используются две статические переменные:
указатель на вершину стека и вспомогательный указатель.
Тип указателей должен соответствовать типу элементов стека.
Занесение первого элемента в стек выполняется в два приема:
сначала выделяется место в памяти и адрес его начала заносится в указатель на вершину стека (оператор 1), а затем заполняются все поля элемента стека (операторы 2):
new(top); {1}
top^.d:=100;
top^.s:=’Вася’;
top^.p:=nil; {2}
Значение nil в поле указателя на следующий элемент говорит о том, что этот элемент в стеке является последним (рис. 5.4).
При добавлении элемента в стек кроме создания элемента и заполнения его информационной части (операторы 1 и 2) требуется связать его с предыдущим top (оператор 3) и обновить указатель на вершину стека (оператор 4), потому что теперь в вершине стека находится новый элемент:
new(p);
p^.d:=10; {1}
p^.s:=’Петя’; {2}
p^.p:=top; {3}
top:=p; {4}
Стек, состоящий из трех элементов, изображен на рис. 5.5.
Выборка из стека состоит в получении информационной части элемента (оператор 1), переносе указателя на вершину стека на следующий элемент (оператор 2) и освобождении памяти из-под элемента (оператор 3):
with top^ do writeln(d, s);
p:=top; {1}
top:=top^.p; {2}
dispose(p); {3}
Рассмотренные операции удобно оформить в виде отдельных функций. Ниже приведена программа, которая формирует стек из пяти целых чисел и их текстового представления и выводит его на экран.
Функция занесения называется push, а функция выборки — pop.
program stack;
const n = 5;
type pnode = ^node;
node = record { элемент стека }
d:word;
s:string;
p:pnode:
end:
var top:pnode; { указатель на вершину стека }
i:word:
s:string;
const text : array [1 .. n] of string = (‘one’, ‘two’, ‘three’, ‘four’, ‘five');
{------------------------------ занесение в стек -------------------------}
function push(top:pnode; d:word; const s:string):pnode;
var p:pnode;
begin
new(p);
p^.d := d; p^.s := s; p^.p := top;
push := p;
end:
{------------------------------ выборка из стека--------------------------}
function pop(top : pnode; var d:word; var s:string):pnode;
var p:pnode:
begin
d:= top^.d; s := top^.s;
pop := top^.p;
dispose(top);
end:
{--------------------------- главная программа -------------------------}
begin
top := nil:
{ занесение в стек: }
for i := 1 to n do top := push(top. i, text[i]);
{ выборка из стека: }
while top <> nil do begin
top:=pop(top, i, s); writeln(i:2, s);
end;
end.
Обратите внимание на то, что вспомогательный указатель объявлен внутри функций, а их интерфейс содержит все необходимые сведения: с каким стеком идет работа и что в него заносится или выбирается. Функции возвращают указатель на вершину стека.
Более подробно с пояснениями рассмотрим следующий пример работы со стеком
Пусть поле p - указатель; поле D - данные. Описание этой компоненты дадим следующим образом:
type
Pointer = ^Comp;
Comp = record
D:T;
pNext:Pointer
end;
Пусть описание переменных имеет вид:
var pTop, pAux: Pointer;
где pTop - указатель вершины стека;
pAux - вспомогательный указатель.
Начальное формирование стека выполняется следующими операторами:
New(pTop); - в памяти ЭВМ выделяется участок для размещения величины определенного типа и адрес этого участка присваивается переменной pTop:
pTop^.pNext:=NIL;
pTop^.D:=D1;- записывает содержимое поля данных первой компоненты.
Добавление компоненты в стек производится с использованием вспомогательного указателя:
New(pAux);
pAux^.pNext:=pTop;
pTop:=pAux;
Механизм получения 2 компоненты и её связи с первой.
pTop^.D:=D2; pTop^.D→→ D2→ D1
Механизм процесса выборки компонент из стека
Первый оператор или группа операторов осуществляет чтение данных из компоненты(Например-D3:) - вершины стека. Второй оператор изменяет значение указателя вершины стека:
D3:=pTop^.D;
pTop:=pTop^.pNext;
Type
EXST = ^ST;
ST = record
Data : integer;
Next : EXST;
end;
Var
Stack : EXST; {Текущая переменная}
Процедуры работы со стеком
Занесение элемента в стек производится аналогично вставке нового элемента в начало списка. Процедура занесения элемента в стек должна содержать два параметра: первый задает вершину стека, в который нужно занести элемент, второй – заносимое значение элемента стека.
Процедура формирования стека будет иметь следующий вид:
Procedure FormStack;
Var
Stack : EXST; {Текущая переменная}
Digit : integer;
Procedure writeStack(Var u : EXST; Digit : integer);
Var x : EXST;
Begin
new(x); {выделяем память под хранение нового элемента стека}
x^.Data := Digit; {заполняем поле данных элемента}
x^.Next := u; {новый элемент "связываем" со стеком}
u := x; {созданный элемент определяем как вершину стека}
End;
Begin
Stack := Nil; {инициализация стека}
writeln('Введите элементы стека. Окончание ввода – 0');
read(Digit);
while Digit <> 0 do
begin
writeStack(Stack, Digit);
read(Digit);
end;
End;
Извлечение элемента из стека
В результате выполнения этой операции некоторой переменной i должно быть присвоено значение первого элемента стека и значение указателя на начало списка должно быть перенесено на следующий элемент стека.
Procedure readStack(Var u : EXST; Var i : integer);
Var
x : EXST;
Begin
i := u^.Data; {считываем значение поля данных в переменную}
x := u; {запоминаем адрес вершины стека}
u := u^.Next; {переносим вершину стека на следующий элемент}
dispose(x); {освобождаем память, занятую уже ненужным элементом стека}
End.
Недостатком описанной процедуры является предположение о том, что стек не пуст. Для его исправления следует разработать логическую функцию проверки пустоты обрабатываемого стека.
Function FreeStack(u : EXST) : boolean;
Пример.
Составить программу, которая формирует стек, добавляет в него произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея, В качестве данных взять строку символов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка символов END.
Program STACK;
uses Crt;
type
Alfa= String[10];
PComp= ^Comp;
Comp= Record
sD: Alfa;
pNext: PComp
end;
var
pTop: PComp;
sC: Alfa;
Procedure CreateStack(var pTop: PComp; var sC: Alfa);
begin
New(pTop);
pTop^.pNext:=NIL;
pTop^.sD:=sC
end;
Procedure AddComp(var pTop: PComp; var sC: Alfa);
var pAux: PComp;
begin
NEW(pAux);
pAux^.pNext:=pTop;
pTop:=pAux;
pTop^.sD:=sC
end;
Procedure DelComp(var pTop: PComp; var sC:ALFA);
begin
sC:=pTop^.sD;
pTop:=pTop^.pNext
end;
begin
Clrscr;
writeln(' ВВЕДИ СТРОКУ ');
readln(sC);
CreateStack(pTop,sC);
repeat
writeln(' ВВЕДИ СТРОКУ ');
readln(sC);
AddComp(pTop,sC)
until sC='END';
writeln('****** ВЫВОД РЕЗУЛЬТАТОВ ******');
repeat
DelComp(pTop,sC);
writeln(sC);
until pTop = NIL
end.
Задание
1. Набрать программу и пояснить алгоритм работы
Структура односвязного списка - 'стек'
Тип информационного поля - вещественный
Поиск: 1-го элемента, имеющего значение > заданного
program list;
type
data = ^dat;
dat = record
r: real;
link: data;
end;
var
BegQ, p: data;
r2: real;
procedure create;
var
i, j: integer;
begin
writeln('Введите изначльное количество элементов стэка');
read(j);
BegQ := nil;
p := nil;
for i := 1 to j do
begin
new(p);
write('Введите элемент стека ');
read(p^.r);
if BegQ = nil then p^.link := nil else p^.link := BegQ;
BegQ := p;
end;
end;
begin
create;
write('Введите критерий поиска ');
read(r2);
p := BegQ;
if begQ^.r > r2 then
begin
write(BegQ^.r);
Exit;
end
else
repeat
begin
if p^.r > r2 then
begin
write(p^.r);
exit;
end;
p := p^.link;
end;
until p^.link = nil;
end.
2. Доработать и отладить программу для создания списка в стеке из 5-ти записей, в которых хранятся целые числа.
При указании на тип записи обычно используется следующая конструкция:
type uk =^rec;
rec=record
inf:integer;
v:uk;
end;
program;
type uk=^rec;
rec=record
v:uk;
c:integer
end;
var top,pred,tek:uk; k:integer; {top-указатель на вершину стека, tek-на текущую, pred-на предыдущую запись}
begin
pred :=nil;
for k:=1 to 5 do
begin new(tek);{резервируется память}
tek^.c:=k; {заносится информация}
tek^.v:=pred; {v указывает на предыдущую запись}
pred:=tek; {в pred заносится адрес текущей записи}
top:=tek;
end;
tek:=top;
for k:=1
Вывод элементов стека производится в обратном порядке. Его можно осуществлять по следующему условию:
tek:=top;
while tek <> nil do
begin
writeln(tek^.c);
tek:=tek^.v;
end;
Начиная с вершины стека (указатель top), просматриваются все записи до тех пор, пока список не будет исчерпан, т.к. самая первая запись никуда не указывает. Чтобы удалить запись из стека, достаточно переместить указатель его вершины:
top:=top^.v;
Разобраться с процедурами и функциями
Хорошим примером применения стека является калькулятор, который может выполнять четыре действия. Большинство калькуляторов используют стандартную форму выражений, которая носит название инфиксной формы. В общем виде ее можно представить в виде "операнд-оператор-операнд". Например, для прибавления 100 к 200 вы должны ввести число 100, набрать символ сложения, ввести число 200 и нажать клавишу со знаком равенства. Однако, некоторые калькуляторы применяют другую форму выражений, получившую название постфиксной формы. В этом случае оба операнда вводятся перед вводом оператора. Например, для добавления 100 к 200 при использовании постфиксной формы сначала вводится число 100, затем вводится число 200 и после этого нажимается клавиша со знаком плюс. Введенные операнды помещаются в стек. При вводе оператора из стека выбираются два операнда и результат помещается в стек. При использовании постфиксной формы очень сложные выражения могут легко вычисляться на калькуляторе.
Ниже показана программа для такого калькулятора.
{калькулятор с четырьмя операциями, иллюстрирующий работу}
Пример 2.
program four_function_calc;
const
MAX = 100;
var
stack: array [1..100] of integer;
tos:integer;{указатель вершины стека}
a, b:integer;
s:string[80];
{поместить объект в стек}
procedure Push(i:integer);
begin
if tos >= MAX then Writeln('Стек полон') else
begin
stack[tos] :=1;
tos := tos+1;
end;
end;{Push}
{выборка объекта из стека}
function Pop:integer;
begin
tos := tos-1;
if tos < 1 then
begin
Writeln('Стек переполнен')
tos := tos+1;
Pop := 0;
end;
else Pop := stack[tos];
end;{Pop}
begin{калькулятор}
tos := 1;
Writeln('For Function Calculator');
repeat
Write(': '); { вывод приглашения }
Readln(s);
Val(s, a, b) { преобразование строки символов в целое число }{ считается, что при успешном преобразовании пользователь ввел число, а в противном случае пользователь ввел оператор}
if (b=0) and ((Length(s)>1) or (s[1]<>'-')) thenPush(a);
else case s[1] of
'+' begin
a := Pop;
b := Pop;
Writeln(a+b);
Push(a+b);
end;
'-' begin
a := Pop;
b := Pop;
Writeln(b+a);
Push(b+a);
end;
'*' begin
a := Pop;
b := Pop;
Writeln(a*b);
Push(a*b);
end;
'/' begin
a := Pop;
b := Pop;
if a=0 then Writeln('делим на ноль')
else
begin
Writeln(b div a);
Push(b div a);
end;
end;
'.' begin
a := Pop
Writeln(a);
Push(a);
end;
end;
until UpCase(s[1])='G';
end.
Для того чтобы посмотреть, что находится в вершине стека, достаточно ввести точку. Хотя данная программа выполняет арифметические действия только с целыми числами, ее легко можно приспособить для чисел с плавающей запятой, изменяя тип данных стека и преобразуя, оператор "div" в оператор деления для чисел с плавающей запятой (наклонная черта).
pTop
D1
pAux
pTop
Aux
D1
NIL