Теория. Структуры данных. Сортировка. Бинарный поиск

Общие сведения

Структура данных (англ. data structure) — это программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных. Для добавления, поиска, изменения и удаления данных структура данных предоставляет набор функций, составляющих её интерфейс (Вики). В зависимости от назначения структуры, данные, хранящиеся в ней, организованы в памяти различным образом. Наиболее простая (в этом смысле) структура данных – это обычный массив. Данные в массиве хранятся в одной области памяти в соседних ячейках. Это обеспечивает индексацию элементов, так как, фактически, индекс привязан к номеру ячейки памяти. Отсюда и название этих структур данных – последовательные контейнеры (C++). Им родственны структуры дек, стек и очередь. А вот множества, словари и хэши основаны на древовидных структурах, поэтому индексация для них не применяется. В этих структурах доступ к элементам осуществляется не по индексу, а с помощью специальных функций или итераторов. Такое различие в устройстве объясняется сферами применения этих структур.
Для разработчика особый интерес имеют операции с данными, которые предоставляют классы обслуживающие эти структуры. Конечно, наиболее значимы – это операции сортировки и поиска. Эти процессы используются во многих сложных, но эффективно решаемых задачах. Мы не уточняли какие конкретно операции можно выполнять для соответствующих структур. Эти сведения вы можете получить на других страницах сайта или в учебнике. Ниже дается только краткая характеристика с приложением ссылок для более детального знакомства с перечисленными структурами. Структуры данных можно моделировать и самостоятельно, но это очень сложные алгоритмы, требующих от разработчика значительных временных затрат. Использование же встроенных структур данных, в решаемых задачах, может существенно ускорить разработку и значительно повысить эффективность создаваемых программ.

Динамический массив

Динамический массив отличается от статического тем, что может изменять свой размер с конца массива. В некоторых задачах применение динамических массивов очень удобно, так как сокращает объем разработки. Эффективная работа с массивом выполняется только тогда, когда данные добавляются или удаляются с конца. Если данные вставляются в начало или середину массива – эффективность снижается. На эффективность влияет и перераспределение памяти (если размер массива превысит его объем, данные будут перенесены в другую область памяти).

Если же нужно осуществлять эффективную вставку или удаление в любую область в массиве, то необходимо применять двусвязный список – list (C++).

Динамические массивы:

  • C++ -> vector
  • python -> list
Несколько слов о статических массивах. Поскольку область памяти, где хранятся элементы, не изменяется, то работа со статическим массивом будет более эффективна. Если в задаче не предусмотрено изменение размеров массива, то лучше использовать статический массив.
Статические массивы:
  • C++ -> array
  • python -> tuple (неизменяемый)
Учебник
inf-w.ru

Дек

Дек, двусвязная очередь (от англ. deque — double ended queue) — структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов массива. Во всем подобен vector‘у в C++. На основе deque можно создавать и другие структуры данных, например стек или очередь. Наиболее эффективная операция – вставка и удаление элементов в начале и конце массива. В отличие от вектора (в C++), дек эффективно увеличивает свой объем (по мере необходимости). Поддерживает индексацию. В python реализован в классе collections.deque (док. collections — Container datatypes)
Деки:

  • C++ -> deque
  • python -> deque
Учебник
inf-w.ru

Список

Или двусвязный список (list) – структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как стек и очередь. Индексация в списках не поддерживается, но зато можно быстро вставлять элементы в любую позицию. Интересно, что перемещение и удаление элементов в list (C++) работает быстрее, нежели при использовании библиотеки algorithm.

Не путайте List в python с этой структурой данных! В не зависимости от реализации, List python подобен vector в C++, за той лишь разницей, что он более универсален, т.е. может хранить одновременно разные типы (что приводит к его низкой эффективности).

Стек

Стек (от англ. stack — стопка) — структура данных, представляющая из себя набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел — первым вышел» (last-in, first-out — LIFO). Примером стека в реальной жизни может являться стопка тарелок: когда мы хотим вытащить тарелку, мы должны снять все тарелки выше. (Вики).
В C++ стек реализован как адаптер контейнера (vector). Аналигично можно сказать и о python. Стек в python создается на основе List (док. 5.1.1. Using Lists as Stacks).
Stacks:

  • C++ -> stack
  • python -> list
