- Главная
- Информатика
- Структуры данных
Содержание
- 2. Тема 3. Указатели Основные понятия Структура данных – одно из первичных понятий программирования, и как любое
- 3. Тема 3. Указатели Основные понятия Любая структура данных имеет две стороны. Физическая структура данных – это
- 4. Тема 3. Указатели Основные понятия
- 5. Тема 3. Указатели Связанный список Связный список — одна из базовых структур данных. Ее часто сравнивают
- 6. Тема 3. Указатели Связанный список Учитывая количество связей между элементами списка различают одно- или двусвязные списки.
- 7. Тема 3. Указатели Стек Стек — это базовая структура данных, которая позволяет добавлять или удалять элементы
- 8. Тема 3. Указатели Очередь Эту структуру можно представить как очередь в продуктовом магазине. Первым обслуживают того,
- 9. Тема 3. Указатели Очередь Очередь позволяет выполнять две основных операции: добавлять элементы в конец очереди (enqueue)
- 10. Тема 3. Указатели Множество Множество хранит значения данных без определенного порядка, не повторяя их. Оно позволяет
- 11. Тема 3. Указатели Map Map — это структура, которая хранит данные в парах ключ/значение, где каждый
- 12. Тема 3. Указатели Хэш-таблица Хэш-таблица — это похожая на Map структура, которая содержит пары ключ/значение. Она
- 13. Тема 3. Указатели Дерево Дерево — это структура данных, состоящая из узлов. Дерево – это иерархическая
- 14. Тема 3. Указатели Дерево Те узлы, которые не ссылаются ни на какие другие узлы, называются листьями.
- 15. Тема 3. Указатели Реализация стека при помощи массива
- 16. Тема 3. Указатели Реализация стека при помощи массива Как мы видим, заполняя стек методом push ,
- 17. Тема 3. Указатели Реализация стека при помощи массива Приведенную программу логично дополнить проверкой стека на наличие
- 18. Тема 3. Указатели Задачи, решаемые при помощи стека Грамматика правильной скобочной последовательности. Правильная скобочная последовательность –
- 20. Скачать презентацию
Тема 3. Указатели
Основные понятия
Структура данных – одно из первичных понятий программирования, и как
Тема 3. Указатели
Основные понятия
Структура данных – одно из первичных понятий программирования, и как
Свойства структуры данных и взаимосвязи с другими понятиями программирования и языков:
Структура данных и переменная. Переменная – элемент языка программирования, структура данных – внеязыковая единица, технологический элемент программирования. Структура данных – совокупность переменных, взаимосвязанных через свои значения в единое целое.
Структура данных и внешняя реальность. Не все внешние объекты (сущности), отображаемые в программе, могут быть представлены переменными. Некоторым из них соответствуют структуры данных – множество взаимосвязанных переменных.
Структура данных и алгоритм. Взаимосвязь значений переменных не может быть только статичной. Алгоритмы, работающие со структурой данных, связывают между собой значения переменных динамически, соблюдая установленные для них соглашения.
Структура данных - совокупность взаимосвязанных переменных и их значений
Тема 3. Указатели
Основные понятия
Любая структура данных имеет две стороны. Физическая структура данных –
Тема 3. Указатели
Основные понятия
Любая структура данных имеет две стороны. Физическая структура данных –
Перед написанием программы важно правильно выбрать структуру данных, обеспечивающую эффективное решение задачи. Одни и те же данные можно сохранить в структурах, требующих различного объема памяти, а алгоритмы работы с каждой структурой могут иметь различную эффективность. Если выбрана наиболее подходящая структура и вы в совершенстве владеете методами работы с ней, то разработка алгоритма уже не вызовет затруднений, а сам алгоритм решения будет оптимален и по объему занимаемой памяти, и по времени работы алгоритма. Структура данных определяет объекты, организованные определенным образом и операции, которые можно выполнять над объектами. Доступ к объектам и все операции с ними осуществляются только через интерфейс. Интерфейс отделяет реализацию структуры данных от клиента, и является «непрозрачным» для клиента. Структура данных может быть представлена как некий «черный ящик» с интерфейсами.
Тема 3. Указатели
Основные понятия
Тема 3. Указатели
Основные понятия
Тема 3. Указатели
Связанный список
Связный список — одна из базовых структур данных. Ее часто
Тема 3. Указатели
Связанный список
Связный список — одна из базовых структур данных. Ее часто
Связный список состоит из группы узлов, которые вместе образуют последовательность. Каждый элемент списка содержит, по крайней мере, два поля. Одно поле – информационное (ради которого и создаётся список), другое поле - предназначено для размещения указателя на следующий или предыдущий элемент этого списка. Последний элемент в поле ссылки содержит признак конца списка (null). Кроме того, программа должна содержать ссылку на первый элемент списка – голову списка. Основные операции в связном списке включают добавление, удаление и поиск элемента в списке.
Список является линейной упорядоченной динамической структурой хранения данных, в которой между элементами имеются явные связи. Доступ к элементам списка – последовательный.
Тема 3. Указатели
Связанный список
Учитывая количество связей между элементами списка различают одно- или двусвязные
Тема 3. Указатели
Связанный список
Учитывая количество связей между элементами списка различают одно- или двусвязные
Возможна организация списка и на смежной памяти. В этом случае все элементы структуры данных имеют один и тот же тип, а число возможных элементов ограничено длиной массива, выделенного под список. Список на смежной памяти можно создать с использованием нескольких массивов с одним и тем же индексом или на одном массиве структур (записей).
Пример списка, содержащего символы, и реализованного на массиве структур (линейный односвязный список). На рисунке информационная часть списка содержит слово «АЗБУКА», ссылочная часть списка содержит индекс следующего элемента списка. Последний элемент списка в ссылочной части содержит значение -1. Чтобы реализовать операции «удалить-добавить элемент» в таком списке требуется создать дополнительный список (стек) свободных элементов. Удаляемый элемент при этом включается в список свободных, а для включения нового элемента используется элемент из списка свободных. Естественно, что в этом случае возможна ситуация, когда свободные элементы отсутствуют.
Тема 3. Указатели
Стек
Стек — это базовая структура данных, которая позволяет добавлять или удалять
Тема 3. Указатели
Стек
Стек — это базовая структура данных, которая позволяет добавлять или удалять
Стек - это динамически изменяемый упорядоченный набор элементов. Засылка элементов в стек и выборка их из стека производятся с одного и того же конца стека, который называется вершиной стека.
Выборка элементов из стека осуществляется в порядке, обратном их засылке. Это правило формулируется так: «последний пришёл, первым ушел» (принцип Last In First Out) . Это значит, что последний элемент, который вы добавили в стек, первым выйдет из него. Для работы со стеком необходимо иметь один адрес: адрес вершины стека. Для стека возможны следующие операции:
добавление элемента (push);
удаление элемента (pop);
отображение содержимого стека (pip).
выбрать элемент из стека;
проверить наличие элементов в стеке.
Тема 3. Указатели
Очередь
Эту структуру можно представить как очередь в продуктовом магазине. Первым обслуживают
Тема 3. Указатели
Очередь
Эту структуру можно представить как очередь в продуктовом магазине. Первым обслуживают
Очередь – это линейно упорядоченный динамический набор следующих друг за другом элементов, доступ к которым происходит по следующим правилам:
- новые элементы могут добавляться лишь в конец (хвост) очереди;
значения элементов могут читаться (извлекаться) лишь в порядке следования элементов от «головы» к «хвосту» очереди.
Размер очереди заранее не оговаривается (теоретически может быть бесконечно большим). Для запоминания (хранения) элементов очереди часто используют внешние запоминающие устройства большой емкости.
Для очереди принцип извлечения и добавления элементов
следующий: первым пришел – первым вышел (First In First Out).
Это значит, что удалить элемент можно только
после того, как были убраны все ранее добавленные элементы.
Тема 3. Указатели
Очередь
Очередь позволяет выполнять две основных операции: добавлять элементы в конец очереди
Тема 3. Указатели
Очередь
Очередь позволяет выполнять две основных операции: добавлять элементы в конец очереди
Таким образом, при работе с очередью необходимо иметь два адреса: первый - адрес «хвоста» очереди (чтобы поместить туда новый элемент); второй - адрес начала очереди (чтобы извлечь первый элемент).
Операции, которые можно выполнить над очередью:
1) добавить элемент в очередь;
2) извлечь элемент из очереди;
3) проверить наличие элементов в очереди.
Дек – это разновидность очереди, в которой включение и выборка элементов возможны с обоих концов. Дек может использоваться, например, для управления памятью, когда распределение производится и сверху и снизу.
И очередь и дек можно реализовывать как на связанной памяти, так и на смежной памяти.
Тема 3. Указатели
Множество
Множество хранит значения данных без определенного порядка, не повторяя их. Оно
Тема 3. Указатели
Множество
Множество хранит значения данных без определенного порядка, не повторяя их. Оно
Объединение комбинирует все элементы из двух разных множеств, превращая их в одно (без дубликатов).
Пересечение анализирует два множества и создает еще одно из тех элементов, которые присутствуют в обоих изначальных множествах.
Разность выводит список элементов, которые есть в одном множестве, но отсутствуют в другом.
Подмножество выдает булево значение, которое показывает, включает ли одно множество все элементы другого множества.
Тема 3. Указатели
Map
Map — это структура, которая хранит данные в парах ключ/значение, где
Тема 3. Указатели
Map
Map — это структура, которая хранит данные в парах ключ/значение, где
добавлять пары в коллекцию;
удалять пары из коллекции;
изменять существующей пары;
искать значение, связанное с определенным ключом.
Тема 3. Указатели
Хэш-таблица
Хэш-таблица — это похожая на Map структура, которая содержит пары ключ/значение.
Тема 3. Указатели
Хэш-таблица
Хэш-таблица — это похожая на Map структура, которая содержит пары ключ/значение.
Обычно хэш-функция принимает строку символов в качестве вводных данных и выводит числовое значение. Для одного и того же ввода хэш-функция должна возвращать одинаковое число. Если два разных ввода хэшируются с одним и тем же итогом, возникает коллизия. Цель в том, чтобы таких случаев было как можно меньше.
При вводе пары ключ/значение в хэш-таблицу, ключ проходит через хэш-функцию и превращается в число. В дальнейшем это число используется как фактический ключ, который соответствует определенному значению. Когда вы снова введёте тот же ключ, хэш-функция обработает его и вернет такой же числовой результат. Затем этот результат будет использован для поиска связанного значения. Такой подход заметно сокращает среднее время поиска.
Тема 3. Указатели
Дерево
Дерево — это структура данных, состоящая из узлов. Дерево – это
Тема 3. Указатели
Дерево
Дерево — это структура данных, состоящая из узлов. Дерево – это
Ей присущи следующие свойства:
Каждое дерево имеет корневой узел (вверху).
Корневой узел имеет ноль или более дочерних узлов.
Каждый дочерний узел имеет ноль или более дочерних узлов, и так далее.
Деревья, у которых узлы могут иметь не более двух потомков, называются бинарными. У двоичного дерева поиска есть два дополнительных свойства:
Каждый узел имеет до двух дочерних узлов (потомков).
Каждый узел меньше своих потомков справа, а его потомки слева меньше его самого.
Двоичные деревья поиска позволяют быстро находить, добавлять и удалять элементы. Они устроены так, что время каждой операции пропорционально логарифму общего числа элементов в дереве.
Тема 3. Указатели
Дерево
Те узлы, которые не ссылаются ни на какие другие узлы, называются
Тема 3. Указатели
Дерево
Те узлы, которые не ссылаются ни на какие другие узлы, называются
Тема 3. Указатели
Реализация стека при помощи массива
Тема 3. Указатели
Реализация стека при помощи массива
Тема 3. Указатели
Реализация стека при помощи массива
Как мы видим, заполняя стек методом push
Тема 3. Указатели
Реализация стека при помощи массива
Как мы видим, заполняя стек методом push
Тема 3. Указатели
Реализация стека при помощи массива
Приведенную программу логично дополнить проверкой стека на
Тема 3. Указатели
Реализация стека при помощи массива
Приведенную программу логично дополнить проверкой стека на
Функция size() позволяет определить количество элементов в стеке.
Функция top() позволяет обращаться к вершине стека – возвращать элемент, находящийся в вершине стека, но при этом не удалять его (в отличие от метода pop()).
Тема 3. Указатели
Задачи, решаемые при помощи стека
Грамматика правильной скобочной последовательности. Правильная скобочная последовательность
Тема 3. Указатели
Задачи, решаемые при помощи стека
Грамматика правильной скобочной последовательности. Правильная скобочная последовательность
Вычисления арифметических выражений. Арифметическое выражение состоит из чисел, знаков арифметических действий и скобок.
Ближайший меньший слева и справа. Дан массив чисел. Требуется вывести ближайший меньший слева и справа для данного элемента. Например, для массива a[9]={6 5 9 8 7 1 2 3 5}