Практикум программирования. Модуль 7

1. Практикум программирования. модуль 7

www.specialist.ru

2. Коллекции.

Набор однотипных элементов.
Зачем?
Массив vs. Коллекция
www.specialist.ru
2

3.

Массив:
Доступ
Поиск
Вставка
Удаление
Worst
О(1)
О(n)
О(n)
О(n)
Average
Θ(1)
Θ(n)
Θ(n)
Θ(n)
www.specialist.ru
3

4.

Стек (LIFO):
Доступ
Поиск
Вставка
Удаление
Worst
О(n)
О(n)
О(1)
О(1)
Average
Θ(n)
Θ(n)
Θ(1)
Θ(1)
www.specialist.ru
4

5.

Очередь(FIFO):
Доступ
Поиск
Вставка
Удаление
Worst
О(n)
О(n)
О(1)
О(1)
Average
Θ(n)
Θ(n)
Θ(1)
Θ(1)
www.specialist.ru
5

6.

Список:
Доступ
Поиск
Вставка
Удаление
Worst
О(n)
О(n)
О(1)
О(1)
Average
Θ(n)
Θ(n)
Θ(1)
Θ(1)
www.specialist.ru
6

7.

Бинарное дерево:
Доступ
Поиск
Вставка
Удаление
Worst
О(n)
О(n)
О(n)
О(n)
Average
Θ(log(n))
Θ((log(n))
Θ((log(n))
Θ((log(n))
www.specialist.ru
7

8.

Хеш-таблица:
Доступ
Поиск
Вставка
Удаление
Worst
N/A
О(n)
О(n)
О(n)
Average
N/A
Θ(1)
Θ(1)
Θ(1)
www.specialist.ru
8

9. Практика

Проектирование связанного списка.
Реализация связанного списка.
Использование связанного списка для хранения
данных.
ДЗ
www.specialist.ru
9