База знаний студента. Реферат, курсовая, контрольная, диплом на заказ

курсовые,контрольные,дипломы,рефераты

Динамические структуры данных: стеки — Информатика, программирование

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

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

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

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

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

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

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

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

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

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

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

{ 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/

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

 

 

 

Внимание! Представленный Доклад находится в открытом доступе в сети Интернет, и уже неоднократно сдавался, возможно, даже в твоем учебном заведении.
Советуем не рисковать. Узнай, сколько стоит абсолютно уникальный Доклад по твоей теме:

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

Заказать уникальную работу

Свои сданные студенческие работы

присылайте нам на e-mail

Client@Stud-Baza.ru