Структуры данных

1.

Тема 7. Структуры данных
«Плохие программисты думают о коде.
Хорошие программисты думают о
структурах данных и их взаимосвязях», —
Линус Торвальдс, создатель Linux
• Основные понятия
• Линейный список
• Стек
• Очередь
• Мар
• Хэш-таблица
• Дерево
• Реализация стека при помощи массива

2.

Тема 3. Указатели
Основные понятия
Структура данных – одно из первичных понятий программирования, и как любое первичное
понятие достаточно трудно определимое. «Структура данных – систематизированный способ
организации данных и доступа к ним».
Свойства структуры данных и взаимосвязи с другими понятиями программирования и языков:
• Структура данных и переменная. Переменная – элемент языка программирования, структура
данных – внеязыковая единица, технологический элемент программирования. Структура
данных – совокупность переменных, взаимосвязанных через свои значения в единое
целое.
• Структура данных и внешняя реальность. Не все внешние объекты (сущности), отображаемые
в программе, могут быть представлены переменными. Некоторым из них соответствуют
структуры данных – множество взаимосвязанных переменных.
• Структура данных и алгоритм. Взаимосвязь значений переменных не может быть только
статичной. Алгоритмы, работающие со структурой данных, связывают между собой значения
переменных динамически, соблюдая установленные для них соглашения.
Структура данных - совокупность взаимосвязанных переменных и их значений
2

3.

Основные понятия
Тема 3. Указатели
Любая структура данных имеет две стороны. Физическая структура данных – это ее
представление в памяти в том виде, как она выглядит «на самом деле». Логическая структура
данных – это созданная программными средствами образное, абстрактное ее представление.
При этом оба представления могут сосуществовать при самых разных сочетаниях их свойств:
одномерная – двумерная, линейная – нелинейная и т.п..
Перед написанием программы важно правильно выбрать структуру данных, обеспечивающую
эффективное решение задачи. Одни и те же данные можно сохранить в структурах, требующих
различного объема памяти, а алгоритмы работы с каждой структурой могут иметь различную
эффективность. Если выбрана наиболее подходящая структура и вы в совершенстве владеете
методами работы с ней, то разработка алгоритма уже не вызовет затруднений, а сам алгоритм
решения будет оптимален и по объему занимаемой памяти, и по времени работы алгоритма.
Структура данных определяет объекты, организованные определенным образом и операции,
которые можно выполнять над объектами. Доступ к объектам и все операции с ними
осуществляются только через интерфейс. Интерфейс отделяет реализацию структуры данных от
клиента, и является «непрозрачным» для клиента. Структура данных может быть представлена
3
как некий «черный ящик» с интерфейсами.

4.

Тема 3. Указатели
Основные понятия
4

5.

Тема 3. Указатели
Связанный список
Связный список — одна из базовых структур данных. Ее часто сравнивают с массивом, так как
многие другие структуры можно реализовать с помощью либо массива, либо связного списка. У
этих двух типов есть преимущества и недостатки.
Список
является
линейной
упорядоченной
динамической структурой хранения данных, в
которой между элементами имеются явные связи.
Доступ к элементам списка – последовательный.
Связный список состоит из группы узлов, которые вместе образуют последовательность.
Каждый элемент списка содержит, по крайней мере, два поля. Одно поле – информационное
(ради которого и создаётся список), другое поле - предназначено для размещения указателя на
следующий или предыдущий элемент этого списка. Последний элемент в поле ссылки
содержит признак конца списка (null). Кроме того, программа должна содержать ссылку на
первый элемент списка – голову списка. Основные операции в связном списке включают
добавление, удаление и поиск элемента в списке.
5

6.

Связанный список
Тема 3. Указатели
Учитывая количество связей между элементами списка различают одно- или двусвязные
списки. В последнем случае элемент списка содержит ссылку, как на последующий элемент, так
и на предыдущий. Кроме того, возможны циклические списки. Тогда поле ссылки последнего
элемента содержит ссылку на первый элемент списка.
Возможна организация списка и на смежной памяти. В этом случае все элементы структуры
данных имеют один и тот же тип, а число возможных элементов ограничено длиной массива,
выделенного под список. Список на смежной памяти можно создать с использованием
нескольких массивов с одним и тем же индексом или на одном массиве структур (записей).
Head
А А Б
З
К
-1 4
3
1
7
У
0
5
0
Пример списка, содержащего символы, и реализованного на
массиве структур (линейный односвязный список). На рисунке
информационная часть списка содержит слово «АЗБУКА»,
ссылочная часть списка содержит индекс следующего элемента
списка. Последний элемент списка в ссылочной части содержит
значение -1. Чтобы реализовать операции «удалить-добавить
элемент» в таком списке требуется создать дополнительный
список (стек) свободных элементов. Удаляемый элемент при
этом включается в список свободных, а для включения нового
элемента используется элемент из списка свободных.
Естественно, что в этом случае возможна ситуация, когда
свободные элементы отсутствуют.
6

