4. Указания по выполнению работы
В качестве первого шага по выполнению работы следует построить схему алгоритма, по которой реализуется заданный процесс на основе стека. Существенными элементами указанной схемы алгоритма должны являться стандартные операции со стеком:
1) инициализация стека;
2) проверка: "пуст ли стек?";
3) проверка: "полон ли стек?";
4) затолкнуть элемент в стек;
5) вытолкнуть элемент из стека;
6) посмотреть верхний элемент стека.
Эти стандартные операции либо можно оформить в виде отдельных процедур или функций, либо внести в состав более общих процедур, разбиение на которые осуществляется в контексте конкретной задачи. В первом случае максимально достигается универсальность, так как стандартные процедуры, написанные для одной задачи, являются пригодными для всех остальных, использующих данную структуру.
Во втором случае при решении конкретной задачи можно добиться большого эффекта, жертвуя, однако при этом универсальностью. В примерах, которые даны в приложениях, применяется комбинированный подход, который и является наиболее распространенным. Однако студентам с целью наилучшего освоения структуры (как в этой лабораторной работе, так и в других) рекомендуется максимально использовать принцип универсальности.
Хорошо составленная схема алгоритма (хорошо составленная схема алгоритма, в частности, удовлетворяет требованию "наглядности") в качестве второго шага переводится на один из языков программирования.
Следует отметить, что при ясной, четкой схеме алгоритма существенно легче осуществить третий этап выполнения лабораторной работы-отладка программы. В противном случае процесс отладки программы может стать утомительным и неэффективным занятием.
Приложение 1 Пример программы с использованием стека
Пусть требуется введенную последовательность символов прочитать в обратном порядке, устранив предварительно повторяющиеся соседние символы.
Для решения этой задачи представим стек в виде символьного массива. При этом максимальное число элементов этого массива будет соответствовать верхней границе стека. Введем следующие обозначения:
процедура "инициализации"- ins(var st:stec)
процедура "выталкивания"- push(var st:stec)
процедура "заталкиваниия"- pop(var st:stec)
функция "стек не пуст"- empty(var st:stec):boolean
функция "стек не полон"- full(var st:stec):boolean
функция "показать верхний элемент"- werx(var st:stec):char
Ниже приведен текст программы на языке Турбо Паскаль.
program stek;
uses crt;
CONST glub=80;
type
p=array[0..glub]of char;
stec=record {модель стека}
ve:0..glub;
sim:p;
end;
var
st:stec;
{**************************************************************
инициализация
***************************************************************}
procedure ins(var st:stec);
begin
clrscr;
st.ve:=0;
end;
{**************************************************************}
function werx(st:stec):char;
forward;
{**************************************************************
стек не пуст
*************************************************************}
function empty(st:stec):boolean;
begin
clrscr;
if st.ve<>0 then empty:=true
else empty:=false;
end;
{**************************************************************
. стек не полон
*************************************************************}
function full(st:stec):boolean;
begin
clrscr;
if st.ve=glub then full:=false
else full:=true;
end;
{****************************************************************
заталкивание
***************************************************************}
procedure push(var st:stec);
var
x,k:char;
i:integer;
begin
writeln('Введите последовательность символьных переменных');
i:=st.ve-1;
with st do
begin
while not(eoln) do
begin
read(x);
if((werx(st)<>x)or(not(empty(st)))) then
begin
if full(st) then
begin
ve:=ve+1;
i:=i+1;
sim[i]:=x;
end
else
write('ввод не возможен стек полон');
end;
end;{конец ввода строки}
end; {конец для st}
end;
{***********************************************************************
вытолкнуть
********************************************************************}
procedure pop(var st:stec);
var
n:integer;
xx:char;
begin
clrscr;
if empty(st) then
begin {стек не пуст}
with st do {для st}
begin
ve:=ve-1;
n:=ve;
while n>=0 do
begin
write(sim[n],' ');
n:=n-1;
end
end;
end
else writeln('стек пуст');
end;
{******************************************************************
показать верхний элемент
******************************************************************}
function werx(st:stec):char;
begin
clrscr; {очистка экрана}
if empty(st) then
werx:=st.sim[st.ve-1] {стек не пуст возвращаем верхний элемент}
else werx:=' ' ; {иначе возвращаем пробел}
end;
{**** программа ******}
BEGIN
repeat
readln;
clrscr; {очистка экрана}
ins(st); {инизиализация стека}
push(st); {заталкивангие в стек}
pop(st); { выталкивание из стека}
writeln;
writeln('если хотите окончить работу нажмите ESC, иначе продолжение');
until readkey=#27; {выход по нажатию ключа}
END.
ПРИЛОЖЕНИЕ 2
Пример программы с использованием стека на С++
Ниже приведена программа на языке С++ для задачи, приведенной в
в приложении 1.
/* !!=======================!!
!! стек !!
!!=======================!! */
#include <dos.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <mem.h>
int nfull(int f);
int nempty(int e);
int push(char *pt,char *st,int f);
int pop( char *sym,char ste,int e);
int main ()
{
int i,kod,top;
char stek[50],*st,symb,ch[80],*ptrr;
st=stek;
ptrr=ch;
/* ******************************************************************
Основная программа
****************************************************************** */
top=st-&stek[0]; /* инициализация стека */
printf("введите последовательность символов: при окончании строки нажмите'='\n");
scanf("%[^\n]",ptrr);
printf("\n");
/* заталкивание в стек последовательности сим.*/
push(&*ptrr,&*st,top);
ptrr++;
for(i=0; ((*ptrr!=0)&&(top<50));ptrr++,i++)
{
if (*ptrr!=*(ptrr-1)) /* исключение соседних одинаковых */
{ top++; st++;
push(&*ptrr,&*st,top);
}
} /* конец заталкивания */
printf("\n");
/* выталкивание из стека последовательности сим.*/
printf("искомая последовательность символов \n ");
for(i=top;i>-1;i--,top--)
{ pop(&symb,stek[top],top);
printf("%c",symb);
} /* конец выталкивания */
printf("\n");
}
/* *************************************************************
. стек не полон
************************************************************* */
int nfull(int f)
{
if (f>=50) return(0);
else return(1);
}
/* *************************************************************
стек не пуст
************************************************************* */
int nempty(int e)
{
if (e<0 ) return(0);
else return(1);
}
/* **********+++++++++++++++++++++++++++**********************************************
заталкивание элемента
*************************************************************** */
int push(char *pt,char *tp,int f)
{
if (nfull(f)) {
*tp=*pt; /* ввод символa в стек */
}
else{
printf("стек полон\n");
return(1);
}
}
/* ***************************************************************
выталкивание элемента
*************************************************************** */
int pop(char *sym,char ste,int e)
{
if (nempty(e)) {
*sym=ste; /* выталкивание символa из стека */
}
else{
printf("стек пуст\n");
return(0);
}
}