Получите бесплатно 3 курса для старта работы в IT
Получить курсы бесплатно
ГлавнаяБлогТипы структур данных в программировании
Типы структур данных в программировании
4 259
Время чтения: 16 минут

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

4 259
Время чтения: 16 минут
Сохранить статью:
Сохранить статью:

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

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

В статье рассказывается:

  1. Понятие структуры данных
  2. Классификация структур данных
  3. Основные типы структур данных
  4. Массив
  5. Динамический массив
  6. Связанный список
  7. Пройди тест и узнай, какая сфера тебе подходит:
    айти, дизайн или маркетинг.
    Бесплатно от Geekbrains

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

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

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

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

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

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

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

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

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

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

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

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

  • Простые. Они не делятся на составные части, которые больше, чем биты. Для простого типа четко определен размер и способ размещения структуры в памяти устройства.
  • Сложные (интегрированные). Они включают в себя другие структуры, которые, в свою очередь, могут быть простыми или сложными.
Узнай, какие ИТ - профессии
входят в ТОП-30 с доходом
от 210 000 ₽/мес
Павел Симонов - исполнительный директор Geekbrains
Павел Симонов
Исполнительный директор Geekbrains
Команда GeekBrains совместно с международными специалистами по развитию карьеры подготовили материалы, которые помогут вам начать путь к профессии мечты.
Подборка содержит только самые востребованные и высокооплачиваемые специальности и направления в IT-сфере. 86% наших учеников с помощью данных материалов определились с карьерной целью на ближайшее будущее!

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

Павел Симонов - исполнительный директор Geekbrains
Павел Симонов
Исполнительный директор Geekbrains
pdf иконка

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

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

doc иконка

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

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

pdf иконка

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

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

pdf 3,7mb
doc 1,7mb
Уже скачали 26506 pdf иконка

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

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

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

  • статические;
  • полустатические;
  • динамические.
Классификация структур данных
Классификация структур данных

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

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

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

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

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

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

Массив

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

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

  • Одномерные — простейшие линейные структуры.
  • Многомерные — вложенные структуры, которые состоят из других массивов.
Как используются? За счёт своей простоты эти составные элементы более сложных структур (стеков, очередей и т.п.) применяются для хранения несложных связанных данных. Они также нужны для различных алгоритмов сортировки (сортировка вставок, сортировка пузырьком и т.д.).

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

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

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

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

Как используются? Динамические массивы играют роль блоков для структур данных. Их применяют в целях хранения неопределённого количества элементов.

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

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

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

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

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

Стек

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

Стек
Стек

Очередь

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

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

Множество

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

Дарим скидку от 60%
на обучение «Инженер-программист» до 25 февраля
Уже через 9 месяцев сможете устроиться на работу с доходом от 150 000 рублей
Забронировать скидку

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

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

Карта (Map)

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

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

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

Только до 26.02
Скачай подборку материалов, чтобы гарантированно найти работу в IT за 14 дней
Список документов:
ТОП-100 площадок для поиска работы от GeekBrains
20 профессий 2023 года, с доходом от 150 000 рублей
Чек-лист «Как успешно пройти собеседование»
Чтобы получить файл, укажите e-mail:
Введите e-mail, чтобы получить доступ к документам
Подтвердите, что вы не робот,
указав номер телефона:
Введите телефон, чтобы получить доступ к документам
Уже скачали 52300

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

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

Откройте для себя захватывающий мир IT! Обучайтесь со скидкой до 61% и получайте современную профессию с гарантией трудоустройства. Первый месяц – бесплатно. Выбирайте программу прямо сейчас и станьте востребованным специалистом.

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

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

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

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

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

Граф (Graph)

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

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

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

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

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

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

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

Граф
Граф

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

Оцените статью
Рейтинг: 2.17
( голосов 6 )
Поделиться статьей
Добавить комментарий

Сортировать:
По дате публикации
По рейтингу
До конца акции осталось
0 дней 00:00:00
Дарим скидку 64% на обучение «Разработчик»
  • Получите новую профессию с гарантией трудоустройства
  • Начните учиться бесплатно, 3 месяца обучения в подарок
Забронировать скидку на обучение
Забрать подарок

Получите подробную стратегию для новичков на 2023 год, как с нуля выйти на доход 200 000 ₽ за 7 месяцев

Подарки от Geekbrains из закрытой базы:
Осталось 17 мест

Поздравляем!
Вы выиграли 4 курса по IT-профессиям.
Дождитесь звонка нашего менеджера для уточнения деталей

Иван Степанин
Иван Степанин печатает ...