Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Структуры данных: динамический массив, стек, очередь, дек, бинарная куча

Содержание

СодержаниеСтруктура данных «Динамический массив»Амортизированное время работыМетод предоплатыМетод потенциаловОднонаправленные, двунаправленные спискиПоиск, добавление элементов, слияние списковАбстрактные типы данных«Стек»Амортизированное время работы«Очередь»«Дек»Способы реализацииСтруктура данных «Двоичная куча»АТД «Очередь с приоритетом»
{ Алгоритмы и структуры данных }Структуры данных: динамический массив, стек, очередь, дек, бинарная кучаНечаев Михаил СодержаниеСтруктура данных «Динамический массив»Амортизированное время работыМетод предоплатыМетод потенциаловОднонаправленные, двунаправленные спискиПоиск, добавление элементов, Основные понятияСтруктура данных (англ. data structure) — программная единица, позволяющая хранить и Основные понятияАбстрактный тип данных (АТД) — это множество объектов, определяемое списком операций, Основные понятияПри этом доступ к отдельным элементам массива осуществляется с помощью индексации, Динамический массивМассив — набор однотипных переменных с доступом по индексу.Динамический массив — Динамический массив13241325467132546+ 5, + 6+ 76612 Динамический массив— Добавления элемента в конец— Доступ к элементу по индексу— Изменение Динамический массив…Пример реализации Динамический массивO(1) — в лучшем случаеO(n) — в худшем случаеА сколько в среднем Амортизационный анализМетод подсчета времени, которое необходимо для последовательности операций над структурой данных.Проводится Амортизационный анализНапример, чтобы показать, что хотя существуют «дорогие» операции, то после усреднения Амортизационный анализS = ∑ti / nt1, t2, …, tn — время выполнения операций Амортизационный анализИспользование X времени равносильно использованию X монет(плата за операцию)У каждой операции Амортизационный анализФ — потенциал текущего состояния структура данныхФ0, Ф1, … Фii-a операция Амортизационный анализ— Метод предоплаты— Метод потенциаловВремя работы динамического массива Связный списокДинамическая структура данных, имеющая помимо своих собственных элементов, ссылки на следующий Связный списокОдносвязный список1234 Связный списокДвусвязный список1234 Связный список— Поиск элемента— Вставка элемента— Удаление элемента— Объединение списков— Получение размераОперации Связный список…Пример реализации Связный список— Быстрая вставка элемента в любое место, при наличии указателя— Быстрое удаление СтекАбстрактный тип данных (или структура данных), работающий по принципу LIFO — Last In, First OutАТД Стек Стек— Вставка (Push)— Извлечение (Pop)Операции Динамический массив1324132546Push(5), Push(6)Pop()13254 СтекНа (динамическом) массиве1324132546Push(5), Push(6)Pop()132546 СтекНа спискеPush(3)Pop()2132121 Стек…Пример реализации СтекPush — O(1)PopO(1) — в лучшем случаеO(n) — в худшем случаеА сколько в среднем случае?Время Push/Pop? ОчередьАбстрактный тип данных (или структура данных), работающий по принципу FIFO — First In, First OutАТД Очередь Очередь— Вставка (EnQueue)— Извлечение (DeQueue)Операции ОчередьОчередьEnQueue(3)DeQueue()1212323 ОчередьНа (динамическом) массиве132413254632546HeadTailEnQueue(5)EnQueue(6)DeQueue() ДэкАбстрактный тип данных (или структура данных), работающий по принципу FIFO и LIFOМожно Дэк— Вставка в начало (PushFront)— Вставка в конец (PushBack)— Извлечение из начала ДэкДэк1234123 Дэк…Пример реализации Двоичная кучаДвоичный подвешенный [связный ациклический граф — дерево],для которого выполнены условия:1 — Значение Двоичная кучаДвоичная куча58611109141413Глубина O(log(n)) Двоичная кучаУдобно хранить в массивеa[0] — кореньа дети a[i] - a[2i + Двоичная кучаПосле изменение элемента в куче, она может перестать удовлетворять условиям кучи.Для Двоичная кучаИзменили элементЕсли его значение стало больше, то используем siftDownЕсли элемент меньше Двоичная кучаИзменили элементЕсли его значение стало меньше, то используем siftUpЕсли элемент больше Двоичная кучаЭлемент в корне :)≻ Получаем значение корняВосстанавливаем кучуБерём последний элементСтавим на Двоичная кучаВставляем элемент в конецВосстанавливаем кучуsiftUp(elementIndex)Время работы O(log n)Добавление элемента Двоичная кучаВход — неупорядоченный массив данныхПервый элемент кладём в кореньВторой и последующие Двоичная кучаВход — неупорядоченный массив данныхПредставим что наш массив — это деревоЗапустим Двоичная кучаДоказательство времени работы…Построение кучи [2] Очередь с приоритетомАбстрактный тип данных (или структура данных),с операциями:1 — Добавить элемент с Очередь с приоритетом1 — Добавить элемент с приоритетомO(log n)2 — Достать элемент с наименьшим mikhail.nechaev@corp.mail.ruСпасибо за внимание!
Слайды презентации

