Что такое 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
  • Количество просмотров: 189
  • Количество скачиваний: 0
- Предыдущая Ойын арқылы оқыту технологиясы
Следующая - ОСББ Наша мрія

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

Адресация в сети Адресация в сети 124
Компьютерная обработка изображений Компьютерная обработка изображений 112
Языки представления онтологий RDFS, OWL Языки представления онтологий RDFS, OWL 108
Построение таблиц истинности Построение таблиц истинности 107
Электронные таблицы (табличный процессор MS Excel) Электронные таблицы (табличный процессор MS Excel) 145
Работа со строковыми типами данных Работа со строковыми типами данных 140
Общая характеристика графического редактора Общая характеристика графического редактора 106
Как влияет компьютер на здоровье школьника? Как влияет компьютер на здоровье школьника? 147
Лекция 13. Сортировка и поиск информации. Методы внутренней сортировки Лекция 13. Сортировка и поиск информации. Методы внутренней сортировки 141
Образцы шаблонов оформления Образцы шаблонов оформления 136
Интернет безопасность Интернет безопасность 137
Табличная форма представления информации Табличная форма представления информации 104
Свойства алгоритмов Свойства алгоритмов 140
Исследования видеоигр Исследования видеоигр 136
Презентация по информатике Базы данных 11 класс Презентация по информатике Базы данных 11 класс 171
Как можно трактовать понятие “мультимедиа с точки зрения технологий, аппаратных и программных средств? Какие предпосылки привели к усилению использования мультимедийных технологий в образовании? Перечислите достоинства и недостатки мультимедийных техноло Как можно трактовать понятие “мультимедиа с точки зрения технологий, аппаратных и программных средств? Какие предпосылки привели к усилению использования мультимедийных технологий в образовании? Перечислите достоинства и недостатки мультимедийных техноло 184
Обмен данными в системе поездной радиосвязи Обмен данными в системе поездной радиосвязи 129
Определение каскадной точки входа Определение каскадной точки входа 138
Дистанционные технологии на уроке Дистанционные технологии на уроке 111
Компьютерная графика Компьютерная графика 127
Форматы графических файлов Форматы графических файлов 153
Программное обеспечение компьютера Программное обеспечение компьютера 143
Введение в Интернет Введение в Интернет 142
Самовыгорание на работе статья по информатике (средняя группа) Самовыгорание на работе статья по информатике (средняя группа) 143
Языки программирования Языки программирования 135
ППрезентация по информатике на тему Выражения, операнды и операции в языке программирования ПАСКАЛЬ ( 9 класс) ППрезентация по информатике на тему Выражения, операнды и операции в языке программирования ПАСКАЛЬ ( 9 класс) 135
Компьютерные вирусы Компьютерные вирусы 118
Сканеры Сканеры 162
Работа с XML-данными в Java Работа с XML-данными в Java 154
История интернета в датах История интернета в датах 141