Динамическая структура - данные
Cтраница 3
Все ссылочные переменные имеют одинаковый размер, равный 4 байтам, и содержат адрес начала участка оперативной памяти, в котором размещена динамическая структура данных. Сравните с простой переменной I типа Integer на том же рисунке. [31]
Материал о добавлении и удалении узлов охватывает почти все то, что в основном связано с применением указателей для приложений, требующих динамических структур данных. [32]
Мы изучили такие структуры данных фиксированного размера, как одномерные индексированные массивы, двумерные индексированные массивы и структуры struct. В этой главе вводятся динамические структуры данных, которые нарастают и сокращаются в процессе выполнения программы. Связные списки являются наборами элементов данных, выстроенными в линейку; операции вставки элементов данных и их удаления могут осуществляться в любом месте связного списка. Стеки играют существенную роль в компиляторах и операционных системах; операции вставки и удаления проводятся в конце стека, то есть в его вершине. Бинарные деревья способствуют высокоскоростному поиску и быстрой сортировке данных, эффективному удалению дубликатов элементов данных, отображению системы каталогов файлов а также компиляции выражений на машинный язык. У этих структур данных имеется много других любопытных приложений. [33]
Представленная программа создает связанный список объектов класса Part. Связанный список - это динамическая структура данных вроде массива, за исключением того, что в список можно добавлять произвольное число объектов указанного типа и удалять любой из введенных объектов. [34]
В этом случае будем считать, что вершины дерева должны храниться во вторичной памяти, скажем на диске. Вводимые в данной главе динамические структуры данных особенно подходят именно для такой вторичной памяти. Принципиальное новшество - ссылки представляют собой адреса на диске, а не в оперативной памяти. Поскольку теперь каждый шаг включает обращение к диску ( с его собственнТым латентным временем), то крайне желательна организация памяти, требующая меньшего числа обращений. Сильно ветвящиеся деревья представляют собой идеальное решение этой проблемы. Если происходит обращение к одному элементу, расположенному во вторичной памяти, то без больших дополнительных затрат можно обратиться и к целой группе элементов. Это предполагает, что дерево разбито на поддеревья и эти поддеревья как раз те группы, которые одновременно доступны. [35]
В этой главе будут рассмотрены динамические структуры данных, размер которых, может увеличиваться или уменьшаться при исполнении программы. [36]
Другой случай, в котором рекурсия оказывается полезным методом решения, - структура данных программы определяется ( или может определяться) рекурсивно. Классические примеры здесь относятся к динамическим структурам данных, описанным в гл. [37]
Динамические структуры данных реализуются в Модуле-2 при помощи указателей. Поэтому программы, в которых применяются динамические структуры данных, обязаны использовать указатели. Очевидно, что указатели не следует использовать, и в практике программирования на Модуле-2 их никогда не применяют в более тривиальных обстоятельствах. Риск, связанный с использованием указателей, несколько снижается благодаря тому, что большинство программистов, достаточно изощренных, чтобы использовать динамические структуры, умеют с ними обращаться. [38]
Основным новым инструментом для работы с динамическими структурами данных служит указатель. Указатель ( POINTER) - это переменная, которая указывает на динамически размещенную переменную. В системном программировании допустимо и более гибкое применение указателей. [39]
Основное преимущество использования бинарного поиска по сравнению с динамическими структурами данных заключается в экономии используемого объема памяти. Как правило, индексные указатели текста огромны, поэтому бинарный поиск может оказаться более предпочтительным, т.к. гарантировано обеспечивает логарифмическую зависимость времени поиска, но при этом задействуется лишь одна треть объема памяти, используемого методами, основанными на деревьях. Однако, при наличии достаточного объема доступной памяти TST-деревья позволяют реализовать более быстрые операции search для многих приложений, поскольку, в отличие от бинарного поиска, перемещение по ключам выполняется без возвратов. [40]
Вообще говоря, указатели совместимы только с указателями того же самого типа, но значение NIL совместимо со всеми типами указателей. Это значение обычно используют для того, чтобы пометить концевой элемент динамической структуры данных, хотя для этого можно использовать и какую-либо иную технику. [41]
Переменная процедурного типа - переменная, используемая для активации любой процедуры с совместимыми параметрами и результатом. Переменная процедурного типа служит для процедур тем же, чем указатели для динамических структур данных. [42]
 |
Прямая и косвенная ссылки на переменную. [43] |
В главе 6 исследуется использование указателей со структурами. Глава 15 знакомит с техникой управления динамической памятью и содержит примеры создания и использования динамических структур данных. [44]
ПОИСКЕ ПЕРЕСЕЧЕНИЙ С ОРТОГОНАЛЬНЫМИ ОТРЕЗКАМИ, в которой требуется найти среди N заданных горизонтальных и вертикальных прямолинейных отрезков все пересекающие заданный ортогональный запросный отрезок. Для случая, когда в данной задаче разрешены вставки и удаления отрезков, Мак-крейт предложил динамическую структуру данных [ McCreight ( 1981) ], которая требует 0 ( N) памяти и 0 ( log2 N - - К) времени, где 0 ( N) выражает мощность множества различных значений координат. Недавно Эдельсбруннер и Маурер [ Edelsbrunner, Maurer ( 1981) ] унифицировали некоторые из ранее упомянутых методов решения данного класса задач о поиске пересечений и получили следующие результаты. [45]
Страницы: 1 2 3 4