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

Содержание

Слайд 2

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Таблицы

Таблица – это набор

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

Слайд 3

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Основные операции над таблицами:

Инициализация

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

Слайд 4

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Типы таблиц:

статическая (постоянная) и

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

Слайд 5

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Очереди

Очередь – это упорядоченная

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

Слайд 6

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Основные операции над очередью:

Инициализация

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

Слайд 7

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Представление очереди в виде

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

Слайд 8

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Представление очереди в виде

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

Очередь можно хранить в виде списка с двумя указателями: начала и конца очереди.
1-й элемент 2-й элемент n-й элемент
указатель указатель
начала конца

Слайд 9

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Стеки

Стек (stack) - это

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

Слайд 10

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Стек

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

Слайд 11

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Типовые операции над стеком:

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

1. Инициализация (создание, подготовка к работе);
2. Вталкивание (включение) элемента - PUSH;
3. Выталкивание (исключение) элемента - POP;
4. Проверка пустоты стека;
5. Проверка переполнения стека;
6. Доступ к вершине (получение / изменение значения последнего поступившего элемента).

Слайд 12

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Представление стека в виде

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

Слайд 13

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Представление стека в виде

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