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

Министерство образования и науки

Российской Федерации

Новосибирский Государственный Технический Университет

Кафедра ПМт

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

Тема: «Структуры данных и алгоритмы»

Студент: Вознюк А.В

Факультет: ПМИ

Группа: ПМ-95

Преподаватель: Еланцева И.Л.

Новосибирск, 2010

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

1.  Написать  операции работы с заданной структурой данных, включив их в один

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

2.  Написать программу, демонстрирующую выполнение операций, над заданной

структурой данных. Эту программу надо поместить в свой модуль (файл). Модуль с основными операциями включать в программу, используя директиву include. 

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

          Дано:  S= {S| Sсимвол i =1,2,…}

          Результат: B= {b | bсимвол i =1,2,…} или сообщение об отсутствии

                                                                                                               символа в стеке

          Решение: 

1.  Создание пустого стека

      i=0

2.  Добавление элемента в стек

     a=b

     i=i+1;

3.  Удаление элемента из стека

      если i>0, то

      b=a

      i=i-1

      вывод b

      иначе вывести сообщение об ошибке

4.  Вывод элементов стека на экран

      j=i

     повторять

     вывод a

      j=j-1

     пока  j0

5.  Проверка стека на пустоту

     если i>0, то стек не пуст

     иначе стек пуст

Очевидно, что при решении задачи выделяются след подзадачи:

1.  Создать стек

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

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

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

5.  Вывести содержимое стека на экран

3. Структуры  данных

Внешнее представление:

                    Входные данные: последовательность символов на экране   

                    Выходные данные: последовательность символов на экране   

Внутреннее представление:

                    Входные данные: Динамический стек представлен линейным однонаправленным не циклическим списком без заглавного звена. Элемент списка представлен структурой: struct dstack{int el; dstack *next;};    

                    Выходные данные: Динамический стек представлен линейным однонаправленным не циклическим списком без заглавного звена. Элемент стека представлен структурой: struct dstack{int el; dstack *next;};    

4. Алгоритмы

                 Алгоритм решения подзадачи newstack (создание нового стека):

 

  

                 Алгоритм решения подзадачи instack (добавление нового элемента в

                стек):

               

                  Алгоритм решения подзадачи outstack (удаление элемента из стека):

 

                  Алгоритм решения задачи pust (проверка на пустоту):

k=0

                

 

                  

                       

                  Алгоритм решения задачи prosmotr (вывод на экран):

                

 

                 Алгоритм решения основной задачи:

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

//модуль вклчает в себя функции

//для работы с динамическим стеком       

#include <stdio.h>

     struct dstack

     {int el;

       dstack *next;};

//функция добавления элемента в стек

     void instack (int x, dstack **S)

     {

      dstack *r;

      r = new dstack;

      r->el = x;

      r->next=*S;

      *S=r;

     }

//функция проверки стека на пустоту

     int pust (dstack *S)

     {

      if (S==NULL) return 1;

      return 0;

     }

//функция взятия элемента из стека

     int outstack(int *x, dstack **S)

     {

      dstack *r;

      int t;

      t=pust (*S);

      if (t==0)

      {r=*S; *x=r->el;

       *S=r->next;

       delete r;

       return 1;

      }

      return 0;

     }

//функция создания стека

     void newstack (dstack **S)

     {

      *S=NULL;

     }

//функция просмотра стека

     void prosmotr (dstack **S)

     {

      dstack *r;

      newstack (&r);

      while (pust (*S)!=1)

      {int q;

       int x;

       q=outstack (&x, S);

       printf ("%d ", x);

       instack (x, &r);

     }

      while (pust (r)!=1)

      {int q;

       int x;

       q=outstack (&x, &r);

       instack (x, S);

      }

     }

#include <stdio.h>

#include <conio.h>

#include <windows.h>

#include "modul.cpp"

void main()

{      

 dstack *M;

 int a=0;

 while(a<6 && a>-1){

 system ("cls");

 printf("1-sozdat\n2-dobavit\n3-udalit\n4-pust?\n5-prosmotr\n6-exit\n");

 scanf("%d",&a);

   switch(a){

             case 1 : newstack (&M);break;

             case 2 : printf ("vvedite element\n");

                         int w;

                   scanf ("%d", &w);

                         instack (w, &M);

                         break;

             case 3 : int z;

                   int p;

                         z=outstack(&p, &M);

                         if (z==1) printf ("elem = %d\n", p);

                         else printf ("ne udalili\n"); getch();break;

             case 4 : if (pust (M)==1) printf ("pust\n");

                         else printf ("ne pust\n"); getch(); break;

             case 5 : prosmotr (&M);printf("\n");getch(); break;

             case 6 : break;

             default: printf ("neizvestnaya operaciya\n"); getch();

                     }

            }

}

6. Набор тестов:

№	функция	дано	результат
1.	newstack instack outstack pust prosmotr	4 3 2 1 4 3 Ne pust 1 2	S=NULL 1 2 3 4 1 2 1 2  1 2

7. Результаты работы программы:

      Программа выдала желаемый результат на всех тестах.