Файл: Митрофанов, С. П. Автоматизация технологической подготовки серийного производства.pdf

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

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

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

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

138

ВУ — внешний указатель; АС — адрес связи

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

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

В отличие от списков, в которых записи последовательно соеди­ нены в цепочку адресами связи, так называемые «цепные списки» для ускорения поиска могут быть снабжены более чем одним вну­ тренним указателем и организованы в более сложные списки [10]. В первую очередь это относится к записям, из которых образован внешний каталог и которые физически разнесены в памяти ЭВМ. Структура записи в этом случае

Xyi АСх а с 2 АС3

где АСх — адрес записи, на которую происходит переход при выполнении условия хк < ху1\ АС3 и АС3 адреса записи соответ­ ственно для условий хк = xyi и хк > xyi.

139

Таким образом, переход к тому или иному адресу связи зави­ сит от результатов сравнения значения хк характеристики, обра­ зующей ключевое слово со значением ху1 одноименной характе­ ристики, входящей в запись. Адреса связи могут указывать либо на следующую запись внешнего указателя, либо на запись самого объекта. Скорость поиска при правильном выборе значений xyi приближается к скорости поиска при способе деления пополам, а количество записей во внешнем указателе равно примерно поло­ вине количества записей в массиве с характеристиками объекта. Процедура внесения изменений достаточно проста и заключается в поиске записи, в которой необходимо сделать ссылку на вводи­ мую информацию, или внесении новой записи во внешний указа­ тель. Аналогичным образом образуется указатель для поиска по признаку, значения которого выражены алфавитно-цифровой информацией, но сравнение ведется лишь по условию «равно» или «не равно». Данный способ организации списков может быть использован для опознания и кодирования длинных фраз, выра­ жающих значения некоторых признаков в программах-трансля­ торах с внешнего на внутренний язык описания объектов. Замена фразы эквивалентным ей кодом удобна для обработки информации и компактного ее представления внутри ЭВМ.

Более сложно организованы списки, названные А. Н. Китовым «ассоциативными списками с узловой структурой» [10]. Рассмо­ трим их использование на примере массива с описанием деталей. В данном случае «узлами» являются записи с описанием деталей, причем каждый узел «пронизан» списками, соединяющими в це­ почки детали с одинаковыми значениями некоторых характеристик. Например, для каждого значения кода типового элемента детали создается свой список, в котором объединяются записи, имеющие это значение. В любой записи каждый элемент, входящий в спи­ сок, снабжается внутренним указателем на следующий член списка. Структура внутреннего указателя, закрепленного за кодом элемента детали, имеет вид

Код элемента АС НП

где АС — адрес связи с записью, имеющей в своем составе элемент с тем же кодом и являющейся следующим членом списка, НП — номер поля записи с адресом АС. Для указания начала и конца списка, а также числа записей в списке создается внешний указа­ тель (табл. 23).

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

140

Таблица 23

Схема организации списков и поиска по коду элемента в массиве с описанием деталей

. .

I к ВУ

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

вуказателе. После того, как пройдены все записи данного списка

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

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

ствуют только записи с адресами 3), 5). К достоинствам данного способа относится простота поиска необходимых записей по задаваемым условиям, возможность поиска по характеристикам, не привязанным жестко к определенным полям записей. Напри­ мер, коды элемента детали могут быть зафиксированы в любых полях записи с описанием детали, но в то же время не нужен поиск элемента с нужным кодом внутри записи. Добавление новых записей является несложной процедурой. Их заносят в конец всех записей на свободное место и затем определяют, в какие списки входят характеристики объекта. Внутренние указатели корректируют только для последних в списках записей, к которым относится включаемая. Аналогично проводят корректирование во внешнем указателе для соответствующих списков. Данный метод организации массива целесообразно применять для поиска в большом массиве по небольшому числу характеристик, могущих принимать ограниченное число значений (до 200—500). Когда необходимо вести поиск по характеристикам, принимающим боль­ шое число значений, данный способ непригоден.

Пусть длина детали может колебаться от 1 до 500 мм. Если оформлять список на эту характеристику, то во внешнем каталоге будет столько строк, сколько значений длин деталей имеется в массиве с описанием деталей. Списки будут короткими, так как число деталей в списке с какой-либо длиной невелико, а коли­ чество списков по данной характеристике в пределе может дости-

142