Презентация Динамические структуры данных. Стек, очередь, дек, деревья онлайн
Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
49 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
384.00 kB
Просмотров:
141
Скачиваний:
1
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Динамические структуры данных](/documents_6/a8727192cf93654905cd92aa7980e9ff/img0.jpg)
Содержание слайда: Динамические
структуры данных
№2 слайд![Стек Стеком называется](/documents_6/a8727192cf93654905cd92aa7980e9ff/img1.jpg)
Содержание слайда: Стек
Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека.
Стек работает по принципу LIFO (Last-In, First-Out) - поступивший последним, обслуживается первым.
№3 слайд![Стек Использование стека в](/documents_6/a8727192cf93654905cd92aa7980e9ff/img2.jpg)
Содержание слайда: Стек
Использование стека в программировании:
Нужно сохранить некоторую работу, которая еще не выполнена до конца, при необходимости переключения на другую задачу. Стек используется для временного сохранения состояния не выполненного до конца задания. После сохранения состояния компьютер переключается на другую задачу. По окончании ее выполнения состояние отложенного задания восстанавливается из стека, и компьютер продолжает прерванную работу.
№4 слайд![Стек Использование стека в](/documents_6/a8727192cf93654905cd92aa7980e9ff/img3.jpg)
Содержание слайда: Стек
Использование стека в программировании:
используются при разборе (parsing) грамматик (от простых алгебраических выражений до языков программирования)
как средство моделирования рекурсии
как модель исполнения инструкций.
№5 слайд![Стек](/documents_6/a8727192cf93654905cd92aa7980e9ff/img4.jpg)
№6 слайд![Стек](/documents_6/a8727192cf93654905cd92aa7980e9ff/img5.jpg)
№7 слайд![Стек](/documents_6/a8727192cf93654905cd92aa7980e9ff/img6.jpg)
№8 слайд![Стек](/documents_6/a8727192cf93654905cd92aa7980e9ff/img7.jpg)
№9 слайд![Стек](/documents_6/a8727192cf93654905cd92aa7980e9ff/img8.jpg)
№10 слайд![Стек](/documents_6/a8727192cf93654905cd92aa7980e9ff/img9.jpg)
№11 слайд![Стек](/documents_6/a8727192cf93654905cd92aa7980e9ff/img10.jpg)
№12 слайд![Стек](/documents_6/a8727192cf93654905cd92aa7980e9ff/img11.jpg)
№13 слайд![Стек](/documents_6/a8727192cf93654905cd92aa7980e9ff/img12.jpg)
№14 слайд![Стек](/documents_6/a8727192cf93654905cd92aa7980e9ff/img13.jpg)
№15 слайд![Стек](/documents_6/a8727192cf93654905cd92aa7980e9ff/img14.jpg)
№16 слайд![Стек](/documents_6/a8727192cf93654905cd92aa7980e9ff/img15.jpg)
№17 слайд![Очередь](/documents_6/a8727192cf93654905cd92aa7980e9ff/img16.jpg)
Содержание слайда: Очередь
№18 слайд![Очередь](/documents_6/a8727192cf93654905cd92aa7980e9ff/img17.jpg)
Содержание слайда: Очередь
№19 слайд![Очередь](/documents_6/a8727192cf93654905cd92aa7980e9ff/img18.jpg)
Содержание слайда: Очередь
№20 слайд![Очередь](/documents_6/a8727192cf93654905cd92aa7980e9ff/img19.jpg)
Содержание слайда: Очередь
№21 слайд![Очередь](/documents_6/a8727192cf93654905cd92aa7980e9ff/img20.jpg)
Содержание слайда: Очередь
№22 слайд![Очередь](/documents_6/a8727192cf93654905cd92aa7980e9ff/img21.jpg)
Содержание слайда: Очередь
№23 слайд![Очередь. Добавление элемента](/documents_6/a8727192cf93654905cd92aa7980e9ff/img22.jpg)
Содержание слайда: Очередь. Добавление элемента
№24 слайд![Очередь. Добавление элемента](/documents_6/a8727192cf93654905cd92aa7980e9ff/img23.jpg)
Содержание слайда: Очередь. Добавление элемента
№25 слайд![Очередь. Извлечение элемента](/documents_6/a8727192cf93654905cd92aa7980e9ff/img24.jpg)
Содержание слайда: Очередь. Извлечение элемента
№26 слайд![Очередь. Очистка очереди](/documents_6/a8727192cf93654905cd92aa7980e9ff/img25.jpg)
Содержание слайда: Очередь. Очистка очереди
№27 слайд![Дек Дек является симбиозом](/documents_6/a8727192cf93654905cd92aa7980e9ff/img26.jpg)
Содержание слайда: Дек
Дек является симбиозом стека и очереди - это та же структура, но на этот раз с ней можно работать с обеих концов. Таким образом, если мы будем работать с деком только с левого края, то фактически получается стек. Аналогично мы получим стек, если будем работать только с правого края (конца дека).
Пользуясь предписаниями "добавить в конец" и "взять из начала", мы сможем получить очередь, элементы которой будут продвигаться справа налево.
Название дека произошло от сокращения английских слов Double Ended Queue - очередь с двумя концами.
№28 слайд![Граф](/documents_6/a8727192cf93654905cd92aa7980e9ff/img27.jpg)
№29 слайд![Деревья Деревом называют](/documents_6/a8727192cf93654905cd92aa7980e9ff/img28.jpg)
Содержание слайда: Деревья
Деревом называют конечный связный граф с выделенной вершиной (корнем), не имеющий циклов.
№30 слайд![Деревья Для каждой пары](/documents_6/a8727192cf93654905cd92aa7980e9ff/img29.jpg)
Содержание слайда: Деревья
Для каждой пары вершин дерева – узлов – существует единственный маршрут, поэтому вершины удобно классифицировать по степени удалённости от корневой вершины .
№31 слайд![Деревья Висячие вершины, за](/documents_6/a8727192cf93654905cd92aa7980e9ff/img30.jpg)
Содержание слайда: Деревья
Висячие вершины, за исключением корневой, называются листьями.
Число путей в каждом дереве соответствует числу висячих вершин (листьев).
№32 слайд![Бинарные деревья Деревья, в](/documents_6/a8727192cf93654905cd92aa7980e9ff/img31.jpg)
Содержание слайда: Бинарные деревья
Деревья, в которых каждый узел либо является листом, либо образует два поддерева: левое и правое, называются бинарными деревьями и используются при делении множества на два взаимоисключающих подмножества по какому-то признаку (дихотомическое деление).
№33 слайд![Бинарные деревья Ключевые](/documents_6/a8727192cf93654905cd92aa7980e9ff/img32.jpg)
Содержание слайда: Бинарные деревья
Ключевые термины:
Бинарное (двоичное) дерево – это дерево, в котором каждая вершина имеет не более двух потомков.
Вершина (узел) дерева – это каждый элемент дерева.
Ветви дерева – это направленные дуги, которыми соединены вершины дерева.
Высота (глубина) дерева – это количество уровней, на которых располагаются его вершины.
Корень дерева – это начальный узел дерева, ему соответствует нулевой уровень.
№34 слайд![Бинарные деревья Ключевые](/documents_6/a8727192cf93654905cd92aa7980e9ff/img33.jpg)
Содержание слайда: Бинарные деревья
Ключевые термины:
Листья дерева – это вершины, в которые входит одна ветвь и не выходит ни одной ветви.
Неполное бинарное дерево – это дерево, уровни которого заполнены не полностью.
Нестрогое бинарное дерево – это дерево, у которого вершины имеют степень ноль (у листьев), один или два (у узлов).
Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается только один раз.
Поддерево – это часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева.
№35 слайд![Бинарные деревья Ключевые](/documents_6/a8727192cf93654905cd92aa7980e9ff/img34.jpg)
Содержание слайда: Бинарные деревья
Ключевые термины:
Полное бинарное дерево – это дерево, которое содержит только полностью заполненные уровни.
Потомки – это все вершины, в которые входят ветви, исходящие из одной общей вершины.
Почти сбалансированное дерево – это дерево, у которого длины всевозможных путей от корня к внешним вершинам отличаются не более, чем на единицу.
Предок – это вершина, из которой исходят ветви к вершинам следующего уровня.
Сбалансированное дерево – это дерево, у которого длины всех путей от корня к внешним вершинам равны между собой.
№36 слайд![Бинарные деревья Ключевые](/documents_6/a8727192cf93654905cd92aa7980e9ff/img35.jpg)
Содержание слайда: Бинарные деревья
Ключевые термины:
Степень вершины – это количество дуг, которое выходит из этой вершины.
Степень дерева – это максимальная степень вершин, входящих в дерево.
Строгое бинарное дерево – это дерево, у которого вершины имеют степень ноль (у листьев) или два (у узлов).
Упорядоченное дерево – это дерево, у которого ветви, исходящие из каждой вершины, упорядочены по определенному критерию.
Уровень вершины – это количество дуг от корня дерева до вершины.
№37 слайд![Бинарные деревья В](/documents_6/a8727192cf93654905cd92aa7980e9ff/img36.jpg)
Содержание слайда: Бинарные деревья
В программировании при решении большого класса задач используются бинарные деревья.
Бинарные деревья могут применяться для поиска данных в специально построенных деревьях (базы данных), сортировки данных, вычислений арифметических выражений, кодирования.
№38 слайд![Бинарные деревья Описание](/documents_6/a8727192cf93654905cd92aa7980e9ff/img37.jpg)
Содержание слайда: Бинарные деревья
Описание бинарного дерева выглядит следующим образом:
struct имя_типа {
информационное поле;
адрес левого поддерева;
адрес правого поддерева;
};
где информационное поле – это поле любого ранее объявленного или стандартного типа;
адрес левого (правого) поддерева – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента левого (правого) поддерева.
№39 слайд![Бинарные деревья](/documents_6/a8727192cf93654905cd92aa7980e9ff/img38.jpg)
Содержание слайда: Бинарные деревья
№40 слайд![Бинарные деревья](/documents_6/a8727192cf93654905cd92aa7980e9ff/img39.jpg)
Содержание слайда: Бинарные деревья
№41 слайд![Бинарные деревья](/documents_6/a8727192cf93654905cd92aa7980e9ff/img40.jpg)
Содержание слайда: Бинарные деревья
№42 слайд![Бинарные деревья](/documents_6/a8727192cf93654905cd92aa7980e9ff/img41.jpg)
Содержание слайда: Бинарные деревья
№43 слайд![Бинарные деревья](/documents_6/a8727192cf93654905cd92aa7980e9ff/img42.jpg)
Содержание слайда: Бинарные деревья
№44 слайд![Бинарные деревья](/documents_6/a8727192cf93654905cd92aa7980e9ff/img43.jpg)
Содержание слайда: Бинарные деревья
№45 слайд![Бинарные деревья](/documents_6/a8727192cf93654905cd92aa7980e9ff/img44.jpg)
Содержание слайда: Бинарные деревья
№46 слайд![Бинарные деревья](/documents_6/a8727192cf93654905cd92aa7980e9ff/img45.jpg)
Содержание слайда: Бинарные деревья
№47 слайд![Бинарные деревья](/documents_6/a8727192cf93654905cd92aa7980e9ff/img46.jpg)
Содержание слайда: Бинарные деревья
№48 слайд![Бинарные деревья](/documents_6/a8727192cf93654905cd92aa7980e9ff/img47.jpg)
Содержание слайда: Бинарные деревья
№49 слайд![Бинарные деревья](/documents_6/a8727192cf93654905cd92aa7980e9ff/img48.jpg)
Содержание слайда: Бинарные деревья