Связной списки
Cтраница 2
Преимущество связных списков перед массивами состоит в том, что связные списки эффективно изменяют размеры на протяжении времени жизни. В частности, необязательно заранее знать максимальный размер списка. Одно из важных практических следствий этого свойства состоит в возможности иметь несколько структур данных, обладающих общим пространством, не уделяя особого внимания их относительному размеру в любой момент времени. [16]
Построить программную реализацию варианта сортировки методом Шелла, ориентированного на связные списки, который не требует существенно большего объема памяти и времени для сортировки случайно упорядоченного файла, нежели вариант, предназначенный для сортировки массивов. [17]
Далее мы сортируем подсписки, после чего объединяем все эти связные списки в единое целое. Соединение связных списков требует отслеживания начала и конца каждого из этих списков, и, естественно, многие из них вполне могут оказаться пустыми. [18]
При реализации двух стеков 1ST и OST наиболее удобно хранить их как связные списки, используя два массива, называемые stack и next. Элемент stack ( i) означает текущий элемент стека, и next ( г) указывает на следующий ( расположенный ниже) элемент того же стека. Элемент next ( Q) указывает на верхний элемент в 1ST, и next ( - 1) указывает на верхний элемент в OST. Пример на рис. 8.33 иллюстрирует, как два стека реализуются двумя массивами. Преимущество такого представления состоит в том, что, когда мы переводим связку элементов из одного стека в другой, перемещать сами элементы на самом деле не нужно; нужно только изменить указатели начала и конца связки. Поскольку возможна много перемещений связок вперед и назад, такое представление важно. [20]
Некоторые программисты предпочитают инкапсулировать все операции в низкоуровневых структурах данных, таких как связные списки, путем описания функция для каждой низкоуровневой операции в интерфейсах, подобных показанному в программе 3.12. Действительно, как будет продемонстрировано в главе 4, классы C упрощают это решение. Однако такой дополнительный уровень абстракции иногда скрывает факт использования небольшого количества операций низкого уровня. В данной книге при реализации высокоуровневых интерфейсов низкоуровневые операции обычно описываются непосредственно в связных структурах, дабы ясно выразить существенные подробности алгоритмов и структур данных. [21]
Для отображения структур данных, например деревьев или транзитивных графов, автор использует связные списки. Для связного списка рассмотрены операции поиска, добавления и удаления записей. [22]
Некоторые программисты предпочитают инкапсулировать асе операции fi низкю-урсшне ЕЫ структурах данных, таких как связные списки, путем осшсакич функция для кажлой HHJKoypoBHeeoH отфиичи и интйрф й-сих подобный иокД ннЕму к программе J. Дсй-стнитсльну, как будет 1градемонстриройано а главе 4, KJiatxba С - Р - уЕтрощаюг это решение, Однако такой дополнительный уровень абстракции ноглэ скрьшмт факт и ЕГО - аадокум н нсСолъпюго количества операций низкою уроння. [23]
Следующая часть - глава 15, подробно излагает динамические структуры данных, такие, как связные списки, очереди, стеки и деревья. [24]
В данном разделе рассматриваются две реализации АТД стека: в одной используются массивы, в другой - связные списки. [25]
Эта программа использует АТД очереди ( программа 4 19 для реализации восходящей сортировки спнпнмем - Элементы очер & ди представляют собой упорядоченные связные списки, После инициализации очереди списком длиной 1Г программа просто удаляет из очереди два списка, слиеэет их, а полученный результат эту же очередь и продолжа & т процесс до тен пор, пока g очереди не только один списог. [26]
Напишите реализацию для приведенного в тексте АТД Полином ( программа 4.24), в которой в качестве базовой структуры данных используются связные списки. Списки не должны содержать узлов, соответствующих членам с нулевыми коэффициентами. [27]
Лемма 4.2 Для ЛТД Очередь FIFO имеется возможность реализовать операции get и put с постоянным временем выполнения, используя либо массивы, либо связные списки. [28]
Для практической реализации в любом случае требуется дополнительное пространство памяти, так почему бы не рассмотреть возможность реализации сортировки слиянием, ориентированной на связные списки. [29]
Операция индексации массива [ ] не ограничена применением только к массивам; ее можно использовать для выделения элементов из других видов классов-контейнеров, таких, как связные списки, строки, словари и так далее. [30]
Страницы: 1 2 3 4