рефераты

Рефераты

рефераты   Главная
рефераты   Краткое содержание
      произведений
рефераты   Архитектура
рефераты   Астрономия
рефераты   Банковское дело
      и кредитование
рефераты   Безопасность
      жизнедеятельности
рефераты   Биографии
рефераты   Биология
рефераты   Биржевое дело
рефераты   Бухгалтерия и аудит
рефераты   Военное дело
рефераты   География
рефераты   Геодезия
рефераты   Геология
рефераты   Гражданская оборона
рефераты   Животные
рефераты   Здоровье
рефераты   Земельное право
рефераты   Иностранные языки
      лингвистика
рефераты   Искусство
рефераты   Историческая личность
рефераты   История
рефераты   История отечественного
      государства и права
рефераты   История политичиских
      учений
рефераты   История техники
рефераты   Компьютерные сети
рефераты   Компьютеры ЭВМ
рефераты   Криминалистика и
      криминология
рефераты   Культурология
рефераты   Литература
рефераты   Литература языковедение
рефераты   Маркетинг товароведение
      реклама
рефераты   Математика
рефераты   Материаловедение
рефераты   Медицина
рефераты   Медицина здоровье отдых
рефераты   Менеджмент (теория
      управления и организации)
рефераты   Металлургия
рефераты   Москвоведение
рефераты   Музыка
рефераты   Наука и техника
рефераты   Нотариат
рефераты   Общениеэтика семья брак
рефераты   Педагогика
рефераты   Право
рефераты   Программирование
      базы данных
рефераты   Программное обеспечение
рефераты   Промышленность
      сельское хозяйство
рефераты   Психология
рефераты   Радиоэлектроника
      компьютеры
      и перифирийные устройства
рефераты   Реклама
рефераты   Религия
рефераты   Сексология
рефераты   Социология
рефераты   Теория государства и права
рефераты   Технология
рефераты   Физика
рефераты   Физкультура и спорт
рефераты   Философия
рефераты   Финансовое право
рефераты   Химия - рефераты
рефераты   Хозяйственное право
рефераты   Ценный бумаги
рефераты   Экологическое право
рефераты   Экология
рефераты   Экономика
рефераты   Экономика
      предпринимательство
рефераты   Юридическая психология

 
 
 

Доклад: Динамические структуры данных: стеки

Динамические структуры данных: стеки

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

По определению, элементы извлекаются из стека в порядке, обратном их добавлению в эту структуру, т.е. действует принцип "последний пришёл — первый ушёл".

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

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

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

добавление элемента в стек;

удаление элемента из стека;

проверка, пуст ли стек;

просмотр элемента в вершине стека без удаления;

очистка стека.

Реализуем эти операции, используя разработанный ранее модуль для однонаправленных списков (см. материал "Динамические структуры данных: списки ").

{ Turbo Pascal, файл STACK.PAS }

Unit Stack;

Interface

 Uses Spisok;

 Procedure V_Stack(Var Versh : U; X : BT);

 Procedure Iz_Stack(Var Versh : U; Var X : BT);

 Function Pust(Versh : U) : Boolean;

 Function V_Vershine(Versh : U) : BT;

 Procedure Ochistka(Var Versh : U);

Implementation

 Procedure V_Stack;

 Begin

     V_Nachalo(Versh, X)

 End;

 Procedure Iz_Stack;

 Begin

     Iz_Nachala(Versh, X)

 End;

 Function Pust;

 Begin

     Pust := Versh = Nil

 End;

 Function V_Vershine;

 Begin

      V_Vershine := Versh^.Inf

 End;

 Procedure Ochistka;

 Begin

      Spisok.Ochistka(Versh)

 End;

Begin

End.

/* C++, файл STACK.CPP */

#include "SPIS.CPP"

Zveno *V_Stack(Zveno *Versh, BT X)

{

 return V_Nachalo(Versh, X);

}

Zveno *Iz_Stack(Zveno *Versh)

{

 return Iz_Nachala(Versh);

}

int SPust(Zveno *Versh)

{

            return !Versh;

}

BT V_Vershine(Zveno *Versh)

{

            return Versh->Inf;

}

Zveno *Chistka(Zveno *Versh)

{

while (!Pust(Versh)) Versh=Iz_Stack(Versh);

                        return Versh;

}

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

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

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

{ Turbo Pascal, файл ST2.PAS }

 Program St2;

 Uses Spisok, Stack;

 Const Znak = ['+', '-', '*', '/'];

 Var S, S1 : String;

     T : Text;

     I, N : Byte;

     X, Y : BT; Code : Integer;

     NS : U;

 Begin

   Write('Введите имя файла: ');   ReadLn(S1);

   Assign(T, S1);   ReSet(T);

   NS := Nil;

   While Not Eof(T) Do

    Begin

      ReadLn(T, S);  I := 1;

      While I <= Length(S) Do

        Begin

          If S[I] In ['0'..'9']

          Then

          Begin

           N := I;

           While S[I] In ['0'..'9'] Do

            I := I + 1;

           Val(Copy(S, N, I - N), X, Code);

          V_Stack(NS, X);

          End

          Else

          If S[I] In Znak

          Then

           Begin

             Iz_Stack(NS, X);

             Iz_Stack(NS, Y);

             Case S[I] Of

             '+' : X := X + Y;

             '-' : X := Y - X;

             '*' : X := X * Y;

             '/' : X := Y Div X

             End;

             V_Stack(NS, X)

           End;

          I := I + 1

         End;

         Iz_Stack(NS, X);

         WriteLn(S, ' = ', X);

       End

   End.

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://www.comp-science.ru/


© 2011 Рефераты