материалы_к_лекции_списки

Массив (низкоуровневый)

int arr[20]; // или

int* arr = new int[size];

Достоинства

высокая скорость доступа по индексу

высокая скорость вставки/удаления в конец

Недостатки

ограниченный размер

низкая скорость вставки/удаления в начало и середину

нет контроля индекса

медленный поиск

9

•Линейные списки – структуры данных, в которых элементы (переменные) следуют друг за другом, и каждому можно поставить в соответствие порядковый номер

НГТУ, Кафедра АППМ

Примеры других контейнеров

Очередь (двухсторонняя, односторонняя)

Стек

Дерево (бинарное, общее)

Хэш-таблица

Линейный список (однонаправленный, двунаправленный, кольцевой)

13

Виды линейных списков

НГТУ, Кафедра АППМ

Операции с линейными списками

к-1 к к+1

НГТУ, Кафедра АППМ

Очередь и стек

Стек

Односторонняя очередь

Двухсторонняя очередь

Реализация? Использование?

Достоинства? Недостатки?

14

Бинарное дерево – разновидность общего дерева

15

Хэш-таблица

ключ данные

ключ данные

ключ данные

ключ данные

Если данные равны, то ключи равны

Если данные различаются, то ключи, как правило, тоже различаются (за редкими исключениями)

Хэш-функция – порождает ключ по данным

Сравнение ключей существенно проще сравнения данных

16

Принцип организации линейного списка

Элементы списка могут располагаться в памяти не подряд

Место под элементы выделяется и

освобождается по необходимости

Каждый элемент, помимо полезных данных, хранит указатель на соседний элемент

Достоинства, недостатки?

17

Линейный список – достоинства и недостатки

Достоинства

высокая скорость операций вставки и удаления

возможность создавать списки любого размера

высокая скорость перебора

Недостатки

низкая скорость операции доступа по индексу

низкая скорость поиска элементов

18