Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестр 13

Эффективность сортировки можно повысить, используя многопутевое слияние, в котором распределение выполняется на k лент. Поскольку число серий на каждом проходе уменьшается в k раз, количество пересылок M пропорционально величине n log_kn. Если общее число лент четное, то можно использовать однофазный метод слияния, распределяя серии с одной половины лент на другую. Платой за повышение эффективности многопутевого слияния являются, как всегда, увеличение сложности реализации и дополнительные затраты внешней памяти.

На сколько может отличаться количество серий после разделения? На первый взгляд кажется, что не более, чем на одну, но это не так. Например, при распределении серий 17, 25, 41, ’ 9, 60, ‘ 50, 52, ‘ 7 первая и третья серии сливаются в общую серию, что не происходит со второй и четвертой сериями. В результате при последующем слиянии серии на одной из лент могут закончиться раньше, и придется впустую переписывать остаток другой ленты, теряя эффективность. Подобные ситуации учитываются в методе многофазной сортировки. Рассмотрим его на примере трех лент.

Пусть при соединении лент B и C на ленту A серии на B заканчиваются раньше. Тогда лента B объявляется выходной, а лента A становится входной. Процесс продолжается до нового повторения ситуации, когда серии на одной из входных лент заканчиваются. Многофазная сортировка возможна и при многопутевом слиянии. Например, при использовании в сортировке k лент можно постоянно иметь одну выходную ленту. При исчерпании серий на одной из k-1 входных лент эта лента становится выходной вместо предыдущей выходной ленты.

Методы внутренней и внешней сортировок могут использоваться совместно. Пусть сортируется большой по объему файл. В оперативной памяти выделяется буфер максимально возможного размера. Файл делится на блоки, соответствующие величине буфера. Блоки читаются в буфер, сортируются одним из методов внутренней сортировки и переписываются в другой файл. Сейчас каждый блок нового файла является серией достаточно большой длины, определяемой размером буфера. Остается применить один из методов внешней сортировки, использующий данные серии.

7. Введение в объектно-ориентированное программирование

В основе любого языка программирования некоторая основная идея, выраженная в конструкциях языка и отражающая принципы разработки программ. Исторически первой была идея процедурного программирования, в соответствии с которой программист детально прорабатывал алгоритм решения задачи, а затем программные процедуры для реализации алгоритма. Структуры данных при этом оставались на втором плане и играли сугубо вспомогательную роль. Типичными представителями этого подхода являются такие языки, как Фортран и Алгол. Не случайно в Алголе операторы ввода-вывода оказались вообще нестандартизованными. По мере прогресса в области программирования акцент стал смещаться в сторону организации данных. Языки программирования Ада, Паскаль, Си имеют более или менее развитые структуры типов данных. Логическим следствием этого направления стал модульный подход к разработке программ, характеризующийся стремлениями разделить программу на функционально самостоятельные модули и "спрятать” детали реализации в виде данных и процедур внутри модулей.

Начиная с языков SmallTalk и Симула 67, в программировании наметился новый подход, который получил название объектно-ориентированного программирования (ООП). Его руководящей идеей является стремление связать данные с процедурами их обработки, называемыми методами, в единое целое – объект. Фактически ООП можно рассматривать как модульное программирование нового уровня, когда вместо во многом случайного объединения в модуле процедур и данных акцент делается на смысловую связь полей и методов объекта.

Язык ООП характеризуют три основных свойства:

• инкапсуляция: объединение данных с процедурами их обработки в новый тип данных – объект;

• наследование: построение и использование иерархии объектов, порожденных из родительского объекта и обладающих доступом к коду и данным всех своих предков;

• полиморфизм: присвоение одного имени действию, которое имеет одинаковый смысл и передается по иерархии объектов, но реализуется разными способами в разных объектах.

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

Type TPerson = record

Name: string; { имя }

Dolgn: string; { должность }

Stavka: integer { основная ставка }

end;

Var Person: TPerson;

Здесь TPerson является типом записи, то есть шаблоном для создания переменных записи, а переменная Person - экземпляром этого типа. Тип TPerson определяет два уровня абстракции. Можно рассматривать поля Name, Dolgn и Stavka по отдельности либо в совокупности для описания конкретного работника.

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

Type TScience = record

Name: string; { имя }

Dolgn: string; { должность }

Stavka: integer; { основная ставка }

Stepen: integer; { доплата за степень}

Zvanie: string { доплата за звание }

end;

Можно сохранить тип TPerson внутри типа TScience

Type TScience = record

Sience: TPerson; { имя, должность и основная ставка }

Stepen: integer; { доплата за степень}

Zvanie: integer { доплата за звание }

end;

Тип TScience является дочерним для типа TPerson. TScience наследует все, что принадлежит TPerson, и кроме того имеет кое-что новое, что делает TSsience уникальным.

В объектном расширении Паскаля существует еще один тип данных, который обладает этим свойством. Это объектный тип. Типы данных в этой новой категории определяются с помощью зарезервированного слова Object

Type TPerson = Object

Name: string; { имя }

Dolgn: string; { должность }

Stavka: integer { основная ставка }

end;

TScience = Object(TPerson)

Stepen: integer; { доплата за степень}

Zvanie: integer { доплата за звание }

end;

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

Экземпляры объектных типов описываются так же, как в Паскале описывается любая переменная. Можно обратиться к полю объекта, как к полю обычной записи. Например,

Person.Stavka:=2300;

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

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

Тип объекта описывается следующим образом:

Type

NewObject = Object

Поля данных;

Заголовки методов;

End;

