Информатика и информационные технологии: конспект лекций

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

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;

ЛЕКЦИЯ № 11. Объектный тип данных

1. Объектный тип в Pascal. Понятие объекта, его описание и использование

Исторически первым подходом в программировании являлось процедурное программирование, иначе называемое программированием снизу вверх. Вначале создавались общие библиотеки стандартных программ, используемые в различных областях применения ЭВМ. Затем на основе этих программ создавались более сложные программы для решения конкретных задач.

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

1) проектирование сверху вниз;

2) модульное программирование;

3) структурное кодирование.

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

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

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

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

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

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

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

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