Рефетека.ру / Информатика и програм-ие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

            

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

#include "STACK.CPP"

#include < string.h >

#include < stdio.h >

void main(void)

{

char S[255];

FILE *T;

int I; BT X, Y;

Zveno *NS;

  clrscr();

  cout << "Введите имя файла: "; cin >> S;

  T=fopen(S, "r");

  NS = NULL;

  while (!feof(T))

  {

     fgets(S, 255, T);

     I = 0;

     while (I <= strlen(S)-1)

{

  if (S[I]>='0'&&S[I]<='9')

  {

   X=0;

   while(S[I]>='0'&&S[I]<='9') {X=X*10+(S[I]-'0'); I++;}

   NS=V_Stack(NS, X);

  }

  else

  if (S[I]=='+'||S[I]=='-'||S[I]=='/'||S[I]=='*')

  {

     X=V_Vershine(NS);

     NS=Iz_Stack(NS);

     Y=V_Vershine(NS);

     NS=Iz_Stack(NS);

     switch (S[I]) {

     case '+' : X += Y; break;

     case '-' : X = Y - X; break;

     case '*' : X *= Y; break;

     case '/' : X = Y / X; break;}

     NS=V_Stack(NS, X);

  }

  I++;

 }

 X=V_Vershine(NS);

 NS=Iz_Stack(NS);

 cout << S << " => " << X << "n";}

}

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

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


Похожие работы:

  1. • Динамические структуры данных: стеки
  2. • Динамические структуры данных: стеки
  3. • Динамические структуры данных: стеки
  4. • Динамические структуры данных: стеки
  5. • Ответы на вопросы по курсу "Системное программирование"
  6. • Динамические структуры данных
  7. • Разработка программ с использованием динамической ...
  8. • Разработка программ с использованием динамической ...
  9. • Основные понятия алгоритмического языка
  10. • Алгоритмический язык Паскаль
  11. • Алгоритмический язык Паскаль
  12. • AGraph: библиотека классов для работы с помеченными графами
  13. • Программное обеспечение встроенных систем ...
  14. • Алгоритмические языки и программирование Системное ...
  15. • Динамические структуры данных
  16. • Динамические структуры данных: дек
  17. • Динамические структуры данных
  18. • Динамические структуры данных: списки
  19. • Динамические структуры данных: списки
Рефетека ру refoteka@gmail.com