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

Этот метод является менее эффективным, чем первый, так как требует большего числа проб на поиск элемента. Это происходит за счет того, что после нескольких «столкно­ вений» элементы имеют тенденцию группироваться, так как вероятность столкновения элементов в ячейке с ад­ ресом /+1, если ячейка с адресом I уже занята, стано­ вится больше средней вероятности по всей таблице.

ТАБЛИЦА ЭЛЕМЕН­

ТОВ

ИДЕНТИ­ ФИКАТОР

Рис. 6.4. Связь элементов в список при формировании таблицы

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

Когда необходимо определить, находится ли элемент с данным идентификатором в таблице, по идентифика­

168

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

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

1) если ячейка с этим адресом окажется свободной, то новый элемент помещается в ней;

2) если ячейка занята заголовком списка, связыва­ ющего все элементы с одинаковыми вычисленными адре­

с помощью адреса связи включается в список, начинаю­ щийся с вычисленного адреса;

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

Принципиальным недостатком данного метода явля­

числу проб, необходимых для поиска свободной ячейки, в которую требуется поместить новый элемент, можно заключить, что:

1) в том случае, если таблица свободна или только начала заполняться, существует малая вероятность «столкновений» и среднее число проб во всех методах близко к нулю;

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

Ряд сложных структур данных, построенных на осно­ ве метода кодирования по идентификатору в сочетании

169

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

Цепные списки. Определение цепного списка. Цепной

Рмс. 6.5. Цепной список: а — представление цепного списка символов; б — граф цепного списка

Рис. 6.6. Представление цепного списка символов в памяти (несколь­ ко слов на блок)

а-2, .... и/,} образует единственный простой путь, а для вер­ шин справедливы следующие условия:

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

на рис. 6. 6.

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

171

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

Рис. 6.7. Представление цепного списка символов в памяти (одно слово па блок)

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

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

В том случае если машина оперирует с байтами ин­ формации, а данные и адреса связи можно разместить в одной ячейке, то расход памяти при этом уменьшается в

172