Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Связанные структуры данных включают в себя связанные списки , деревья поиска , деревья выражений и многие другие широко используемые структуры данных. Они также являются ключевыми строительными блоками для многих эффективных алгоритмов, таких как топологическая сортировка [1] и набор-объединение-поиск . [2]

Общие типы связанных структур данных [ править ]

Связанные списки [ править ]

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

Связанный список может быть односвязным, двусвязным или многосвязным, а также линейным или кольцевым.

Основные свойства
  • Объекты, называемые узлами , связаны в линейной последовательности.
  • Ссылка на первый узел списка всегда сохраняется. Это называется «голова» или «перед». [3]
Односвязный-list.svg
Связанный список с тремя узлами содержит по два поля каждое: целочисленное значение и ссылку на следующий узел.
Связанный список с одним узлом.

Пример на Java [ править ]

Это пример класса узла, используемого для хранения целых чисел в Java-реализации связанного списка:

публичный  класс  IntNode  {  публичное  значение int  ; общедоступная ссылка на IntNode ; общедоступный IntNode ( int v ) { значение = v ; } }

Пример на C [ править ]

Это пример структуры, используемой для реализации связного списка в C:

struct  node { int  val ; struct  node  * next ; };

Это пример использования typedefs :

typedef  struct  node  node ;struct  node { int  val ; узел  * следующий ; };

Примечание. Подобная структура, содержащая член, указывающий на ту же структуру, называется самореферентной структурой.

Пример на C ++ [ править ]

Это пример структуры класса узла, используемой для реализации связного списка в C ++:

класс  Node { int  val ; Узел  * следующий ; };

Деревья поиска [ править ]

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

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

Преимущества и недостатки [ править ]

Связанный список против массивов [ править ]

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

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

С другой стороны, доступ к любому конкретному узлу в связанной структуре данных требует следования цепочке ссылок, которые хранятся в каждом узле. Если структура имеет n узлов, и каждый узел содержит не более b ссылок, будут некоторые узлы, которые нельзя будет достичь менее чем за log b n шагов, что замедляет процесс доступа к этим узлам - иногда это означает значительное замедление, особенно в случае конструкций, содержащих большое количество узлов. Для многих структур некоторые узлы могут потребовать наихудшего случая до n -1 шагов. Напротив, многие структуры данных массивов позволяют получить доступ к любому элементу с постоянным количеством операций, независимо от количества записей.

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

Общие недостатки [ править ]

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

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

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

См. Также [ править ]

  • Список структур данных
  • Промежуточное ПО

Ссылки [ править ]

  1. ^ Дональд Кнут , Искусство компьютерного программирования
  2. ^ Бернард А. Галлер и Майкл Дж. Фишер . Улучшенный алгоритм эквивалентности. Сообщения ACM , том 7, выпуск 5 (май 1964 г.), страницы 301–303. Бумага, порождающая непересекающиеся леса. Цифровая библиотека ACM
  3. ^ http://www.cs.toronto.edu/~hojjat/148s07/lectures/week5/07linked.pdf