Какие существуют структуры организации данных информатика кратко

Обновлено: 28.06.2024

Структуры данных являются важной частью разработки программного обеспечения и одной из наиболее распространенных тем для вопросов на собеседованиях с разработчиками.
Хорошая новость в том, что они в основном являются просто специализированными форматами для организации и хранения данных.
Из этой статьи вы узнаете о 10 наиболее распространенных структурах данных. Также сюда добавлены видеоролики (на английском языке) по каждой из структур, и код их реализации на JS. А чтобы вы немного попрактиковались, я добавил сюда задачи из бесплатной учебной программы freeCodeCamp.
Обратите внимание, что некоторые из этих структур данных включают временную сложность в нотации Big O. Это не относится ко всем из них, поскольку временная сложность иногда основана на реализации. Если вы хотите узнать больше о нотации Big O, посмотрите видео от Briana Marie .
Несмотря на то, что для каждой структуры я привожу код реализации на JavaScript, вам вероятно, никогда не придется делать этого самостоятельно, только если вы не будете использовать низкоуровневый язык вроде С. JavaScript (как и большинство языков высокого уровня) имеет встроенные реализации многих из этих структур данных.
Тем не менее, знание того, как реализовать эти структуры данных, даст вам огромное преимущество в поиске работы и может пригодиться, когда вы попытаетесь написать высокопроизводительный код.

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

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

Задания с freeCodeCamp:

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

Если рассматривать очередь с точки доступа к данным, то она является FIFO (First In First Out). Это означает, что после добавления нового элемента все элементы, которые были добавлены до этого, должны быть удалены до того, как новый элемент будет удален.
В очереди есть только две основные операции: enqueue и dequeue. Enqueue означает вставить элемент в конец очереди, а dequeue означает удаление переднего элемента.

Задания с freeCodeCamp:

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

Union (Объединение). Объединяет все элементы из двух разных множеств и возвращает результат, как новый набор (без дубликатов).
Intersection (Пересечение). Если заданы два множества, эта функция вернет другое множество, содержащее элементы, которые имеются и в первом и во втором множестве.
Difference (Разница). Вернет список элементов, которые находятся в одном множестве, но НЕ повторяются в другом.
Subset(Подмножество) - возвращает булево значение, показывающее, содержит ли одно множество все элементы другого множества.

Задания с freeCodeCamp:

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

Добавление пары в коллекцию
Удаление пары из коллекции
Изменение существующей пары
Поиск значения, связанного с определенным ключом

Задания с freeCodeCamp:

Хэш-таблица - это структура данных, реализующая интерфейс map, который позволяет хранить пары ключ / значение. Она использует хеш-функцию для вычисления индекса в массиве, по которым можно найти желаемое значение.
Хеш-функция обычно принимает строку и возвращает числовое значение. Хеш-функция всегда должна возвращать одинаковое число для одного и того же ввода. Когда два ввода хешируются с одним и тем же цифровым выходом, это коллизия. Суть в том, чтобы их было как можно меньше.
Поэтому, когда вы вводите пару ключ / значение в хеш-таблице, ключ проходит через хеш-функцию и превращается в число. Это числовое значение затем используется в качестве фактического ключа, в котором значение хранится. Когда вы снова попытаетесь получить доступ к тому же ключу, хеширующая функция обработает ключ и вернет тот же числовой результат. Затем число будет использовано для поиска связанного значения. Это обеспечивает очень эффективное время поиска O (1) в среднем.

Задания с freeCodeCamp:

Дерево - это структура данных, состоящая из узлов. Она имеет следующие характеристики:

Каждое дерево имеет корневой узел (вверху).
Корневой узел имеет ноль или более дочерних узлов.
Каждый дочерний узел имеет ноль или более дочерних узлов и т. д.

Двоичное дерево поиска имеет + две характеристики:

Каждый узел имеет до двух детей(потомков).
Для каждого узла его левые потомки меньше текущего узла, что меньше, чем у правых потомков.

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

Задания с freeCodeCamp:

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

