Какие бывают структуры данных в программировании

9 структур данных, которые вам понадобятся

Еще в девяностые профессор Корейского университета передовых технологий Сонгчун Мун предложил Биллу Гейтсу назвать свой стартап Microdata, а не Microsoft. Мун указал на то, что данные и их структура — будущее программирования.

Структуры данных — способы хранения и извлечения информации. Правильный выбор структуры поможет эффективнее выполнить задачу. СД важны в разработке ПО, от них зависит, как будут работать алгоритмы.

Рассказываем о структурах данных, которые используются чаще всего.

#1. Массив (Array)

Массив — простая базовая структура. Стеки, очереди и списки — производные от массивов. Единице данных в массиве присваивается число или индекс, который указывает на ее расположение. Чтобы найти ячейку с информацией в массиве, нужно добавить к базовому элементу ее индекс. Базовый элемент, как правило, обозначается именем самого массива.

Представьте себе записную книжку со страницами, пронумерованными от 1 до 10. Каждая из них может содержать информацию или быть пустой. Блокнот — массив страниц, страницы — элементы массива «блокнот». Программно вы извлекаете информацию со страницы, обращаясь к ее индексу, то есть «блокнот+4» будет ссылаться на содержимое четвертой страницы.

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

#2. Матрица (Matrix)

Матрица — двумерный массив, выглядящий как список столбцов и строк, на пересечении которых находятся элементы данных. Это прямоугольный массив, в котором количество строк и столбцов задает его размер. В математике их используют для компактной записи линейных алгебраических или дифференциальных уравнений.

Матрицы используют для описания вероятностей. Например, для ранжирования страниц в поиске Google при помощи алгоритма PageRank. В компьютерной графике — для работы с 3D-моделями и проецирования их на двумерный экран.

#3. Связный список (Linked list)

Списки схожи с массивами, но отличаются более гибкой структурой. Они выглядят как цепочки нод или узлов, где каждая нода содержит ссылку на следующую. Доступ к элементам в связном списке осуществляется последовательно, в отличие от массивов с произвольным доступом. Списки бывают односвязными и двусвязными.

Начальный элемент этой структуры называется головой, а все последующие узлы цепочки — хвостом. Хвост состоит из элементов двух типов: с информацией (info) и с указанием на следующий узел (next). Конец цепочки обозначается как null.

#4. Стек (Stack)

Это вертикальный столбец с блоками, доступ к которым можно получить только с одного конца: сверху или снизу. Как в стопке книг — чтобы добраться до нижней, нужно сначала убрать все книги сверху.

Новые элементы стека заменяют старые. Принцип работы такой структуры — LIFO (last in — first out, «последним пришел — первым ушел»). Поэтому стек еще называют магазином — по аналогии с огнестрельным оружием: выстрелит патрон, который был заряжен последним.

Эта структура данных реализована в функции «отменить» (undo). Программа сохраняет статус работы так, что последнее действие становится первым в очереди на отмену. В стеке возможны всего три операции: добавление элемента (push), удаление (pop), чтение (peek).

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

Существует похожая СД — дек (deque — double ended queue, «двусторонняя очередь»). Это стек с двусторонним доступом.

#5. Очередь (Queue)

Этот тип СД напоминает стеки, но принцип работы реализован как FIFO (first in — first out, «первым пришел — первым ушел»). Как в супермаркете: первым покупки унесет домой тот, кто раньше всех займет очередь.

Очереди используются, когда ресурс нужно распределить между несколькими потребителями (работа ЦП, пропускная способность роутера). Или когда данные передаются асинхронно, то есть скорости приема и отдачи — разные.

В этой СД можно выполнить две операции: добавление элемента в конец очереди (enqueue) и удаление первого элемента (dequeue). Очереди бывают в виде связных списков или массивов, по аналогии со стеками.

#6. Дерево (Tree)

