Абстрактные структуры данных

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.
КГТУ (КАИ), кафедра АСОИУ
Таблицы
Таблица – это набор элементов, содержащих ключ – отличительный признак для поиска элементов, и тело – сопутствующую информацию.
Примеры таблиц:
1) Таблица функции f(x): ключ – аргумент x, тело – значение f(x).
2) Словарь: ключ – слово, тело – его перевод.
3) Таблица имен компилятора: ключ – имя объекта программы (например, переменной), тело – его характеристики (тип, адрес, значение и т.п.).

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.
КГТУ (КАИ), кафедра АСОИУ
Основные операции над таблицами:
Инициализация (подготовка к работе).
Поиск элемента по ключу – основная операция (входит в другие операции).
Включение в таблицу данного элемента.
Исключение из таблицы элемента с данным ключом.
Изменение в таблице тела элемента с данным ключом.
Распечатка элементов таблицы в порядке, определяемом ключами.
Сортировка таблицы по возрастанию или убыванию ключей.

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.
КГТУ (КАИ), кафедра АСОИУ
Типы таблиц:
статическая (постоянная) и динамическая (меняющаяся при выполнении программы);
внутренняя (в ОП) и внешняя (во внешней памяти, в файле);
последовательная, с прямым доступом, древовидная.

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.
КГТУ (КАИ), кафедра АСОИУ
Очереди
Очередь – это упорядоченная последовательность элементов, в которой операции включения и исключения элементов выполняются по принципу “первым пришел – первым ушел”, т.е. включение всегда происходит в конец очереди, а исключение – из начала очереди.

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.
КГТУ (КАИ), кафедра АСОИУ
Основные операции над очередью:
Инициализация (создание пустой очереди).
Включение элемента в очередь.
Исключение элемента из очереди.

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.
КГТУ (КАИ), кафедра АСОИУ
Представление очереди в виде циклического вектора

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.
КГТУ (КАИ), кафедра АСОИУ
Представление очереди в виде списка
Очередь можно хранить в виде списка с двумя указателями: начала и конца очереди.
1-й элемент 2-й элемент n-й элемент
указатель указатель
начала конца

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.
КГТУ (КАИ), кафедра АСОИУ
Стеки
Стек (stack) - это упорядоченная последовательность элементов, в которой выполняются операции включения и исключения элемента по принципу LIFO (Last-In-First-Out) - "последним пришел - первым ушел", т.е. включение и исключение всегда происходят в одном конце. Этот конец называют верхом, противоположный - дном стека.

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.
КГТУ (КАИ), кафедра АСОИУ
Стек

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.
КГТУ (КАИ), кафедра АСОИУ
Типовые операции над стеком:
1. Инициализация (создание, подготовка к работе);
2. Вталкивание (включение) элемента - PUSH;
3. Выталкивание (исключение) элемента - POP;
4. Проверка пустоты стека;
5. Проверка переполнения стека;
6. Доступ к вершине (получение / изменение значения последнего поступившего элемента).

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.
КГТУ (КАИ), кафедра АСОИУ
Представление стека в виде вектора

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.
КГТУ (КАИ), кафедра АСОИУ
Представление стека в виде списка