Рассмотрим подробнее свойство наследования в ООП. Можно определить объект-наследник существующего объекта. В этом случае тип определяется следующим образом:

Type

ИмяОбъектаНаследника = Object ( ИмяОбъектаРодителя)

Новые поля данных;

Заголовки новых методов;

End;

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

Var

Person: TPerson;

Science: TScience;

то возможен оператор присваивания

Person:=Science;

Данная операция заполнит поля данных Person значениями соответствующих полей, унаследованных Science. Обратная операция недопустима.

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

Type TPerson = Object

Name: string; { имя }

Dolgn: string; { должность }

Stavka: integer; { основная ставка }

Procedure Init (Nm, Dg: string; Sv: integer);

Function GetDolgn: string;

Function GetStavka: integer;

Function GetName: string;

Procedure ShowName;

Procedure ShowDolgn;

Procedure ShowStavka;

end;

TScience = Object(TPerson)

Stepen: integer; { доплата за степень}

Zvanie: integer; { доплата за звание }

Procedure Init (Nm, Dg: string; Sv, St, Zv: integer);

Function GetStepen: integer;

Function GetZvanie: integer;

Function GetSum: integer;

Procedure ShowStepen;

Procedure ShowZvanie;

Procedure ShowSum;

end;

TTeacher = Object(TScience)

Hours: integer; { часы }

HourRate: integer; { почасовая оплата }

Procedure Init (Nm, Dg: string; Sv, Ho, Hr: integer);

Function GetSum: integer;

Procedure ShowSum;

end;

Методы GetName, GetDolgn, GetStavka, ShowName, ShowDolgn, ShowStavka путем наследования используются во всей иерархии объектов. Метод Init должен переопределяться в каждом объекте, так как у объектов отличается набор полей. Например, для объекта TScience этот метод может выглядеть следующим образом

Procedure TScience.Init;

Begin

TPerson.Init(Nm, Dg, Sv);

Stepen:=St;

Zvanie:=Zv;

End;

Расчет выплаты в объекте TScience выполняется функцией

Function TScience.GetSum: integer;

Begin

GetSum:=Stavka+Stepen+Zvanie

End;

а в объекте TTeacher функцией

Function TTeacher.GetSum: integer;

Begin

GetSum:=TScience.GetSum + Hours * HourRate;

End;

Методы могут быть переопределены, но поля переопределяться не могут.

Объекты TScience и TTeacher содержат процедуру ShowSum. Для объекта TScience эта процедура может выглядеть следующим образом:

Procedure TScience.ShowSum;

Begin

WriteLn(GetSum)

End;

Для объекта TTeacher эта процедура имеет тот же самый вид:

Procedure TTeacher.ShowSum;

Begin

WriteLn(GetSum)

End;

Поскольку TTeacher может унаследовать ShowSum от TScience, нужно ли описывать этот метод для обоих объектов? Нужно! Дело в том, что в противном случае при использовании ShowSum в TTeacher будет вызван метод GetSum из TScience, а не TTeacher.

Все описанные методы являются статическими. Ссылки на статические методы осуществляются еще на этапе компиляции. Это называют ранним связыванием.

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

Метод становится виртуальным, когда за его определением в типе объекта ставится служебное слово Virtual. При виртуализации методов должны выполняться следующие условия:

• если родительский тип объекта описывает метод как виртуальный, то все производные типы должны описывать метод с этим же именем тоже как виртуальный;

• порядок расположения, количество и типы формальных параметров в одноименных виртуальных методах должны быть неизменными;

• в описании объекта должен присутствовать конструктор - специальный метод, инициализирующий объект (обычно ему дают название Init).

Конструктор выделяется служебным словом Constructor, заменяющим слово Procedure в объявлении и реализации метода. Конструктор выполняет установочную работу для механизма виртуальных методов, поэтому должен вызываться до первого вызова виртуального метода.

В приведенном примере можно определить метод GetSum в объектах TScience и TTeacher как виртуальный. Тогда метод ShowSum достаточно объявить один раз в объекте TScience и также единожды привести код этого метода.

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

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

Program ObjectTest;

{ работа со стеком и очередью, организованных на массиве }

Uses Crt;

Type

TStek=Object

Top: integer; {вершина стека; для очереди - конец}

List: array [1..100] of integer; {массив для списка}

Constructor Init; {требуется, т.к. есть виртуальные методы}

Procedure Dopoln(Knew: integer); {Knew-дополняемый элемент}

Procedure Udal; {удаление из вершины стека}

Function GetTop: integer; {возврат значения Top}

Procedure ShowNext(var I: integer); Virtual;

{вывод следующего элемента, в стеке от вершины к началу}

Procedure Show(Ind: integer);

{вывод списка на экран, Ind-первый элемент}

End;

TOcher=Object(TStek)

{начало очереди в первом элементе массива List, конец в Top}

{процедуры Dopoln, Show, GetTop наследуются из объекта TStek}

Constructor Init; {требуется, т.к. есть виртуальные методы}

Procedure Udal; {удаление из начала - продвижение очереди}

Procedure ShowNext(var I: integer); Virtual;

{вывод следующего элемента, в очереди от начала к концу}

End;

Var

Stek: TStek;

Ocher: TOcher;

B1, B2: boolean;

M, N, K: integer;

Constructor TStek.Init;

Begin

Top:=0;

End;

Procedure TStek.Dopoln(Knew: integer);

Begin

Top:=Top+1;

List[Top]:=Knew

End;

Procedure TStek.Udal;

Begin

if Top=0 then WriteLn('Список пуст, удалять нечего !')

else Top:=Top-1

End;