Каждый узел в префиксном дереве содержит одну букву слова. Вы следуете ветвям дерева, чтобы записать слово, по одной букве за раз. Шаги начинают расходиться, когда порядок букв отличается от других слов в дереве или, когда заканчивается слово. Каждый узел содержит букву (данные) и логическое значение, указывающее, является ли узел последним узлом в слове.
Посмотрите на изображение, и вы можете создавать слова. Всегда начинайте с корневого узла вверху и двигайтесь вниз. Показанное здесь дерево содержит слово ball, bat, doll, do, dork, dorm, send, sense.

Задания с freeCodeCamp:

Двоичная куча - это очередное дерево, в каждом узле которого не более двух детей. Кроме того, это полное дерево. Это означает, что все уровни полностью заполнены до последнего уровня, а последний уровень заполняется слева направо.
Двоичная куча может быть либо минимальной, либо максимальной. В максимальной -ключи родительских узлов всегда больше или равны тем, что у детей. В минимальной -ключи родительских узлов меньше или равны ключам дочерних элементов.
Важен порядок между уровнями, но не узлами на одном уровне. На изображении вы можете видеть, что третий уровень минимальной кучи имеет значения 10, 6 и 12. Они расположены не по порядку.

Задания с freeCodeCamp:

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

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

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

Задания с freeCodeCamp:

Если хотите узнать больше:

Книга Grokking Algorithms - лучшая книга на эту тему, если вы новичок в структурах данных / алгоритмах и не обладаете базой компьютерных наук. Автор использует простые объяснения и юмор, рисованные иллюстрации (он является ведущим разработчиком в Etsy), чтобы объяснить некоторые структуры данных, представленные в этой статье.

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

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

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

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

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

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

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

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

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

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

Массивы

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

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

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

Бывают

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

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

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

Вопросы

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

Стеки

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

