Файл: Зингер И.С. Обеспечение достоверности данных в автоматизированных системах управления производством.pdf

Понятие «списка» и «списковой структуры» данных уни­ версальное. Например, структуру данных типа «дерево» можно представить как некоторую структуру, образую­ щую списки с иерархической ссылкой, между элементами списков. В этом случае деревья не должны иметь мно­ гократных ссылок, так как это может привести к более чем одному пути, сходящемуся па данном элементе или к циклам и контурам из элементов списков этой структу­ ры. «Цепная», или «решетчатая», структура является структурой как с иерархической, так и с многократной ссылкой [16]. Цепные списки фундаментально исследова-^ ны А. И. Китовым [10].

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

«Дерево» — направленный граф, в котором есть един и только один узел, называемый корнем, такой, что для любого узла х существует один и только один путь, начи­ нающийся с корня и кончающийся узлом я» [17, стр. 58]Г Существуют и другие определения дерева. Например, деревом называется связный граф, не содержащий циклов; такой граф, в частности, не имеет и кратных ребер. Из определения дерева вытекает также, что для каждой пары его вершин существует единственная соединяющая их цепь. Если граф, вообще говоря, не связный, не содержит циклов, то каждая его связная компонента будет деревом. Узлы дерева распределены по ярусам. На первом яру­ се находится только корень; к /-му ярусу принадлежат

все узлы, путь к которым от корня имеет длину / — 1. Множество узлов, путь к которым от узла» ж имеет длину 1 называется частным множеством узла х.

Многие структуры, называемые в литературе «деревья­ ми», имеют более сложную систему перекрестных ссылок по сравнению с тем, что допускает прямое определение де­ ревьев в работе [17].

Рассмотрим некоторые типы структур данных, органи­ зация которых может быть интерпретирована в виде де­ рева.

В работе [18] представлена информационная структура,

22

(за исключением узлов последнего уровня) состоят ровно из двух элементов. В каждом частном множестве один узел условно называется левым, другой — правым.

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

Узлу дерева х соответствует группа ячеек рабочего поля, содержащих код некоторого признака Rx и три адреса, два из которых—начальные адреса групп ячеек,

узла х. Построение дерева выполняется таким образом, что значения узлов левой ветви любого узла со значением R меньше Rx, а значения узлов правой ветви — больше [17].

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

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

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

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

\~ Любая таблица в общем случае имеет вид табл. 2. Как принято, наименованиями строк таблиц служат наименования объектов, а наименования граф (столбцов)

23

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

Значения характеристик (ац) могут выражаться чис­ лами и алфавитно-цифровым текстом. Вычисляемые ац могут быть функцией значений характеристик как данной таблицы, так н других таблиц. Значение характеристики (aji) одной таблицы может быть объектом или группой объ­ ектов других таблиц.

Запись информационных таблиц в память ЭВМ произ­ водится с разверткой по столбцам, т: е. в явном виде за­ даются связи значений характеристик с их наименования­ ми, а связи значений характеристик с объектами отра­ жаются позициями характеристик в столбце. Такая за­ пись вызвана необходимостью производить расчеты в

^ большинстве случаев не для отдельных объектов, а для

• класса характеристик.

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

24

может быть отличным от нуля (равен 1), т. е. матрица является нуле-единичной. Это указывает на родо-видовые отношения двух объектов — объект Nf может быть «ча­ стью» только одного объекта («целого») таблицы tk.

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

Более сложные отношения между двумя комплексами объектов представлены в табл. 4.' Это могут быть отноше­ ния такого вида, как связь объектов — наименований продукции — с объектами — наименованиями материаль­ но-сырьевых ресурсов. Эта связь, как правило, имеет ко­ личественные оценки (а$ч). Кроме того, наименования ма­

25

табл. 2, построенной для комплекса объектов Np, служат характеристиками (например, рубрики: сырье со стороны, вспомогательные материалы, топливо, полуфабрикаты, реагенты и т. д.). Хранить такую таблицу в развернутом виде нерационально, так как она содержит незначитель­ ное число а)% =j= 0. (Как правило, в практических задача a)i =f= 0 не превышает 2%) . Однако необходимо учитывать возможность появления элемента, отличного от нуля, с любыми координатами [19].

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

Из других способов использования табличного метода организации информационных массивов следует указать на организацию памяти типа «матричный каталог» [17].

Рассмотрим соответствующие оценки эффективности для некоторых типов информационных структур.

При последовательном способе построения списков слова, представляющие отдельные элементы массива, размещаются в последовательно расположенных ячейках машинной памяти [10]. Различают списки с упорядочен­ ным расположением элементов по какому-либо признаку и неупорядоченные.

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

26

однако, затруднен поиск элемента при решении задач й при исключении либо изменении содержимого элемента.

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

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

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

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

шинном массиве); число сдвигов элементов массива при внесении измене­

ний — S;

объем дополнительной памяти, выраженной числом элементов массива,— W.

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

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

Максимальное время поиска одного элемента, если он имеется в данном массиве, по способу перебора равно времени, которое необходимо для просмотра всех элемен­ тов массива:

27