Слайд 2 Содержание
Структура данных «Динамический массив»
Амортизированное время работы
Метод предоплаты
Метод потенциалов
Однонаправленные,

СодержаниеСтруктура данных «Динамический массив»Амортизированное время работыМетод предоплатыМетод потенциаловОднонаправленные, двунаправленные спискиПоиск, добавление

двунаправленные списки
Поиск, добавление элементов, слияние списков
Абстрактные типы данных
«Стек»
Амортизированное время

работы
«Очередь»
«Дек»
Способы реализации
Структура данных «Двоичная куча»
АТД «Очередь с приоритетом»

Слайд 3 Основные понятия
Структура данных (англ. data structure) — программная

Основные понятияСтруктура данных (англ. data structure) — программная единица, позволяющая хранить

единица, позволяющая хранить и обрабатывать множество однотипных и/или логически

связанных данных

Структура данных

Слайд 4 Основные понятия
Абстрактный тип данных (АТД) — это множество

Основные понятияАбстрактный тип данных (АТД) — это множество объектов, определяемое списком

объектов, определяемое списком операций, применимых к этим объектам, и

их свойств. Вся внутренняя структура такого типа инкапсулирована. Абстрактный тип данных определяет набор функций, независимых от конкретной реализации типа, для оперирования его значениями.
Конкретные реализации АТД называются структурами данных.

Абстрактный тип данных

Слайд 5 Основные понятия
При этом доступ к отдельным элементам массива

Основные понятияПри этом доступ к отдельным элементам массива осуществляется с помощью

осуществляется с помощью индексации, то есть через ссылку на

массив с указанием номера (индекса) нужного элемента. За счёт этого, в отличие от списка, массив является структурой данных, пригодной для осуществления произвольного доступа к её ячейкам

Массив

Тип или структура данных в виде набора компонентов (элементов массива), расположенных в памяти непосредственно друг за другом.

Слайд 6 Динамический массив
Массив — набор однотипных переменных с доступом

Динамический массивМассив — набор однотипных переменных с доступом по индексу.Динамический массив

по индексу.

Динамический массив — массив (буффер), изменяющий свой размер

в зависимости от количества элементов.

Динамический массив

Слайд 7 Динамический массив
1
3
2

4

1
3
2
5
4
6
7







1
3
2
5
4
6

+ 5, + 6
+ 7
6
6
12

Динамический массив13241325467132546+ 5, + 6+ 76612

Слайд 8 Динамический массив
— Добавления элемента в конец

— Доступ к

Динамический массив— Добавления элемента в конец— Доступ к элементу по индексу—

элементу по индексу

— Изменение элемента по индексу

— Удаление последнего элемента

— Получение

размера

Операции

Слайд 9 Динамический массив
…
Пример реализации

Динамический массив…Пример реализации

Слайд 10 Динамический массив
O(1) — в лучшем случае

O(n) — в худшем

Динамический массивO(1) — в лучшем случаеO(n) — в худшем случаеА сколько в

случае

А сколько в среднем случае?

Уменьшение в два раза, если

в 4 раза больше элементов

Время добавления/удаления элемента

Слайд 11 Амортизационный анализ
Метод подсчета времени, которое необходимо для последовательности

Амортизационный анализМетод подсчета времени, которое необходимо для последовательности операций над структурой

операций над структурой данных.

Проводится анализ средней производительности в худшем

случае, усредняя время по всем операциям.

Амортизационный анализ

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

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

операции, то после усреднения по всем возможным операциям, средняя

стоимость может быть низкой, из-за редкого выполнения «дорогой» операции.

Оценка не учитывает вероятности

Зачем?

Слайд 13 Амортизационный анализ
S = ∑ti / n

t1, t2, …,

Амортизационный анализS = ∑ti / nt1, t2, …, tn — время выполнения

tn — время выполнения операций 1, 2, … n,
совершённых над

структурой данных

