Методические указания для выполнения лабораторных работ и курсовой работы содержание

Вид материала

Методические указания

Содержание 9Лабораторная работа № 8. Стек 2. Цель работы 4. Указания по выполнению работы

Подобный материал:

• Методические указания по выполнению курсовых работ для студентов заочной формы обучения, 300.18kb.
• Рабочая программа, методические указания по выполнению курсовой работы, темы курсовых, 1694.43kb.
• Методические указания по выполнению курсовой работы Составитель Виничук, 2013.82kb.
• Методические указания для выполнения курсовой работы по дисциплине «Макроэкономика», 976.03kb.
• Методические указания к выполнению лабораторных работ по дисциплине «Интеллектуальные, 653.36kb.
• Методические указания для выполнения курсовой работы по дисциплине: «Метрология, стандартизация, 170.43kb.
• Методические указания для выполнения курсовой работы по дисциплине «Теория принятия, 547.84kb.
• Методические указания для ее выполнения по дисциплине «финансы» 2008-2009 уч. Год (для, 247.31kb.
• Методические указания по содержанию и организации выполнения курсовой работы по дисциплине, 1445.93kb.
• Петроченко Любовь Викторовна Учебно методические указания, 199.16kb.

9Лабораторная работа № 8. Стек

1.Общие понятия


Стеком называется линейно-упорядоченная последовательность Е(1),Е(2),.,Е(n), где n>0, причем каждый элемент характеризуется одним и тем же набором полей. В общем случае "n" не является const. Это обстоятельство позволяет назвать стек полу статической структурой. В стеке реализуется принцип LIFO (последний пришел - первый ушел), или по другому принцип "мешка"-то, что положено в последнюю очередь, вынимается в первую. Этот принцип оказывается очень удобным при решении некоторых специальных задач, связанных, например, с использованием рекурсии или анализом арифметических выражений. Он поддерживается обращением к стеку через указатель, указывающий на верхний занятый слот (значение этого указателя изменяется в пределах, определённых при описании стека). При этом можно говорить об обычной модели стека, если все операции производятся только над верхними элементами стека, и о расширенной

модели стека, в которой могут производиться операции и над элементами, лежащими в глубине стека. Нужно помнить, что стек считается одной из самых "быстродействующих структур". Поэтому при использовании расширенной модели стека число операций с верхними элементами должно быть существенно больше, чем с глубинными, так как в противном случае стек теряет свои "скоростные" качества и его применение становиться нецелесообразным.


2. Цель работы


Целью работы является изучение и отработка технологии и навыков использования стеков в организации алгоритмических структур. Машинная реализация этих структур планируется на языке Турбо Паскаль или С++.


Эта работа выполняется в два этапа. На первом этапе создается модуль, который описан по соответствующему формату (см. лекции) и содержит полную информацию о стеке (т.е. его описание и функции, изменяющие его состояние). Далее следует объединить этот модуль с основной программой и выполнить соответствующий из нижепредставленных простых вариантов.

На втором этапе, используя созданный ранее для поддержания стека модуль, решить соответственно вариантам второго списка более сложную алгоритмическую задачу.


3 Список вариантов для первого зтапа

Используя стек, выполнить следующие варианты:

1. Обменять значения в двух переменных;

2. Обменять значения в трех переменных в следующем порядке : 1->2,2->3,3->1;

3. Обменять значения в трех переменных в следующем порядке : 1->3,3->2,2->1;

4. Обменять значения в трех переменных в следующем порядке : 2->1,3->2,1->3;

5. Обменять значения в трех переменных в следующем порядке : 2->3,1->2,3->1;

6. Представить в польской записи выражение a+b;

7. Представить в польской записи выражение a-b;

8. Представить в польской записи выражение a*b;

9. Представить в польской записи выражение a/b;

10. Представить в польской записи выражение a+b*c;

11. Представить в польской записи выражение c*a+b;

12. Представить в польской записи выражение c*a-b;


4. Варианты заданий для второго этапа


При выполнении заданий следует задействовать все стандартные операции работы со стеком, каждая из которых должна быть оформлена в виде отдельной процедуры или функции.

1.Используя стек, сравнить символьный запрос с набором шаблонов.

2.Используя стек, разработать механизм вычисления арифметических выражений, записанных в постфиксной форме.

3.В режиме мультистека (не менее 4-х простых стеков) организовать сравнение элементов простых стеков, находящихся на одинаковом расстоянии от вершины стека с последующим выводом одинаковых элементов на экран.

4.Используя стек, разработать процедуру обнаружения некорректных скобок в арифметических выражениях, записанных в инфиксной форме.

5.Используя стек, преобразовать инфиксную форму без скобок в постфиксную.

6.Используя стек, преобразовать инфиксную форму в постфиксную.

7.Используя стек, создать простейшую БД, содержащую сведения о студентах.

8.Используя стек, вывести из экзаменационной ведомости список студентов, получивших одинаковые оценки.

9.Используя стек, сосчитать вероятность появления в тексте букв: а,б,в.

10.Используя стек, определить символ, наиболее часто появляющийся в случайно выбранном тексте.

11.Используя стек, разработать процедуру изъятия лишних скобок.

12.Разработать комплекс процедур, позволяющих организовать работу двух стеков, которые занимают одну область памяти.

13.Используя стек, построенный в динамической памяти, введенную последовательность символов прочитать в обратном порядке, устранив повторяющие символы.

14.Объединить два стека в один таким образом, чтобы элементы в нем следовали в алфавитном порядке.

15.Для стека, организованного в динамической памяти, построить все стандартные операции со стеками.

16.Организовать обмен данных между двумя стеками, один из которых построен на статической памяти, а другой на динамической.

17.Перевести выражение, представленное в постфиксной форме, в инфиксную форму.

18.Организовать с помощью стека передачу локальных параметров в подпрограм­му при встроенном ассемблере.

19.Использование стека для вывода числа в 4 байтном формате на ассемблере.

20.Перевести префиксное выражение в инфиксное.

21.Используя стек, вычислить выражение в префиксной форме.

22.Перевести инфиксное выражение в выражение в префиксной форме.


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

#include

#include

#include

#include


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);

}

}