Алгоритмы и структуры данных. Лекция 5

Элементарные структуры данных.

• Абстрактные типы данных, интерфейс и реализация.
• Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации.
• Анализ учётных стоимостей операций: функция потенциала, истинные и учётные стоимости.
• Стек, очередь, дек.
• Реализация на основе массива переменного размера и на основе связанного списка.
• Моделирование очереди с помощью двух стеков.
• Корневое дерево: бинарное дерево, дерево с произвольным ветвлением, представление "левый ребёнок - правый сосед".