24. Различные представления графа
Для реализации графа в виде списка инцидентности можно использовать следующий тип:
Type List = ^S;
S = record;
inf: Byte;
next: List;
end;
Тогда граф задается следующим образом:
Var Gr: array[1..n] of List;
Теперь обратимся к процедуре обхода графа. Это вспомогательный алгоритм, который позволяет просмотреть все вершины графа, проанализировать все информационные поля. Если рассматривать обход графа в глубину, то существуют два типа алгоритмов: рекурсивный и нерекурсивный.
На языке Pascal процедура обхода в глубину будет выглядеть следующим образом:
Procedure Obhod(gr: Graph; k: Byte);
Var g: Graph; l: List;
Begin
nov[k]:= false;
g:= gr;
While g^.inf <> k do
g:= g^.next;
l:= g^.smeg;
While l <> nil do begin
If nov[l^.inf] then Obhod(gr, l^.inf);
l:= l^.next;
End;
End;
Представление графа списком списков
Граф можно определить с помощью списка списков следующим образом:
Type List = ^Tlist;
Tlist = record
inf: Byte;
next: List;
end;
Graph = ^TGpaph;
TGpaph = record
inf: Byte;
smeg: List;
next: Graph;
end;
При обходе графа в ширину мы выбираем произвольную вершину и просматриваем сразу все вершины, смежные с ней.
Приведем процедуру обхода графа в ширину на псевдокоде:
Procedure Obhod2(v);
Begin
queue = O;
queue <= v;
nov[v] = False;
While queue <> O do
Begin
p <= queue;
For u in spisok(p) do
If nov[u] then
Begin
nov[u]:= False;
queue <= u;
End;
End;
End;
25. Объектный тип в Pascal
Понятие объекта, его описание и использование
Объектно-ориентированный язык программирования характеризуется тремя основными свойствами:
1) инкапсуляцией. Комбинирование записей с процедурами и функциями, манипулирующими полями этих записей, формирует новый тип данных – объект;
2) наследованием. Определение объекта и его дальнейшее использование для построения иерархии порожденных объектов с возможностью для каждого порожденного объекта, относящегося к иерархии, доступа к коду и данным всех порождающих объектов;
3) полиморфизмом. Присваивание действию одного имени, которое затем совместно используется вниз и вверх по иерархии объектов, причем каждый объект иерархии выполняет это действие способом, именно ему подходящим.
Говоря об объекте, мы вводим в рассмотрение новый тип данных – объектный. Объектный тип является структурой, состоящей из фиксированного числа компонентов. Каждый компонент является либо полем, содержащим данные строго определенного типа, либо методом, выполняющим операции над объектом.
Объектный тип может наследовать компоненты другого объектного типа. Если тип T
Следующий исходный код приводит пример описания объектного типа.
function Contains(P: Point): Boolean;
end;
В отличие от других типов объектные типы могут описываться только в разделе описаний типов, находящемся на самом внешнем уровне области действия программы или модуля. Таким образом, объектные типы не могут описываться в разделе описаний переменных или внутри блока процедуры, функции или метода.
Тип компоненты файлового типа не может иметь объектный тип или любой структурный тип, содержащий компоненты объектного типа.
26. Наследование
Наследование – это процесс порождения новых типов-потомков от существующих типов-
