Презентация по программированию на стему "Стек", раздел "Динамическое прогаммрование" (11 класс)

• 1 слайд

  Стек
  

• 2 слайд

  История
  В 1946 Алан Тьюринг ввёл понятие стека [1].
  В 1957 году немцы Клаус Самельсон и Фридрих Л. Бауэр запатентовали идею [2].
  

• 3 слайд

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

• 4 слайд

  LIFO
  Стек функционирует по принципу LIFO
  (Last-In-First-Out) - "последним пришел - первым исключается".
  При записи и выборке изменяется только адрес вершины стека. Поэтому каждый стек имеет базовый адрес, от которого производятся все операции со стеком. В случае, когда стек пуст, адреса вершины и основания стека совпадают.
  

• 5 слайд

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

• 6 слайд

  Реализация
  Так как язык Pascal не имеет непосредственно типа данных стек, то для его моделирования наиболее подходящими структурами являются
  массивы (статический стек для моделирования структур заданного размера ) и
  динамический стек, при этом структура будет помещаться в динамической памяти, и её размер будет ограничен только размером кучи.
  

• 7 слайд

  Описание стека
  
  Type Tptr=^TElem; {Тип указателя на элемент стека} TElem = record {Тип элемента стека }
  inf : integer; {информационная часть} link : Tptr; {соединительная часть}
  end;
  
  

• 8 слайд

  Исходное состояние
  Для работы со стеком необходимо иметь
  один основной указатель на вершину стека (возьмём идентификатор Top) и
  один дополнительный временный указатель (возьмём идентификатор P), который используется для выделения и освобождения из памяти элементов стека.
  Top
  P
  nil
  ?
  Top:=nil;
  

• 9 слайд

  Выделение памяти под первый элемент стека и занесение в него информации:
  Top
  nil
  P
  Inf: 5
  Link
  nil
  New(P);
  P^.Inf:=5;
  P^.Link:=nil;
  

• 10 слайд

  Установка вершины стека Top на созданный элемент:
  Link
  nil
  Inf: 5
  Top
  P
  Top:=P;
  

• 11 слайд

  Добавление элемента стека
  Исходное состояние:
  
  P
  ?
  Top
  Link
  Inf: 5
  Link
  Inf: 1
  Link
  Inf: 3
  nil
  

• 12 слайд

  Добавление элемента стека
  Выделение памяти под новый элемент стека. Внесение значения в информационное поле нового элемента и установка связи между ним и "старой" вершиной стека Top:
  Top
  Link
  Inf: 5
  Link
  Inf: 1
  Link
  Inf: 3
  nil
  P
  Inf: 10
  Link
  New(P);
  P^.Inf:=10;
  P^.Link:=Top;
  

• 13 слайд

  Добавление элемента стека
  Перемещение вершины стека Top на новый элемент:
  Top
  Link
  Inf: 5
  Link
  Inf: 1
  Link
  Inf: 3
  P
  Inf: 10
  Link
  nil
  Top:=P;
  

• 14 слайд

  Удаление элемента стека
  Исходное состояние
  Top
  Link
  Inf: 5
  Link
  Inf: 1
  Link
  Inf: 3
  P
  Inf: 10
  Link
  Val:?
  ?
  

• 15 слайд

  Удаление элемента стека
  Извлечение информации из информационного поля вершины стека Top в переменную Val и установка на вершину стека вспомогательного указателя P:
  Top
  Link
  Inf: 5
  Link
  Inf: 1
  Link
  Inf: 3
  P
  Inf: 10
  Link
  Val:10
  Val:=Top^.Inf;
  P:=Top;
  

• 16 слайд

  Удаление элемента стека
  Перемещение указателя вершины стека Top на следующий элемент и освобождение памяти, занимаемой "старой" вершиной стека:
  Top
  Link
  Inf: 5
  Link
  Inf: 1
  Link
  Inf: 3
  P
  Inf: 10
  Link
  Val:10
  Top:=P^.Link;
  Dispose(P);
  

• 17 слайд

  Задание
  Исследовать и доработать программу стек_на основе_списка.pas.
  Разместить в стеке 10 символов и распечатать их в обратном порядке.
  Проверить в выражении баланс открывающихся "(" и закрывающихся ")" скобок.
  Идея алгоритма заключается в следующем. Если встречается открывающаяся скобка, то в стек помещают какой-либо символ. Если встречается закрывающаяся скобка, то проверяют состояние стека. При этом возможны следующие ситуации:
  стек непуст: из стека извлекают один элемент;
  стек пуст, это свидетельствует о том, что закрывающихся скобок больше чем открывающихся.
  После того, как просмотрена вся строка символов, необходимо проверить состояние стека. Если он пуст, то баланс скобок не нарушен. В противном случае - баланса нет.