А. Цветкова - Информатика и информационные технологии

На языке 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;

Объектно-ориентированный язык программирования характеризуется тремя основными свойствами:

1) инкапсуляцией. Комбинирование записей с процедурами и функциями, манипулирующими полями этих записей, формирует новый тип данных – объект;

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

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

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

Объектный тип может наследовать компоненты другого объектного типа. Если тип T2 наследует от типа T1, то тип T2 является потомком типа Г, а сам тип Г, является родителем типа Г2.

Следующий исходный код приводит пример описания объектного типа.

type

Point = object

X, Y: integer;

end;

Rect = object

A, B: TPoint;

procedure Init(XA, YA, XB, YB: Integer);

procedure Copy(var R: TRectangle);

procedure Move(DX, DY: Integer);

procedure Grow(DX, DY: Integer);

procedure Intersect(var R: TRectangle);

procedure Union(var R: TRectangle);

function Contains(P: Point): Boolean;

end;

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

Тип компоненты файлового типа не может иметь объектный тип или любой структурный тип, содержащий компоненты объектного типа.

Наследование – это процесс порождения новых типов-потомков от существующих типов-родителей, при этом потомок получает (наследует) от родителя все его поля и методы.

Тип-потомок, при этом, называется наследником или порожденным (дочерним) типом. А тип, которому наследует дочерний тип, называется порождающим (родительским) типом.

Наследуемые поля и методы можно использовать в неизменном виде или переопределять (модифицировать).

Н. Вирт в своем языке Паскаль стремился к максимальной простоте, поэтому он не стал его усложнять введением отношения наследования. Поэтому типы в Паскале не могут наследовать.

Однако Turbo Pascal 7.0 расширяет этот язык для поддержки наследования. Одним из таких расширений является новая категория структуры данных, связанная с записями, но значительно более мощная. Типы данных в этой новой категории определяются с помощью нового зарезервированного слова Object. Синтаксис при этом очень похож на синтаксис определения записей:

Type

<имя типа> = Object [(<имя типа родителя>)]

([<область действия>]

<описание полей и методов>)+

end;

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

Область действия есть одно из следующих ключевых слов:

– Private;

– Protected;

– Public.

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

Подробнее об областях действия компонент рассказано в вопросе № 28.

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

Экземпляр объекта создается посредством описания переменной или константы объектного типа или путем применения стандартной процедуры New к переменной типа «указатель на объектный тип». Результирующий объект называется экземпляром объектного типа.

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

Присваивание экземпляра объектного типа не подразумевает инициализации экземпляра. Объект инициализируется кодом, генерируемым компилятором, который выполняется между вызовом конструктора и моментом когда выполнение фактически достигает первого оператора в блоке кода конструктора.

Если экземпляр объекта не инициализируется и проверка диапазона включена (директивой {$R+}), то первый вызов виртуального метода экземпляра объекта дает ошибку этапа выполнения. Если проверка диапазона выключена директивой {$R—}), то первый вызов виртуального метода неинициализированного объекта может привести к непредсказуемому поведению.

Правило обязательной инициализации применимо также к экземплярам, которые являются компонентами структурных типов. Например:

var

Comment: array [1..5] of TStrField;

I: integer;

begin

for I:= 1 to 5 do

Comment [I].Init (1, I + 10, 40, 'первое_имя');

.

.

.

for I:= 1 to 5 do Comment [I].Done;

end;

Для динамических экземпляров инициализация, как правило, связана с размещением, а очистка – с удалением, что достигается благодаря расширенному синтаксису стандартных процедур New и Dispose. Например:

var

SP: StrFieldPtr;

begin

New (SP, Init (1, 1, 25, 'первое_имя');

SP^.Put ('Владимир');

SP^.Display;

.

.

.

Dispose (SP, Done);

end.

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

Область действия идентификатора компоненты простирается за пределы объектного типа. Более того, область действия идентификатора компонента простирается сквозь блоки процедур, функций, конструкторов и деструкторов, которые реализуют методы объектного типа и его наследников. Исходя из этих соображений, идентификатор компоненты должен быть уникальным внутри объектного типа и внутри всех его наследников, а также внутри всех его методов.

В описании объектного типа заголовок метода может задавать параметры описываемого объектного типа, даже если описание еще не полное.

Рассмотрим следующую схему описания типа, содержащего компоненты всех допустимых областей действия:

Type

<имя типа> = Object [(<имя типа родителя>)]

Private

<частные описания полей и методов>

Protected

<защищенные описания полей и методов>

Public

<общедоступные описания полей и методов>

end;

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

Защищенные поля и методы, то есть описанные в разделе Protected, видимы в модуле, где определяется тип, и потомкам данного типа.

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

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