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

Cтраница 3

Иллюстрация к расстановке указателей при разрезании произвольного многоугольника произвольной прямой. [31]

Для описания П ] и всех остальных многоугольников, которые могут возникнуть в процессе разрезания, лучше всего использовать связный список. В частности, каждой вершине ставится в соответствие указатель, который при обходе многочлена по часовой стрелке указывает следующую вершину. Перейдем теперь к модификации алгоритма 15.3. Вместо проведения сторон многоугольников будут просто корректироваться соответствующие указатели. В частности, на шаге 6 в список вводится точка пересечения и устанавливается NxT ( Pm j) Pi, где j - число, обозначающее позицию новой точки в конце списка. На шаге 7 устанавливается NxT ( Pi i) Pm j и NxT ( Pm j) 0, поскольку следующая точка пока не известна. Элементы этой процедуры иллюстрируются на рис. 15.4, где стрелками отмечены результаты использования указателей. Для придания процедуре законченности необходимо задать указатели для связывания точек пересечения. Для этого точки Pm j сортируются в порядке увеличения значений координаты у или х, если режущая прямая горизонтальна. Затем эти точки берутся попарно и указателем с нулевыми значениями присваиваются значения адресов вторых элементов соответствующей пары. [32]

Создайте АТД Неупорядоченная очередь ( напишите интерфейс и реализацию), в котором в качестве базовой структуры данных используется связный список. Напишите как можно более эффективные реализации операций insert и remove и проанализируйте связанные с ними издержки для наихудшего случая их выполнения. [33]

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

Разработайте реализацию АТД первого класса для стека ю упражнения 4 73, когорт я качестве базовой структуры данных использует связный список. [35]

На рис. 11.1.2 изображено дерево бинарного поиска, которое соответствует списку рис. 11.1.1. Это не только дерево, но и связный список, каждая ячейка которого содержит два указателя: по одному на каждый альтернативный путь поиска. [36]

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

Определение 3.3 Связный список содержит либо null - ссылки, либо ссылки на узлы, которые содержат элемент и ссылку на связный список. [38]

Связный список является линейным набором объектов классов с самоадресацией, называемых узлами, связанных при помощи указателей связи и поэтому определяемых термином связный список. Доступ к связному списку осуществляется через указатель на первый узел списка. Последующие узлы доступны через указатели связи, хранящиеся в каждом узле. В соответствии с соглашением указатель связи в последнем узле списка устанавливается на нуль для того, чтобы отметить конец списка. Данные в связном списке хранятся динамически, то есть каждый узел создается по мере необходимости. Узлы могут содержать данные любого типа, включая объекты других классов. Стеки и очереди также являются линейными структурами данных и, как мы увидим, являются частными случаями связного списка. Деревья являются нелинейной структурой данных. [39]

Шченнте хеширование с раздельным стоыианисм ( программа 14 3), чтобы в нем использовалась хеш-таблица размером 2 Л /, а элементы хранились на страницах размером 2Л /, Другими слоьамн, когда страница заполняете h оз Спи-дываетсд с новой пустой страннцейн чтобы каждая sattittb хеш-та Слниы указывала на связный список страниц. [40]

Программа 3.10 служит реализацией простой задачи обработки списка, состоящей в изменении на обратный порядка следования узлов. Она принимает связный список в качестве аргумента и возвращает связный список, состоящий из тех же узлов, но расположенных в обратном порядке. На рис. 3.7 показано изменение, выполняемое функцией в своем главном цикле для каждого узла. Эта диаграмма упрощает проверку каждого оператора программы на правильность изменения ссылок. Программисты обычно используют подобные диаграммы для осмысления операций обработки списков. [41]

Каждое определение CCL-команды занимает один малый буфер. Список CCL-определений составляет связный список малых буферов в оперативной памяти, поэтому определение стандартного языка CCL необходимо выполнять при запуске каждого сеанса разделения времени. [42]

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

Пример i-узла. [44]

Обычно этот размер значительно меньше, чем FAT-таблица, описанная в предыдущем разделе. Размер таблицы, хранящей связный список всех блоков диска, пропорционален размеру самого диска. Для диска из п блоков потребуется п записей в таблице. Таким образом, размер таблицы линейно1 растет с ростом размера диска. Для схемы i-узлов, напротив, требуется массив в памяти с размером, пропорциональным максимальному количеству файлов, которые могут быть открыты одновременно. При этом не важно, будет ли размер диска 1 Гбайт, 10 Гбайт или 100 Гбайт. [45]

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