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

1.

ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
КАФЕДРА ПОВТАС
АЛГОРИТМЫ И СТРУКТУРЫ
ДАННЫХ
Климачев Сергей Александрович
Старший преподаватель
ПИнж(з)
2021

2.

ЛЕКЦИЯ 2. ЭЛЕМЕНТАРНЫЕ СТРУКТУРЫ ДАННЫХ
Вопросы
1 Тип данных. Структура данных
2 Массив. Табличные структуры данных
3 Список. Стек. Очередь
4 Вычисление арифметических выражений
Литература
1. Курносов М.Г., Берлизов Д.М. Алгоритмы и структуры обработки информации
2. Кормен Т. Алгоритмы: построение и анализ
3. Макконнел Дж. Основы современных алгоритмов
2

3.

1 Тип данных. Структура данных
Тип данных – множество величин, объединенных
определенной
совокупностью
допустимых
операций [ГОСТ Р 52292-2004].
3
Базовые типы данных
bool, char, short, int, long, float, double
Тип данных – это атрибут любого значения,
которое встречается в программе, определяющий:
• множество допустимых значений, которые
могут принимать данные, принадлежащие к
этому типу;
• набор операций, которые можно выполнять над
данными этого типа.
Составные типы данных
(агрегатные, структурные,
композитные типы)
это типы данных, которые
формируются на основе базовых
(массивы, структуры и классы)

4.

1 Тип данных. Структура данных
Структура данных – программная единица,
реализующая хранение и выполнение операций
над совокупностью однотипных элементов.
Интерфейс структуры данных – набор функций
для выполнения операций над структурой данных.
//Узел односвязного списка
struct Node {
int value;
//Данные узла
struct Node *next; //Указатель на следующий узел
};
//Добавление узла в начало списка
struct Node* addFront(struct Node *list, int value);
//Поиск узла с заданным значением
struct Node* lookup(struct Node *list, int value);
//Удаление узла с заданным значением
struct Node* delete(struct Node *list, int value);
4
Абстрактный тип данных
Это тип данных, который задан только
описанием своего интерфейса.
Способ хранения данных в памяти
компьютера и алгоритмы работы с
ними сокрыты внутри функций
интерфейса.
РЕАЛИЗАЦИЯ
СТРУКТУРА ДАННЫХ

5.

1 Тип данных. Структура данных
5
Интерфейс абстрактного типа данных «Список»:
добавление элемента;
удаление элемента;
поиск элемента;
переход к следующему элементу;
переход к предыдущему элементу.
Статический массив
Связный список
Вычислительная сложность и сложность по памяти функций разных реализаций могут
быть различными!

6.

1 Тип данных. Структура данных
6
Классификация структур данных
Наличие явных связей
между элементами
Изменчивость
Упорядоченность
Связные
Статические
Линейные
• во время выполнения
программы не
изменяют ни своего
вида, ни количества
занимаемой памяти
связные списки
Несвязные
векторы
массивы
строки
стеки
очереди
Полустатические
• во время выполнения
программы могут
изменять количество
элементов, но не могут
изменить свой вид
Динамические
• во время выполнения
программы могут
изменять не только
свой размер, но и вид
каждый элемент имеет
не более одного
предшественника
два разных элемента
не могут иметь
одинакового
последователя
Нелинейные
каждый элемент имеет
некоторое количество
связей
Взаимное
расположение
элементов в памяти
Для линейных
структур данных
Структуры с
последовательным
распределением
элементов в памяти
Структуры с
произвольным
связным
распределением
элементов в памяти

7.

2 Массив. Табличные структуры данных
7
Массив – структура данных, позволяющая организовывать непрерывные конечные
последовательности однотипных элементов и обращаться к ним по номеру (индексу).
Таблица – набор элементов одинаковой организации, каждый из которых можно представить в
виде двойки