Деревья — структура, в которой данные связаны между собой узлами, и при этом расположены иерархически. Различают двоичное дерево поиска, расширенное, черно-красное и еще десяток видов.

Как и у настоящего дерева, тут есть корни, ветви и листья. Самый верхний узел в этой СД, не имеющий предков, называется корневым. Остальные узлы — потомками или дочерними элементами. Дочерние узлы с одним и тем же родителем — это узлы-братья. А листья — это узлы, не имеющие потомков.

Деревья используют, например, в разработке видеоигр. Они позволяют разделить пространство и быстро находить объекты. Так, дерево с четырьмя дочерними узлами (quadtree) — квадрант — используется для создания карты и ориентации по четырем сторонам света в игре.

Но деревья сложно хранить и у них невысокая скорость работы.

курсы по теме:

Data Science with Python

Основные структуры данных. Матчасть. Азы

Все чаще замечаю, что современным самоучкам очень не хватает матчасти. Все знают языки, но мало основы, такие как типы данных или алгоритмы. Немного про типы данных.

Еще в далеком 1976 швейцарский ученый Никлаус Вирт написал книгу Алгоритмы + структуры данных = программы.

40+ лет спустя это уравнение все еще верно. И если вы самоучка и надолго в программировании пробегитесь по статье, можно по диагонали. Можно код кофе.

В статье так же будут вопросы, которое вы можете услышать на интервью.

Что такое структура данных?

Структура данных — это контейнер, который хранит данные в определенном макете. Этот «макет» позволяет структуре данных быть эффективной в некоторых операциях и неэффективной в других.

Какие бывают?

Линейные, элементы образуют последовательность или линейный список, обход узлов линеен. Примеры: Массивы. Связанный список, стеки и очереди.

Нелинейные, если обход узлов нелинейный, а данные не последовательны. Пример: граф и деревья.

Основные структуры данных.

Массивы
Стеки
Очереди
Связанные списки
Графы
Деревья
Префиксные деревья
Хэш таблицы

Массивы

Массив — это самая простая и широко используемая структура данных. Другие структуры данных, такие как стеки и очереди, являются производными от массивов.

Изображение простого массива размера 4, содержащего элементы (1, 2, 3 и 4).

Каждому элементу данных присваивается положительное числовое значение (индекс), который соответствует позиции элемента в массиве. Большинство языков определяют начальный индекс массива как 0.

Бывают

Одномерные, как показано выше.
Многомерные, массивы внутри массивов.

Основные операции

Insert-вставляет элемент по заданному индексу
Get-возвращает элемент по заданному индексу
Delete-удаление элемента по заданному индексу
Size-получить общее количество элементов в массиве

Вопросы

Найти второй минимальный элемент массива
Первые неповторяющиеся целые числа в массиве
Объединить два отсортированных массива
Изменение порядка положительных и отрицательных значений в массиве

Стеки

Стек — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

Это не массивы. Это очередь. Придумал Алан Тюринг.

Примером стека может быть куча книг, расположенных в вертикальном порядке. Для того, чтобы получить книгу, которая где-то посередине, вам нужно будет удалить все книги, размещенные на ней. Так работает метод LIFO (Last In First Out). Функция «Отменить» в приложениях работает по LIFO.

Изображение стека, в три элемента (1, 2 и 3), где 3 находится наверху и будет удален первым.

Основные операции

Push-вставляет элемент сверху
Pop-возвращает верхний элемент после удаления из стека
isEmpty-возвращает true, если стек пуст
Top-возвращает верхний элемент без удаления из стека

Вопросы

Реализовать очередь с помощью стека
Сортировка значений в стеке
Реализация двух стеков в массиве
Реверс строки с помощью стека

Очереди

Подобно стекам, очередь — хранит элемент последовательным образом. Существенное отличие от стека – использование FIFO (First in First Out) вместо LIFO.

Пример очереди – очередь людей. Последний занял последним и будешь, а первый первым ее и покинет.

