Связанные списки

Cтраница 4

Различные реализации стеков и очередей обладают неодинаковыми свойствами. Стеки и циклические очереди на основе массивов просты и эффективны, в особенности если заранее известен их потенциальный размер. Связанные списки обеспечивают большую гибкость, если необходимо часто изменять размер списка. [46]

Мы рекомендуем представлять данные в виде связанных списков в тех случаях, когда число элементов меняется относительно мало ( 50), и, кроме того, кет никаких сведений о частоте их использования. Типичный пример - таблица имен в трансляторах для языков программирования, Каждое описание приводит к добавлению нового имени, а при выходе из области действия его описания это имя из списка вычеркивается. Простые связанные списки особенно подходят для относительно коротких программ. [47]

Примеры связанных линейных списков. [48]

Очевидно, что адресная функция а не зависит от линейного упорядочения ячеек машинной памяти. Любое произвольное изменение порядка записей, сокращение или расширение вектора данных могут быть сделаны без перемещений записей внутри вектора данных; для этого необходимо лишь изменить значения полей связи. Таким образом, связанные списки являются удобной формой представления динамически изменяющихся линейных структур. [49]

В этой главе мы обсудим один из наиболее мощных элементов языка С - указатели. Овладение техникой работы с указателями - дело достаточно трудное. Указатели дают возможность программам генерировать вызов по ссылке, создавать и управлять динамическими структурами данных, которые могут увеличиваться и уменьшаться в размере, - это могут быть, например, связанные списки, очереди, стеки и деревья. Эта глава посвящена основам работы с указателями. В главе 10 будет рассказано о роли указателей в работе со структурами. В главе 12 будут представлены динамические методы управления памятью с примерами создания и использования динамических структур данных. [50]

Связанные списки могут быть представлены с помощью основной для Фортрана структуры данных - вектора. Сначала определяется один большой вектор М, который будет изображать память. Индексы элементов вектора служат в качестве адресов или указателей позиций ( элементов вектора) в этой памяти. Поскольку индексы являются целыми числами, они могут храниться в тех же самых векторах, что и целочисленные данные, содержащиеся в списках; следовательно, вектор М должен иметь тип integer. Теперь связанные списки можно представить, в векторе так, как это предлагается в разд. Таким образом каждый элемент списка занимает в М две последовательные позиции. Это представление иллюстрируется на рис. 3.20. Несмотря на простоту такого представления списков, их невозможно использовать эффективно, если программист не напишет набор подпрограмм для выполнения соответствующих операций над списками и, что более важно, не построит для вектора М систему управления памятью, которая позволит по мере необходимости выделять, возвращать и повторно использовать память во время обработки списка. Несколько методов, с помощью которых можно реализовать эти механизмы, обсуждаются в гл. [51]

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

Целочисленный массив из 100 элементов ( я и результат добавления к нему нового элемента ( б 118. [53]

Тецерь посмотрим, как эта же самая проблема решается с помощью связанного списка. На рис. 7.5 а, как будет выглядеть отсортированный список в виде фиксированного массива, приведенный на рис. 7.4 а, если его реализовать с помощью связанного списка. На рис. 7.5 6 показано, что при добавлении нового числа перемещения данных не происходит. Вместо этого создается новый узел и этот новый узел вставляется в список просто за счет перемещения указателей. Аналогичным образом узел удаляется ( исключается) из списка за счет переупорядочивания указателей. Легко понять, что много времени можно сэкономить, применяя в подобных случаях связанные списки вместо массива. [54]

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