Связной списки

Cтраница 3

Интересно, что операция индексации массива не ограничивается применением только к массивам; ее можно использовать для выделения элементов из других видов классов-контейнеров, таких, как связные списки, строки, словари и так далее. [31]

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

Это предоставляет возможность мгновенного доступа к любому элементу массива, поскольку адрес любого элемента может быть вычислен непосредственно путем определения его позиции по отношению к началу массива. Связные списки не предоставляют возможности для такого мгновенного доступа к своим элементам. [33]

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

Связные списки могут также применяться при наложении новой структуры на головную часть существующей. [35]

Другие примеры оптимизации включают структуры данных. Двойные связные списки занимают больше памяти, чем одинарные связные списки, зато они часто предоставляют более быстрый доступ к элементам списка. Хэш-таблицы занимают еще больше памяти, но еще более ускоряют поиск. Короче говоря, при оптимизации участка программы следует уделить особое внимание проблеме компромисса между занимаемой памятью и скоростью выполнения программы. [37]

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

Связные списки используются в материале книги, во-первых, для основных ADT-реализаций ( см. главу 4), во-вторых, в качестве компонентов более сложных структур данных. Для многих программистов связные списки являются первым знакомством с абстрактными структурами данных, которыми разработчик может непосредственно управлять. Они образуют важное средство разработки высокоуровневых абстрактных структур данных, необходимых для решения множества задач, в чем будет возможность убедиться. [39]

Эта программа использует АТД очереди ( программа 4.18) для реализации восходящей сортировки слиянием. Элементы очереди представляют собой упорядоченные связные списки. После инициализации очереди списком длиной 1, программа просто удаляет из очереди два списка, сливает их, а полученный результат возвращает в эту же очередь и продолжает процесс до тех пор, пока в очереди не останется только один список. Это соответствует последовательности проходов через все элементы, при этом на каждом проходе длина упорядоченных списков удваивается, как и в случае восходящей сортировки слиянием. [40]

Изучаемые в этой главе структуры данных служат в качестве строительных блоков, которые можно использовать естественным образом в C и многих других языках программирования. Массивы, строки, связные списки и деревья служат базовыми элементами большинства алгоритмов, о которых идет речь в книге. В главе 4 рассматривается использование конкретных представлений, разработанных на основе абстрактных типов данных. Эти представления могут применяться в различных приложениях. Остальная часть книги посвящена разработке различных вариантов базовых средств, деревьев и абстрактных типов данных для создания алгоритмов, решающих более сложные задачи. Они также могут служить основой для высокоуровневых абстрактных типов данных в различных приложениях. [41]

Запись, соответствующая а. [42]

Зт ячеек, не обязательно непрерывно следующих друг за другом. Таким образом, если мы применяем связные списки, то для хранения матрицы А в упакованной форме потребуется объем памяти в n - f Зт ячеек. [43]

Как указывалось в разделе 3.3, для первого и последнего указателей списка применяется ряд различных соглашений. Некоторые из них рассматриваются в этом разделе, хотя мы взяли за правило резервировать термин связные списки для описания простейших ситуаций. [45]

Страницы: 1 2 3 4