Связной списки
Cтраница 1
 |
Графическое представление дерева. [1] |
Связные списки, стеки и очереди являются линейными структурами данных. Дерево является нелинейной двумерной структурой данных с особыми свойствами. Узлы дерева могут содержать два и более указателей связи. Корневой узел является первым узлом дерева. Каждый указатель связи в корневом узле ссылается на дочерний узел или узел-потомок. Левый узел-потомок является первым узлом в левом поддереве, а правый узел-потомок является первым узлом в правом поддереве. Узел без узлов-потомков называется листом дерева или концевым узлом. Специалисты по вычислительной технике обычно рисуют деревья сверху-вниз, начиная с корневого узла, то есть противоположно тому, как растут деревья в природе. [2]
 |
Дерево двоичного поиска. [3] |
Связные списки обеспечивают простые механизмы вставки и удаления данных путем манипулирования указателями. [4]
Связные списки плохо приспособлены для поиска k - того элемента ( по индексу) - операции, которая характеризует эффективность доступа к данным массивов. В массиве для доступа к Атому элементу используется простая запись a [ k ], а в списке для этого необходимо отследить k ссылок. [5]
Связные списки используются в материале книги, во-первых, для основных ADT-реализаций ( см. главу 4), во-вторых, в качестве компонентов более сложных структур данных. Для многих программистов связные списки являются первым знакомством с абстрактными структурами данных, которыми разработчик может непосредственно управлять. Они образуют важное средство разработки высокоуровневых абстрактных структур данных, необходимых для решения множества задач, в чем будет возможность убедиться. [6]
Связные списки позволяют обрабатывать за - ПИС1Г переменной длины. Как в этом случае k поступают со свободной областью. [7]
Связные списки могут сортироваться просто путем вставки каждого нового элемента в соответствующую позицию в списке. [8]
Индексированные списки) Мы рассматривали связные списки, которые должны просматриваться последовательно. Для больших списков это может приводить к плохой производительности. Обычный способ улучшения производительности поиска заключается в создании и поддержке индексных указателей списка. [9]
Множества реализованы в LEAP как связные списки, каждый элемент которых содержит ID. Как видно на рисунке, множество упорядочено по возрастанию ID для ускорения работы. [10]
Узлы определяются ссылками на узлы, поэтому связные списки иногда называют самоссылочыми ( self-referent) структурами. Более того, хотя узел обычно ссылается на другой узел, возможна ссылка на самого себя, поэтому связные списки могут представлять собой циклические ( cyclic) структуры. Последствия этих двух фактов станут ясны при рассмотрении конкретных представлений и применений связных списков. [11]
В одном из рассматриваемых методов разрешения конфликтов используются связные списки, поэтому он находит непосредственное применение в динамических ситуациях, когда заранее трудно предвидеть количество ключей поиска. В других двух методах разрешения конфликтов высокая производительность поиска обеспечивается для элементов, хранящихся в фиксированном массиве. [12]
Как было показано в главе 3, массивы и связные списки обеспечивают основные механизмы, позволяющие вставлять и удалять заданные элементы. Действительно, связные списки и массивы - это структуры данных, лежащие в основе нескольких реализаций рассматриваемых нами обобщенных очередей. Как мы знаем, затраты на вставку и удаление элементов зависят от конкретной используемой структуры и от конкретного вставляемого или удаляемого элемента. В отношении некоторого данного АТД задача заключается в том, чтобы выбрать структуру данных, позволяющую эффективно выполнять требуемые операции. В настоящей главе подробно рассматриваются несколько примеров абстрактных типов данных, для которых связные списки и массивы обеспечивают подходящие решения. Абстрактные типы данных, обеспечивающие более эффективные операции, требуют более сложных реализаций, что является главной движущей силой создания многих алгоритмов, рассматриваемых в настоящей книге. [13]
Списки данных могут храниться и в массивах, но связные списки предоставляют некоторые преимущества. Применение связных списков является уместным в том случае, когда число элементов, которые должны быть представлены в структуре данных, заранее не известно. Размер обычного массива в C не может быть изменен, поскольку он зафиксирован на этапе компиляции. Обычные массивы могут переполняться. Связные списки могут переполняться только в том случае, если у системы нет достаточного места для удовлетворения запросов по динамическому выделению памяти. [14]
Если обработка файла сводится в основном к изменениям, связные списки имеют преимущество перед последовательными. [15]
Страницы: 1 2 3 4