Изображение стека, в три элемента (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 дерево
Сбалансированное дерево
Дерево Бинарного Поиска

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

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

Вопросы

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

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

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

Вопросы

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

Хэш таблицы

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

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

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

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

Вопросы

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

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

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

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

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

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

Екатерина Малахова, редактор-фрилансер, специально для блога Нетологии адаптировала статью Beau Carnes об основных типах структур данных.

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

В этой статье я покажу вам 10 самых распространенных структур данных. Для каждой из них приведены видео и примеры их реализации на JavaScript. Чтобы вы смогли попрактиковаться, я также добавил несколько упражнений из бета-версии новой учебной программы freeCodeCamp.

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

Связные списки

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

Так устроен связный список

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

Основные операции в связном списке включают добавление, удаление и поиск элемента в списке.

Временная сложность связного списка

Упражнения от freeCodeCamp

Стеки

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

Так устроен стек

В стеках можно выполнять три операции: добавление элемента (push), удаление элемента (pop) и отображение содержимого стека (pip).

Временная сложность стека

Упражнения от freeCodeCamp

Очереди

Эту структуру можно представить как очередь в продуктовом магазине. Первым обслуживают того, кто пришёл в самом начале — всё как в жизни.

Так устроена очередь

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

Временная сложность очереди

Упражнения от freeCodeCamp

Множества

Так выглядит множество

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

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

Упражнения от freeCodeCamp

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

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

Так устроена структура map

Упражнения от freeCodeCamp

Хэш-таблицы

Так работают хэш-таблица и хэш-функция

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

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

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

Временная сложность хэш-таблицы

Упражнения от freeCodeCamp

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

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

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

Каждое дерево имеет корневой узел (вверху).
Корневой узел имеет ноль или более дочерних узлов.
Каждый дочерний узел имеет ноль или более дочерних узлов, и так далее.

У двоичного дерева поиска есть два дополнительных свойства:

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

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

Временная сложность двоичного дерева поиска

Упражнения от freeCodeCamp

Префиксное дерево

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

Так устроено префиксное дерево

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

Посмотрите на иллюстрацию и попробуйте составить слова. Всегда начинайте с корневого узла вверху и спускайтесь вниз. Это дерево содержит следующие слова: ball, bat, doll, do, dork, dorm, send, sense.

Упражнения от freeCodeCamp

Двоичная куча

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

Так устроены минимальная и максимальная кучи

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

Порядок уровней в двоичной куче важен, в отличие от порядка узлов на одном и том же уровне. На иллюстрации видно, что в минимальной куче на третьем уровне значения идут не по порядку: 10, 6 и 12.

Временная сложность двоичной кучи

Упражнения от freeCodeCamp

Графы — это совокупности узлов (вершин) и связей между ними (рёбер). Также их называют сетями.

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

Графы делятся на два основных типа: ориентированные и неориентированные. У неориентированных графов рёбра между узлами не имеют какого-либо направления, тогда как у рёбер в ориентированных графах оно есть.

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

Граф в виде матрицы смежности

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

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

Существуют специальные алгоритмы для просмотра рёбер и вершин в графах — так называемые алгоритмы обхода. К их основным типам относят поиск в ширину (breadth-first search) и в глубину (depth-first search). Как вариант, с их помощью можно определить, насколько близко к корневому узлу находятся те или иные вершины графа. В видео ниже показано, как на JavaScript выполнить поиск в ширину.

Временная сложность списка смежности (графа)

Упражнения от freeCodeCamp

Узнать больше

Если до этого вы никогда не сталкивались с алгоритмами или структурами данных, и у вас нет какой-либо подготовки в области ИТ, лучше всего подойдет книга Grokking Algorithms. В ней материал подан доступно и с забавными иллюстрациями (их автор — ведущий разработчик в Etsy), в том числе и по некоторым структурам данных, которые мы рассмотрели в этой статье.

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

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

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

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

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

— простые. Их нельзя разделить на составные части, которые больше, чем биты, то есть мы говорим о неделимых единицах. Для простого типа ясно определен размер и способ размещения структуры в памяти ПК;

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

По наличию связей структуры бывают:

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

— связные (к примеру, связные списки).

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

— статические;

— полустатические;

— динамические.

Классификацию можно посмотреть на картинке ниже:

Здесь отдельного упоминания заслуживают файлы как структуры данных. Файлами называют, к примеру, совокупность записей, структурированных одинаково. Файлы бывают:

— прямого или комбинированного доступа;

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

— нелинейные: деревья, графы, многосвязные списки;

— линейные. По характеру распределения компонентов в памяти ЭВМ они могут иметь последовательное распределение (строки, векторы, массивы, стеки, очереди) и произвольное связное распределение (односвязные и двусвязные списки).

Когда мы указываем тип данных, мы четко определяем:

— размер памяти, который отводится под конкретную структуру;

— способ размещения структуры в памяти;

— значения, которые допустимы для этого типа данных;

— операции, которые поддерживаются.

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

Как уже было сказано выше, это основа для создания более сложных структур. Также простые структуры называют примитивными либо базовыми (типами данных). Какие структуры сюда относят:

Для примера — структура простых типов для языка программирования Pascal:

Далее — формат представления беззнаковых чисел:

И формат представления чисел со знаком:

Статические структуры

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

Вектор

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

Двумерный массив

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

Множество

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

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

Записи

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

В памяти компьютера это можно представить:

— в виде последовательности полей, которые занимают произвольную непрерывную область памяти:

— в виде связного списка, имеющего указатели на значения полей записи:

Полустатические структуры

— поддержка простых способов изменения этой длины;

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

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

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

Примеры: стеки, строки, очереди, деки.

Динамические структуры

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

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

• размер структуры ограничивается лишь объемом памяти ЭВМ;

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

• работа с указателями требует от разработчика высокой квалификации;

• на указатели тратится дополнительная память;

• на доступ тратится дополнительное время.

Связные линейные списки

Это простейшие динамические структуры. Они представляют собой упорядоченные множества, которые содержат переменное число компонентов, причем отсутствуют ограничения по длине.

Ниже изображен односвязный список:

— INF — информационное поле, которое содержит данные;

— NEXT — указатель на последующий компонент списка;

— nil — указатель на последний элемент.

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

Заключение

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

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