Изображение очереди, в четыре элемента (1, 2, 3 и 4), где 1 находится наверху и будет удален первым

Основные операции

Enqueue—) — вставляет элемент в конец очереди
Dequeue () — удаляет элемент из начала очереди
isEmpty () — возвращает значение true, если очередь пуста
Top () — возвращает первый элемент очереди

Вопросы

Реализовать cтек с помощью очереди
Реверс первых N элементов очереди
Генерация двоичных чисел от 1 до N с помощью очереди

Связанный список

Связанный список – массив где каждый элемент является отдельным объектом и состоит из двух элементов – данных и ссылки на следующий узел.

Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Бывают

Однонаправленный, каждый узел хранит адрес или ссылку на следующий узел в списке и последний узел имеет следующий адрес или ссылку как NULL.

Двунаправленный, две ссылки, связанные с каждым узлом, одним из опорных пунктов на следующий узел и один к предыдущему узлу.

Круговой, все узлы соединяются, образуя круг. В конце нет NULL. Циклический связанный список может быть одно-или двукратным циклическим связанным списком.

Самое частое, линейный однонаправленный список. Пример – файловая система.

Основные операции

InsertAtEnd — Вставка заданного элемента в конец списка
InsertAtHead — Вставка элемента в начало списка
Delete — удаляет заданный элемент из списка
DeleteAtHead — удаляет первый элемент списка
Search — возвращает заданный элемент из списка
isEmpty — возвращает True, если связанный список пуст

Вопросы

Реверс связанного списка
Определение цикла в связанном списке
Возврат N элемента из конца в связанном списке
Удаление дубликатов из связанного списка

Графы

Граф-это набор узлов (вершин), которые соединены друг с другом в виде сети ребрами (дугами).

Бывают

Ориентированный, ребра являются направленными, т.е. существует только одно доступное направление между двумя связными вершинами.
Неориентированные, к каждому из ребер можно осуществлять переход в обоих направлениях.
Смешанные

Встречаются в таких формах как

Матрица смежности
Список смежности

Общие алгоритмы обхода графа

Поиск в ширину – обход по уровням
Поиск в глубину – обход по вершинам

Вопросы

Реализовать поиск по ширине и глубине
Проверить является ли граф деревом или нет
Посчитать количество ребер в графе
Найти кратчайший путь между двумя вершинами

Деревья

Дерево-это иерархическая структура данных, состоящая из узлов (вершин) и ребер (дуг). Деревья по сути связанные графы без циклов.

Древовидные структуры везде и всюду. Дерево скилов в играх знают все.

N дерево
Сбалансированное дерево
Бинарное дерево
Дерево Бинарного Поиска
AVL дерево
2-3-4 деревья

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

Три способа обхода дерева

В прямом порядке (сверху вниз) — префиксная форма.
В симметричном порядке (слева направо) — инфиксная форма.
В обратном порядке (снизу вверх) — постфиксная форма.

Вопросы

Найти высоту бинарного дерева
Найти N наименьший элемент в двоичном дереве поиска
Найти узлы на расстоянии N от корня
Найти предков N узла в двоичном дереве

Trie ( префиксное деревое )

Разновидность дерева для строк, быстрый поиск. Словари. Т9.

Вот как такое дерево хранит слова «top», «thus» и «their».

Слова хранятся сверху вниз, зеленые цветные узлы «p», «s» и «r» указывают на конец «top», «thus « и «their» соответственно.

Вопросы

Подсчитать общее количество слов
Вывести все слова
Сортировка элементов массива с префиксного дерева
Создание словаря T9

Хэш таблицы

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

Объект хранится в виде пары «ключ-значение», а коллекция таких элементов называется «словарем». Каждый объект можно найти с помощью этого ключа.

По сути это массив, в котором ключ представлен в виде хеш-функции.

Эффективность хеширования зависит от

