Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Презентации / Презентация по программированию на стему "Стек", раздел "Динамическое прогаммрование" (11 класс)

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

Идёт приём заявок на самые массовые международные олимпиады проекта "Инфоурок"

Для учителей мы подготовили самые привлекательные условия в русскоязычном интернете:

1. Бесплатные наградные документы с указанием данных образовательной Лицензии и Свидeтельства СМИ;
2. Призовой фонд 1.500.000 рублей для самых активных учителей;
3. До 100 рублей за одного ученика остаётся у учителя (при орг.взносе 150 рублей);
4. Бесплатные путёвки в Турцию (на двоих, всё включено) - розыгрыш среди активных учителей;
5. Бесплатная подписка на месяц на видеоуроки от "Инфоурок" - активным учителям;
6. Благодарность учителю будет выслана на адрес руководителя школы.

Подайте заявку на олимпиаду сейчас - https://infourok.ru/konkurs

  • Информатика
Стек
История В 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. Размест...
1 из 17

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

№ слайда 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% скидкой при обучении по программам профессиональной переподготовки.

После окончания обучения выдаётся диплом о профессиональной переподготовке установленного образца (признаётся при прохождении аттестации по всей России).

Обучение проходит заочно прямо на сайте проекта "Инфоурок".

Начало обучения ближайших групп: 18 января и 25 января. Оплата возможна в беспроцентную рассрочку (20% в начале обучения и 80% в конце обучения)!

Подайте заявку на интересующий Вас курс сейчас: https://infourok.ru/kursy

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

УЖЕ ЧЕРЕЗ 10 МИНУТ ВЫ МОЖЕТЕ ПОЛУЧИТЬ ДИПЛОМ

от проекта "Инфоурок" с указанием данных образовательной лицензии, что важно при прохождении аттестации.

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

Список всех тестов можно посмотреть тут - https://infourok.ru/tests


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