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

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

Существуют четыре основных способа организации массивов [13]: последовательно-смежный; цепной; с ветвящейся структу­ рой; списковой структуры. Последовательно-смежный способ заключается в том, что за п-й записью непосредственно следует п + 1-я запись. Такой метод позволяет создавать довольно про­ стые программы обработки информации и хранить записи в ком­ пактной форме, что способствует экономии объема памяти ЭВМ. В общем случае запись произвольной формы с полями переменной длины и произвольным количеством характеристик выглядит так:

Поле

специальные символы типа «:», «;», «,», «=», «.», .«*», «X», которые ставят в конце наименования признака, его значения и в конце записи объекта. Если используются поля фиксированной длины при произвольном количестве характеристик в описании объекта, символы «конец поля» не нужны:

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

133

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

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

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

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

вявном виде. Тогда программа может самостоятельно определить,

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

(9)

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

134

тельно по мере поступления, начиная с начала массива. Возможен вариант последовательного занесения записей в массив и от конца к началу. При упорядоченной организации массива записи рас­ полагают в порядке возрастания или убывания значения какойлибо характеристики, называемой ключевым словом. Если, на­ пример, в качестве такого слова взята характеристика НОМЕР ЧЕРТЕЖА ДЕТАЛИ, то записи с описанием детали будут располагаться в порядке возрастания (убывания) номера чертежа детали, т. е. у каждой последующей записи значение номера чертежа будет больше (меньше), чем у предыдущей. Возможен выбор ключевых слов по нескольким характеристикам. Например, описание технологических операций может быть упорядочено по номеру цеха и коду оборудования, на котором выполняется опе­ рация. Ключевое слово в этом случае состоит из двух характе­ ристик: НОМЕР ЦЕХА, КОД ОБОРУДОВАНИЯ. Записи, упорядоченные по значению данного ключевого слова, распо­ лагаются в порядке возрастания числа, выражающего номер цеха. Внутри группы с одинаковым номером цеха записи идут в порядке возрастания кода оборудования. Следовательно, весь массив будет разделен на группы, внутри которых записи имеют одинаковый номер цеха и код группы оборудования. Если массив упорядочен по одной характеристике, а поиск идет по другой то по отношению к последней массив является неупорядоченным.

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

Пусть, например, имеем следующие значения поисковых при­ знаков: КОД ОПЕРАЦИИ = 120 (токарная операция), габарит детали: L = 60, максимальный диаметр D — 30. В результате

135

поиска могут быть выбраны записки с характеристиками станков мод. 1615М, 1П61, 1А62, 1М620, 1620, 1П625 и т. д.

Введем некоторые обозначения. Ключевое слово будем обо­ значать следующим образом: Х к — хк, где Х к — наименование характеристики, по которой идет поиск и, следовательно, входя­ щей в ключевое слово, а хк — ее значение. Если ключевое слово

рения поиска в упорядоченном массиве с последовательно-смеж­ ным расположением записей применяют способ последовательного деления на части [22 ]. Весь массив из N записей делят на п частей и вместо последовательного просмотра на X характеристике ведут

на п частей, но при этом шаг уже становится в п раз меньше,

ит. д. Процесс сужения области поиска продолжают до тех пор, пока не будет выполнено условие х,- = хк.

При этом способе поиска минимальное число циклов, где под циклом понимается совокупность арифметических и логических операций, связанных с просмотром одной записи, достигается при п = 2. В этом случае способ называется «делением пополам»

ичисло циклов I ^ log2 N. Для массива из 10 тыс. записей при последовательном переборе число просмотров в среднем будет составлять около 5000, а при способе деления пополам / = log2

свободные места (записи или их группы не являются смежными). Это удобно для внесения новых записей без их сдвига. Во многих случаях целесообразно все записи разделить на группы (подмас­ сивы) по какой-либо характеристике и внутри каждой группы оставить место для внесения новых записей. Группы, в свою очередь, могут иметь плотное или свободное расположение внутри данного массива. Например, массив с характеристиками обору­ дования можно разделить по типам оборудования в соответствии с классификацией ЭНИМСа на 65 групп записей. Внутри каждой из них собираются характеристики оборудования одного типа, но отличающиеся по типоразмерам и модификациям. Добавление новых моделей оборудования .производится в свободные места

136

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

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

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

Кроме того, в каждой графе могут указываться параметры, определяющие структуру записи, например, ее длину, количество и длину полей и т. д. При машинной реализации внешнего ука­ зателя каждая графа таблицы представляет собой запись с описа­ нием, хотя и неполным, характеристик некоторой другой записи с адресом at, т. е. описание некоторого объекта. Поэтому внешний указатель можно рассматривать как массив записей, к которому применимы все рассматриваемые методы поиска и организации массивов. Скорость поиска записей при наличии внешних указа­ телей зависит от способов поиска информации во внешнем ката­ логе. Проследим это на примере организации массива с характе­ ристиками оборудования. Внешний указатель (каталог) можно создать таким, чтобы в каждой его записи содержался код модели оборудования и адрес записи с характеристиками оборудования этой модели. Поиск таких характеристик по данному коду осу­ ществляется либо перебором кодов моделей, либо делением попо­ лам, если записи внешнего указателя упорядочены по коду мо­ дели. При объеме в 250 записей на их перебор в среднем понадоби­ лось бы 120 циклов, а при делении пополам — 9 циклов. Если записи разделены на группы по типам оборудования, то внешний каталог можно организовать по-иному, например использовав вместо кода модели автомата двухзначный десятичный код, первая цифра которого выражает группу, а вторая — тип оборудования. При объеме указателя, равном 65 записям, число циклов при деле­ нии пополам равно 5, т. е. поиск внутри найденной группы записей осуществляется перебором в среднем за 5 циклов.’ Хотя в рассма­ триваемых вариантах число циклов поиска примерно одинаково, второй вариант удобнее с точки зрения внесения новой информа­ ции. В первом случае запись о новой модели оборудования зано­ сится в любое место массива, а информация об этой записи фикси­ руется во внешнем каталоге. Причем в указателе она помещается

137