Функции хеширования
Размера хэш-таблицы
Метода борьбы с коллизиями

Пример сопоставления хеша в массиве. Индекс этого массива вычисляется через хэш-функцию.

Вопросы

Найти симметричные пары в массиве
Найти, если массив является подмножеством другого массива
Описать открытое хеширование

Список ресурсов

medium.freecodecamp.org/the-top-data-structures-you-should-know-for-your-next-coding-interview-36af0831f5e3
www.geeksforgeeks.org/commonly-asked-data-structure-interview-questions-set-1
prog-cpp.ru/data-list
habr.com/post/267855
habr.com/post/273687
habr.com/post/150732
ruhighload.com/%D0%A7%D1%82%D0%BE+%D1%82%D0%B0%D0%BA%D0%BE%D0%B5+%D1%85%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B+%D0%B8+%D0%BA%D0%B0%D0%BA+%D0%BE%D0%BD%D0%B8+%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%B0%D1%8E%D1%82
ru.wikipedia.org

Вместо заключения

Матчасть так же интересна, как и сами языки. Возможно, кто-то увидит знакомые ему базовые структуры и заинтересуется.

Спасибо, что прочли. Надеюсь не зря потратили время =)

PS: Прошу извинить, как оказалось, перевод статьи уже был тут и очень недавно, я проглядел.
Если интересно, вот она, спасибо Hokum, буду внимательнее.

Программирование
Алгоритмы

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

В этой статье мы представим основные термины и классификацию простейших структур и типов данных, расскажем про их особенности и нюансы применения. Также приведем примеры статических и динамических структур.

Классификации

Вряд ли кто-нибудь решится спорить с тем, что в памяти компьютера данные (data) представлены в виде последовательности битов. Эти последовательности структурированы недостаточно, что затрудняет их применение на практике. Именно поэтому широко используются специальные структуры данных.

Структурой данных можно назвать некое количество элементов, которые имеют между собой внутренние связи. Существуют как простые, так и интегрированные структуры данных. Простые организуются из битов, вот их примеры:

Интегрированные организуются с помощью простых и других интегрированных структур. Также структуры бывают физические и логические.

Немаловажно знать и такой термин, как изменчивость структуры — речь идет об изменении количества элементов и связей между ними. Учитывая понятие изменчивости, можно разделить структуры на статические и динамические. Статические структуры данных мы все хорошо знаем — из основных можно вспомнить массив, множество, вектор, запись, таблицу. Программистам хорошо известны и динамические структуры данных (три наиболее популярные — очередь, стек, списки).

Как уже было сказано выше, структура состоит из элементов данных. Эти элементы бывают как упорядоченными, так и неупорядоченными. С учетом этого признака, структуры данных можно разделить на следующие группы:

— нелинейные (к примеру, многосвязные списки, графы, деревья с их корневыми узлами, потомками и т. д.);

— линейные с последовательным распределением (это вектор, массив, строка, очередь, стек);

— линейные, но уже с произвольным связным распределением (это односвязные и двусвязные списки).

Простейшие структуры и основные типы

Такие конструкции называют примитивами либо базовыми структурами данных. К примеру, в языках программирования они представлены простыми типами данных. В зависимости от языка набор типов может отличаться, но эти различия не очень существенны, поэтому можно говорить о наличии неких общих принципов.

Первый тип — целочисленный (целый тип), который применяется для обозначения целых чисел (int, integer). Из школьного курса математики мы знаем, что целые числа бывают отрицательными либо беззнаковыми. Во внутреннем машинном представлении целое число может занимать 1, 2 либо 4 байта.

Второй тип— вещественный. Он уже имеют вид числа с плавающей точкой. Такое число представляется посредством двух целых чисел – матиссы и порядка, плюс знака.

Третье — десятичный тип (decimal). Его поддерживает не каждый язык программирования. К примеру, такой тип есть в C# — он имеет разрядность 128 бит и может представлять числовые значения в пределах от 1Е-28 до 7,9Е+28. Применяется в финансовых расчетах.

