Методические указания для студентов 1 курса факультета математики, механики и компьютерных наук
| Вид материала | Методические указания |
- Программа курса «история и методология математики» для студентов дневного отделения, 151.46kb.
- Методические указания курса «культурология» Для студентов биологического факультета, 331.04kb.
- Войта Елена Александровна, магистрант факультета математики, механики и компьютерных, 129.35kb.
- Методические указания по изучению дисциплины Для студентов 4 курса заочного факультета, 3497.6kb.
- Методические указания и контрольные задания по английскому языку для студентов II курса, 375.13kb.
- И. И. Мечникова Институт математики, экономики и механики Кафедра математического обеспечения, 900.66kb.
- Методические указания к изучению курса «История мифологии» для студентов 1 курса факультета, 420.44kb.
- Методические указания к выполнению курсовой работы по дисциплине «Основы научных исследований», 403.99kb.
- Отчет по самообследованию дополнительной профессиональной программы для получения дополнительной, 317.2kb.
- Методические указания к выполнению курсовой работы по дисциплине «Оценка качества продовольственного, 856.1kb.
3.2Классы: основные понятия
АТД «Стек» на базе линейного односвязного списка (класс)
Оформим реализацию АТД «Стек» на базе линейного односвязного списка с помощью класса. После этого дадим определения основных понятий, связанных с классами. Далее приводится текст класса, реализующего стек целых чисел.
type
PNode=Node;
Node=record
data: integer;
next: PNode;
end;
Stack = class
private
head: PNode;
public
constructor Create;
destructor Destroy;
procedure Push(i: integer);
function Pop: integer;
function Top: integer;
function IsEmpty: boolean;
end;
function NewNode(data: integer; next: PNode): PNode;
begin
New(Result);
Result.data:=data;
Result.next:=next;
end;
constructor Stack.Create;
begin
head:=nil;
end;
destructor Stack.Destroy;
begin
while not IsEmpty do
Pop;
end;
procedure Stack.Push(i: integer);
begin
head:=NewNode(i,head);
end;
function Stack.Pop: integer;
var v: PNode;
begin
Assert(not IsEmpty);
v:=head;
head:=head.next;
Result:=v.data;
dispose(v);
end;
function Stack.IsEmpty: boolean;
begin
Result:= head=nil;
end;
function Stack.Top: integer;
begin
Assert(not IsEmpty);
Result:=head.data;
end;
Классы и объекты
Итак, что такое класс? Класс – это реализация абстрактного типа данных в языке программирования. Класс сочетает в себе свойства модуля и типа данных. С одной стороны, класс является модулем: он содержит интерфейс и реализацию, обеспечивает защиту данных. С другой стороны, класс является типом данных: можно описать любое количество переменных типа класс, эти переменные определенным образом хранятся в оперативной памяти, операции над переменными этого типа определяются в интерфейсе класса. Классовые переменные называются экземплярами класса, или объектами.
По описанию класс похож на запись, однако, вместо зарезервированного слова
record используется слово class. Описание класса состоит из описаний полей и заголовков методов – подпрограмм, осуществляющих доступ к полям. Разновидностями методов являются две особые подпрограммы – конструктор и деструктор, предназначенные для создания и разрушения объектов. Реализация методов должна быть дана позднее, при этом в заголовке метода перед его именем указывается имя класса с последующей точкой. Совокупность методов образует интерфейс класса.
Принцип объединения в одной оболочке полей и методов для доступа к этим полям и работы с ними называется инкапсуляцией (encapsulation, «как бы в капсуле»). Инкапсуляция предусматривает также защиту доступа: у класса имеется закрытая (private, приватная) и открытая (public, публичная) часть. Обычно в закрытую часть помещаются все поля и некоторые вспомогательные методы. Методы в открытой части образуют открытый интерфейс класса. Доступ к полям и методам из приватной части возможен только из методов этого класса. Например, в методе Push класса Stack осуществляется доступ к приватному полю head. Доступ к полям и методам из публичной части возможен отовсюду. В Delphi имеется небольшое ослабление правил доступа: к приватной части класса доступ возможен отовсюду из модуля, в котором данный класс определен.
Поскольку, создавая класс, мы определяем новый тип данных общего пользования, то обычно классы описываются в модуле. При этом объявление класса помещается в секцию интерфейса модуля, а реализация его методов – в секцию реализации модуля.
Заметим, что описания классов внутри подпрограмм в Delphi запрещены.
Конструкторы и деструкторы
В состав любого класса входят два специальных метода – конструктор и деструктор. Их объявления аналогичны объявлению метода-процедуры, но вместо зарезервированного слова procedure используются зарезервированные слова constructor и destructor. Традиционно в Delphi конструктор принято именовать Create, а деструктор – Destroy. В классе может быть несколько конструкторов с разными наборами параметров, а деструктор, как правило, один и не имеет параметров.
Конструктор выделяет место под объект в динамической памяти и возвращает адрес начала этого участка памяти, а также инициализирует поля созданного объекта. Этот адрес присваивается переменной-объекту. Вызов конструктора имеет следующий вид:
ИмяОбъекта := ИмяКласса.ИмяКонструктора(параметры);
Например, в результате создания объекта
var s1: Stack;
begin
s1:=Stack.Create;
мы получим следующую структуру в оперативной памяти:
Далее мы можем вызвать любой метод объекта, используя такую же точечную нотацию, что и при обращении к полю объекта:
s1.Push(5);
В результате структура в оперативной памяти изменится следующим образом:
Заметим, что хотя s1 и хранит адрес объекта, при доступе к объекту не требует использования операции разыменования , т.е. имя переменной класса является как бы разыменованным указателем. Таким образом, переменная-объект по существу представляет собой ссылку на объект в динамической памяти.
Деструктор разрушает объект в динамической памяти, его вызов производится как вызов обычного метода:
s1.Destroy;
До вызова конструктора и после вызова деструктора обращение к полям объекта и вызов его методов приводят к ошибке времени выполнения.
Ссылочная природа объектов в языке Delphi Pascal приводит к следующим особенностям выполнения операций присваивания и сравнения объектов. При присваивании объектов (s1:=s2) в переменную s1 записывается тот адрес, который хранится в переменной s2, в результате чего s1 и s2 будут указывать на один и тот же объект в динамической памяти. Если требуется отметить, что переменная типа класс не связана ни с каким объектом в динамической памяти, ей присваивают значение nil: s1:=nil. При сравнении (s1=s2, s1<>s2) происходит сравнение адресов объектов, то есть две переменных-объекта считаются равными только тогда, когда они ссылаются на один и тот же объект в динамической памяти.
Клиентская программа для АТД «Стек»
Задача. Дана последовательность целых положительных чисел, признаком ее завершения служит число 0. Вывести сначала все четные числа в обратном порядке, а затем все нечетные – также в обратном порядке.
Решение. Воспользуемся двумя стеками; по мере считывания четные числа будем помещать в первый стек (s1), нечетные – во второй (s2). По окончании ввода выведем содержимое обоих стеков.
Пусть описание класса Stack помещено в модуль IntStack.pas. Далее приводится код программы, решающей поставленную задачу:
uses IntStack;
var
s1,s2: Stack;
x: integer;
begin
s1:=Stack.Create; // создание и инициализация
s2:=Stack.Create;
while True do // заполнение
begin
read(x)
if x=0 then
break;
if Odd(x) then
s2.Push(x)
else s1.Push(x);
end;
while not s1.IsEmpty do // вывод
write (s1.Pop,' ');
while not s2.IsEmpty do
write (s2.Pop,' ');
writeln;
s1.Destroy; // разрушение
s2.Destroy;
end.
Переменная Self
Рассмотрим следующий код:
function Stack.IsEmpty: boolean;
begin
Result := head=nil;
end;
Каким образом при вызове метода s1.IsEmpty осуществляется доступ к полю head именно объекта s1? Ведь нигде в теле метода имя s1 не указано! Оказывается, в каждый метод неявно первым параметром передается специальная переменная Self, являющаяся ссылкой на объект класса, вызвавшего данный метод. Кроме того, переменная Self неявно добавляется при обращении к полям и методам данного класса, используемым в теле метода. Таким образом, для компилятора метод IsEmpty имеет вид:
function Stack.IsEmpty(Self: IntStack): boolean;
begin
Result := Self.head=nil;
end;
При вызове s1.IsEmpty компилятор добавляет в качестве первого параметра объект, вызвавший метод: s1.IsEmpty(s1). Таким образом, переменная Self вводится внутри метода неявно (как и переменная Result внутри функции) и обозначает ссылку на объект, вызвавший метод, то есть ссылку на самого себя.
3.3Класс «Очередь»
Очередь – это абстрактный тип данных, состоящий из последовательности элементов, которые можно добавлять в конец, а извлекать из начала. Как и стек, очередь можно проверять на пустоту.
Говорят, что очередь реализует принцип FIFO – first in first out (первым пришел – первым вышел): элемент, добавленный в очередь первым, будет извлечен из нее также первым.
Составим открытый интерфейс класса, представляющего очередь целых чисел:
type Queue = class
public
constructor Create;
destructor Destroy;
procedure Enqueue(i: integer);
function Dequeue: integer;
function First: integer;
function IsEmpty: boolean;
end;
Процедура Enqueue добавляет элемент i в конец очереди, функция Dequeue извлекает из очереди первый элемент и возвращает его значение, функция First возвращает значение первого элемента, не извлекая его из очереди, и, наконец, функция IsEmpty возвращает логическое значение True, если очередь пуста, и False в противном случае. Очевидно, при выполнении операций Enqueue и First очередь должна быть непустой, что проверяется с помощью вызова процедуры Assert. Отметим, что иногда вместо имен Enqueue и Dequeue используются имена Push и Pop.
Клиентская программа для класса «Очередь»
Задача. Дана последовательность целых положительных чисел, заканчивающаяся числом 0. Вывести сначала нечетные, а потом двузначные числа в том же порядке, что и в исходной последовательности.
Решение. Будем считать, что класс Queue, представляющий очередь целых, реализован в модуле IntQueue. При вводе будем записывать нечетные числа в первую очередь, а двузначные – во вторую. По окончании ввода выведем обе очереди. Далее приводится код решения:
uses IntQueue;
var q1,q2: Queue;
x: integer;
begin
q1:=Queue.Create;
q2:=Queue.Create;
while True do
begin
read(x);
if x=0 then break;
if Odd(x) then
q1.Enqueue(x);
if (x>=10) and (x<=99) then
q2.Enqueue(x);
end;
while not q1.IsEmpty do
write(q1.Dequeue,' ');
while not q2.IsEmpty do
write(q2.Dequeue,' ');
q1.Destroy;
q2.Destroy;
end;
Заметим, что клиентская программа уже написана, а мы еще не приступали к реализации класса «Очередь». Данный подход иллюстрирует модификацию метода программирования сверху вниз применительно к абстрактным типам данных: вначале составляется интерфейс АТД, после чего можно писать клиентские программы, пользующиеся этим АТД. Реализация же АТД автора клиентской программы не интересует.
Класс «Очередь» на базе линейного односвязного списка
Дадим реализацию класса Queue, используя в качестве структуры данных для хранения элементов односвязный список. Будем хранить указатели f и l на начало и конец такого списка:
Вначале список пуст: f=l=nil.
Добавление элемента будем проводить в конец очереди. Для этого вначале создадим новый узел и, если список не пуст, свяжем с ним поле next последнего элемента. Если же список пуст, то добавляемый элемент является первым, поэтому присвоим указателю f его адрес. В любом случае добавленный элемент является последним, поэтому присвоим указателю l адрес добавленного элемента:
v:=NewNode(i,nil);
if IsEmpty then
f:=v
else l.next:=v;
l:=v;
Извлечение элемента будем проводить из начала очереди. Для этого сохраним адрес первого элемента во вспомогательном указателе, переместим указатель f на следующий элемент очереди и удалим элемент, адрес которого сохранен во вспомогательном указателе, предварительно вернув значение удаляемого элемента. Если удаляемый элемент является последним, то изменим также l на nil:
v:=f;
f:=f.next;
if f=nil then
l:=nil;
Result:=v.data;
Dispose(v);
Поместим реализацию класса «Очередь целых» в модуль IntQueue. Удобно также ввести имя для типа элементов очереди:
type DataType=integer;
Если теперь потребуется создать, скажем, очередь вещественных элементов, то следует скопировать содержимое файла IntQueue.pas в файл RealQuеue.pas и изменить в нем определение типа DataType:
type DataType=real;
Приведем код модуля IntQueue:
unit IntQueue;
interface
type
DataType = integer;
Queue = class
private
f,l: PNode;
public
constructor Create;
destructor Destroy;
procedure Enqueue(i: DataType);
function Dequeue: DataType;
function First: DataType;
function IsEmpty: boolean;
end;
implementation
constructor Queue.Create;
begin
f:=nil;
l:=nil;
end;
destructor Queue.Destroy;
begin
while not IsEmpty do
Dequeue;
end;
procedure Queue.Enqueue(i: DataType);
var v: PNode;
begin
v:=NewNode(i,nil);
if IsEmpty then
f:=v
else l.next:=v;
l:=v;
end;
function Queue.Dequeue: DataType;
var v: PNode;
begin
Assert(not IsEmpty);
v:=f;
f:=f.next;
if f=nil then
l:=nil;
Result:=v.data;
Dispose(v);
end;
function Queue.IsEmpty: DataType;
begin
Result:=f=nil;
end;
function Queue.First: DataType;
begin
Assert(not IsEmpty);
Result:=f.data;
end;
end.
При выполнении операций Dequeue и First осуществляется проверка утверждения Assert(not IsEmpty), как и при выполнении аналогичных операций для стека.
Одновременное использование очередей с разными типами элементов
При использовании в одной программе очередей с разными типами элементов перед именем типа Queue следует указывать имя модуля во избежание ошибки неоднозначности имени Queue во время компиляции. Например, вот как следует использовать в одной программе очередь целых и очередь вещественных:
uses IntQueue, RealQueue;
var q1: IntQueue.Queue;
q2: RealQueue.Queue;
begin
q1:= IntQueue.Queue.Create;
q2:= RealQueue.Queue.Create;
...
Для удобства можно также в основной программе ввести другие имена для типов IntQueue.Queue и RealQueue.Queue:
uses IntQueue,RealQueue;
type IQueue=IntQueue.Queue;
RQueue=RealQueue.Queue;
var q1: IQueue;
q2: RQueue;
begin
q1:= IQueue.Create;
q2:= RQueue.Create;
...
Разумеется, в модулях IntQueue и RealQueue можно сразу дать очередям разных типов имена IQueue и RQueue. Но такой способ менее удобен, поскольку потребует менять не только имя типа DataType, но и менять имя типа очереди по всему модулю (в частности, при определении всех методов).
К сожалению, в языке Delphi Pascal отсутствует возможность создавать классы, параметризованные некоторым типом (например, Queue
Литература
1. Зеленяк О. Практикум программирования на Turbo Pascal / О. Зеленяк. – М.: DiaSoft, 2002. – 310 с.
2. Ставровский А. Турбо Паскаль 7.0 / А.Ставровский. – Киев: BHV, 2001. – 400 с.
3. Вирт Н. Алгоритмы и структуры данных / Н. Вирт. – М.: Мир, 1989. – 360 с.