Стеки и очереди (Лабораторная работа № 3)

Министерство образования Российской Федерации

НГТУ

Кафедра прикладной математики

Лабораторная работа  №3

По дисциплине: Структура данных и алгоритм

                     Тема: стеки и очереди

Группа: ПМ-33

Выполнила:

Проверила: Еланцева И Л

                                        Новосибирск 2004

1 Условие задачи

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

2 Анализ задачи

Дано: стек S

Результат: стек S после выполнения над ним операций.

Анализ

Для начала определим, что такое стек.      Стек – это список, у которого доступен один элемент (одна позиция).  Этот элемент называется вершиной стека. Взять элемент можно только из  вершины стека, добавить  элемент можно только в вершину стека.

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

…

             

NULL

             

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

 

В стеке, представленном линейным односвязным списком, вершина стека – первый элемент списка.

Определим теперь основные операции над стеком.

1. Взять элемент из стека.

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

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

                             X = значение S

                             T = S

                             S = след. за S элемент

                             Удалить элемент Т

                             Х – результат

              2. Положить элемент в стек

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

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

                             X – элемент который необходимо добавить

                             N = новый элемент типа стек

                             Информационное поле N = X

                             След. элемент за N = S

                             S = N

              3. Проверить пусти ли стек

Для проверки пустоты  стека достаточно проверить его вершину на указатель в никуда, т.е.  на равенство NULL

              4. Очистить стек

              Для того, чтобы очистить стек необходимо последовательно взять из него все элементы без сохранения результатов. То есть, алгоритмически это можно записать так:

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

                             ПОКА S не пуст

                                           T = S

                                           S = след. за S элемент

                                           Удалить элемент Т

              Определяя дополнительную операцию распечатки содержимого стека через основные, определенные выше, мы должны учесть условие, что в стеке мы можем брать элементы только с вершины и класть, соответственно, только на вершину. Поэтому, наверняка нам придется использовать какую-то вспомогательную структуру. Используем для этого второй такой же стек. Будем брать элементы из первого стека, распечатывать и складывать во второй. А затем в обратном порядке переложим все второго в первый.

              Алгоритм распечатки стека:

              S – Стек, который необходимо распечатать

              T = Новый стек

              ПОКА S не пуст

                             X = ИЗ_СТЕКА(S)

                             ПЕЧАТЬ Х

                             ВСТЕК(T,X)

              ПОКА T НЕ ПУСТ

                             X = ИЗ_СТЕКА(T)

                             ВСТЕК(S)

3 Структура основных входных и выходных данных

Структура входных

              В качестве входных данных программа получает команды, вводимые пользователем с клавиатуры. Для их обработки не требуется выделение отдельного типа структур данных

Структура выходных

              В качестве выходных – программа выдает состояние стека в текущий момент времени после выполнения над ним некоторых операций.

4 Текст программы

 

#include<stdio.h>

#include<conio.h>

#include"d:\bc\pp.cpp"

void main()

{//clrscr();

int k,x,f,a,c;

a=0;

c=0;

dstack *s,*r;

s=NULL;

while(a!=6)

{printf("\n Onepacii_nad dstakom");

printf("\n 1 Prosmotr steka");

printf("\n 2 Vzat element iz steka");

printf("\n 3 Pust li stek");

printf("\n 4 Dobavit element v stek");

printf("\n 5 Ochistit stek");

printf("\n 6 Vihod iz programmy");

printf("\n  Viberite punkt ");

scanf("%d",&a);

//clrscr()

if(a==2){

f=take(&s,&c);

if(f==1)

printf("Vzali element %d",c);

else printf("Element nelzya vzat stack pust") ;

a=1;

};

if(a==3)

{

c=check(s);

if(c==0) {printf("Stack pust");}

else{printf("stack ne pust");}

a=1;

};

if(a==4)

{

//clrscr();

printf("Vvedite element ");

scanf("%d",&x);

add(&s,x);

a=1;

};

if(a==5)

{

clear(&s);

a=1;

};

if(a==1){

printf("\n");

prf(s);

};

getch();}}

5 Набор тестов

пункт	результат
2	Element nelzya vzat stack pust
4	5
4	3
1	3 5
2	Vzali element 3
3	stack ne pust
1	5
5
3	stack  pust

6 Результаты отладки и их анализ

программа работает верно