Для подсчёта используются следующие методы
Метод усреднения (по формуле выше)
Метод потенциалов
Метод предоплаты

Средняя амортизационная стоимость операций

Слайд 14 Амортизационный анализ
Использование X времени равносильно использованию X монет
(плата

Амортизационный анализИспользование X времени равносильно использованию X монет(плата за операцию)У каждой

за операцию)

У каждой операции своя стоимость (может быть больше

или меньше реальной)

Для доказательство оценки строим учётные стоимости, что для каждой операции они составляли O(f(n,m))

Тогда S = ∑ti / n = n * O(f(n,m)) / n = O(f(n,m))

Метод предоплаты

Слайд 15 Амортизационный анализ
Ф — потенциал текущего состояния структура данных

Ф0,

Амортизационный анализФ — потенциал текущего состояния структура данныхФ0, Ф1, … Фii-a

Ф1, … Фi

i-a операция стоит = si = ti

+ Фi - Ф(i - 1)

n — количество операций, m — размер СД
S = O(f(n,m)), если
∀ i : si = O(f(n,m))
∀ i : Фi = O(n * f(n,m))

Метод потенциалов

Слайд 16 Амортизационный анализ
— Метод предоплаты

— Метод потенциалов
Время работы динамического

Амортизационный анализ— Метод предоплаты— Метод потенциаловВремя работы динамического массива

массива

Слайд 17 Связный список
Динамическая структура данных, имеющая помимо своих собственных

Связный списокДинамическая структура данных, имеющая помимо своих собственных элементов, ссылки на

элементов, ссылки на следующий и/или предыдущий элемент списка
Связный список

Слайд 18 Связный список
Односвязный список

1

2

3

4

Связный списокОдносвязный список1234

Слайд 19 Связный список
Двусвязный список

1

2

3

4

Связный списокДвусвязный список1234

Слайд 20 Связный список
— Поиск элемента

— Вставка элемента

— Удаление элемента

— Объединение

Связный список— Поиск элемента— Вставка элемента— Удаление элемента— Объединение списков— Получение размераОперации

списков

— Получение размера
Операции

Слайд 21 Связный список
…
Пример реализации

Связный список…Пример реализации

Слайд 22 Связный список
— Быстрая вставка элемента в любое место,

Связный список— Быстрая вставка элемента в любое место, при наличии указателя— Быстрое

при наличии указателя
— Быстрое удаление элемента, при наличии указателя
— Элементы

в памяти находятся «разреженно»

— Долгий поиск нужного элемента
— Дополнительная память на ссылки
— Элементы в памяти находятся «разреженно»

Преимущества и недостатки

Слайд 23 Стек
Абстрактный тип данных (или структура данных), работающий по

СтекАбстрактный тип данных (или структура данных), работающий по принципу LIFO — Last In, First OutАТД Стек

принципу LIFO — Last In, First Out
АТД Стек

Слайд 24 Стек
— Вставка (Push)

— Извлечение (Pop)
Операции

Стек— Вставка (Push)— Извлечение (Pop)Операции

Слайд 25 Динамический массив
1
3
2
4

1
3
2
5
4
6

Push(5), Push(6)
Pop()
1
3
2
5
4




Динамический массив1324132546Push(5), Push(6)Pop()13254

Слайд 26 Стек
На (динамическом) массиве
1
3
2
4

1
3
2
5
4
6

Push(5), Push(6)
Pop()
1
3
2
5
4

6


СтекНа (динамическом) массиве1324132546Push(5), Push(6)Pop()132546

Слайд 27 Стек
На списке
Push(3)
Pop()

2

1

3

2

1

2

1

СтекНа спискеPush(3)Pop()2132121

Слайд 28 Стек
…
Пример реализации

Стек…Пример реализации

Слайд 29 Стек
Push — O(1)

Pop
O(1) — в лучшем случае
O(n) —

СтекPush — O(1)PopO(1) — в лучшем случаеO(n) — в худшем случаеА сколько в среднем случае?Время Push/Pop?

в худшем случае

А сколько в среднем случае?
Время Push/Pop?

Слайд 30 Очередь
Абстрактный тип данных (или структура данных), работающий по

ОчередьАбстрактный тип данных (или структура данных), работающий по принципу FIFO — First In, First OutАТД Очередь

принципу FIFO — First In, First Out
АТД Очередь

Слайд 31 Очередь
— Вставка (EnQueue)

— Извлечение (DeQueue)
Операции

Очередь— Вставка (EnQueue)— Извлечение (DeQueue)Операции

