3.1 Классификация структур данных¶
К распространенным структурам данных относятся массивы, связные списки, стеки, очереди, хеш-таблицы, деревья, кучи и графы. Их можно классифицировать по двум измерениям: логической структуре и физической структуре.
3.1.1 Логическая структура: линейная и нелинейная¶
Логическая структура раскрывает логические отношения между элементами данных. В массивах и связных списках данные расположены в определенном порядке, что отражает линейные отношения между элементами. В деревьях данные расположены по уровням сверху вниз, что демонстрирует отношения «предок» и «потомок». Графы состоят из вершин и ребер, отражая сложные сетевые отношения.
Как показано на рисунке 3-1, логические структуры делятся на две большие категории: линейные и нелинейные. Линейные структуры более интуитивны, поскольку в них данные расположены линейно и логически связаны. Нелинейные структуры, напротив, представляют собой нелинейное расположение элементов данных.
- Линейные структуры данных: массивы, связные списки, стеки, очереди, хеш-таблицы, в которых элементы связаны отношением «один к одному».
- Нелинейные структуры данных: деревья, кучи, графы, хеш-таблицы.
Нелинейные структуры данных можно дополнительно разделить на древовидные и сетевые.
- Древовидные структуры: деревья, кучи, хеш-таблицы, в которых элементы связаны отношением «один ко многим».
- Сетевые структуры: графы, в которых элементы связаны отношением «многие ко многим».
Рисунок 3-1 Линейные и нелинейные структуры данных
3.1.2 Физическая структура: непрерывная и разрозненная¶
Во время выполнения программы обрабатываемые данные в основном хранятся в памяти. На рисунке 3-2 показан модуль оперативной памяти компьютера, где каждый черный блок содержит определенный участок памяти. Память можно представить как огромную таблицу Excel, в которой каждая ячейка способна хранить данные определенного размера.
Система обращается к данным по адресам памяти соответствующих позиций. Как показано на рисунке 3-2, компьютер по определенным правилам присваивает каждой ячейке в этой таблице номер, чтобы каждый участок памяти имел уникальный адрес. Благодаря этим адресам программа получает доступ к данным, находящимся в памяти.
Рисунок 3-2 Планка памяти, участок памяти и адрес памяти
Tip
Стоит отметить, что сравнение памяти с таблицей Excel - это упрощенная аналогия. Реальный механизм работы памяти гораздо сложнее и включает такие понятия, как адресное пространство, управление памятью, кэш-механизмы, виртуальная и физическая память.
Память - общий ресурс для всех программ. Когда некоторый участок памяти занят одной программой, другие программы обычно не могут использовать его одновременно. Поэтому при проектировании структур данных и алгоритмов память занимает важное место. Например, пиковое потребление памяти алгоритмом не должно превышать объем доступной свободной памяти системы. Если не хватает непрерывных крупных участков памяти, выбранная структура данных должна уметь размещаться в разрозненных областях памяти.
Как показано на рисунке 3-3, физическая структура отражает способ хранения данных в памяти компьютера. Ее можно разделить на хранение в непрерывном пространстве (массивы) и хранение в разрозненном пространстве (связные списки). Физическая структура на низком уровне определяет способы доступа к данным, их обновления, вставки и удаления. Эти два типа физических структур взаимно дополняют друг друга по временной и пространственной эффективности.
Рисунок 3-3 Хранение в непрерывном и разрозненном пространстве
Стоит отметить, что все структуры данных реализуются на основе массивов, связных списков или их комбинации. Например, стек и очередь можно реализовать как с помощью массивов, так и с помощью связных списков. Реализация хеш-таблицы также может одновременно включать массивы и связные списки.
- Можно реализовать на основе массивов: стеки, очереди, хеш-таблицы, деревья, кучи, графы, матрицы, тензоры (массивы размерности \(\geq 3\) ) и т.д.
- Можно реализовать на основе связных списков: стеки, очереди, хеш-таблицы, деревья, кучи, графы и т.д.
После инициализации длину связного списка все еще можно изменять во время выполнения программы, поэтому его также называют «динамической структурой данных». Длина массива после инициализации неизменна, поэтому его также называют «статической структурой данных». Стоит отметить, что массив может изменять длину за счет повторного выделения памяти, тем самым приобретая определенную «динамичность».
Tip
Если тебе пока трудно понять физическую структуру, рекомендуется сначала прочитать следующую главу, а затем вернуться к этому разделу.