- Главная
- Разное
- Образование
- Спорт
- Естествознание
- Природоведение
- Религиоведение
- Французский язык
- Черчение
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, фоны, картинки для презентаций
- Экология
- Экономика
Презентация, доклад по программированию на стему Стек, раздел Динамическое прогаммрование (11 класс)
Содержание
- 1. Презентация по программированию на стему Стек, раздел Динамическое прогаммрование (11 класс)
- 2. ИсторияВ 1946 Алан Тьюринг Алан Тьюринг ввёл
- 3. ОпределениеСтек - это данные динамической структуры, которые
- 4. LIFOСтек функционирует по принципу LIFO (Last-In-First-Out)
- 5. Использование При работе со стеком нет необходимости
- 6. РеализацияТак как язык Pascal не имеет непосредственно
- 7. Описание стекаType Tptr=^TElem; {Тип указателя на элемент
- 8. Исходное состояниеДля работы со стеком необходимо иметь
- 9. Выделение памяти под первый элемент стека и занесение в него информации: TopnilPInf: 5LinknilNew(P);P^.Inf:=5;P^.Link:=nil;
- 10. Установка вершины стека Top на созданный элемент: LinknilInf: 5TopPTop:=P;
- 11. Добавление элемента стека Исходное состояние: P?TopLinkInf: 5LinkInf: 1LinkInf: 3nil
- 12. Добавление элемента стека Выделение памяти под новый
- 13. Добавление элемента стека Перемещение вершины стека Top на новый элемент: TopLinkInf: 5LinkInf: 1LinkInf: 3PInf: 10LinknilTop:=P;
- 14. Удаление элемента стека Исходное состояние TopLinkInf: 5LinkInf: 1LinkInf: 3PInf: 10LinkVal:??
- 15. Удаление элемента стекаИзвлечение информации из информационного поля
- 16. Удаление элемента стекаПеремещение указателя вершины стека Top
- 17. ЗаданиеИсследовать и доработать программу стек_на основе_списка.pas.Разместить в
ИсторияВ 1946 Алан Тьюринг Алан Тьюринг ввёл понятие стека [1]. В 1957 году немцы Клаус Самельсон и Фридрих Л. Бауэр запатентовали идею [2].
Слайд 2История
В 1946 Алан Тьюринг Алан Тьюринг ввёл понятие стека [1].
В
1957 году немцы Клаус Самельсон и Фридрих Л. Бауэр запатентовали идею [2].
![ИсторияВ 1946 Алан Тьюринг Алан Тьюринг ввёл понятие стека [1]. В 1957 году немцы Клаус Самельсон и](/img/thumbs/26a0d261650d60d9ab050939321dbcdc-800x.jpg "Презентация по программированию на стему Стек, раздел Динамическое прогаммрование (11 класс) ИсторияВ 1946 Алан Тьюринг Алан Тьюринг ввёл понятие стека [1]. В")
Слайд 3Определение
Стек - это данные динамической структуры, которые представляют собой совокупность линейно-связанных
однородных элементов, для которых разрешено добавлять или удалять элементы только с одного конца списка, который называется вершиной (головой) стека.
Слайд 4LIFO
Стек функционирует по принципу LIFO
(Last-In-First-Out) - "последним пришел - первым
исключается".
При записи и выборке изменяется только адрес вершины стека. Поэтому каждый стек имеет базовый адрес, от которого производятся все операции со стеком. В случае, когда стек пуст, адреса вершины и основания стека совпадают.
При записи и выборке изменяется только адрес вершины стека. Поэтому каждый стек имеет базовый адрес, от которого производятся все операции со стеком. В случае, когда стек пуст, адреса вершины и основания стека совпадают.
Слайд 5Использование
При работе со стеком нет необходимости прямо использовать адресацию памяти.
Самым важным применением стека в программах является:
использование стека для хранения адресов возврата в программу из подпрограмм;
из процедур обработки прерываний;
передача через стек параметров в подпрограммы;
размещение в стеке локальных параметров процедур.
Стеки используются в работе алгоритмов, имеющих рекурсивный характер.
Слайд 6Реализация
Так как язык Pascal не имеет непосредственно типа данных стек, то
для его моделирования наиболее подходящими структурами являются
массивы (статический стек для моделирования структур заданного размера ) и
динамический стек, при этом структура будет помещаться в динамической памяти, и её размер будет ограничен только размером кучи.
массивы (статический стек для моделирования структур заданного размера ) и
динамический стек, при этом структура будет помещаться в динамической памяти, и её размер будет ограничен только размером кучи.
Слайд 7Описание стека
Type Tptr=^TElem; {Тип указателя на элемент стека}
TElem = record {Тип элемента стека }
inf : integer; {информационная часть} link : Tptr; {соединительная часть}
end;
inf : integer; {информационная часть} link : Tptr; {соединительная часть}
end;
Слайд 8Исходное состояние
Для работы со стеком необходимо иметь
один основной указатель на
вершину стека (возьмём идентификатор Top) и
один дополнительный временный указатель (возьмём идентификатор P), который используется для выделения и освобождения из памяти элементов стека.
один дополнительный временный указатель (возьмём идентификатор P), который используется для выделения и освобождения из памяти элементов стека.
Top
P
nil
?
Top:=nil;
Слайд 9Выделение памяти под первый элемент стека и занесение в него информации:
Top
nil
P
Inf: 5
Link
nil
New(P);
P^.Inf:=5;
P^.Link:=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 символов и
распечатать их в обратном порядке.
Проверить в выражении баланс открывающихся "(" и закрывающихся ")" скобок.
Идея алгоритма заключается в следующем. Если встречается открывающаяся скобка, то в стек помещают какой-либо символ. Если встречается закрывающаяся скобка, то проверяют состояние стека. При этом возможны следующие ситуации:
стек непуст: из стека извлекают один элемент;
стек пуст, это свидетельствует о том, что закрывающихся скобок больше чем открывающихся.
После того, как просмотрена вся строка символов, необходимо проверить состояние стека. Если он пуст, то баланс скобок не нарушен. В противном случае - баланса нет.
Проверить в выражении баланс открывающихся "(" и закрывающихся ")" скобок.
Идея алгоритма заключается в следующем. Если встречается открывающаяся скобка, то в стек помещают какой-либо символ. Если встречается закрывающаяся скобка, то проверяют состояние стека. При этом возможны следующие ситуации:
стек непуст: из стека извлекают один элемент;
стек пуст, это свидетельствует о том, что закрывающихся скобок больше чем открывающихся.
После того, как просмотрена вся строка символов, необходимо проверить состояние стека. Если он пуст, то баланс скобок не нарушен. В противном случае - баланса нет.
