СИАКОД Flashcards
(27 cards)
Абстрактный тип данных (АТД)
АТД (абстрактный тип данных) – это математическая модель данных и совокупность операций, определенных в рамках этой модели. Определим структуру данных как набор следующих компонент:
- совокупность операций с данными;
- структура хранения данных в памяти;
- реализация каждой операции.
Линейный однонаправленный список. Описание
Линейный однонаправленный список - это структура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент. Последний элемент списка указывает на NULL. Элемент, на который нет указателя, является первым (головным) элементом списка. Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.
Линейный однонаправленный список. Множество операций
- создание пустого списка;
- вставка нового элемента в или после позиции р;
- получение доступа к элементу в позиции р для проверки и\или изменения;
- переход к следующему или предыдущему элементу.
Линейный однонаправленный список. Способы реализации
- посредством массивов (последовательное распределение памяти) в этом случае все элементы списка хранятся в смежных ячейках;
- при помощи связных списков.
Линейный однонаправленный список. Характеристики
- длина списка - количество элементов в списке;
- списки могут быть типизированными или нетипизированными, если список типизирован, то тип его элементов задан, и все его элементы должны иметь типы, совместимые с заданным типом элементов списка (обычно списки, реализованные при помощи массивов, являются типизированными);
- список может быть сортированным или несортированным;
- в зависимости от реализации может быть возможен произвольный доступ к элементам списка.
Линейный однонаправленный список. Двусвязный список
В двусвязном (двунаправленном) списке ссылки в каждом узле указывают на предыдущий и на последующий узел в списке. По двусвязному списку можно передвигаться в любом направлении - как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, так как всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.
Линейный однонаправленный список. Кольцевой связный список
Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний.
Реализация такой структуры происходит на базе линейного списка. В каждом кольцевом списке есть указатель на первый элемент. В этом списке константы NULL не существует.
Линейный однонаправленный список. Достоинства связных списков
- лёгкость добавления и удаления элементов;
- размер ограничен только объёмом памяти компьютера и разрядностью указателей;
- динамическое добавление и удаление элементов.
Линейный однонаправленный список. Недостатки связных списков
- сложность определения адреса элемента по его индексу (номеру) в списке;
- на поля-указатели (указатели на следующий и предыдущий элемент) расходуется дополнительная память (в массивах, например, указатели не нужны);
- работа со списком медленнее, чем с массивами, так как к любому элементу списка можно обратиться, только пройдя все предшествующие ему элементы;
- элементы списка могут быть расположены в памяти разреженно, что окажет негативный эффект на кэширование процессора;
- над связными списками гораздо труднее (хотя и в принципе возможно) производить параллельные векторные операции, такие как вычисление суммы;
- кэш-промахи при обходе списка.
Стек. Описание
Стек (англ. stack - стопка) - структура данных, представляющая собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.
Стек. Организация в памяти
Зачастую стек реализуется в виде однонаправленного списка (каждый элемент списка указывает только на следующий). Но в таком случае невозможно применить операцию обхода элементов. А доступ возможен только к верхнему элементу структуры. Для обхода такой проблемы можно взять за основу двусвязный список (каждый элемент указывает на обоих соседей справа и слева). Кроме того, можно организовать его на обыкновенном массиве.
Значением переменной стека является указатель на вершину стека. Если стек пуст, то значение указателя равно NULL.
Стек. Операции со стеком
Возможны три операции со стеком: добавление элемента (иначе проталкивание, push), удаление элемента (pop) и чтение головного элемента (peek).
При проталкивании (push) указывается новый элемент, указывающий на элемент бывший до этого головой. Новый элемент теперь становится головным.
При удалении элемента убирается первый, а головным становится тот, на который был указатель у этого объекта (следующий элемент).
Очередь. Описание
Очередь - структура данных с дисциплиной доступа к элементам «первый пришёл - первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.
Очередь. Массивы. Принцип работы
Обычно start указывает на голову очереди, end — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в q[end] записывается новый элемент очереди, а end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично: после извлечения элемента q[start] из очереди переменная start уменьшается на 1. С такими алгоритмами одна ячейка из n всегда будет незанятой (так как очередь с n элементами невозможно отличить от пустой), что компенсируется простотой алгоритмов.
Очередь. Массивы. Преимущества
- возможна незначительная экономия памяти по сравнению со способом на связных списках;
- проще в разработке.
Очередь. Массивы. Недостатки
- максимальное количество элементов в очереди ограничено размером массива.
- при его переполнении требуется перевыделение памяти и копирование всех элементов в новый массив.
Очередь. Связные списки. Описание
Способ на связных списках основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление/удаление элементов идет строго с соответствующих его концов.
Очередь. Связные списки. Преимущества
Размер очереди ограничен лишь объёмом памяти
Очередь. Связные списки. Недостатки
- сложнее в разработке;
- требуется больше памяти;
- при работе с такой очередью память сильнее фрагментируется;
- работа с очередью несколько медленнее.
Очередь. Способы реализации очереди
- массивы;
- связный список;
- на двух стеках.
Дерево. Описание
Дерево - одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указываются, что рёбра графа не должны быть взвешенными.
Дерево. Корневой узел
Корневой узел - самый верхний узел дерева.
Дерево. Корень
Корень - одна из вершин, по желанию наблюдателя.
Дерево. Лист
Лист, листовой или терминальный узел — узел, не имеющий дочерних элементов.