Слайд 32 Очередь
Очередь
EnQueue(3)
DeQueue()

1

2

1

2

3

2

3

ОчередьОчередьEnQueue(3)DeQueue()1212323

Слайд 33 Очередь
На (динамическом) массиве
1
3
2
4

1
3
2
5
4
6


3
2
5
4

6


Head
Tail
EnQueue(5)
EnQueue(6)
DeQueue()

ОчередьНа (динамическом) массиве132413254632546HeadTailEnQueue(5)EnQueue(6)DeQueue()

Слайд 34 Дэк
Абстрактный тип данных (или структура данных), работающий по

ДэкАбстрактный тип данных (или структура данных), работающий по принципу FIFO и

принципу FIFO и LIFO

Можно добавлять и удалять элементы и

в начале и в конце

АТД Дэк

Слайд 35 Дэк
— Вставка в начало (PushFront)

— Вставка в конец

Дэк— Вставка в начало (PushFront)— Вставка в конец (PushBack)— Извлечение из

(PushBack)

— Извлечение из начала (PopFront)

— Извлечение из конца (PopBack)
Операции

Слайд 36 Дэк
Дэк

1

2

3

4

1

2

3

ДэкДэк1234123

Слайд 37 Дэк
…
Пример реализации

Дэк…Пример реализации

Слайд 38 Двоичная куча
Двоичный подвешенный [связный ациклический граф — дерево],
для

Двоичная кучаДвоичный подвешенный [связный ациклический граф — дерево],для которого выполнены условия:1

которого выполнены условия:

1 — Значение в любой вершине ≤ (≥)

значений детей
2 — На i-ом слое, кроме последнего 2^i вершин,
где слои нумеруются с нуля
3 — Последний слой заполняется слева направо
(может быть неполным)

Двоичная куча

Слайд 39 Двоичная куча
Двоичная куча
5
8
6
11
10
9
14
14
13
Глубина O(log(n))

Двоичная кучаДвоичная куча58611109141413Глубина O(log(n))

Слайд 40 Двоичная куча
Удобно хранить в массиве
a[0] — корень
а дети

Двоичная кучаУдобно хранить в массивеa[0] — кореньа дети a[i] - a[2i

a[i] - a[2i + 2] и a[2i + 1]
0
1
2
3
4
5
6
7
5
8
6
11
10
14
9
14
8
13
5
8
6
11
10
9
14
14
13

Слайд 41 Двоичная куча
После изменение элемента в куче, она может

Двоичная кучаПосле изменение элемента в куче, она может перестать удовлетворять условиям

перестать удовлетворять условиям кучи.
Для поддержания свойств, есть:

— siftDown (просеивание

вниз)
Спуск элемента, который меньше детей

— siftUp (просеивание вверх)
Подъём элемента, который больше родителей

Восстановление свойств

Слайд 42 Двоичная куча
Изменили элемент
Если его значение стало больше, то

Двоичная кучаИзменили элементЕсли его значение стало больше, то используем siftDownЕсли элемент

используем siftDown

Если элемент меньше детей — ОК
Иначе меняем элемент с

наименьшим из его сыновей
siftDown для сына

Время работы O(log n)

siftDown

Слайд 43 Двоичная куча
Изменили элемент
Если его значение стало меньше, то

Двоичная кучаИзменили элементЕсли его значение стало меньше, то используем siftUpЕсли элемент

используем siftUp

Если элемент больше родителя — ОК
Иначе меняем элемент с

отцом
siftUp для сына

Время работы O(log n)

siftUp

Слайд 44 Двоичная куча
Элемент в корне :)
≻ Получаем значение корня

Восстанавливаем

Двоичная кучаЭлемент в корне :)≻ Получаем значение корняВосстанавливаем кучуБерём последний элементСтавим

кучу
Берём последний элемент
Ставим на место корня
siftDown(0)

Время работы O(log n)
Извлечение

минимального элемента

Слайд 45 Двоичная куча
Вставляем элемент в конец

Восстанавливаем кучу
siftUp(elementIndex)


Время работы O(log

Двоичная кучаВставляем элемент в конецВосстанавливаем кучуsiftUp(elementIndex)Время работы O(log n)Добавление элемента

n)
Добавление элемента

Слайд 46 Двоичная куча
Вход — неупорядоченный массив данных

Первый элемент кладём

Двоичная кучаВход — неупорядоченный массив данныхПервый элемент кладём в кореньВторой и

в корень
Второй и последующие — в конец кучи
Запускаем siftUp

для каждого добавленного

Время работы O(n * log(n))

