Cтраница 3
Только что рассмотренный вариант не единственный для представления очередей в виде линейного списка со связями; далее в этой же главе мы приведем несколько других вариантов. Более того, не следует думать, что какая-либо из приведенных выше операций представляет собой единственно возможную реализацию соответствующего действия; их следует рассматривать лишь как примеры того, как нужно работать со связанными списками. Читателю, у которого опыт использования таких методов невелик, будет полезно еще раз прочитать этот пункт, прежде чем продолжать чтение книги. [31]
Связанное распределение - более сложный, но и более гибкий способ хранения линейного списка. При связанном распределении не требуется, чтобы список хранился в последовательных элементах памяти. [32]
Отсюда следует, что r - плотное ттг-арное дерево не может выродиться в линейный список. [33]
Для обработки коллизий записи, входящие в класс коллизий, вместе с их ключами организуются в виде линейного списка, первый элемент которого размещается по адресу, получаемому при перемешивании. Для нахождения конкретной записи список просматривается и ключи записей сравниваются с заданным ключом. Хороший алгоритм перемешивания хотя и не сможет предотвратить возникновение коллизий совсем, обычно позволяет сохранять небольшой размер списков коллизий, делая приемлемым их последовательный просмотр. Отметим, что списки коллизий требуют дополнительной памяти. В то же время некоторые участки памяти могут остаться свободными из-за того, что ключи, соответствующие адресам этих участков, могут никогда не встретиться. Поэтому файл, для адресации записей которого используются методы перемешивания, неизбежно имеет дыры ( в связи с этим данный метод часто называют рассеянной памятью), но это вполне окупается получаемыми преимуществами. [34]
Последнее преобразование является принципиальным этапом лексического анализа в РЕФАЛ-трансляторах, так как в отсутствие его результатом ЛЕКС будет линейный список. Скобочная структуризация позволяет явным образом отразить укрупненную иерархию понятий, используемых в исходном тексте, а специфика РЕФАЛ - эффективная обработка скобочных структур. За счет этого существенно увеличивается скорость синтаксического анализа и упрощаются его алгоритмы. [35]
Для хеш-таблиц с внешними цепочками переполнения удаление является процедурой, обратной вставке, и выполняется аналогично операции удаления из обычного линейного списка. Для хеш-таблиц с линейным опробованием или с внутренними цепочками переполнения связь между занятыми позициями однозначна, поэтому возможны реальные удаления. Для этого достаточно переместить содержимое всех позиций, приндалежащих списку и следующих за удаленной. Для выявления синонимов может потребоваться повторно вычислить хеш-функцию ключей, принадлежащих списку. Если потребовать, чтобы каждый список синонимов обязательно начинался со своего хеш-адреса h0 ( k), то это позволит сократить затраты на удаление. Затраты на вставку в этом методе будут несколько выше, так как может потребоваться переместить ключ, занимавший чужую позицию. Этот метод можно рекомендовать и в том случае, когда вставки ключей в таблицу редки по сравнению с поиском. [36]
Список может быть списком списков, а ЛинейныйСписок - это тот же список, но выровненный таким образом, что элементы его подсписков составляют один линейный список. [37]
Поле След записи указывает на следующий элемент в списке, а поле Знач содержит целочисленную информацию. Линейный список, пример которого был приведен выше, является простейшей полезной структурой данных, которую можно сконструировать при помощи указателей. [38]
Во многих алгоритмах САПР требуется упорядочение записей по какому-либо параметру. Линейный список дает возможность реализовывать алгоритмы сортировки ( упорядочения) без физического перемещения записей в ОП только путем соответствующей корректировки указателей. [39]
Таким образом, в языке L4 есть произвольные многооперандные операции с любым требуемым числом параметров. Программа на этом языке имеет вид линейного списка инструкций, оканчивающегося специальной инструкцией-ограничителем. Инструкция DATA предназначена для передачи данных. Данные могут передаваться как из основной ЭВМ в сателлит, так и наоборот. Следовательно, язык может использоваться для передачи протоколов и одновременно с этим он может играть роль независимого от устройства промежуточного языка. От устройства зависит только размещающийся в сателлите интерпретатор, который транслирует инструкций L4 в соответствующие программы на языке дисплейного процессора. Для каждой конкретной дисплейной системы должен создаваться свой интерпретатор. [40]
Очередь - линейный список, в котором все включения производятся на одном конце списка, а все исключения ( и обычно всякий доступ) делаются на другом его конце. Дек ( очередь с двумя концами) - линейный список, в котором все включения и исключения ( и обычно всякий доступ) делаются на обоих концах списка. [41]
В приведенных выше строках из монографии Кнута иллюстрируется не только важность понятия структуры данных, но и указывается различие между структурой данных и ее представлением в ЭВМ. Например, некоторая структура, такая, как линейный список или дерево, может быть представлена в файле ЭВМ разными способами. [42]
Линейный список - наиболее универсальная структура данных, в нем доступна для чтения и удаления любая запись, более того, новая запись может быть включена между двумя любыми соседними записями списка. На рис. 1.5, а показана физическая реализация двунаправленного линейного списка. Встречное направление указателей позволяет осуществить в таком списке поиск записей с обеих сторон. [43]
Эти стеки могут содержать либо числа, представленные в двоичной системе счисления, либо специальные символы, называемые код-1, код-2, код-3 и код-4. Алгоритм строит также дополнительную таблицу чисел qh, rk; эта таблица устроена таким образом, что ее можно хранить в запоминающем устройстве как линейный список, и все доступы к этой таблице просты, так что, пользуясь одним-единственным указателем ( который проходит список, двигаясь взад и вперед), можно выбрать нужный текущий элемент. [44]
Однако доступ к конкретному узлу может оказаться намного длительнее, чем при последовательном распределении памяти. Для этого линейный список делится на группы узлов, связанные между собой обратными указателями. Вначале осуществляется доступ по обратным указателям к группе, в которой находится требуемый узел, а затем по прямым указателям перебираются узлы группы, пока не будет найден требуемый узел. Вход в список при таком способе организации осуществляется с конца. Другой способ ( рис. 7.5 6) заключается в построении специального дополнительного линейного списка - индекса, например, с последовательным распределением памяти. Элементы индекса - значения первых узлов каждой группы и указатели на них. [45]