Реферат: Отображение АСД на СДХ

По организации поля указатель на другое звено:

-однонаправленные;

-двунаправленные;

-мультиссылочные (когда один элемент структуры связан с несколькими другими элементами).

Заметим, что в случае мультиссылочного звена по некоторым направлениям мы можем иметь двунаправленную связь между звеньями, а по некоторым - однонапрвленную.

2.3. Представление графов

При представлении графов можно использовать несколько подходов:

- использовать звенья только для представления вершин, а дуги отображать через указатели; недостатком здесь является то, что негде отобразить информацию, например, о весе дуги, а так же - в случае неориентированного графа одной дуге будет соотвествовать два указателя.

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

- наконец можно ввести два вида звеньев один для представления дуг, другой для представления вершин; звенья-дуги увязываются в список, звенья-вершины также увязываются в список с перекрестными ссылками между списками.

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

2.4. Представление стека и очереди

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

type

звено = record тело: char; следующий:связь end;

связь = Iзвено;

var тело:char;

стек:связь;

procedure загрузить (тело:char;var стек:связь);

var элемент:связь;

begin new(элемент); элементI.тело:=тело;элементI.следующий:=стек;

стек:=элемент

end{загрузить}

procedure выгрузить (var тело:char;var стек:связь);

var использованный:связь;

begin ifnot(стек = nil) then

begin тело := стекI.тело; использованный:= стек;

стек:=стекI.следующий; dispose(использованный) end

else write ('стекпуст')

end{загрузить}

Обратите внимание на значение оператора dispose.