Читать онлайн «Информатика и информационные технологии: конспект лекций». Страница 10

2. Представление графа списком инцидентности. Алгоритм обхода графа в глубину

Для реализации графа в виде списка инцидентности можно использовать следующий тип:

Type List = ^S;

S = record;

inf : Byte;

next : List;

end;

Тогда граф задается следующим образом:

Var Gr : array[1..n] of List;

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

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

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

Примечание

В данной процедуре при описании типа Graph имелось в виду описание графа списком списков. Массив nov[i] – специальный массив, i-ый элемент которого равен True, если i-ая вершина не просмотрена, и False – в противном случае.

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

Граф можно определить с помощью списка списков следующим образом:

Type List = ^Tlist;

Tlist = record

inf : Byte;

next : List;

end;

Graph = ^TGpaph;

TGpaph = record

inf : Byte;

smeg : List;

next : Graph;

end;

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

Приведем процедуру обхода графа в ширину на псевдокоде:

Procedure Obhod2(v);

{величины spisok, nov – глобальные}

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) структурное кодирование.

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

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

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

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

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

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

Объектный тип может наследовать компоненты другого объектного типа. Если тип Т2 наследует от типа Т1, то тип Т2 является потомком типа Т1, а сам тип Т1 является родителем типа Т2. Наследование является транзитивным, т. е. если ТЗ наследует от Т2, а Т2 наследует от Т1, то ТЗ наследует от Т1. Область (домен) объектного типа состоит из него самого и из всех его наследников.

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

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;

StringPtr = ^String;

FieldPtr = ^TField;

TField = object

X, Y, Len: Integer;

Name: StringPtr;

constructor Copy(var F: TField);

constructor Init(FX, FY, FLen: Integer; FName: String);

destructor Done; virtual;

procedure Display; virtual;

procedure Edit; virtual;

function GetStr: String; virtual;

function PutStr(S: String): Boolean; virtual;

end;

StrFieldPtr = ^TStrField;

StrField = object(TField)

Value: PString;

constructor Init(FX, FY, FLen: Integer; FName: String);

destructor Done; virtual;

function GetStr: String; virtual;

function PutStr(S: String): Boolean;

virtual;

function Get: string;

procedure Put(S: String);

end;

NumFieldPtr = ^TNumField;

TNumField = object(TField)

private

Value, Min, Max: Longint;

public

constructor Init(FX, FY, FLen: Integer; FName: String;

FMin, FMax: Longint);

function GetStr: String; virtual;

function PutStr(S: String): Boolean; virtual;

function Get: Longint;

function Put(N: Longint);

end;

ZipFieldPtr = ^TZipField;

ZipField = object(TNumField)

function GetStr: String; virtual;

function PutStr(S: String): Boolean;

virtual;

end.

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

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

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

Ранее известные типы записей Pascal не могут наследовать. Однако Borland Pascal расширяет язык Pascal для поддержки наследования. Одним из этих расширений является новая категория структуры данных, связанная с записями, но значительно более мощная. Типы данных в этой новой категории определяются с помощью нового зарезервированного слова «object». Тип объекта может быть определен как полный, самостоятельный тип в манере описания записей Pascal, но он может определяться и как потомок существующего типа объекта путем помещения порождающего (родительского) типа в скобки после зарезервированного слова «object».