Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Информатика / Презентации / Презентация по программированию на стему "Стек", раздел "Динамическое прогаммрование" (11 класс)
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Информатика

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

библиотека
материалов
Стек
История В 1946 Алан Тьюринг ввёл понятие стека [1]. В 1957 году немцы Клаус С...
Определение Стек - это данные динамической структуры, которые представляют со...
LIFO Стек функционирует по принципу LIFO (Last-In-First-Out) - "последним при...
Использование При работе со стеком нет необходимости прямо использовать адрес...
Реализация Так как язык Pascal не имеет непосредственно типа данных стек, то...
Описание стека Type Tptr=^TElem; {Тип указателя на элемент стека} TElem = rec...
Исходное состояние Для работы со стеком необходимо иметь один основной указат...
Выделение памяти под первый элемент стека и занесение в него информации: Top...
Установка вершины стека Top на созданный элемент: Link nil Inf: 5 Top P Top:=P;
Добавление элемента стека Исходное состояние: P ? Top Link Inf: 5 Link Inf: 1...
Добавление элемента стека Выделение памяти под новый элемент стека. Внесение...
Добавление элемента стека Перемещение вершины стека Top на новый элемент: Top...
Удаление элемента стека Исходное состояние Top Link Inf: 5 Link Inf: 1 Link I...
Удаление элемента стека Извлечение информации из информационного поля вершины...
Удаление элемента стека Перемещение указателя вершины стека Top на следующий...
Задание Исследовать и доработать программу стек_на основе_списка.pas. Размест...
17 1

Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Описание презентации по отдельным слайдам:

№ слайда 1 Стек
Описание слайда:

Стек

№ слайда 2 История В 1946 Алан Тьюринг ввёл понятие стека [1]. В 1957 году немцы Клаус С
Описание слайда:

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

№ слайда 3 Определение Стек - это данные динамической структуры, которые представляют со
Описание слайда:

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

№ слайда 4 LIFO Стек функционирует по принципу LIFO (Last-In-First-Out) - "последним при
Описание слайда:

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

№ слайда 5 Использование При работе со стеком нет необходимости прямо использовать адрес
Описание слайда:

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

№ слайда 6 Реализация Так как язык Pascal не имеет непосредственно типа данных стек, то
Описание слайда:

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

№ слайда 7 Описание стека Type Tptr=^TElem; {Тип указателя на элемент стека} TElem = rec
Описание слайда:

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

№ слайда 8 Исходное состояние Для работы со стеком необходимо иметь один основной указат
Описание слайда:

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

№ слайда 9 Выделение памяти под первый элемент стека и занесение в него информации: Top
Описание слайда:

Выделение памяти под первый элемент стека и занесение в него информации: 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;
Описание слайда:

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

№ слайда 11 Добавление элемента стека Исходное состояние: P ? Top Link Inf: 5 Link Inf: 1
Описание слайда:

Добавление элемента стека Исходное состояние: 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
Описание слайда:

Добавление элемента стека Перемещение вершины стека 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 I
Описание слайда:

Удаление элемента стека Исходное состояние 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 на следующий элемент и освобождение памяти, занимаемой "старой" вершиной стека: Top Link Inf: 5 Link Inf: 1 Link Inf: 3 P Inf: 10 Link Val:10 Top:=P^.Link; Dispose(P);

№ слайда 17 Задание Исследовать и доработать программу стек_на основе_списка.pas. Размест
Описание слайда:

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


Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Автор
Дата добавления 12.01.2016
Раздел Информатика
Подраздел Презентации
Просмотров313
Номер материала ДВ-329271
Получить свидетельство о публикации
Похожие материалы

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