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

довых списков. Кроме того, списки подразделяют на одно­ направленные, двунаправленные и списки^выборки эле­ ментов по правилам L I F O , FIFO и LOFIFO [15].

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

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

L I F O — сокращение, используемое в теории очередей

всегда движется в противоположном направлении при чте­ нии списка в отличие от направления движения при фор­ мировании списка в памяти ЭВМ. Списки типа L I F O часто называют также «последовательно выталкиваемыми»

чают выбор и обработку первого из поступивших в систе­ му элементов списка и «произвольную» обработку (first i n - first out — «первый в очереди обслуживается первым» и last or first i n - first out — «последний или первый — об­ служивается первым»).

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

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

20

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

Различают следующие виды отсылок: перекрестную, боковую, иерархическую и многократную [16].

Перекрестная ссылка в данных заключается в том, что между различными частями структур упорядоченных дан-

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

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

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

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

иерархические ссылки. В таких структурах данные спис­ ки могут иметь элементы, которые сами являются списками.

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

21