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

К распространенным структурам данных относятся массивы, связные списки, стеки, очереди, хеш-таблицы, деревья, кучи и графы; их можно классифицировать по двум измерениям: "логическая структура" и "физическая структура".

3.1.1   Логическая структура: линейная и нелинейная¶

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

Как показано на рисунке 3-1, логические структуры можно разделить на два больших класса: "линейные" и "нелинейные". Линейные структуры более интуитивны и означают, что данные логически выстроены в линию; нелинейные структуры, напротив, располагаются нелинейно.

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

Нелинейные структуры данных можно дополнительно разделить на древовидные и сетевые.

• Древовидные структуры: деревья, кучи, хеш-таблицы; между элементами существует отношение "один ко многим".
• Сетевые структуры: графы; между элементами существует отношение "многие ко многим".

Рисунок 3-1   Линейные и нелинейные структуры данных

3.1.2   Физическая структура: непрерывная и разрозненная¶

Во время выполнения алгоритма обрабатываемые данные в основном хранятся в памяти. На рисунке 3-2 показана планка памяти компьютера, где каждый черный блок содержит некоторый участок памяти. Мы можем представить память как огромную таблицу Excel, в которой каждая ячейка способна хранить данные определенного размера.

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

Рисунок 3-2   Планка памяти, участок памяти и адрес памяти

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

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

Рисунок 3-3   Хранение в непрерывном и разрозненном пространстве

Стоит отметить, что все структуры данных реализуются на основе массивов, связных списков или их комбинации. Например, стеки и очереди можно реализовать как с помощью массивов, так и с помощью связных списков; а реализация хеш-таблицы может одновременно содержать массивы и связные списки.

• Можно реализовать на основе массивов: стеки, очереди, хеш-таблицы, деревья, кучи, графы, матрицы, тензоры (массивы размерности \(\geq 3\) ) и т.д.
• Можно реализовать на основе связных списков: стеки, очереди, хеш-таблицы, деревья, кучи, графы и т.д.

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

Оставляйте свои идеи, вопросы и предложения в комментариях