7.

Стек
Тема 3. Указатели
Стек — это базовая структура данных, которая позволяет добавлять или удалять элементы только
в её начале. Она похожа на стопку книг: если вы хотите взглянуть на книгу в середине стека,
сперва придется убрать лежащие сверху.
Стек - это динамически изменяемый упорядоченный набор элементов. Засылка элементов
в стек и выборка их из стека производятся с одного и того же конца стека, который
называется вершиной стека.
Выборка элементов из стека осуществляется в порядке, обратном их засылке. Это правило
формулируется так: «последний пришёл, первым ушел» (принцип Last In First Out). Это значит,
что последний элемент, который вы добавили в стек, первым выйдет из него. Для работы со
стеком необходимо иметь один адрес: адрес вершины стека. Для стека возможны следующие
операции:
- добавление элемента (push);
- удаление элемента (pop);
- отображение содержимого стека (pip).
- выбрать элемент из стека;
7
- проверить наличие элементов в стеке.

8.

Тема 3. Указатели
Очередь
Эту структуру можно представить как очередь в продуктовом магазине. Первым обслуживают
того, кто пришёл в самом начале — всё как в жизни.
Очередь – это линейно упорядоченный динамический набор следующих друг за другом
элементов, доступ к которым происходит по следующим правилам:
- новые элементы могут добавляться лишь в конец (хвост) очереди;
- значения элементов могут читаться (извлекаться) лишь в порядке следования элементов от
«головы» к «хвосту» очереди.
Размер очереди заранее не оговаривается (теоретически может быть бесконечно большим). Для
запоминания (хранения) элементов очереди часто используют внешние запоминающие
устройства большой емкости.
Для очереди принцип извлечения и добавления элементов
следующий: первым пришел – первым вышел (First In First Out).
Это значит, что удалить элемент можно только
после того, как были убраны все ранее добавленные элементы.
8

9.

Тема 3. Указатели
Очередь
Очередь позволяет выполнять две основных операции: добавлять элементы в конец очереди
(enqueue) и удалять первый элемент (dequeue).
Таким образом, при работе с очередью необходимо иметь два адреса: первый - адрес «хвоста»
очереди (чтобы поместить туда новый элемент); второй - адрес начала очереди (чтобы извлечь
первый элемент).
Операции, которые можно выполнить над очередью:
1)
добавить элемент в очередь;
2)
извлечь элемент из очереди;
3)
проверить наличие элементов в очереди.
Дек – это разновидность очереди, в которой включение и выборка элементов возможны с обоих
концов. Дек может использоваться, например, для управления памятью, когда распределение
производится и сверху и снизу.
И очередь и дек можно реализовывать как на связанной памяти, так и на смежной памяти.
9

10.

Тема 3. Указатели
Множество
Множество хранит значения данных без определенного порядка, не повторяя их. Оно
позволяет не только добавлять и удалять элементы: есть ещё несколько важных функций,
которые можно применять к двум множествам сразу.
• Объединение комбинирует все элементы из двух разных множеств, превращая их в одно (без
дубликатов).
• Пересечение анализирует два множества и создает еще одно из тех элементов, которые
присутствуют в обоих изначальных множествах.
• Разность выводит список элементов, которые есть в одном множестве, но отсутствуют в
другом.
• Подмножество выдает булево значение, которое показывает, включает ли одно множество все
элементы другого множества.
10

11.

Тема 3. Указатели
Map
Map — это структура, которая хранит данные в парах ключ/значение, где каждый ключ
уникален. Иногда её также называют ассоциативным массивом или словарём. Map часто
используют для быстрого поиска данных. Она позволяет делать следующие вещи:
добавлять пары в коллекцию;
удалять пары из коллекции;
изменять существующей пары;
искать значение, связанное с определенным ключом.
11