Учебник
inf-w.ru

Очередь

Очередь (англ. queue) — это структура данных, в которой добавление элемента производится с одной стороны, а удаление с другой. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. first-in, first-out — FIFO). У очереди имеется голова (англ. head) и хвост (англ. tail). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится (удаляется) элемент, который находится в ее голове. В C++ очередь является адаптером контейнера (deque). В python создается на основе класса collections.deque.
Очередь:

  • C++ -> queue
  • python -> deque
Учебник
inf-w.ru

Куча

Двоичная куча или пирамида (англ. Binary heap) — это структура данных на основе двоичного дерева. Двоичные кучи используют, например, для того, чтобы извлекать минимальный (или максимальный) элемент из набора за время O(log n). Куча является частным случаем очереди с приоритетом (Вики). В C++ куча реализована в адаптере контейнера (vector) – priority_queue (очередь с приоритетом).
Для создания кучи и выполнения в ней различных операций с данными, в библиотеке algorithm разработаны специальные функции.
В python куча разработана в модуле heapq (heapq — Heap queue algorithm).

inf-w.ru

Множество

Множество (англ. – set) открывает важные структуры данных принципиально иного устройства в памяти (в основе красно-черные деревья). Множество — это структура данных, которая является реализацией математического объекта множество. В python класс set реализован в ядре языка и является одним из основных типов (наряду с list). В С++ set является одним из контейнеров (шаблонным классом). И в python и в C++, set является упорядоченной совокупностью уникальных элементов (ключей). При создании объекта set производится автоматическая сортировка. В C++ существует версия set‘а в которой допускаются дубликаты ключей (multiset). Поиск данных в множестве осуществляется максимально эффективно, по сравнению с другими контейнерами. Индексации нет. Доступ к элементам осуществляется только с помощью итераторов или диапазонного цикла for.
В python две реализации set’а – set и frozenset. set является изменяемым множеством, а frozenset – нет. Как следствие, set не может быть элементом другого множества или ключом словаря, а frozenset – может (док. Set Types — set, frozenset).
Множества:

  • C++ -> set
  • python -> set
inf-w.ru

Словарь

Словарь (ассоциативный массив) – структура данных которая содержит пары “ключ” – “значение”. Ключ – это неизменяемая часть пары, а значение – изменяемое. В остальном, словарь аналогичен set. В C++ реализован в виде контейнера map и версии, в которой могут быть дубликаты ключей (multimap). И для set и для map не используются модифицирующие алгоритмы библиотеки algorithm (C++). В python словарь реализован в классе dict, который является одним из встроенных типов (док. Mapping Types — dict).
Словарь:

  • C++ -> map
  • python -> dict
Учебник
inf-w.ru

Сортировка

Сортировкой (англ. sorting) называется процесс упорядочивания массива объектов по какому-либо признаку. Различают следующие разновидности сортировок:

  • по возрастанию (от меньшего к большему);
  • по убыванию (от большего к меньшему);
  • если в массиве имеются равные элементы, то сортировка в направлении от меньшего к большему называется сортировкой по не убыванию;
  • а от большего к меньшему – сортировкой по не возрастанию.
Сортировка в C++ реализована в библиотеке обобщенных алгоритмов algorithm в функции sort(). В качестве аргументов принимаются итераторы и функтор для сравнения (для изменения направления сортировки – qreater<int>()). В python, для сортировки List, используется стандартный метод sort(). Аргумент метода – reverse = "True", изменяющий направление сортировки. Помимо метода списка list.sort() существует встроенная функция sorted(). Она отличается от метода списка тем, что принимает в качестве аргумента коллекцию, а возвращает копию отсотированного массива, в то время как sort() сортирует взятый список на месте, в памяти. sorted() можно использовать для любой коллекции.

Учебник
inf-w.ru

Бинарный поиск

Бинарный (или двоичный) поиск (также известен как метод деления пополам или дихотомия) — классический алгоритм поиска элемента в отсортированном массиве, использующий дробление массива на половины (Вики).

Учебник
inf-w.ru

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.


Обсуждение закрыто.