Файл: Оперативные графические системы в автоматизации проектирования..pdf

димо отметить элементы во всех списках и подсписках структуры.

В качестве примера рассмотрим алгоритм чистки па­ мяти в случае применения однонаправленного узлового списка [10]. Приведенный алгоритм является эффектив­ ным как по объему рабочей памяти, так и по количеству проходов по одним и тем же элементам списков и при­ годен для прохождения по элементам любой списочной структуры с любым числом адресов перехода к подспис­ кам.

Каждый элемент с.с.д. представляется блоком, со­ стоящим из одной ячейки, разделенной на 4 поля. В поле, названном СВЯЗЬ, содержится адрес связи, указываю­ щий на следующий элемент списка. Поле ЗАГОЛОВОК содержит атом или адрес перехода к подсписку. Два поля ЗНАК и УКАЗАТЕЛЬ ПЕРЕХОДА используются специально для алгоритма чистки памяти. На рис. 6. 23, а приведен список {А. ((£>. (Е. (...).В. (С))), который необ­ ходимо пройти в первом шаге чистки. Первоначально знак всех элементов положительный. При прямом прохо­ де по элементам списка (от качала к концу) игнориру­ ются переходы к подспискам, адреса связи пройденных элементов только реверсируются, и в поле ЗНАК этих элементов записывается минус. Реверсирование адресов связи, т. е. изменение прямых адресов связи на обрат­ ные, позволяет в случае однонаправленного списка вер­ нуться к заголовку списка в процессе чистки памяти. Первый проход заканчивается в том случае, если встречен элемент с признаком конца списка пли очеред­ ной элемент имеет в поле ЗНАК минус, показывающий, что этот элемент входит в подсписок ранее пройденного списка. В результате прямого прохода списочная струк­ тура представляется так, как показано на рис. 6.23, б. После окончания прямого прохода начинается обратный проход (от конца списка к началу), при котором восста­ навливаются адреса связи и проверяется поле ЗАГОЛО­ ВОК на наличие в нем адреса перехода к подсписку. Если обнаружен элемент с адресом перехода, то его УКАЗАТЕЛЬ ПЕРЕХОДА устанавливается в единицу (рис. 6.23, в) . После этого начинается прямой проход подсписка и выполняются те же действия, что и при пря­ мом проходе списка. На рис. 6.23, г приведен подсписок после прямого прохода.

189

а

5

г

В процессе обратного прохода подсписка будут прой­ дены и отмечены все подсписки данного подсписка, после чего необходимо возвратиться к началу основного списка. Далее, аналогично следует отметить следующий список п т. д., пока не будут пройдены все списки. На этом пер­ вый шаг оканчивается.

Во втором шаге необходимо последовательно проска­ нировать всю память п всякий элемент с плюсом пере­ дать в список свободных ячеек. Элементы с минусом используются в структуре, поэтому их ЗНАК устанавли­ вается в плюс, т. е. они подготавливаются для следующе­ го процесса чистки. После создания списка свободных ячеек возобновляется выполнение программы.

Блок-схема программы, осуществляющей первый шаг чистки (прямой и обратные переходы), приведена на рис. 6.24, а, б. Для удобства начертания блок-схемы эле­ менты списка пронумерованы последовательно, т. е. эле­ мент /+ 1 расположен в списке за элементом I (адрес элемента /4-1 находится в поле СВЯЗЬ элемента /).

В программе для временного хранения адресов связи используются два индексных регистра п сумматор, хотя можно использовать любые три ячейки памяти. Первая ячейка содержит адрес предыдущего элемента, вторая — адрес элемента, который в данный момент проверяется, третья — адрес следующего элемента списка. Это явля­ ется необходимым для реверсирования адресов связи при прямом проходе и восстановлении их при обратном про­ ходе.

В случае использования списков, в которых адрес свя­ зи последнего элемента указывает на заголовок списка пли подсписка, отпадает необходимость реверсировать адреса связи при прямом проходе, а также не надо де­ лать обратный проход, так как оба эти действия необхо­ димы для возвращения к заголовку списка (подсписка). Представление сложной списочной структуры в виде на­ правленного графа в данном случае является не только наглядным, но необходимым средством при разработке алгоритма чистки памяти. На графе можно легко отме­ тить порядок просмотра и отметки элементов. Первый шаг чистки реализуется с помощью алгоритма, блоксхема которого представлена на рис. 6.25.

Этот же алгоритм с некоторыми изменениями можно применить для чистки памяти в случае с.с.д. с двухна-

191

правленнымм кольцами. Для этого алгоритм должен быть модифицирован следующим образом:

1.Когда список встречается впервые, необходимо проверить, не был ли он уже ранее пройден.

2.Когда встречается элемент, определяющий подспи­

сок (т. е. его И Д =1, рис. 6.19), прямой адрес, связи (ПАС) заголовка, указывающий па последний элемент подсписка, изменяется на адрес, который указывает об­ ратно на элемент, определяющий подсписок. Это необхо­ димо для перехода в дальнейшем к основному списку.

Рис. 6.24. Алгоритм чистки памяти для однонаправленного

192

3. Когда проходится список (подсписок), всегда со­ храняется адрес предыдущего отмеченного элемента. При достижении последнего элемента, прямой адрес которого указывает на заголовок, сохраненный адрес использует­ ся для восстановления ранее измененного прямого адре­ са связи заголовка, а находящийся в этом поле адрес используется для возвращения к тому месту основного списка, с которого произошел переход к подсписку. Затем продолжается сканирование и отметка элементов основ­ ного списка. Рассмотренный алгоритм чистки памяти оказывается более эффективным, чем метод подсчета ссылок для той же структуры с двухнаправлепнымп кольцами.

б

списка: а — алгоритм прямого прохода; б — обратного прохода

в х о д

Рис. 6.25. Блок-схема алгоритма прямого прохода узлового списка с кольцами

Древовидные и иерархические структуры данных

Используя основные структуры — цепные и узловые списки, можно построить более сложные организации данных — древовидные п иерархические. Эти структуры широко применяются в информационно-поисковых систе­ мах, системах обработки данных, графических системах.

Определение древовидной структуры. Древовидная структура может быть описана конечным связанным графом G— (A, U), не содержащим контуров, с корнем в вершине /1:6 А, в которую не заходит ни одна дуга, с вер­ шинами, неравными А ь в каждую из которых заходит одна единственная дуга. Длина пути от корня к любой вершине определяет уровень, на котором находится данная вершина.

Древовидная структура является обобщением узлово­ го списка, так как информация может храниться не толь­ ко в висячих, но п в любых других вершинах графа. Дре­ вовидная структура п определяющий ее граф представ­ лены на рнс. 6.26, а, б.

В такой структуре любой блок может быть с е я з э н с блоком, расположенным на том же уровне, либо с бло­ ком нижнего уровня, но не с блоком, размещенным на более высоком уровне.

л,

Рис. 6.26. Древовидная структура данных: а, б — представление и

граф древовидной структуры

Представление древовидной структуры в памяти. Раз­ личные методы представления цепных и узловых списков могут быть использованы при рассмотрении древовидной структуры. Так, если вершины древовидной структуры представить блоком, содержащим информацию п адреса связи, указывающие на вершины ппжнего уровня, то все дерево А изображенное на рис. 6.27, а, может храниться в памяти так, как показано на рис. 6.27, б.

Основным недостатком такого представления являет­ ся уменьшение гибкости структуры, так как нельзя увели­ чить количество вершин, связанных с данной вершиной, более чем позволяет заранее выбранный максимальный размер блока. Для ликвидации этого недостатка можно дерево D преобразовать в однонаправленное дерево, каж­ дая вершина которого представляется блоком, показан­ ным на рис. 6.28, а. Тогда дерево D приобретает вид, изо­ браженный на рис. 6.28,6.

196

Рассмотрим два примера организации данных в виде деревьев в информационно-поисковых и оперативных графических системах.

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

а

6

ДАННЫЕ

Адрес связи, указывающий на соседнюю вершину данного уровня

Рис. 6.28. Второй вариант организации древовидной структуры (одно­ направленное дерево): а — блок структуры; б—представление дерева

вершине двоичного дерева.

Опишем вариант построения двоичного дерева, орга­ низующего массив.

Первый элемент массива поместим в корень дерева. Сравнивая значение Р2 признака второго элемента со значением Р i признака элемента, помещенного в корень дерева (т. е. первого элемента), выполним следующие процедуры:

1.Если Р2< Р и пририсуем к корню дугу, направлен­ ную влево, и поместим второй элемент в конце этой дуги.

2.Если Р2^ Р \ , то сделаем то же самое, но дугу на­

правим вправо.

Этот же процесс повторяется и в случае выбора места на дереве для г-го элемента, причем при размещении это­ го элемента просматривается путь по дереву, выходящий всегда из корня.

197

Если в исходном массиве значения признака встреча­ ются в последовательности 5, 8, 2, 6, 1, 3, 7, .... то двоич­ ное дерево строится в той очередности, которая показана на рис. 6.29, а. Каждая вершина дерева может быть пред­ ставлена блоком, содержащим значение признака п два адреса связи, указывающих на элементы с меньшим (ле­ вая дуга) п большим (правая дуга) значениями призна­ ка. Тогда двоичное дерево приобретает вид, изображен­ ный на рис. 6.29, б. Основным преимуществом организа­ ции массива в виде двоичного дерева является снижение трудоемкости поиска элементов. Так, если элементы в массиве перемешаны хаотически, т. е. вероятность слу­ чайного появления полностью упорядоченной последова­ тельности мала, то среднее число сравнений для поиска одного элемента среди элементов двоичного дерева опре-

Рис. 6.29. Двоичное дерево: а — последовательность построения де­ рева; б — представление двоичного, дерева

198

деляется величиной порядка logVT в то время как в слу­ чае упорядочения массива в линейную последователь­ ность.эта величина равна п/2. Организация элементов в виде дерева с использованием адресов связи позволяет динамически изменять структуру, достраивая дерево или изменяя элементы в нем.

Использование древовидной структуры для прострое­ ния массива команд отображения. Последовательная структура, используемая в некоторых графических систе­ мах для создания массива команд отображения, являет­ ся недостаточно эффективным средством, так как тре­ бует усложнения программ поиска элементов изображе­ ния и их модификации, связанного часто с перестроением всего массива. Все это приводит к увеличению времени реакции системы, либо вынуждает применять в одной си­ стеме несколько структур: одну, способную осуществить быстрые преобразования в структуре и служащую непо­ средственно для реализации графического диалога, дру­ гую—для организации массива команд отображения, ко­ торый используется для поддержания изображения на экране ЭЛТ. Такое решение ведет к лишнему расходу памяти.

Рис. G.30. Использование древовидной структуры для записи элек­ тронной схемы: а — многозвенный RC фильтр; б — элементы одного звена фильтра; п — древовидная структура

199

1