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

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

Читайте также:
  1. GT-R V-Spec — Дополнительные аэродинамические части, вентиляционные каналы для тормозов, аэродинамический диффузор.
  2. Автокорреляция уровней временного ряда и выявление его структуры
  3. Автокорреляция уровней временного ряда. Анализ структуры временного ряда на основании коэффициентов автокорреляции
  4. Адаптивные или органические организационные структуры
  5. Адаптивные организационные структуры.
  6. Адаптивные организационные структуры: достоинства, недостатки, особенности применения на практике
  7. Алгебраические структуры.
  8. Анализ наличия, состава, структуры и состояния имущества предприятия
  9. Анализ организационной структуры управления предприятием
  10. Анализ состава и структуры основных средств предприятия
  11. Анализ состава и структуры пассивов.
  12. Анализ структуры и ассортимента выпускаемой (реализуемой) продукции

 

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

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

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

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

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

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

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

 

{ 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;BeginEnd.   /* 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";}}

 

Контрольные вопросы и задания

  1. Какую структуру данных называют стеком?
  2. На базе каких структур может быть организован стек?
  3. Приведите из жизни примеры организации чего-либо по принципу стека.
  4. Используя стек, напечатайте символы данной строки в обратном порядке.

http://algolist.manual.ru/olimp/str_prb.php дополнит информ - задачи и решения

http://www.sgu.ru/prcnit/teach/1.php


Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)