Структуры данных — это форматы, используемые для организации, хранения и изменения данных. Структуры данных являются фундаментальным компонентом информатики и разработки программного обеспечения. Их можно реализовать на любом языке программирования, включая язык программирования C ++. Если вам предстоит собеседование по кодированию, ожидается, что вы будете знать, как использовать структуры данных для эффективной работы с данными.
Сегодня мы рассмотрим структуры данных C ++, которые вам нужно знать на собеседовании по кодированию.
Что такое структуры данных C ++?
Структуры данных — это форматы, используемые для организации, хранения и управления данными. Вы можете использовать структуры данных для эффективного доступа и изменения данных. Существуют различные типы структур данных. Тип, который вы используете, будет зависеть от используемого вами приложения. Каждая структура данных имеет свои преимущества и недостатки.
Структуры данных обычно подпадают под эти две категории:
- Линейные структуры данных: элементы расположены последовательно (например, массивы, связанные списки, стеки, очереди)
- Нелинейные структуры данных: элементы не располагаются последовательно, а хранятся на разных уровнях (например, деревья, графики).
9 структур данных C ++, которые нужно знать перед собеседованием
1. Массивы
Массив — это последовательный список значений. Вы можете использовать массивы для хранения и доступа к нескольким значениям одного и того же типа данных под одним идентификатором. Массивы упрощают выполнение операций со всем набором данных. Они также отлично подходят для получения данных.
Есть одномерные массивы и многомерные массивы. Значения, хранящиеся в массиве, называются элементами. Элементы хранятся в последовательных блоках памяти, называемых индексами. Размер массива определяется количеством содержащихся в нем элементов. На фото — одномерный массив размером шесть.
Общий синтаксис для инициализации одномерного массива:
ArrayName [ArrayIndex] = значение;
В этом коде мы инициализируем массив с именем, Exampleкоторый хранит 200 по индексу 0и 201 по индексу 1.
#include <iostream>using namespace std;int main() {int Example[2];Example[0] = 200;Example[1] = 201;}
2. Графики
Графики — это нелинейные структуры данных. Они состоят из конечного набора вершин (то есть узлов), соединенных набором ребер. Порядок графа относится к количеству вершин в графе. Размер графа соответствует количеству его ребер.
На этой иллюстрации представлены вершины и ребра. Граф также представляет собой циклический граф. Граф является циклическим, если хотя бы один узел имеет путь, который ведет обратно к самому себе.
Графики часто используются для моделирования реальных отношений в различных контекстах, от социальных сетей до нейронных сетей.
Есть три распространенных типа графиков:
- Ненаправленные графы: граф, в котором все ребра двунаправлены.
- Направленные графы: граф, в котором все ребра однонаправлены.
- Взвешенные графы: граф, в котором всем ребрам присвоено значение, называемое весом.
Скорее всего, на собеседовании вас попросят просмотреть график.
3. Связанные списки
Связанные списки — это линейные структуры данных, состоящие из набора узлов, представляющих последовательность. Каждый узел содержит значение и указатель на следующий узел в последовательности. Связанные списки отлично подходят для добавления и удаления узлов. Однако они не подходят для извлечения узлов, поскольку каждый узел знает только об узле рядом с ним.
Существуют как односвязные списки, так и двусвязные списки. Односвязный список — это самая основная форма связанного списка, где каждый узел знает только о следующем узле в последовательности. В двусвязном списке каждый узел указывает на узел, предшествующий и следующий за ним в последовательности. Направление этих ссылок часто бывает «вперед» и «назад», «следующее» и «предыдущее».
Убедитесь, что вы знаете, как перевернуть связанный список, прежде чем идти на собеседование по C ++.
4. Хеш-таблицы
В хэш-таблицах хранятся пары ключей и данных. Обычно они реализуются с использованием массивов, где каждый элемент имеет собственное уникальное значение индекса для быстрого доступа. Хотя вы можете назначить ключ (целочисленное значение) в качестве индекса для данных, в случае больших ключей это усложняется. Вместо этого для создания индексов элементов используется метод хеширования.
На этом рисунке представлены пары ключей и данных, хранящиеся в хэш-таблице.
В методе хеширования используется хеш-функция для преобразования больших ключей в более мелкие, которые затем могут быть сохранены в хеш-таблице. Хорошая хеш-функция должна соответствовать следующим условиям:
- Легко вычислить
- Равномерно распределяет данные (без кластеризации)
- Минимизирует столкновение
Производительность хеш-таблицы зависит от размера хеш-таблицы, используемой хеш-функции и метода обработки конфликтов.
Коллизии — это то, чего мы стараемся избегать при хешировании. Коллизия относится к случаям, когда два разных ключа, переданные хеш-функции, возвращают один и тот же индекс. Вероятность столкновения увеличивается, когда мы имеем дело с большими клавишами. Методы обработки коллизий помогают обойти коллизии и включают следующие общие стратегии: линейное зондирование, объединение в цепочку и изменение размера массива.
Хеш-таблицы — отличные структуры данных для алгоритмов, приоритезирующих поисковые операции. Операции вставки и поиска в хеш-таблицах выполняются довольно быстро. Хеш-таблицы — популярная тема собеседований по программированию на C ++.
5. Стеки и очереди
Стеки и очереди — это отдельные, но похожие линейные структуры данных. Они оба являются контейнерами объектов, основанными на массивах. Они гибкие по размеру.
Их отличительной особенностью является порядок, в котором над ними могут выполняться операции:
- Операции стека следуют порядку следования поступил — первым ушел (LIFO) или первым пришел — последний ушел (FILO).
- Операции с очередями следуют порядку FIFO (First-In-First-Out).
В случае стека мы удаляем только последний добавленный элемент. Популярный пример — стопка подносов для обеда в кафетерии. С очередями мы удаляем только последний добавленный элемент. Популярным примером является очередь в общественных местах, где первым обслуживается человек, ожидающий дольше всех (конечно, это зависит от того, соблюдает ли культура или местность правило FIFO для постановки в очередь)!
Стеки и очереди имеют различные применения. Они часто используются с алгоритмом рекурсивного поиска с возвратом. Стеки — это механизм, поддерживающий кнопку «отменить» или «назад» во многих приложениях и браузерах. Компиляторы часто используют стеки для анализа синтаксиса выражений перед их преобразованием в низкоуровневый код. Очереди полезны в случаях, когда необходимо поддерживать порядок данных. Таким образом, они используются для кэширования, а также для обработки системных сбоев в реальном времени.
6. Strings
Строка обычно является типом данных, но часто может быть реализована как структура данных массива, в которой хранится последовательность символов. В C ++ есть строковый класс, который упрощает управление строками символов. А строка C ++ изменчива и может быть изменен, в отличие от неизменного строки Java.
Вы можете объявить строку, объявив одномерный массив. Разница между символьным массивом и строкой заключается в том, что строка заканчивается нулевым символом \0.
\0При объявлении строки необязательно помещать нулевой символ. Используя синтаксис в следующем коде, двойные кавычки «говорят вашему компилятору автоматически добавить \0.
char greeting[] = "hello"
Это соответствует следующей иллюстрации.
Строки часто используются для хранения удобочитаемых данных, например предложений. Они даже используются для представления последовательностей ДНК.
Trees (#7, 8, и 9)
Далее мы рассмотрим двоичные деревья, деревья двоичного поиска и попытки. Прежде чем мы это сделаем, давайте узнаем о категории, к которой все они принадлежат: деревья.
Деревья — это абстрактные типы данных, моделирующие иерархическую древовидную структуру. Деревья состоят из узлов (то есть вершин) и ребер, которые их соединяют. Связанные узлы называются «родительскими» и «дочерними» узлами. В отличие от графов, цикл не может существовать в дереве. В дереве существует не более одного пути, соединяющего любые два узла.
Некоторые основные термины для деревьев:
- Корневой узел: узел без родительских узлов.
- Родительские узлы: узел, подключенный к одному или нескольким дочерним узлам.
- Дочерний узел: узел, который подключен к верхнему узлу (родительскому узлу).
- Родственный узел: узлы, которые совместно используют один и тот же родительский узел.
- Листовой узел: узел без дочерних узлов.
- Уровень: каждый шаг дерева, начиная с уровня 0в корневом узле и постепенно увеличиваясь сверху вниз.
- Поддерево: часть дерева, которая сама по себе образует полное дерево.
Это изображение иллюстрирует отношения в виде дерева.
7. Бинарные деревья
Двоичные деревья — это один из типов древовидной структуры данных. У вас есть двоичное дерево всякий раз, когда у вас есть дерево, в котором каждый узел имеет не более двух дочерних элементов. Дочерние элементы каждого родительского узла называются левым и правым дочерними элементами.
Бинарные деревья состоят из следующих типов:
- Полное двоичное дерево: двоичное дерево, в котором заполнены все уровни дерева, за исключением последнего уровня, который может быть заполнен слева направо (см. Иллюстрацию)
- Полное двоичное дерево: двоичное дерево, для которого каждый узел имеет ноль или два дочерних элемента.
- Совершенное двоичное дерево: двоичное дерево, которое является как полным, так и завершенным (т.е. все внутренние узлы имеют двух дочерних элементов, и все листья находятся на одном уровне)
8. Деревья двоичного поиска
Деревья двоичного поиска позволяют алгоритмам двоичного поиска быстро искать, добавлять и удалять элементы данных. Двоичный поиск — это алгоритм поиска, который находит позицию целевого значения в отсортированном массиве. Алгоритм делает это, сравнивая целевое значение со средним элементом массива.
Бинарное дерево является бинарным деревом поиска, если оно удовлетворяет следующим условиям:
- Значения всех узлов в левом поддереве равны или меньше значения текущего узла
- Значения всех узлов в правом поддереве больше или равны значению текущего узла
- Вышеуказанные условия применяются как к левому, так и к правому поддеревьям.
На этой иллюстрации представлено двоичное дерево поиска.
Деревья двоичного поиска часто используются в поисковых приложениях, где данные постоянно поступают и уходят. К двоичным деревьям поиска можно применять такие операции, как итеративный и рекурсивный поиск и обход. Деревья двоичного поиска, вероятно, будут задействованы в решениях вопросов собеседования по программированию на C ++.
9. Tries
Дерево — это еще один тип дерева поиска. Попытки — это эффективные структуры данных для решения проблем программирования со строками. Их также называют префиксным деревом, потому что они основаны на префиксе строки.
Термин «trie» происходит от слова «извлекать», потому что попытки извлечения данных отлично подходят.
Попытки состоят из комбинации узлов, каждый из которых представляет собой уникальную букву алфавита. Дерево состоит из одного пустого корневого узла, который связан с другими узлами. В дереве не может быть повторяющихся узлов.
Каждый узел в дереве содержит:
- Значение (может быть null)
- Массив ссылок на дочерние узлы (также может быть null)
Были введены попытки помочь эффективно представить наборы слов. Они часто используются для функций автозаполнения и поиска, а также для IP-маршрутизации.