12.

Хэш-таблица
Тема 3. Указатели
Хэш-таблица — это похожая на Map структура, которая содержит пары ключ/значение. Она
использует хэш-функцию для вычисления индекса в массиве из блоков данных, чтобы найти
желаемое значение.
Обычно хэш-функция принимает строку символов в качестве вводных данных и выводит
числовое значение. Для одного и того же ввода хэш-функция должна возвращать одинаковое
число. Если два разных ввода хэшируются с одним и тем же итогом, возникает коллизия. Цель в
том, чтобы таких случаев было как можно меньше.
При вводе пары ключ/значение в хэш-таблицу, ключ
проходит через хэш-функцию и превращается в число. В
дальнейшем это число используется как фактический ключ,
который соответствует определенному значению. Когда вы
снова введёте тот же ключ, хэш-функция обработает его и
вернет такой же числовой результат. Затем этот результат
будет использован для поиска связанного значения. Такой
12
подход заметно сокращает среднее время поиска.

13.

Дерево
Тема 3. Указатели
Дерево — это структура данных, состоящая из узлов. Дерево – это иерархическая структура,
которая представляет собой нелинейное непустое конечное множество элементов, один из
которых называется корнем, а остальные - делятся на несколько непересекающихся
подмножеств, каждое из которых также является деревом. Каждый элемент дерева
является узлом (вершиной) дерева. Линия, соединяющая пару узлов, называется ветвью.
Ей присущи следующие свойства:
• Каждое дерево имеет корневой узел (вверху).
• Корневой узел имеет ноль или более дочерних узлов.
• Каждый дочерний узел имеет ноль или более дочерних узлов, и так далее.
Деревья, у которых узлы могут иметь не более двух потомков, называются бинарными. У
двоичного дерева поиска есть два дополнительных свойства:
• Каждый узел имеет до двух дочерних узлов (потомков).
• Каждый узел меньше своих потомков справа, а его потомки слева меньше его самого.
Двоичные деревья поиска позволяют быстро находить, добавлять и удалять элементы. Они
устроены так, что время каждой операции пропорционально логарифму общего числа элементов
13
в дереве.

14.

Тема 3. Указатели
Дерево
Те узлы, которые не ссылаются ни на какие другие узлы, называются листьями. Узлы, на которые
ссылается некоторый узел дерева, называются дочерними или его потомками. Узел, который
ссылается на данный узел, называют родительским. На рисунке видно, что вершины дерева
располагаются на четырёх уровнях.
I
II
III
IV
14

15.

Тема 3. Указатели
Реализация стека при помощи массива
15

16.

Тема 3. Указатели
Реализация стека при помощи массива
Как мы видим, заполняя стек методом push ,
мы помещаем каждый новый элемент в
конец массива (Вершину стека). Указателем
на вершину стека служит поле last в
структуре стека. Снимая элемент с вершины
стека методом pop в нашей реализации, мы
возвращаем значение элемента, а затем
удаляем этот элемент (уменьшая указатель
last на единицу). Таким образом, обращаясь
к вершине стека после его заполнения, мы
разворачиваем
последовательность
элементов. Стек можно применять для
разворота последовательности элементов.
16

17.

Тема 3. Указатели
Реализация стека при помощи массива
Приведенную программу логично дополнить проверкой стека на наличие в нем элементов –
методом empty(). Функция empty() вернет true, если стек пуст и false в противном случае.
Функция size() позволяет определить количество элементов в стеке.
Функция top() позволяет обращаться к вершине стека – возвращать элемент,
находящийся в вершине стека, но при этом не удалять его (в отличие от метода pop()).
17

18.

Тема 3. Указатели
Задачи, решаемые при помощи стека
1. Грамматика правильной скобочной последовательности. Правильная скобочная
последовательность – последовательность, состоящая из символов – «скобок», в которой
каждой отрывающейся скобке соответствует закрывающаяся скобка такого же типа, что и
открывающаяся скобка. ()((()))[[]] , [[)) .
2. Вычисления арифметических выражений. Арифметическое выражение состоит из чисел,
знаков арифметических действий и скобок.
3. Ближайший меньший слева и справа. Дан массив чисел. Требуется вывести ближайший
меньший слева и справа для данного элемента. Например, для массива a[9]={6 5 9 8 7 1 2 3 5}
18

19.

Тема 3. Указатели
Алгоритмы
19