Если предполагается работа с отдельными двоичными числовыми разрядами, существует битовый тип. Здесь данные — это набор битов, которые объединены в байты либо слова. При выполнении операций предполагается обращение к каждому биту отдельно.

Идем дальше. Переменная, имеющая логический тип, способна принимать одно из 2-х значений: либо истину, либо ложь. Для хранения такой переменной требуется 1 байт памяти. False кодируется нулевым значением байта, True — любым значением, отличным от нуля.

Символьный тип дает возможность представлять данные в виде последовательности символов какого-нибудь определенного заранее множества. Каждый символ хранится в памяти в качестве последовательности битов. Соответствие символов и последовательностей называют кодировкой. Разные кодировки представляют символы в форме битовых последовательностей разной длины.

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

Примеры статических структур данных

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

В двумерном массиве каждый элемент массива сам будет являться одномерным массивом. В результате у элемента существуют не один, а 2 индекса.

Записи (ассоциативные массивы или хэш-массивы) представляют собой массивы, индексируемые строками, а не натуральными числами. Индекс компонента здесь называют ключом.

Примеры динамических структур данных

В этом случае объем памяти не фиксируется заранее, а определяется «на ходу» в процессе исполнения программы. Чтобы работать с динамическими типами, во многих языках программирования предусмотрены указатели, причем сами по себе они имеют статический тип.

Яркий пример — стек. Это, по сути, вектор, где каждый следующий компонент адресуется указателем на текущий компонент. Ниже рассмотрено последовательное добавление компонентов в стек, а также последовательное извлечение. Стек организован по принципу LIFO (last in — first out).

Нельзя не вспомнить и про очередь — динамическую структуру, отличающуюся от стека наличием 2-х указателей. Эти указатели показывают на 1-й и последний компоненты очереди. Очередь организована по принципу FIFO (first in, first out).

Если хотите узнать про структуры данных подробнее, обратите внимание на следующую статью.

Топ-8 структур данных для программиста

В далеком 1976 году швейцарским ученым была написана книга «Алгоритмы + Структуры данных = Программы». Прошло уже более сорока лет, но это утверждение до сих пор актуально. Вы должны знать структуры данных, если учите языки программирования и желаете стать разработчиком. И не только знать, но и уметь их применять. Причем не столь важно, закончили ли вы институт либо просто освоили курсы программирования, — на собеседовании при устройстве на работу у вас в 90 % случаев спросят про структуры данных.

Этот материал — адаптированный перевод статьи «The top data structures you should know for your next coding interview ». В этом переводе будут вкратце рассмотрены основные структуры данных, которые могут понадобиться при программировании, плюс будут перечислены наиболее популярные вопросы, которые часто задают на собеседованиях.

Изучаем структуры данных: что это?

Если говорить простым языком, то структура данных представляет собой контейнер, в котором информация скомпонована специальным образом. Чего удается достичь благодаря такому строению? Для сравнения, скажем, что при выполнении одних операций определенная структура данных будет весьма эффективна, в то время как при выполнении других — не очень. Задача разработчика вне зависимости от языка программирования (language of programming) как раз в том и состоит, чтобы уметь выбирать наиболее подходящую структуру и знать, как сравнить их между собой с учетом поставленной задачи. Но это невозможно без ясного и единого представления о существующих способах организации информации. Именно это единое представление вы и получите в процессе изучения материалов этой статьи. И займет это совсем немного времени.

Изучаем структуры данных: зачем вообще они нужны?

Структура позволяет хранить информацию в упорядоченном виде, а информация — это основополагающий термин информатики, что понятно даже, исходя из словообразования. И не так уж важно, какую конкретно задачу решает программист: таки или иначе он все равно будет иметь дело с обработкой данных, причем хранить их надо будет то в одном формате, то в другом.