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


Полнотекстовый поиск по базе:

Главная >> Доклад >> Информатика, программирование


Динамические структуры данных: стеки (работа 2)




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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Курсовая работа >> Информатика, программирование
    ... В этом разделе мы ознакомимся с динамическими структурами данных и собственно стеком. Достоинства динамических структур данных Динамические структуры данных по определению характеризуются отсутствием ...
  • Динамические структуры данных. Решение задач. Стек. Очередь. Дек

    Курсовая работа >> Математика
    ... памяти называется динамическим. Существуют множество типов динамических структур данных, среди них, такие как стек, очередь ... №3: деки. Дек как динамическая структура данных включает в себя характерные особенности очереди и стека. Перемещение в очереди ...
  • Динамические структуры данных

    Лабораторная работа >> Информатика, программирование
    ... їв 2009 Теоретична частина 1. Динамические структуры данных Ранее изучаемые типы данных относятся к так называемым статическим ... рекурсивный характер. Конец стека называется вершиной стека. Принцип работы стека - “последний пришел - первый ...
  • Динамические структуры данных: дек

    Курсовая работа >> Информатика, программирование
    ... 2008 Содержание Введение Постановка задачи Динамические структуры данных: дек Описание алгоритма Приложение 1. Текст ... и кольцевые двунаправленные), стеки, деки, очереди, деревья и другие. Описание динамических структур с помощью массивов, записей ...
  • Структуры данных

    Реферат >> Математика
    ... M -> [ 1.. |M| ]. 3. Абстрактные структуры данных. Наиболее часто встречающимися абстрактыми структурами данных являются строка, граф, дерево, стек, очередь ... мы уже сталкивались когда рассматривали динамические структуры данных. Когда мы не можем фиксировать ...
  • Динамические структуры данных

    Лабораторная работа >> Информатика, программирование
    ... Пусть Top - указатель на начало стека. Стек удобно строить в обратном порядке. ... списка с полутора связями Построение сложных структур в динамической памяти С помощью указателей можно ... програми. Висновок Динамічні структури даних дозволяють гнучкіше та ширше ...
  • Алгоритмы и структуры данных. Программирование в Cи

    Реферат >> Информатика, программирование
    ... , которые исчезают после работы функции. 7.2 Динамические структуры данных Динамические структуры данных, как поясняет Юрген Плате в следующих ... списки, специальные формы, буфер(FIFO), стек(LIFO). Деревья - Бинарные деревья – 2 соседа ...
  • Линейные списки. Стек. Дек. Очередь

    Реферат >> Информатика, программирование
    Содержание Введение 3 Глава 1. Динамические типы данных 6 1.1 Списки. Очередь. Стек. Дек. 6 1.2 Динамические информационные структуры 22 Глава 2. Разработка ...
  • Ссылочные типы. Динамические переменные

    Курсовая работа >> Информатика, программирование
    ... , а второй √ с предыдущим. Такая организация динамической структуры данных получила название линейного двунаправленного списка ... writeln end. 3. Очереди и стеки Очередь и стек представляют собой структуры данных с фиксированными механизмами занесения и выбора ...