Главная страница
Навигация по странице:

  • 1.1. Цель работы

  • 1.2. Порядок выполнения работы

  • 1.3. Содержание отчета по ЛР

  • 1.4. Краткая теория

  • 1 Полустатические структуры данных. Отчет по лабораторной работе и защитить его у преподавателя


    Скачать 45.9 Kb.
    НазваниеОтчет по лабораторной работе и защитить его у преподавателя
    Дата22.10.2018
    Размер45.9 Kb.
    Формат файлаdocx
    Имя файла1 Полустатические структуры данных.docx
    ТипОтчет
    #65042

    Подборка по базе: контрольная работа МДК 04.01.Технология составления бухгалтерско, Отчёт о работе системы поддержки принятия решений AssistantChoic.

    1 Полустатические структуры данных
    1.1. Цель работы:

     - исследовать и изучить полустатические структуры данных (на примере стеков, реализованных с помощью массивов);

     - овладеть навыками разработки алгоритмов и написания программ на  по исследованию стеков на языке программирования С++;

    1.2. Порядок выполнения работы

     - ознакомиться с краткой теорией и примерами решения задач, относящихся к работе со стеками;

     - ответить на контрольные вопросы и по знанию теории;

     - получить задание на выполнение конкретного варианта лабораторной работы у преподавателя  и выполнить его;

     - написать и отладить  программу решения задачи на языке С++;

     - подготовить отчет по лабораторной работе и защитить его у преподавателя.

    1.3. Содержание отчета по ЛР

     - наименование ЛР и ее цель;

     - задание на ЛР согласно варианту;

     - листинг приложения, обеспечивающей успешное решение студентом полученного варианта задачи;

     - результаты работы программы.

    1.4. Краткая теория

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

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

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

    Различают два основных вида очередей, отличающихся по дисциплине обслуживания находящихся в них элементов:

    1. При первой из дисциплин заказ, поступивший в очередь первым, выбирается первым для обслуживания (и удаляется из очереди). Эту дисциплину обслуживания принято называть FIFO (First input-First output, т.е. первый пришел - первый ушел). Очередь открыта с обеих сторон.



    2. Вторую дисциплину принято называть LIFO (Last input - First output, т.е. последний  пришел - первый ушел), при которой на обслуживание первым выбирается тот элемент очереди, который поступил в нее последним. Очередь такого вида в программировании принято называть СТЕКОМ (магазином) - это одна из наиболее употребительных структур данных, которая оказывается весьма удобной при решении различных задач.

    В силу указанной дисциплины обслуживания, в стеке доступна единственная его позиция, которая называется ВЕРШИНОЙ стека - эта позиция, в которой находится последний по времени поступления в стек элемент. Когда мы заносим новый элемент в стек, то он помещается поверх вершины и теперь уже сам находится в вершине стека. Выбрать элемент можно только из вершины стека; при этом выбранный элемент исключается из стека, а в его вершине оказывается элемент, который был занесен в стек перед выбранным из него элементом (структура с ограниченным доступом к данным).



    ОПЕРАЦИИ НАД СТЕКАМИ:

     - PUSH (S, x) - занесение элемента в стек, где s - название стека, x - элемент, который заносится в стек;

     - POP (S) - выборка элемента из стека. При выборке элемент помещается в рабочую область памяти, где он используется;

     - EMPTY (S) - проверка стека на пустоту (true - пуст, false - не пуст);

     - STACKTOP (S) - чтение верхнего элемента без его удаления.

     - FULL (S) – проверка стека на переполнение (в случае, если стек реализован с помощью массива.

    Если i – указатель вершины стека, то реализация описанных выше операций в псевдокоде будет выглядеть следующим образом:

    Push(S,x)

    i = i+1

    S(i) = x

    return

     

    Pop(S)

    x = S(i)

    i = i -1

    return

     

    Empty(S)

    if i = 0

      then “пусто

      Stop

      return

    endif 

    условие i=0 означает, что стек пуст

     

    Full(S)

    if i = maxS

      then “переполнение

                Stop

                return

    endif

     

    StackTop(S)

    x = S(i)

    return 

     

    Если при выборке проверять стек на пустоту, а при занесении элемента проверять стек на переполнение, то алгоритмы операций считывания и занесения элемента  будут следующими:

    Pop(S)

    if i = 0 then “пусто

                    Stop

                    return

    endif

    x = S(i)

    i = i -1

    return

     

    Push(S,i)

    if i = maxS

      then “переполнение

                                  Stop

                                  return

    endif

    i = i+1

    S(i) = x

    return
    Рассмотрим, как операции над стеком реализуются на языке программирования С++ с помощью функций. Простейший стек будем реализовывать на одномерном массиве (векторе), элементом стека будет символьная переменная. Обычно указатель стека обозначается sp (Stack Pointer), в любой момент времени он содержит адрес текущего элемента, являющегося вершиной стека и единственным элементом, доступным в данный момент времени для работы со стеком.

             Если исходить из предположения, что вершина стека – последний свободный элемент массива, то операция занесения элемента в стек реализуется присваиванием значения вводимого символа данному элементу. Значение указателя стека при этом должно увеличиваться на единицу, задавая ячейку, как бы находящуюся “над” верхним элементом. При такой реализации представляется вполне возможным заполнение стека с нулевого элемента массива. Если при этом задать начальное значение sp=1, легко можно реализовать все операции работы со стеком.

    Начальная установка sp=1.

    Загрузка элемента х в стек: stack[sp]=x; sp=sp+1.

    Извлечение элемента из стека: sp=sp-1; x=stack[sp];

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

    if (sp<=sd) {stack[sp]=x; sp=sp+1}

               else //стек полон

    Здесь sd – размерность стека (максимальное число элементов массива плюс один, так как в С++ нумерация индексов в массиве начинается с нуля).

    При извлечении элемента из стека и при считывании значения верхнего элемента без извлечения необходимо осуществлять поверку стека на пустоту, поэтому операция извлечения реализуется так:

       if (sp>1) {sp=sp-1; x=stack[sp]}

                      else // стек пуст.

             Чтение верхнего элемента без извлечения:

         if (sp>1) {x=stack[sp-1]}

                      else // стек пуст.

             Поскольку наш стек – последовательность символов, то фрагмент программы с основными функциями работы со стеком будет выглядеть следующим образом:

     

    #define MAX_SIZE 20

    char s[MAX_SIZE]; //компонентыстека

    int next=0; // позиция стека

     

    int Empty() // проверка на пустоту

    { return next==0; }

     

    int Full() // проверка на переполнение

    { return next==MAX_SIZE; }

     

    void Push() // Занесение элемента в стек

    {

       if (next==MAX_SIZE)

       {

          cout<<"Ошибка: стек полон"<

          else { next++;

          cout<<"Что поместить в стек?"<

          cin >> s[next-1];cout<<"Добавлен"<

       }

    }

     

    void Pop()// Считывание элемента с удалением

    {

       if (next==0) cout<<"Ошибка: стекпуст"<

       else {

       next--;cout<<"Удален "<

       }

    }

     

    Void Stacktop() // считывание элемента без удаления

    {

       if (next==0) cout<<"Ошибка: стекпуст"<

       else {

       cout<

       }

    }

    // Данная функция выводит верхний элемент стека на экран.

     

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

     

    // Работа со стеком. Проверка стека на пустоту.

    // Добавление элемента в стек. Выборка элемента  из стека.

    // Проверка стека на переполнение. Печать стека.

    // Просмотр содержимого стека без считывания элементов

    #include

    #include

    #include

    #include


    #include

    #include

    #define MAX_SIZE 200

    char s[MAX_SIZE]; //компонентыстека

    int next=0; // позициястека

     

    int Empty()

    { return next==0; }

     

    int Full()

    { return next==MAX_SIZE; }

     

    void Push()

    {

       if (next==MAX_SIZE)

       {

          cout<<"Ошибка: стек полон"<

          else { next++;

          cout<<"Что поместить в стек?"<

          cin >> s[next-1];cout<<"Добавлен"<

       }

    }

     

    void Printst()

    {

       if (next==0)

          cout<<"Cтекпуст"<

       else

       do

       {cout<

       while(next!=0);

    }

     

    void Clear()

    { next=0; }

     

    void Pop()

    {

       if (next==0) cout<<"Ошибкастекпуст"<

       else {

       next--;cout<<"Удален "<

       }

    }

    void Stacktop()

    {

       if (next==0) cout<<"Ошибкастекпуст"<

       else

       {cout<

    }

     

    void Showst()

    {

       int i=0;

       if (next==0) {

          cout<<"Cтекпуст"<

       }

       else { for(i=0;i

       cout<

       }

    }

    void menu()

    {

       cout<<"0: Печать стека"<

       cout<<"1: Добавление элемента в стек"<

       cout<<"2: Удаление элемента из стека"<

       cout<<"3: Считывание элемента из стека без удаления"<

       cout<<"4: Проверка стека на пустоту"<

       cout<<"5: Проверка стека на переполнение"<

       cout<<"6: Очистка стека"<

       cout<<"7: Просмотр содержимого стека без считывания элементов"<

       cout<<"8: Выход"<

    }

    main()

    {

       char c;

       clrscr();

       textcolor(15);

       do {

          menu();

          cin >> c;

          clrscr();

          switch (c) {

       case '0':Printst();getch();break;

       case '1':Push();break;

       case '2':Pop();getch();break;

       case '3':Stacktop();getch();break;

       case '4':if (Empty()==1) cout<<"Стекпуст"<

          else cout<<"Стекнепуст"<

       case '5':if (Full()==1)cout<<"стекполон"<

          else cout<<"стекнеполон"<

       case '6':Clear();cout<<

          "Стекочищен"<

       case '7':Showst();getch();break;

       case '8':exit(1);

          }

          delay(200);

       }

       while (c!=8);

       return 0;



     

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

     ???

    Теперь рассмотрим более сложные варианты реализации стеков и работы с ними.

    Создадим файл, в котором определены структура дескриптора стека STC и переменная s1 типа STC, а также включены функции, реализующие рассмотренные выше операции над стеками. Дескриптор построен транслятором, память под элементы стека получена динамически. Элементы стека имеют значения типа EL, максимальное число элементов т. В дескрипторе определены указатель начала стека в виде адреса начала динамической памяти и указатели вершины и конца стека в виде целых чисел (индексов элементов стека). Этот файл включается директивой #include в исходный файл с программой для работы со стеком. Предварительно должен быть определен тип элемента EL, например define double EL. Допускаются типы EL, только такие, что переменным этого типа можно присваивать значения оператором «=». Таковыми являются скалярные типы (int, float, double, char) и структурный тип struct.

    /* Файл включения для работы со стеком.

             Содержит дескриптор стека и функции для работы

             со стеком. Включается в головной файл после

             определения элемента стека с именем EL */

    /* c:\bcpp\bin\incl_stc.c */

     #define STC struct st

     STC   /* дескрипторстека */

      { EL *un; /* Указатель начала стека */

              int uk; /* Указатель конца стека */

              int uv; /* Указатель вершины стека */

              int m;  /* число элементов в стеке */

      } s1; /* s1 -переменная типа STC */

    /* ======================================= */

    /*      ДОБАВЛЕНИЕ ЭЛЕМЕНТА В СТЕК   */

    int  Push_el(STC *s,EL el)

     { if (s->un == NULL)  /*стек не создан */

               return -2;

             if (s->uv == s->uk)

               return -1;   /* стекполон */

                       *(s->un + s->uv+1) = el; ++s->uv;

                       return 0;

     }

    /* ====================================== */

    /*       ВЫБОРКА ЭЛЕМЕНТА ИЗ СТЕКА     */

     int Pop_el(STC *s,EL *el)

     { if (s->un == NULL)

               return -2;  /* стекнесоздан */

             if (s->uv < 0)

               return -1; /* стекпуст */

             else

              { *el = *(s->un + s->uv);

                       --s->uv;

                       return 0;

              }

     }

    /* ====================================== */

    /* ИЗВЛЕЧЕНИЕ ЗНАЧЕНИЯ ЭЛЕМЕНТА ИЗ СТЕКА БЕЗ УДАЛЕНИЯ ЭЛЕМЕНТА  */

     int Peek_el(STC *s,EL *el)

     { if (s->un == NULL)

               return -2;  /* стекнесоздан */

             if (s->uv < 0)

               return -1; /* стекпуст */

             else

              { *el = *(s->un + s->uv);

                       return 0;

              }

     }

    /* ====================================== */

    /*       ОСВОБОЖДЕНИЕСТЕКА       */

      int Destroy_stc(STC *s)

      { free(s->un);

              s->un = NULL;  return 0;

      }

    /* ====================================== */

    /*      СОЗДАНИЕ СТЕКА           */

      int Crt_stc(STC *s)

      { int nn=12; /* число элементов стека */

              if (s->un != NULL)

                       { printf("\n Старый стек уничтожить? (y/n) ");

                         flushall();

                         if (getchar() != 'y')

                                 { printf("\n Работаем со старым стеком");

                                          return -2;

                                 }

                       }

              s->un = (EL*) calloc(nn,sizeof(EL));

              if (s->un == NULL)

                       return -1; /* памятьневыделена */

              else

                       { s->uv = -1; s->uk = nn-1;

                         s->m = nn; return 0;

                       }

      }

    /* *************************************************** */

    /* **** Конец файла включения ************** */

    Теперь рассмотрим пример программы для работы со стеком в векторной памяти. Элементом стека является переменная типа struct, Хотя в структуре содержится единственный элемент - строка. Это вызвано тем ограничением, о котором говорилось выше. Содержанием элемента стека является команда операционной системы либо имя исполняемого файла. Обработка элемента стека сводится к выполнению этой команды или исполняемого файла.

     

      /* РАБОТА СО СТЕКОМ В ВЕКТОРНОЙ ПАМЯТИ

               c:\bcpp\bin\dstackg2.c -  головной файл */

     

    #include

    #include

    #include

    #include

    #include


    typedef struct /*Структураэлементастекасименем EL */

      { char Name[80];

      } EL;

    EL e;

    #include "c:\bcpp\bin\incl_stc.c" /*файлвключения */

    char *menu[7][40];

    static int p=1;

    int In_el(EL*);

    int Show_stc(STC);

    void main_menu(void);

    /* ============ГЛАВНАЯФУНКЦИЯ =============== */

    int main()

    {*menu[0]="1.Создание пустого стека";

    *menu[1]="2.Включение элемента в стек";

    *menu[2]="3.Выборка элемента из стека";

    *menu[3]="4.Освобождение стека";

    *menu[4]="5.Вывод содержимого стека на экран";

    *menu[5]="6.Конец работы";

    *menu[6]="         Введите номер строки";

    clrscr();

    printf("    Работа со стеком в векторной памяти\n");

    while(p)

             { main_menu();

               clrscr();

             }

    printf("    Конец pаботы со стеком\n");

    return 0;

    }

    /* ======================================== */

    /*  ВЫВОДГЛАВНОГОМЕНЮ */

    void main_menu(void)

    { char ns; int pp=1,r=0,i; flushall();  /* чисткабуферов */

      while (pp)

              { for(i=0;i<7;i++)

                                printf("\n %s",*menu[i]);

                       printf("\n");

                       ns=getchar();

                       if (ns<'1'  || ns>'6')

                        { clrscr();

                                printf("\nОшибка в номере!!Будьте внимательны.");

                                continue;

                        }

                       else pp=0;

                       switch(ns)

                         { case '1':if ( Crt_stc(&s1) == -1)

                                                   { printf ("\n Память под стек не выделена");

                                                                       getch();

                                                              }              break;

                                 case '2':if (In_el(&e) == 0)

                                                              { r=Push_el(&s1,e);

                                                                       if (r == -2)

                                                                               { printf("\nСтекнесоздан!!!");

                                                                                 getch();

                                                                               }

                                                                       else

                                                                               if (r == -1)

                                                                                 { printf("\n Стекполон!!!");

                                                                                          getch();

                                                                                 }

                                                              }              break;

                                 case '3': r=Pop_el(&s1,&e);

                                                              if (r == -1)

                                                                       printf("\n Стекпуст");

                                                              else

                                                                       if (r == -2)

                                                                               printf("\n Стекнесоздан!!");

                                                                       else

                                                                               { printf("\n Элементвыбран\n");

                                                                                 /* Обработкаэлемента */

                                                                                 system(e.Name);

                                                                               }

                                                              getch();                        break;

                                 case '4': Destroy_stc(&s1);              break;

                                 case '5': if (Show_stc(s1) == -1)

                                                                       { printf("\n Стекнесоздан");

                                                                               getch();

                                                                       }                     break;

                                 case '6': p=0;

                       }

              }

             }

    /* ======================================== */

      int In_el(EL *el)

      { printf("\n Ввод элемента стека или ** для отказа от ввода");

              printf("\n Введите команду DOS или имя исполняемого файла\n=>");

              flushall();

              gets(el->Name);

              return 0;

      }

    /* ===========================================*/

     int Show_stc(STC s)

     { int i;

             if (s.un == NULL)

                       return -1;

             for (i=0; i<=s.uv; i++)

                       printf("\n %s",s.un[i].Name);

             getch();

             return 0;

     }

    /* ******************************************************** */
     Задания

    Ввести символы, формируя из них стек.

    Варианты

    1. Поменять местам первый и последний элементы стека.

    2. Развернуть стек, т.е. сделать "дно" стека вершиной, а вершину - "дном"

    3. Удалить элемент, находящийся в середине стека , если число элементов нечетное, или 2 средних элемента, если число элементов четное.

    4. Удалить каждый второй элемент стека

    5. Вставить символ ‘*’ в середину стека, если число элементов четное, или  после среднего элемента, если число элементов нечетное.

    6. Найти минимальный элемент и вставить после него 0.

    7. Найти максимальный элемент и вставить после него 0

    8. Удалить минимальный элемент.

    9. Удалить все элементы, равные первому.

    10. Удалить все элементы, равные последнему.

    11. Удалить максимальный элемент.

    12. Найти минимальный элемент и вставит на его место 0.

    Вывести полученный стек на экран. 


    написать администратору сайта