Типы структур данных в программировании

Зачем нужны? На сегодняшний день в программировании существуют различные типы структур данных, и уважающий себя специалист должен иметь представление о каждом из них. Это повысит качество работы и значительно сэкономит время.

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

Понятие структуры данных

Все люди используют различные данные в процессе своей жизнедеятельности. Они применяются в самых разных профессиях и областях.

В рамках программирования структуры данных представляют собой специальные контейнеры. Они хранят информацию в определённом формате, который придает структуре те или иные свойства. Именно эти качества отличают одну структуру данных от другой. Кроме того, они определяют ее пригодность для тех или иных сценариев применения.

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

У каждой структуры свой алгоритм, поэтому программисту необходимо либо подобрать уже созданный, либо разработать свой.

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

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

В структуру может входить как множество данных, так и массив из одного единственного элемента.

Классификация структур данных

Различают физические и логические структуры. Физические отражают способ представления данных в памяти ЭВМ. Из-за этого их иногда называют внутренними.

Типы структур данных по составу:

• Простые. Они не делятся на составные части, которые больше, чем биты. Для простого типа четко определен размер и способ размещения структуры в памяти устройства.
• Сложные (интегрированные). Они включают в себя другие структуры, которые, в свою очередь, могут быть простыми или сложными.

Узнай, какие ИТ - профессии
входят в ТОП-30 с доходом
от 210 000 ₽/мес

Павел Симонов

Исполнительный директор Geekbrains

Команда GeekBrains совместно с международными специалистами по развитию карьеры подготовили материалы, которые помогут вам начать путь к профессии мечты.

Подборка содержит только самые востребованные и высокооплачиваемые специальности и направления в IT-сфере. 86% наших учеников с помощью данных материалов определились с карьерной целью на ближайшее будущее!

Скачивайте и используйте уже сегодня:

Павел Симонов

Исполнительный директор Geekbrains

Топ-30 самых востребованных и высокооплачиваемых профессий 2023

Поможет разобраться в актуальной ситуации на рынке труда

Подборка 50+ бесплатных нейросетей для упрощения работы и увеличения заработка

Только проверенные нейросети с доступом из России и свободным использованием

ТОП-100 площадок для поиска работы от GeekBrains

Список проверенных ресурсов реальных вакансий с доходом от 210 000 ₽

Получить подборку бесплатно

pdf 3,7mb

doc 1,7mb

Уже скачали 31976

Типы структур данных по наличию связи:

• несвязные структуры: массивы, векторы, строки, стеки (Last In, First Out), очереди (First In, First Out);
• связные структуры (например, связные списки).

Нельзя не упомянуть про так называемую изменчивость. Речь идёт об изменении числа элементов или связей между ними. В зависимости от уровня изменчивости выделяют:

• статические;
• полустатические;
• динамические.

В зависимости от признака упорядоченности элементов различают два типа структур организации данных:

• Нелинейные: деревья, графы, многосвязные списки.
• Линейные. В зависимости от типа распределения компонентов в памяти устройства они могут иметь последовательное распределение (строки, векторы, массивы, стеки, очереди) и произвольное связное распределение (односвязные и двусвязные списки).

При указании типа данных определяются следующие параметры:

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

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

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

Массив

Массив – это очень распространенная структура, отличающаяся своей простотой. Каждому элементу в массиве соответствует положительное целое число — индекс. Оно указывает на расположение элемента. Практически во всех языках программирования индексы начинаются с нуля (данный подход называют нумерацией на основе нуля).

Читайте также!

Программирование роботов: методы и инструменты

Подробнее

Выделяют две разновидности массивов:

• Одномерные — простейшие линейные структуры.
• Многомерные — вложенные структуры, которые состоят из других массивов.

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

Размер обычного массива указывается заранее. Благодаря этому человек сразу понимает, какое количество индексов в него входит. Динамический массив отличается тем, что его размер не предопределён, он может меняться.

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

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

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

Описание данного типа структуры данных будет следующим. Связанный список представляет собой набор элементов (узлов) в линейной последовательной структуре. Узел — это простой объект, имеющий 2 свойства: переменные для хранения данных и адреса памяти следующего узла в списке. Узел хранит информацию о типе данных, которые он содержит, а также о своем соседе. Благодаря этому можно создавать связанные списки, где все узлы будут связаны между собой.

Различают несколько разновидностей списков:

• Односвязный. Обходить элементы можно лишь в прямом направлении.
• Двусвязный. Кроме прямого, допускается ещё и обратное направление. Узлы включают дополнительный указатель(prev), который указывает на предыдущий узел.
• Круговые связанные. Так называют связанные списки, в которых предыдущий (prev) указатель «головы» указывает на «хвост», а следующий указатель «хвоста» указывает на «голову».

Стек

Стек представляет собой линейную структуру данных, которая формируется на базе массивов или связанных списков. Стек работает по принципу LIFO (от Last-In-First-Out — «первым на вход — последним на выход»). Проще говоря, первым элементом, который покинет стек, станет тот, который последний в него войдёт. Название «stack» переводится как «стопка». Дело в том, что данная структура может быть визуализирована как стопка книг, лежащих на столе.

Очередь

Очередь относится к линейному типу структуры данных так же, как и стек. Формируется она на основе массивов или связанных списков. Работает по принципу FIFO (First-In-First-Out — «первым на вход — первым на выход»). Иначе говоря, первым покинувшим очередь элементом будет тот, который первый в неё вошёл.

Множество

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

Дарим скидку от 60%
на обучение «Инженер-программист» до 01 декабря

Уже через 9 месяцев сможете устроиться на работу с доходом от 150 000 рублей

Забронировать скидку

Карта (Map)

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

Рассмотрим яркий пример такой структуры данных — hash-map (хэш-таблица). В ней размещаются ключи и значения, а для их реализации добавляются индексы. С помощью хэш-функции можно вычислить индекс, зная ключ. Это позволяет отыскивать необходимые данные. Если в хэш-таблицу вставляют ту или иную информацию, то добавляют ключ и данные. После этого функция хэширует ключ, переводит его в число и записывает данные в ячейку, которая соответствует этому числу. Если требуется запросить данные, то следует ещё раз ввести ключ, чтобы хэш-функция выполнила поиск.

Только до 25.11

Скачай подборку материалов, чтобы гарантированно найти работу в IT за 14 дней

Список документов:

ТОП-100 площадок для поиска работы от GeekBrains

20 профессий 2023 года, с доходом от 150 000 рублей

Чек-лист «Как успешно пройти собеседование»

Чтобы получить файл, укажите e-mail:

Введите e-mail, чтобы получить доступ к документам

Подтвердите, что вы не робот,
указав номер телефона:

Введите телефон, чтобы получить доступ к документам

Скачать подборку бесплатно pdf 2,5mb

Уже скачали 52300

Я подтверждаю согласие на обработку персональных данных.

Двоичное дерево поиска

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

Самыми популярными являются деревья поиска, у которых:

• каждый узел имеет не более 2-х дочерних;
• если новое значение меньше, то оно становится левым дочерним (или дочерним левого дочернего);
• если значение больше, то оно становится правым дочерним (либо дочерним правого дочернего).

Префиксное дерево (бор, нагруженное дерево)

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

Граф (Graph)

Граф представляет собой структуру данных, состоящую из нескольких узлов (вершин), связанных между собой. Пару (x,y) называют ребром. Таким образом, вершина x соединена с вершиной y. Ребро может определять вес/стоимость (стоимость прохождения по пути между двумя вершинами).

Читайте также!

Визуальное программирование: задачи, цели, программы

Подробнее

Графы представляют собой более общие случаи деревьев, которые, в свою очередь, нередко называют ациклическими графами. Можно выделить две особенности, которые отличают одну структуру от другой:

• В графе могут быть циклы (когда «ребенок» является «родителем» для того же объекта).
• Ребра могут нести смысловую нагрузку (необходимо сохранять их значения).

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

Популярные статьи

Высокооплачиваемые профессии сегодня и в ближайшем будущем

Дополнительный заработок в Интернете: варианты для новичков и специалистов

Востребованные удаленные профессии: зарабатывайте, не выходя из дома

Разработчик игр: чем занимается, сколько зарабатывает и где учится

Как выбрать профессию по душе: детальное руководство + ценные советы

Стоит отметить, что графы нередко представляют как матрицы смежности. При этом каждая строка или столбец – узел. Если в ячейке появилось значение «1», то между узлами есть связь, а если «0», то связь отсутствует. Учтите, что если у связей (рёбер графа) есть вес, то его можно разместить в ячейке.

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

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

Автор статьи:

Редакция сайта GeekBrains Шеф-редактор раздела Программирование