Построение кучи [1]

Слайд 47 Двоичная куча
Вход — неупорядоченный массив данных

Представим что наш

Двоичная кучаВход — неупорядоченный массив данныхПредставим что наш массив — это

массив — это дерево
Запустим siftDown от всех вершин с

детьми,
начиная с предпоследнего слоя, так как листы уже «упорядочены»

До siftDown — поддерево упорядочено
После siftDown — поддерево и вершина упорядочены

Время работы O(n)

Построение кучи [2]

Слайд 48 Двоичная куча
Доказательство времени работы

…
Построение кучи [2]

Двоичная кучаДоказательство времени работы…Построение кучи [2]

Слайд 49 Очередь с приоритетом
Абстрактный тип данных (или структура данных),
с

Очередь с приоритетомАбстрактный тип данных (или структура данных),с операциями:1 — Добавить элемент

операциями:

1 — Добавить элемент с приоритетом
2 — Достать элемент с наименьшим

(наивысшим) приоритетом
3 — Посмотреть элемент на вершине

АТД Очередь с приоритетом

Слайд 50 Очередь с приоритетом
1 — Добавить элемент с приоритетом
O(log n)
2

Очередь с приоритетом1 — Добавить элемент с приоритетомO(log n)2 — Достать элемент с

— Достать элемент с наименьшим (наивысшим) приоритетом
O(log n)
3 — Посмотреть

элемент на вершине
O(1)

На двоичной куче

  • Имя файла: struktury-dannyh-dinamicheskiy-massiv-stek-ochered-dek-binarnaya-kucha.pptx
  • Количество просмотров: 161
  • Количество скачиваний: 0
- Предыдущая Ойын арқылы оқыту технологиясы
Следующая - ОСББ Наша мрія

Похожие презентации

Презентация Единого урока Безопасность в сети Интернет Презентация Единого урока Безопасность в сети Интернет 125
Курс Введение в язык SQL (Использование SQL-запросов в ASP технологиях) Курс Введение в язык SQL (Использование SQL-запросов в ASP технологиях) 124
Защита собственной информации от несанкционированного доступа Защита собственной информации от несанкционированного доступа 85
Текстовой редактор Microsoft Word 2002. Текстовой редактор Microsoft Word 2002. 118
Сложные условия на Паскале. Операторные скобки Сложные условия на Паскале. Операторные скобки 96
Дербес компьютер құрылысы Дербес компьютер құрылысы 166
Представление информации Представление информации 92
Презентация по информатике на тему Действия с информацией (5 класс) Презентация по информатике на тему Действия с информацией (5 класс) 147
Изображения в памяти компьютера Изображения в памяти компьютера 127
ПРИНЦИПЫ РАБОТЫ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ ПРИНЦИПЫ РАБОТЫ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ 124
Архиваторы Архиваторы 110
Локальные и глобальные переменные Локальные и глобальные переменные 101
Понятие локальной сети Понятие локальной сети 105
Безопасная работа в социальных сетях Безопасная работа в социальных сетях 100
Двумерные массивы. Введение Двумерные массивы. Введение 165
Виртуальный центр обработки данных Виртуальный центр обработки данных 98
Урок 16. Множество. Элементы множества Урок 16. Множество. Элементы множества 83
Особенности работы функций Особенности работы функций 95
Логические функции Логические функции 108
Оптимизационное моделирование в электронных таблицах Excel 2007 Оптимизационное моделирование в электронных таблицах Excel 2007 137
Компьютер Компьютер 125
Интегрированная методика автоматизированного построения формальных поведенческих моделей С- приложений по исходному коду Интегрированная методика автоматизированного построения формальных поведенческих моделей С- приложений по исходному коду 126
Человек и компьютер Человек и компьютер 83
Презентация проекта МТПЛ Использование ИКТ в организации коррекционно - образовательного пространства для детей групп компенсирующей направленности презентация к уроку по информатике по теме Презентация проекта МТПЛ Использование ИКТ в организации коррекционно - образовательного пространства для детей групп компенсирующей направленности презентация к уроку по информатике по теме 108
Искусственный интеллект Искусственный интеллект 103
Встраивание видео в презентацию Встраивание видео в презентацию 112
Назначение и характеристики микропроцессора Назначение и характеристики микропроцессора 82
Логические операции Логические операции 101
SAFA results: Operators Russian Federation SAFA results: Operators Russian Federation 99
Презентация для студентов, к выполнению лабораторной работы : Архивация файлов Презентация для студентов, к выполнению лабораторной работы : Архивация файлов 111