Статическая реализация динамической памяти типа «стек»
имеет свои преимущества: содержательно проста, экономична по времени - операции выполняются быстро,
но имеет и свои недостатки: приходится изначально резервировать память для хранения элементов стека, которой может оказаться расточительно много для одних входных данных задачи, а для других - недостаточно.
Вариант 2. Динамическая реализация стеков.
UNIT UStack; INTERFACE USES UVal;
FUNCTION Empty:BOOLEAN {Проверить на пустоту};
PROCEDURE Push(xPrm:UVal.TVal){Добавить, положить в стек};
PROCEDURE Pop {Удалить, вытолкнуть из стека};
FUNCTION Top:UVal.TVal {Посмотреть вершину};
PROCEDURE WriteAll {Вывести все элементы стека};
VAR ErrStack:INTEGER {Код ошибки};
Implementation
TYPE PElement=^TElement;
TElement= RECORD VElem:TVal; Next:PElement END;
TStack= PElement;
Var Stack:tStack;
FUNCTION Empty:BOOLEAN; BEGIN Empty:=(Stack=NIL) END;
Procedure Push; var p:pElement; begin new(p);
p^.VElem:=xPrm; p^.Next:=Stack; Stack:=p END;
PROCEDURE Pop; VAR xStack:PElement; BEGIN IF Stack=NIL
THEN {недопустима - стек пустой} ErrStack:=-2
ELSE BEGIN xStack:=Stack^.Next; Dispose(Stack);
Stack:=xStack END END;
FUNCTION Top; BEGIN IF Stack=NIL
THEN {недопустима - стек пустой} ErrStack:=-2
ELSE Top:=Stack^.VElem END;
PROCEDURE WriteAll; VAR p:PElement; BEGIN p:=Stack;
WHILE p<>NIL DO BEGIN WriteElement(Stack^.VElem);
p:=p^.Next END END;
INITIALIZATION {Создать пустой стек} Stack:=NIL; ErrStack:=0
END.
PROGRAM\Prg3b\PROJECT1.DPR PROGRAM\C(C++)\prg3b\prg3b.dsw
Динамическая реализация динамической памяти типа «стек» устраняет основной недостаток статической реализации, но имеет свои недостатки - например, дополнительный расход памяти на представление каждого элемента стека для хранения ссылки на следующий элемент.
Отметим технологически важный момент. Мы изменили способ реализации абстрактного типа данных «стек», но сохранили интерфейс. Это позволило сохранить без изменений программу решения задачи «Преобразовать: правильную инфиксную постфиксную». Сохранение ранее накопленного, повторное использование - один из важнейших вопросов современной технологии программирования.
Общий недостаток вышерассмотренных обеих реализаций понятия «стек» состоит в том, что инструменты этих модулей не позволяют работать с двумя стеками одновременно. По сути, оба модуля не столько реализуют абстрактный тип данных «стек», сколько предоставляют пользователю некий (один) информационный ресурс памяти типа «стек». Для одновременной работы с двумя стеками можно конечно продублировать модуль и использовать под одним именем для одного стека, а под другим - для другого. Но очень естественным такой выход из положения назвать трудно...
Вариант 3. Другой выход из вышерассмотренного затруднения - параметризовать инструменты модуля.
UNIT UStack;
INTERFACE USES UVal;
TYPE PElement=^TElement;
TElement=RECORD VElem:UVal.TVal;Next:PElement END;
TStack= PElement;
PROCEDURE MakeNull(VAR Stack:TStack){Создать пустой стек};
FUNCTION Empty(Stack:TStack):BOOLEAN{Проверить на пустоту};
PROCEDURE Push(VAR Stack:TStack;
xPrm:UVal.TVal){Добавить, положить в стек};
PROCEDURE Pop(VAR Stack:TStack)
{Удалить, вытолкнуть из стека};
FUNCTION Top(Stack:TStack):UVal.TVal{Посмотреть вершину};
IMPLEMENTATION
PROCEDURE MakeNull(VAR Stack:TStack);
BEGIN Stack:=NIL END;
FUNCTION Empty(Stack:TStack):BOOLEAN;
BEGIN Empty:=(Stack=NIL) END;
PROCEDURE Push(VAR Stack:TStack; xPrm:UVal.TVal);
VAR p:PElement;
BEGIN NEW(p); p^.VElem:=xPrm; p^.Next:=Stack;
Stack:=p END;
PROCEDURE Pop(VAR Stack:TStack); VAR xStack:PElement;
BEGIN IF Stack=NIL THEN {недопустима - стек пустой}
ELSE BEGIN xStack:=Stack^.Next; Dispose(Stack);
Stack:=xStack END END;
FUNCTION Top(Stack:TStack):UVal.TVal;
BEGIN IF Stack=NIL THEN {недопустима - стек пустой}
ELSE Top:=Stack^.VElem END;
END.
program Project1;
uses UVal in 'UVal.pas', UStack in 'UStack.pas';
VAR Vh,Vih: FILE OF CHAR; x,y: CHAR; S:TStack;
begin Assign(Vh,'VhPrg3.TXT'); RESET(Vh);
Assign(Vih,'VihPrg3.TXT'); REWRITE(Vih);
MakeNull(S);
WHILE NOT EOF(Vh) DO BEGIN READ(Vh,x);
CASE x OF
'(': ;
'+','-','*','/': UStack.Push(S,x);
')': BEGIN y:=UStack.Top(S);WRITE(Vih,y);UStack.Pop(S)
END;
ELSE {'a'..'z'} WRITE(Vih,x);
END END; CloseFile(Vh);
WHILE NOT UStack.Empty(S) DO
BEGIN y:=UStack.Top(S);WRITE(Vih,y);UStack.Pop(S)
END; CloseFile(Vih)
end. PROGRAM\PRG3C\PROJECT1.DPR
Теперь инструменты модуля позволяют работать одновременно с любым числом стеков - требуемые стеки теперь можно описать и в операциях указать, с каким стеком ее выполнять.
Но какой ценой...
Объявление типа TStack пришлось перенести из раздела IMPLEMENTATION, невидимого извне, в раздел INTERFACE - инструментов для внешнего использования.
Теперь пользователь этих инструментов, начиная от переменной типа TStack, может получить непосредственный доступ к любому компоненту «физического» представления стека и при неаккуратном программировании полностью разрушить структуру этого представления...
Предыдущие реализации абстрактного типа данных «стек» позволяли писать программы, независимые от способа представления стека, и препятствовали написанию программ зависящих, защищая свои инструменты.
Механизмы защиты инструментов и уровни независимости программ от способа реализации используемых инструментов - один из важнейших вопросов современной технологии программирования.
Новая реализация оказалась совершенно незащищенной от неаккуратного вмешательства в работу инструментов...
Аккуратную реализацию абстрактного типа данных «стек» можно предложить, совместно используя механизм модулей и механизм классов.
Класс - (обобщенный) структурный тип.
Класс – это набор компонентов возможно разного типа. Способ группировки аналогичен записям/структурам, но
позволяет группировать в единое целое данные и процедуры-функции для работы с этими данными;
предоставляет механизм инкапсуляции компонентов класса.
Поля - компоненты-данные класса, они задают способ представления значений этого типа.
Методы - компоненты-операции класса, они задают процедуры и функции для работы с такими значениями.
Object Pascal 2 |
C (C++) |
Определение типа класс: ИмяТипаКласс = class [СпецификаторНаследования] СекцияКомпонентов... end
У первой секции эту спецификацию можно опустить, тогда она считается public–секцией. Далее в секции следуют:
В секции могут отсутствовать поля или методы, но объявление метода секции не может предшествовать ни одному объявлению поля этой секции. Фактически каждое объявление должно заканчиваться точкой с запятой (разделяющей их), но перед end описателя класса точку с запятой можно опустить, если последним в классе объявлено поле. |
Определение типа класс: class ИмяТипаКласс [СпецификаторНаследования] { СекцияКомпонентов... }
У первой секции эту спецификацию можно опустить, тогда она считается private–секцией. Далее в секции следуют:
В секции могут отсутствовать поля или методы.
|
Классы и модули. Классы можно использовать, не использую модули, и наоборот. Однако наилучших результатов удается добиться, только продуманно комбинируя возможности классов и модулей. В контексте именно такого использования мы и будем рассматривать аппарат классов.
Основные рекомендации общего характера – определения классов, предназначенных «для использования другими», оформлять как интерфейсные инструменты подходящих модулей, а реализацию методов и определения классов (и других типов), предназначенных «для внутреннего пользования», оформлять как инкапсулированные инструменты этих модулей. При этом, используя секции классов можно (и нужно) дополнительно управлять степенью инкапсуляции компонентов класса (повышать защищенность).
В модуле реализация методов класса отделена от определения класса, поэтому в заголовке описания метода (процедуры-функции) имя метода уточняется именем класса:
В Object Pascal 2: ИмяКласса.
В C++: ИмяКласса::
Если процедура или функция описана в модуле без уточнения именем класса, то она трактуется как обычная процедура-функция модуля, никак не связанная ни с каким классом (не трактуется как метод какого-либо класса).
Класс можно объявить как локальный тип данных, например в процедуре или функции. Но оформление локального класса должно удовлетворять ряду требований. Локальные классы в этом курсе не рассматриваются.
Описание переменных типа класс (как всегда):
ИмяПеременной, ... : T class |
T class ИмяПеременной, ... ; |
Переменные типа класс расширяют семантику понятия «переменная»:
Компоненты такой переменной хранят не только данные, но и информацию об операциях с этими данными, кроме того компоненты такой переменной могут быть инкапсулированы (не видимы для «посторонних»).
Переменные типа класс – это специальный вид динамических переменных:
переменные типа класс, в отличие от динамических переменных ранее рассмотренного вида, должны быть описаны, но не создаются неявно (как это происходит согласно семантике локальных переменных);
переменные типа класс явно создаются и уничтожаются в периоде выполнения программы, для этого используются конструкторы и деструкторы.
Конструкторы и деструкторы – это методы класса, нагруженные дополнительной специальной семантикой.
Объявление конструктора и деструктора класса: Конструкторы и деструкторы класса объявляются также как методы-процедуры, но с ключевым словом constructor и destructor соответственно , вместо procedure. |
Объявление конструктора и деструктора класса: Конструкторы и деструкторы класса объявляются также как методы-процедуры, но без void, как признак невозвращения значения, и имя конструктора дожно совпадать с ИмяТипаКласс, а имя деструктора дожно совпадать с ~ИмяТипаКласс. |
Вызов конструктора (базовый вариант): V class := ИмяТипаКласс . ИмяКонструктора [( ФактическийПараметр, ...)] Такой вызов конструктора:
|
Вызов конструктора (базовый вариант): В базовом варианте конструктор вызывается в объявлении переменной типа класс согласно семантике такого объявления, т.е. в некотором определенном смысле неявно (*). Причем, так может быть вызыван только конструктор по умолчанию:
|
|
T class ИмяПеременной; Такой вызов конструктора по умолчанию:
|
Компонентная переменная:
Тип этой переменной - тот, который в определении класса объявлен для поля ИмяПоля. |
|
V class . ИмяМетода [( ФактическийПараметр, ...)] |
V class . ИмяМетода ([ ФактическийПараметр, ...])
V class . ИмяМетода ([ ФактическийПараметр, ...]); |
Вызов метода-процедуры вляется оператором S, а вызов метода-функции – выражением E. |
|
Вариант 4. Динамическая реализация стеков и использование классов и модулей.
Чисто технически новая реализация очень близка к ранее рассмотренной «Вариант 2», поэтому на следующей странице они обе представлены для визуального сравнения.
В новой реализации решены вышерассмотренные проблемы:
Новые инструменты позволяют работать одновременно с любым числом стеков -
теперь можно описать (и создать) переменные типа стек:
VAR OStack1,OStack2:CStack; BEGIN ...
OStack1:=CStack.MakeNull;... OStack2:=CStack.MakeNull;...
операции теперь являются составной частью каждой переменной типа CStack, соответственно они и применяются свои для каждой переменной:
y1:=OStack1.Top; OStack1.Pop;...
y2:=OStack2.Top; OStack2.Pop;...
«Уши» внутреннего представления стека «торчат» в секции INTERFACE, но «вытащить за эти уши» компоненты внутреннего представления стека и испортить их, уже возможности нет - само хранилище стека Stack защищено и недоступно извне.
UNIT UStack;
INTERFACE USES UVal;
FUNCTION Empty:BOOLEAN {Проверить на пустоту};
PROCEDURE Push(xPrm:UVal.TVal){Добавить, положить в стек};
PROCEDURE Pop {Удалить, вытолкнуть из стека};
FUNCTION Top:UVal.TVal {Посмотреть вершину};
PROCEDURE WriteAll {Вывести все элементы стека};
VAR ErrStack:INTEGER {Код ошибки};
IMPLEMENTATION
TYPE PElement=^TElement;
TElement= RECORD VElem:UVal.TVal; Next:PElement END;
TStack= PElement;
VAR Stack:TStack;
FUNCTION Empty:BOOLEAN; BEGIN Empty:=(Stack=NIL) END;
PROCEDURE Push(xPrm:UVal.TVal); VAR p:PElement;
BEGIN NEW(p); p^.VElem:=xPrm; p^.Next:=Stack; Stack:=p END;
PROCEDURE Pop; VAR xStack:PElement;
BEGIN IF Stack=NIL THEN {недопустима - стек пустой} ErrStack:=-2
ELSE BEGIN xStack:=Stack^.Next;
Dispose(Stack); Stack:=xStack END END;
FUNCTION Top;
BEGIN IF Stack=NIL THEN {недопустима - стек пустой} ErrStack:=-2
ELSE Top:=Stack^.VElem END;
PROCEDURE WriteAll; VAR p:PElement; BEGIN p:=Stack;
WHILE p<>NIL DO BEGIN WriteElement(Stack^.VElem); p:=p^.Next
END
END;
INITIALIZATION Stack:=NIL; ErrStack:=0
END.
program Project1;
uses UVal in 'UVal.pas', UStack in 'UStack.pas';
VAR Vh,Vih: FILE OF CHAR; x,y: CHAR;
begin RESET(Vh); REWRITE(Vih);
WHILE NOT EOF(Vh) DO BEGIN READ(Vh,x);
CASE x OF
'(': ;
'+','-','*','/': UStack.Push(x);
')': BEGIN y:=UStack.Top; WRITE(Vih,y); UStack.Pop END;
ELSE {'a'..'z'} WRITE(Vih,x);
END END; CloseFile(Vh); CloseFile(Vih) end.
UNIT UStack;
INTERFACE USES UVal;
TYPE PElement=^TElement;
TElement= RECORD VElem:UVal.TVal; Next:PElement END;
TStack= PElement;
CStack= CLASS PRIVATE Stack:TStack; PUBLIC
ErrStack:INTEGER {Код ошибки};
FUNCTION Empty:BOOLEAN {Проверить на пустоту};
PROCEDURE Push(xPrm:UVal.TVal){Добавить, положить в стек};
PROCEDURE Pop {Удалить, вытолкнуть из стека};
FUNCTION Top:UVal.TVal {Посмотреть вершину};
PROCEDURE WriteAll {Вывести все элементы стека};
CONSTRUCTOR MakeNull {Создать пустой стек};
END;
IMPLEMENTATION
FUNCTION CStack.Empty:BOOLEAN; BEGIN Empty:=(Stack=NIL) END;
PROCEDURE CStack.Push(xPrm:UVal.TVal); VAR p:PElement;
BEGIN NEW(p); p^.VElem:=xPrm; p^.Next:=Stack; Stack:=p END;
PROCEDURE CStack.Pop; VAR xStack:PElement;
BEGIN IF Stack=NIL THEN {недопустима - стек пустой} ErrStack:=-2
ELSE BEGIN xStack:=Stack^.Next;
Dispose(Stack); Stack:=xStack END END;
FUNCTION CStack.Top:UVal.TVal;
BEGIN IF Stack=NIL THEN {недопустима - стек пустой} ErrStack:=-2
ELSE Top:=Stack^.VElem END;
PROCEDURE CStack.WriteAll; VAR p:PElement; BEGIN p:=Stack;
WHILE p<>NIL DO BEGIN WriteElement(Stack^.VElem); p:=p^.Next
END
END;
CONSTRUCTOR CStack.MakeNull; BEGIN Stack:=NIL; ErrStack:=0 END;
END.
program Project1;
uses UVal in 'UVal.pas', UStack in 'UStack.pas';
VAR Vh,Vih: FILE OF CHAR; x,y: CHAR; OStack:CStack;
begin RESET(Vh); REWRITE(Vih);
OStack:=UStack.CStack.MakeNull;
WHILE NOT EOF(Vh) DO BEGIN READ(Vh,x);
CASE x OF
'(': ;
'+','-','*','/': OStack.Push(x);
')': BEGIN y:=OStack.Top; WRITE(Vih,y); OStack.Pop END;
ELSE {'a'..'z'} WRITE(Vih,x);
END END; CloseFile(Vh); CloseFile(Vih) end.
PROGRAM\Prg3d\Project1.dpr
Файл UStack.h:
void MakeNull(); //Создать пустой стек
bool Empty(); //Проверить на пустоту
void Push(TVal xPrm); //Добавить, положить в стек
void Pop(); //Удалить, вытолкнуть из стека
TVal Top(); //Посмотреть вершину
void WriteAll(); //Вывести все элементы стека
extern int ErrStack; //Код ошибки
Файл UStack.cpp:
#include "UVal.h"
int ErrStack; //Код ошибки
struct TElement {TVal VElem; TElement* Next;};
static TElement* Stack;
bool Empty() //Проверить на пустоту
{return (Stack==NULL);}
void Push(TVal xPrm) //Добавить, положить в стек
{TElement* p; p=new(TElement); p->VElem=xPrm; p->Next=Stack;
Stack=p;}
void Pop() //Удалить, вытолкнуть из стека
{TElement* xStack;
if(Stack==NULL) ErrStack=-2; //недопустима - стек пустой
else{ xStack=Stack->Next; delete(Stack); Stack=xStack;}}
TVal Top() //Посмотреть вершину
{if(Stack==NULL) ErrStack=-2; //недопустима - стек пустой
else return Stack->VElem; }
void WriteAll() //Вывести все элементы стека
{TElement* p; p=Stack;
while(p!=NULL){ WriteElement(Stack->VElem); p=p->Next;}}
void MakeNull() //Создать пустой стек
{Stack=NULL; ErrStack=0;}
Файл prg3b.cpp:
#include "UVal.h"
#include "UStack.h"
main(){ifstream Vh/*входной текст*/; ofstream Vih/*выходной текст*/;
char x/*текущий символ*/,y;
Vh.open("VhPrg3.TXT"); Vih.open("VihPrg3.TXT"); MakeNull();
while(Vh.peek()!=EOF){ Vh.get(x); switch (x) {
case '(': break;
case '+': case '-': case '*': case '/': Push(x); break;
case ')': Vih<<Top(); Pop(); break;
default: /*'a'..'z'*/ Vih<<x;
}} Vh.close(); Vih.close();}
Файл UStack.h:
struct TElement {TVal VElem; TElement* Next;};
class CStack{ private: TElement* Stack; public:
int ErrStack; //Код ошибки
bool Empty(); //Проверить на пустоту
void Push(TVal xPrm); //Добавить, положить в стек
void Pop(); //Удалить, вытолкнуть из стека
TVal Top(); //Посмотреть вершину
void WriteAll(); //Вывести все элементы стека
CStack(); //MakeNull - Создать пустой стек
};
Файл UStack.cpp:
#include "UVal.h"
#include "UStack.h"
bool CStack::Empty() //Проверить на пустоту
{return (Stack==NULL);}
void CStack::Push(TVal xPrm) //Добавить, положить в стек
{TElement* p; p=new(TElement); p->VElem=xPrm; p->Next=Stack;
Stack=p;}
void CStack::Pop() //Удалить, вытолкнуть из стека
{TElement* xStack;
if(Stack==NULL) ErrStack=-2; //недопустима - стек пустой
else{ xStack=Stack->Next; delete(Stack); Stack=xStack;}}
TVal CStack::Top() //Посмотреть вершину
{if(Stack==NULL) ErrStack=-2; //недопустима - стек пустой
else return Stack->VElem; }
void CStack::WriteAll() //Вывести все элементы стека
{TElement* p; p=Stack;
while(p!=NULL){ WriteElement(Stack->VElem); p=p->Next;}}
CStack::CStack() //MakeNull - Создать пустой стек
{Stack=NULL; ErrStack=0;}
Файл prg3d.cpp:
#include "UVal.h"
#include "UStack.h"
main(){ifstream Vh/*входной текст*/; ofstream Vih/*выходной текст*/;
char x/*текущий символ*/,y; CStack OStack;
Vh.open("VhPrg3.TXT"); Vih.open("VihPrg3.TXT"); //OStack=CStack();
while(Vh.peek()!=EOF){ Vh.get(x); switch (x) {
case '(': break;
case '+': case '-': case '*': case '/': OStack.Push(x); break;
case ')': Vih<<OStack.Top(); OStack.Pop(); break;
default: /*'a'..'z'*/ Vih<<x;
}} Vh.close(); Vih.close();}
PROGRAM\C(C++)\prg3d\prg3d.dsw
Реализация очередей.
Вариант 1. Статическая реализация очередей.
Также как в случае статической реализации стека, используем вектор для представления очереди. Также как и в задаче о порождении обобщенно-периодичной последовательности мы столкнемся с «неприятностью» - при каждом удалении первого компонента очереди придется передвигать все остальные, поэтому «замкнем вектор в кольцо»(*) . Поскольку операции добавления-удаления (с разных концов) могут выполняться в (почти) любом порядке, придется хранить позицию как первого (Front), так и последнего (Rear) компонента очереди.
CONST CMaxL=1000;
TYPE ... RECORD Elem: ARRAY[1..CMaxL] OF UVal.TVal;
Front,Rear: 0..CMaxL END;
В итоге все получится естественно: удаление - сдвиг Front вперед (по кольцу по часовой стрелке), добавление - сдвиг Rear вперед (по кольцу). Однако возникнет одна двусмысленная ситуация - что означает нижеприведенное положение Front и Rear:
очередь максимальной длины (Front..Rear по часовой стрелке) или пустую очередь? Устранить эту двусмысленность можно, не допуская того чтобы «Rear мог догнать Front», т.е. ограничив максимальную длину очереди величиной строго меньшей, чем длина представляющего вектора. PROGRAM\Prg4d0\Project1.dpr
Вариант 2. Динамическая реализация очередей.
PROGRAM\PRG4D2\Project1.dpr PROGRAM\C(c++)\prg4d2\prg4d.dsw
PROGRAM\Prg4d\Project1.dpr PROGRAM\C(c++)\PRG4D\prg4d.dsw
Еще раз вернемся к общим рассуждениям о динамической памяти и последовательном доступе к ее компонентам. Внимательнее рассмотрим операциональные возможности различных видов динамической памяти.
«Разрушающее» и «неразрушающее» чтение.
Стеки и очереди допускают только «разрушающее» чтение - доступ к чтению очередного компонента возможен только после удаления уже прочитанного.
Отметим одно важное отличие между стеком и очередью в этом отношении. В случае очереди удаляемый компонент можно предварительно перезапомнить (повторно добавить с другого конца). В случае стека перезапоминание неприемлемо - оно «перегораживает» доступ к чтению очередного.
В случае (последовательных) файлов мы имеем «неразрушающее» чтение и связанное с ним понятие - текущий компонент (маркер текущего компонента).
Набор операций для (последовательных) файлов.(*)
Создать пустой файл F.
PROCEDURE ReWrite(VAR F:TFile)
Добавить компонент x в файл F.
PROCEDURE Write(x:TVal; VAR F:TFile)
Установить текущим 1-й компонент файла F.
PROCEDURE Reset(VAR F:TFile)
Установить текущим следующий компонент файла F.
PROCEDURE Next(VAR F:TFile)(**)
Посмотреть значение текущего компонента файла F.
FUNCTION Retrieve(F:TFile):TVal(***)
Проверить на конец файла F.
FUNCTION EOF(F:TFile):BOOLEAN
«Неразрушающее» чтение - это возможность повторного чтения, в этих условиях в определенном смысле реализуем прямой доступ к компонентам памяти. Можно ввести понятие позиция компонента - некий ключ, однозначно определяющий положение компонента в памяти, например просто его порядковый номер в последовательности. Тогда можно рассмотреть операцию «Установить текущим компонент p-ой позиции в файле F», с очевидной реализацией:
PROCEDURE Seek(VAR F:TFile; p:Longint); VAR i:Longint;
BEGIN Reset(F); i:=0; WHILE NOT EOF(F) AND (i<p) DO
BEGIN Next(F); i:=i+1 END END
...Остается конечно вопрос о более эффективной реализации этой операции для конкретных представлений данных типа файл...
Наши рассуждения о памяти процесса изначально проводятся в контексте двух последовательностей - входного потока данных и выходного. С входным потоком связана последовательность «запоминаний» (записи в память), с выходным - последовательность «вспоминаний» (чтения из памяти). Фактически исходный процесс мы трактуем как пару взаимодействующих субпроцессов:
Субпроцесс1: прием последовательности из входного потока
- формирование последовательности в памяти.
Субпроцесс2: просмотр последовательности в памяти
- передача последовательности в выходной поток.
В случае стека последовательность чтения из памяти обратна последовательности записи, в случаях очереди и файла - последовательность чтения совпадает с последовательностью записи.
Однако интуитивно достаточно ясно, что возможность повторного чтения(*) в определенном смысле расширяет возможности управлять формированием выходного потока. Эта возможность управления основана на сведении задачи вывода интересующего элемента в выходной поток к задаче поиска этого элемента в памяти. Однако имеется и другая идея - сохранять элементы в последовательной памяти в том порядке, в котором они в соответствующий момент потребуются для вывода - для этого нужны подходящие средства реструктуризации памяти.
Средства реструктуризации последовательной памяти - это операции вставки элементов в интересующее место памяти (последовательности) и удаления неинтересующих нас элементов из памяти (последовательности).
Линейные списки.
С этим понятием мы тоже уже встречались. Однонаправленный линейный список мы использовали в задаче построения ряда Фарея.
Список как абстрактный тип данных.
Множество возможных значений - (конечные) последовательности компонентов одинакового типа.
Пусть s1,s2,...sl - список типа TList с компонентами типа TElement, l0. Позиция компонента si - i, в общепринятых математических обозначениях, в общем случае - некий ключ (типа TPosition), однозначно определяющий положение компонента в последовательности.
Итак, мы различаем понятия - «значение компонента» (типа TElement) и «позиция компонента» (типа TPosition). Содержательно, «позиция компонента» соответствует понятию «индекс элемента в векторе», а пара (ИмяСписка, ПозицияКомпонента) - понятию «переменная с индексом».
Набор операций(*):
Создать пустой список L.
PROCEDURE MakeNull(VAR L:TList)
Вставить элемент x в позицию p списка L.
PROCEDURE Insert(x:TElement;p:TPosition;VAR L:TList)
Удалить элемент p-й позиции списка L.
PROCEDURE Delete(p:TPosition;VAR L:TList)
Получить позицию первого элемента списка L.
FUNCTION First(L:TList):TPosition
Получить позицию последнего элемента списка L.
FUNCTION Last(L:TList):TPosition
Получить позицию элемента списка L, следующего после элемента p-й позиции.
FUNCTION Next(p:TPosition;L:TList):TPosition
Получить позицию элемента списка L, предшествующего элементу p-й позиции.
FUNCTION Previous(p:TPosition;L:TList):TPosition
Получить элемент p-й позиции списка L.
FUNCTION Retrieve(p:TPosition;L:TList):TElement
Найти позицию элемента x в списке L.
FUNCTION Locate(x:TElement;L:TList):TPosition
Вывести элементы списка L (в порядке их позиций в последовательности).
PROCEDURE PrintList(L:TList)
Линейные списки с подобным набором операций обычно называются двунаправленными - с возможностью движения, как от начала последовательности к ее концу, так и в обратном направлении, причем сменить направление движения можно в любой момент.
Нижеприведенные программы используют следующее представление для таких списков.
Ссылочное представление с элементами вида:
Prev:TPosition |
Val:TElement |
Next:TPosition |
|
|
|
ссылка на предыдущий ссылка на следующий
Использование двух ссылочных полей позволяет предложить «равноправную» реализацию для движений вперед-назад.
Для «равноправно-быстрого» выхода, как на первый, так и на последний элемент в заголовок (head) списка включим две ссылки - на первый и на последний элемент.
При обработке последовательностей обычно имеются технические трудности на концах. Один из известных приемов устранения этих трудностей - предусмотреть «упорчики» (ограничители, математически - выделить верхнюю и нижнюю грань).
В нашем случае двунаправленного списка удобно - замкнуть список в кольцо, тогда начальный и конечный «упорчики» можно слить, а в качестве этого «объединенного упорчика» взять заголовок списка:
Ссылка
на заголовок списка
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Выделенный элемент внутреннего представления является заголовком списка (и «упорчиком»), он содержит: в поле Next - ссылку на 1-й компонент списка, в поле Prev - ссылку на последний компонент списка, в поле Val - пустое-неопределенное значение.
Нижеприведенные реализации обладают некоторыми «недокументированными» свойствами, проистекающими из особенностей внутреннего представления. Некоторые из этих свойств фактически надо «документировать» (в смысле, уточнить вышеприведенную семантику операций):
В результате операций вставки-удаления у (оставшихся) элементов списка не изменяется (физическое) значение позиции (типа TPosition), хотя с логической точки зрения - «старый первый» может уже не быть «новым первым», а «старый непоследний» может оказаться «новым последним». Можно сохранять значения позиций ранее просмотренных элементов и позже использовать их для быстрого возврата в интересующую позицию (...прелести почти-прямого доступа).
Next(Last(L),L)=Prev(First(L),L)=L, поэтому:
Next(Next(Last(L),L),L)=First(L),
Prev(Prev(First(L),L),L)=Last(L).
В частности, Insert(x,Last(L),L) - вставит новый элемент на место последнего, а старый последний так и останется новым последним. Как добавить элемент в конец последовательности?... вставить в позицию «после последнего» - Next(Last(L),L)... хотя возможно правильнее было бы - пополнить состав операций специальной операцией «Добавить в конец»...
Как в цикле просмотра контролировать завершение?... например проверкой просматриваемой позиции p на условие Next(Last(L),L).
PROGRAM\Prg7a\Project1.dpr Версия реализации, не использующая понятие «Класс».
Инструменты модуля почти не защищены. Это связано не только с тем, что определение структуры внутреннего представления пришлось вынести в секцию интерфейса. Серьезные трудности имеются в реализации контроля согласованности параметров операций - действительно ли список L имеет элемент в p-й позиции. С логической точки зрения такой контроль реализуем, например - можно просмотреть список, начиная от 1-го элемента, сравнивая «p» с позицией просматриваемого элемента, однако с прагматической - неразумно обременять эффективно реализуемую операцию Insert(x,p,L) столь неэффективно реализуемым контролем согласованности параметров. ...А с третьей стороны... вставив новый элемент в ранее сохраненную позицию элемента, который позже был удален,... трудно будет выяснять причины странных итоговых результатов работы программы...
PROGRAM\Prg7b\Project1.dpr Объектная версия реализации.
Инструменты модуля защищены лучше, но синтаксис интерфейса немного изменился... придется вносить соответствующие синтаксические изменения и в программы, ранее написанные с использованием предыдущей версии модуля... Проблема контроля согласованности параметров операций осталась в прежнем виде.
PROGRAM\Prg7c\Project1.dpr Другая объектная версия реализации.
В этой версии ликвидирована проблема контроля согласованности параметров операций... возможность явного использования понятия позиция теперь попросту исключена...
Семантика операций основана на понятии «текущая позиция», которая используется и перемещается операциями. «Список» - теперь не столько «тип данный», скорее это «объект». Этот «объект» теперь имеет (изменяющееся) внутреннее состояние - «текущая позиция текущего элемента списка». Такого стиля семантика известна нам по типу данных FILE. В свое время, в задаче построения ряда Фарея, мы рассматривали реализацию АТД «Однонаправленный линейный список», основанную на семантике именно этого стиля.
PROGRAM\Prg7d\Project1.dpr Еще одна объектная версия.
В этой версии операциям придана функциональная форма - кроме основного своего назначения операции-функции возвращают объект, к которому были применены (SELF). Это позволяет широко использовать выражения специфичного объектно-функционального вида. Трудно сказать, «хорошо это или плохо». С одной стороны - «порою очень удобно», с другой - используются функции с «побочным эффектом», с третьей - в «побочном эффекте» и заключен их основной смысл «изменять внутреннее состояние объекта».
Введение в объектно-ориентированное программирование, основные понятия.
Класс – можно понимать (в первом приближении) как новый структурный тип данных, но в трактовке более близкой к понятию абстрактный тип данных, объединяющей собственно данные с операциями над ними.
Объект – экземпляр (instance) класса, можно понимать как данное типа класс, а в самом ближнем контексте просто как переменную типа класс. Дело в том, что «объект» - понятие предельно абстрактного уровня, а здесь и сейчас нас интересует это понятие пусть и не в общефилосовском смысле, но уже в смысле – объект предметной области:
для которой нам предстоит разработать информационную модель, с целью решать задачи этой предметной области,
и главное, описать все это – и способ представления информационной модели и алгоритмы решения соответствующих задач, в терминах самой предметной области, в виде достаточно адекватном нашим рассуждениям об этой предметной области.
На это и нацелены методы и средства объектно-ориентированного проектирования и программирования.
И так, объект - это переменная типа класс, т.е. хранилище данных – информации об объекте предметной области:
объект имеет обозначение (имя переменной...),
имеет значение,
но в семантике объектов еще больше динамики, объекты не просто хранилища данных (значения которых могут изменяться в периоде выполнения программы), но включают и операции над этими данными, поэтому об объектах принято говорить, выделяя понятия:
состояние объекта – оно представлено полями и определяется хранимыми в них данными,
структура объекта - структура хранимой информации о полях и методах объекта,
поведение объекта - оно определяется методами класса, они общие для всех объектов (как переменных) одного класса, но это «линия поведения», а собственно поведение («история поведения») у каждого объекта индивидуальное – это последовательность осуществленных операций, протоколом которых является последовательность состояний этого объекта.
Определяющая характерная особенность классов – это средства инкапсуляции, позволяющие скрыть:
способ представления значений такого типа, это абстракция данных – отвлечение от способа представления состояния объекта,
способ реализации операций с такими значениями, это процедурная абстракция – отвлечение от способа реализации поведения объекта.
Средства инкапсуляции - это те новые средства программирования, которые нам (программистам) дают модули, но классы существенно усиливают эту возможность, позволяют на уровне типа данных детализировать ограничения видимости компонентов класса.
Абстракция данных скрывает способ представления объекта и этим перекрывает стандартные возможности: доступа к компонентам объекта (селекция), модификации компонентов объекта и создания объектов такого типа. Естественно методы класса должны в защищенной форме компенсировать эти потери:
Методы-селекторы – позволяют извлекать свойства объекта, например значения его полей, но не изменяют состояние объекта.
Методы-модификаторы – позволяют изменять состояние объекта, но «стараются пресекать» изменения «правильного» состояния в «неправильное».
Методы-генераторы – на базе существующего объекта (и параметров метода) позволяют создавать новые объекты этого класса, причем «правильные», и «стараются пресекать» попытки изменения состояния базового объекта. Конструкторы класса являются разновидностью генераторов, а точнее базовой основой реализации методов-генераторов.
Пример. «Точка на плоскости».
Точку на плоскости можно представить, например парой (x,y) декартовых координат или (,) – полярных. Для пользователя понятие «точка на плоскости» не зависит от способа её представления, решая свои задачи, он пожелает узнать любое из её свойств, когда-то -угол, а когда-то y-координату. Выбирая способ представления класса, нам придётся выбрать одно из представлений точки, если нам не хочется «возиться» с избыточным представлением, поскольку существенной пользы от этого не предвидим.
Object Pascal 2 |
C (C++) |
unit Unit1; interface TYPE TCPoint= CLASS PROTECTED x:REAL; PRIVATE y:REAL; |
//Файл unit1.h: class TCPoint{ protected: double x; private:double y; |
Спецификатор protected не проявит никаких отличий от private, но это пока, а в будущем (в наследовании) проявит... |
|
Cкрыв способ представления точек, берем на себя ответственность – восстановить доступные инструменты для работы с точками:
|
|
PUBLIC FUNCTION GetX:REAL; FUNCTION GetY:REAL; |
public: double GetX(); double GetY(); |
|
|
FUNCTION GetRo:REAL; FUNCTION GetFi:REAL; FUNCTION GetEq(prmP:TCPoint ):BOOLEAN; |
double GetRo(); double GetFi(); bool GetEq(TCPoint prmP);
|
|
|
PROCEDURE SetX( prmVal:REAL); PROCEDURE SetY( prmVal:REAL); |
void SetX(double prmVal);
void SetY(double prmVal); |
|
|
PROCEDURE SetRo( prmVal:REAL); PROCEDURE SetFi( prmVal:REAL); PROCEDURE Rotat{поворот}( prmDFi:REAL); PROCEDURE Sum{сдвиг}( prmP:TCPoint); |
void SetRo(double prmVal);
void SetFi(double prmVal);
void Rotat/* поворот */( double prmDFi); void Sum/*сдвиг*/( TCPoint prmP); |
|
|
CONSTRUCTOR GenXY( prmX,prmY:REAL); CONSTRUCTOR GenRoFi( prmRo,prmFi:REAL); |
|
Прежде чем рассматривать объявление конструкторов в С++ обсудим два возникших вопроса:
В Object Pascal объявлено два конструктора, но в С++ конструктор должен иметь имя TCPoint – можно ли объявить два метода с одинаковым именем?
В С++ должен быть объявлен конструктор по умолчанию, либо ни одного конструктора не должно быть объявлено (тогда конструктор по умолчанию создается автоматически). Но в Object Pascal оба объявленных конструктора имеют параметры. Обязательно ли объявлять третий – конструктор по умолчанию?
Представить ответы на эти вопросы нам помогут средства программирования в Object Pascal 2 и С++:
Инициализация:
переменных при их объявлении, и
формальных параметров при их спецификации.
Перегрузка (overload) функций-процедур и методов.
Инициализация переменных.
Object Pascal 2 |
C (C++) |
Описание переменной (с инициализацией): ИмяПеременной : T = ИнициализирующаяКонстанта Нельзя инициализировать сразу нескольких переменных одной константой. ИнициализирующаяКонстанта для структурных типов:
(ИмяПоля:Значение , ... )
(ЗначениеЭлемента , ... ) Значения перечисляются в порядке по строкам и должны быть перечислены все. |
Описание переменных (с инициализацией): T ИмяПеременной [[k]...] = ИнициализирующаяКонстанта , ... ; Можно инициализировать любые переменные из списка объявляемых, каждую своей константой. ИнициализирующаяКонстанта для структурных типов: {ЗначениеЭлемента , ... } Если значения перечислены не все, остальные считаются равными 0 (с учетом правил приведения типов). |
|
|
Инициализация формальных параметров.
Инициализация формальных параметров осуществляется аналогично, после спецификации (:T) типа формального параметра можно использовать конструкцию = ИнициализирующаяКонстанта |
Инициализация формальных параметров осуществляется аналогично, объявление формального параметра может заканчиваться конструкцией = ИнициализирующаяКонстанта |
В вызове такой функции (в операторе такой процедуры) список фактических параметров может быть короче списка формальных, если у каждого из «хвостовых» параметров объявлено инициализирующее значение, оно будет считаться значением фактического по умолчанию. Естественно, нельзя инициализировать параметры, передаваемые ссылкой. |
|
Перегрузка (overload) функций-процедур и методов.
В программе (и модуле) можно описать несколько функций (процедур) с одинаковым именем – это называется перегрузкой.
В Object Pascal 2 перегружающие (друг друга) описания должны быть специфицированы – после заголовка описания (после точки с запятой) должен присутствовать спецификатор (с точкой с запятой): overload;
В С++ перегрузка функций считается типовой ситуацией, не требующей никаких специфицирующих оговорок.
Семантика вызова перегруженной функции (оператора перегруженной процедуры) не должна оказаться двусмысленной, поэтому на оформление перегружающих (друг друга) описаний накладывается требование - списки формальных параметров перегружающих описаний должны быть несовместимы:
либо по количеству параметров,
либо по типу хотя бы одной пары параметров, стоящих на одном и том же месте по порядку.
Тип возвращаемого значения функции не участвует в проверке несовместимости.
При проверке требования о несовместимости надо учитывать:
Формальные параметры с инициализацией значения по умолчанию вносят дополнительные тонкости в это требование.
Реально проверяются не столько требования о несовместимости списков формальных параметров перегружаемых описаний, сколько однозначность выбора описания для каждого вызова функции (оператора процедуры). В С++ проверка этих требований осложняется ещё и тем, что при передаче параметров могут неявно отрабатывать приведения типа фактических параметров к типу формальных.
Перегрузка методов оформляется по тем же правилам.
PROGRAM\overload\PRG01\Project1.dpr
PROGRAM\C(C++)\overload\prg01\prg01.dsw
Теперь снова вернёмся к нашему примеру «Точка на плоскости».
Теперь мы знаем, что мы имеем возможность объявить несколько одноимённых методов, в частности несколько конструкторов в С++.
Вопрос о конструкторе по умолчанию может быть решён несколькими способами:
Можно объявить конструктор без параметров, например:
TCPoint();
Можно в одном из конструкторов инициализировать все формальные параметры, например:
TCPoint/*GenXY*/(double prmX=0, double prmY=0);
Тогда этот конструктор будет (по совместительству) конструктором по умолчанию, т.к. его можно вызывать с пустым списком параметров.
Но(!!!) надо помнить – конструктор по умолчанию может быть только один (иначе возникнет двусмысленность, какой из них вызывать...).
Вопрос о конструкторе GenRoFi к сожалению останется:
TCPoint/*GenRoFi*/(double prmRo, double prmFi);
Такое объявление недопустимо – такая перегрузка выше объявленного TCPoint/*GenXY*/ нарушает требования о несовместимости.
TCPoint/*GenRoFi*/(float prmRo, float prmFi);
Такая перегрузка приемлема, но представляется не очень естественной, к тому же потребует использования приёмов явного приведения типа double float double
Можно подумать ещё о каких-нибудь подходящих способах обхода этой ситуации.
Object Pascal 2 |
C (C++) |
|
|
CONSTRUCTOR GenXY( prmX,prmY:REAL); CONSTRUCTOR GenRoFi( prmRo,prmFi:REAL); |
TCPoint/*GenXY*/( double prmX=0, double prmY=0); //Пусть будет так: void setRoFi/*GenRoFi*/( double prmRo, double prmFi); // т.е. модификатор, // а не конструктор. |
|
|
FUNCTION GenRotat( prmDFi:REAL):TCPoint; FUNCTION GenSum( prmP:TCPoint):TCPoint; END{класса}; |
TCPoint GenRotat( double prmDFi); TCPoint GenSum( TCPoint prmP); }/*класса*/; |
implementation FUNCTION TCPoint.GetX:REAL; BEGIN GetX:=x END; // ... GetY ... аналогично FUNCTION TCPoint.GetRo :REAL; BEGIN GetRo:= SQRT(x*x+y*y) END; // ... GetFi ... FUNCTION TCPoint.GetEq( prmP:TCPoint):BOOLEAN; BEGIN GetEq:=(x=prmP.x)AND (y=prmP.y) END; PROCEDURE TCPoint.SetX( prmVal:REAL); BEGIN x:=prmVal END; // ... SetY ... SetRo ... PROCEDURE TCPoint.SetFi( prmVal:REAL); VAR r:REAL; BEGIN r:=SQRT(x*x+y*y); x:=r*COS(prmVal); y:=r*SIN(prmVal) END; PROCEDURE TCPoint.Rotat( prmDFi:REAL); BEGIN SetFi(GetFi+prmDFi) END; // ... Sum ... CONSTRUCTOR TCPoint.GenXY( prmX,prmY:REAL); BEGIN x:=prmX;y:=prmY END; CONSTRUCTOR TCPoint.GenRoFi (prmRo,prmFi:REAL); BEGIN x:=0; y:=0; SetRo(prmRo); SetFi(prmFi) END; // ... GenRotat ... FUNCTION TCPoint.GenSum( prmP:TCPoint):TCPoint; BEGIN GenSum:=TCPoint. GenXY(x+prmP.x,y+prmP.y) END; END. |
//Файл unit1.cpp: #include "unit1.h" double TCPoint::GetX() {return x;} // ... GetY ... аналогично double TCPoint::GetRo() {return sqrt(x*x+y*y);} // ... GetFi ... bool TCPoint::GetEq( TCPoint prmP) {return (x==prmP.x)&& (y==prmP.y);} void TCPoint::SetX( double prmVal) {x=prmVal;} // ... SetY ... SetRo ... void TCPoint::SetFi( double prmVal){double r; r=sqrt(x*x+y*y); x=r*cos(prmVal); y=r*sin(prmVal);} void TCPoint::Rotat( double prmDFi){ SetFi(GetFi()+prmDFi);} // ... Sum ... TCPoint::TCPoint/* GenXY*/( double prmX, double prmY) {x=prmX;y=prmY;} void TCPoint::setRoFi /*GenRoFi*/(double prmRo, double prmFi) {x=0; y=0; SetRo(prmRo);SetFi(prmFi);} // ... GenRotat ... TCPoint TCPoint::GenSum( TCPoint prmP) {return TCPoint( x+prmP.x,y+prmP.y); } |
Замечания к С++ программе. Рассмотрим немного иную реализацию метода GenSum:
TCPoint TCPoint::GenSum(TCPoint prmP){TCPoint u;
u.x=x+prmP.x; u.y=y+prmP.y; return u;}
В этой реализации сначала (неявным вызовом конструктора по умолчанию) создается локальный объект u, потом он модифицируется и возвращается как значение функции.
Вызывает беспокойство, что возвращаемое функцией значение является локальным объектом, но это допустимо - семантикой вызова функции предусмотрено копирование возвращаемого значения. Вот если бы функция возвращала указатель на локальную переменную, то возникли бы проблемы...
Фактически в этой реализации явно прописано ровно то, что в предыдущей реализации предписывает семантика явного вызова конструктора в С++.
TCPoint TCPoint::GenSum(TCPoint prmP){
TCPoint u=TCPoint(x+prmP.x, y+prmP.y); return u;}
В этой реализации использована инициализация переменной типа класс явным вызовом конструктора в С++. Отметим, что в Object Pascal 2 такой возможности нет.
TCPoint TCPoint::GenSum(TCPoint prmP){
TCPoint u(x+prmP.x, y+prmP.y); return u;}
Эта реализация просто иллюстрирует, что в предыдущем случае можно было использовать сокращенную запись инициализации вызовом конструктора.
Object Pascal 2 |
C (C++) |
program Project1; uses Unit1; TYPE TPoint= RECORD x,y:REAL END; VAR p0:TPoint; p1,p2,p3: TCPoint; BEGIN p0.x:=1.5; p0.y:=2*p0.x; |
//Файл prgoopC.cpp : #include "unit1.h" main(){typedef struct{double x,y;}TPoint; TPoint p0; TCPoint p1,p2,p3; p0.x=1.5; p0.y=2*p0.x; |
Тип TPoint не препятствует стандартному (прямому) доступу к компонентам. |
|
// p1.x:=1.5; p1.y:=2*p1.x; |
// p1.x=1.5; p1.y=2*p1.x; |
Но при попытке аналогичной работы с переменной типа TCPoint получаем сообщение периода трансляции: Undeclared identifier: 'x' private-компонент x объекта p1 – невидим вне методов класса. |
|
// p1.SetX(1.5); // p1.SetY(2*p1.GetX); |
|
Попытка воспользоваться public-методами класса тоже оказывается неудачной – сообщение периода выполнения: access violation... (нарушение прав доступа) |
|
В Object Pascal 2 описание переменной типа класс не приводит к её созданию, необходим явный вызов конструктора: |
|
p1:=TCPoint.Create; p1.SetX(1.5); p1.SetY(2*p1.GetX); |
p1.SetX(1.5); p1.SetY(2*p1.GetX()); |
Откуда взялся конструктор Create? В Object Pascal 2, если не объявлено, чьим наследником является класс, то считается, что он наследник предопределенного класса TObject и наследует в частности конструктор Create своего родителя. |
В С++ явный вызов конструктора не понадобился, так как конструктор (неявно) отработал уже в объявлении объекта p1. Отметим, что в С++ конструкторы не наследуются.
|
p2:=p1; WRITELN(p2.GetX,p2.GetY); p1.SetX(-1); p2.SetY(-2); WRITELN(p1.GetX,p1.GetY, p2.GetX,p2.GetY); |
p2=p1; cout<<p2.GetX()<<p2.GetY(); p1.SetX(-1); p2.SetY(-2); cout<<p1.GetX()<<p1.GetY() <<p2.GetX()<<p2.GetY(); |
|
В С++ в отличии от Object Pascal 2:
|
p2:=TCPoint.GenXY(1,2); WRITELN(p1.GetX,p1.GetY, p2.GetX,p2.GetY); |
p2=TCPoint/*GenXY*/(1,2); cout<<p1.GetX()<<p1.GetY() <<p2.GetX()<<p2.GetY(); |
|
|
p3:=p2.GenXY(3,4); WRITELN(p3.GetX,p3.GetY, p2.GetX,p2.GetY); p2.SetX(-3); p3.SetY(-4); WRITELN(p3.GetX,p3.GetY, p2.GetX,p2.GetY); |
//p3=p2.TCPoint(3,4);
|
Присваивание p3:=p2... в итоге имеет такой же смысл, как и ранее рассмотренный случай (p2:=p1): сначала было изменено значение существующего объекта p2, а потом, согласно семантике присваивания по ссылке, p3 стало дополнительным именем объекта p2. |
p3=p2.TCPoint(3,4); даст сообщение: function-style cast' : illegal as right side of '.' operator в С++ нельзя вызывать конструктор как метод объекта.
|
p2:=TCPoint. GenRoFi(1,PI/6); p3:=p1.GenSum(p2); |
p2.setRoFi(1,pi/6);
p3=p1.GenSum(p2);
/* Примеры объявлений объектов с инициализацей вызовом конструктора: */ TCPoint p4=TCPoint(1,2); TCPoint p5(1,2); TCPoint p6(1); |
Зафиксируем и уточним синтаксис и семантику новых понятий, которые были задействованы в рассматриваемом примере.
О семантике присваивания.
Динамический тип данных – это тип данных, значения которого могут отличаться друг от друга по количеству компонентов и даже по структуре связей между компонентами. Такие типы существуют в математике и в других предметных областях, например разнообразные виды последовательностей (*).
В классическом Pascal имелся только один динамический тип – последовательный файл, но использование переменных этого типа фактически было строго ограничено. В частности оператором присваивания такой переменной нельзя было присвоить значение, а использовать переменную типа файл в операторе процедуры в качестве фактического параметра можно было только, если параметр передается ссылкой.
Динамическая переменная – это переменная, которая явно создается и уничтожается соответствующим оператором в программе в периоде её выполнения. Главное методологическое назначение указателей и динамических переменных – служить адекватным и эффективным средством построения динамических структур данных, например разнообразных видов последовательностей.
В процедурных языках программирования такие переменные появились не сразу, но очень рано, просто потому что динамические структуры данных, которые программно строятся с помощью указателей и динамических переменных, были известны изначально ещё с эпоху машинного программирования.
Класс – это понятие позволило интегрировать внеязыковое понятие «динамический тип данных» с языковыми возможностями указателей и динамических переменных в конструировании «динамических структур данных». Класс позволяет оформить ранее внеязыковое понятие «динамический тип данных» как языковой тип данных, определяемый пользователем-программистом (**).
Класс - это динамический тип данных по определению (по крайней мере в Object Pascal 2 и C++), независимо от того как обстоят дела с реальным (физическим) количеством компонентов в его значениях и со связями между ними. Почему?... видимо потому что уже на методологическом уровне разделены понятия «логическое» и «физическое» множество возможных значений этого типа данных. Инкапсуляция способа представления данных этого типа закрывает возможность однозначной трактовки, которая вполне может оказаться различной для логического множества возможных значений и различных физических его представлений.
Появление динамических типов данных в языках программирования привело к расширению семантики понятия переменная, а вместе с этим и к расширению семантики понятия «присваивание».
Семантика присваивания по значению – это традиционная семантика оператора присваивания, которую мы изначально определили, и на которой в определенном смысле (пока) базируем семантику программы в целом. Согласно этой семантике полное значение выражения правой части оператора присваивания копируется и сохраняется в хранилище данных левой части оператора присваивания.
Отметим, что присваивание переменным типа указатель выполняется согласно этой традиционной семантике. Надо четко различать понятия «динамическая переменная» (как переменная, на которую показывает указатель), и «переменная динамического типа» (как переменная, значения которой имеют динамический тип). Если динамическая переменная имеет статический (нединамический) тип, то присваивание ей тоже выполняется согласно семантике по значению. Другое дело, что с содержательной точки зрения указатель и соответствующая динамическая переменная связаны с одним и тем же хранилищем данных, но поразному - первый на него показывает, а вторая его обозначает...
Если же переменная имеет значение динамического типа, например типа «стек», определенного как класс и к тому же реализованного как цепочка с указателями, то естественно возникает много вопросов на тему – насколько рациональным является использование семантики по значению для присваивания значения такой переменной. Единого устоявшегося мнения на сегодня в теории и методологии программирования на этот счет нет.
Семантика присваивания по ссылке используется в некоторых современных языках программирования для переменных динамического типа. Согласно этой семантике значение выражения правой части оператора присваивания не копируется, а хранилище данных, в котором оно хранится, получает (дополнительное) обозначение в виде переменной левой части присваивания.
Надо отметить, что в данном определении семантики по ссылке остаются еще вопросы – а что это за хранилище, в котором хранится значение выражения правой части оператора присваивания... Но обычно, когда в левой части присваивания стоит переменная динамического типа в правой части тоже переменная, именно её хранилище и имеется в виду. Однако, используя методы класса иногда можно написать и сложные выражения в правой части... тогда значение этого выражения видимо всё же в каком-то виде хранится в каком-то подходящем временном хранилище данных... оно и получит обозначение в виде переменной левой части присваивания...
О семантике передачи параметров значением и возвращении значения функцией.
Семантика передачи параметров значением фактически базируется на семантике присваивания, именно так она и была определена в свое время в теме «Процедуры и функции». Естественно это повлечет свои последствия для случая, когда параметр имеет динамический тип. Аналогичная ситуация с семантикой возвращения значения функцией.
Объекты. Семантика присваивания и последствия этого.
Object Pascal 2.
Для объектов действует семантика присваивания по ссылке, естественно последствия проявляются в зависящих от неё местах.
Присваивание переменной типа класс значения переменной типа класс даёт эффект двух имен у одного хранилища данных.
Если в левой части присваивания находится ранее уже созданный объект, то возможно получим «мусор» – хранилище данных потеряет обозначение (одно из ранее имевшихся).
Если в правой части присваивания находится более сложное выражение, то эффект двух имен может не проявиться, это зависит от семантики этого выражения – возможно (обычно) его значение хранится во временном хранилище данных (без имени), которое теперь получит обозначение.
Если параметр функции-процедуры передается значением, а в качестве фактического параметра в вызове используется объект, то реально получим эффект передачи параметра ссылкой.
Это можно пронаблюдать тестированием – в теле соответствующей функции-процедуры присвоить какие-нибудь новые значения этому параметру, после выполнения вызова значение фактического параметра соответственно изменится. Этого не должно происходить при передаче параметра значением и не происходит в случае «нормального» фактического, например типа запись вместо типа класс (что тоже можно проверить тестированием).
Возвращаемое функцией значение всегда сохраняется во временном хранилище данных, откуда оно и возвращается. Поэтому никаких неожиданных эффектов от семантики по ссылке не проявляется.
С++.
Для объектов действует семантика присваивания по значению, поэтому никаких неожиданных эффектов не проявляется.
Присваивание переменной типа класс значения переменной типа класс не даёт эффекта двух имен у одного хранилища данных. Оба хранилища были созданы по крайней мере ещё при объявлении этих переменных, и в присваиваниях каждое из них участвует независимо.
Если параметр функции передается значением, а в качестве фактического параметра в вызове используется объект, то тоже получим ожидаемый результат, а не эффект передачи параметра ссылкой как в Object Pascal 2.
Это можно пронаблюдать тестированием, аналогичным вышеописанному для Object Pascal 2 – оно покажет ровно то, что и должно происходить при передаче параметра значением.
Возвращаемое функцией значение всегда сохраняется во временном хранилище данных, откуда оно и копируется для возвращения согласно семантике по значению, поэтому никаких неожиданных эффектов не наблюдается.
Однако это не означает, что в С++ по обсуждаемому вопросу полностью сохранена «дообъектная ситуация» и не призошло изменений в семантике понятий «переменная» и «присваивание» в связи с появлением классов и определяемых с их помощью динамических типов данных.
Во-первых, семантика присваивания по значению предписывает так называемое «побитовое копирование» значения правой части присваивания в хранилище переменной левой части. При таком копировании, если компонент переменной имеет тип указатель, то он получает соответственно значение указателя, но данное, на которое он показывает, не копируется. Это данное с содержательной точки зрения в некотором смысле теперь будет частью значения двух переменных, той которую копировали и той куда копировали. Эта ситуация может спровоцировать трудно обнаруживаемые ошибки(*).
Во-вторых, семантика присваивания по значению побитовым копированием в С++ действует на оператор присваивания, а для случаев
инициализации объектов другим объектом,
передачи параметров-объектов значением,
возвращения значения-объекта функцией
эта семантика действует только по умолчанию, а в общем случае действует семантика копирования, которая базируется на понятии конструктор копирования.
Конструктор копирования – это конструктор, имеющий точно один параметр - ссылку на объект этого же класса.
Если в классе не объявлен конструктор копирования, то такой конструктор строится автоматически. Он создает объект и устанавливает его значение «побитовым копированием» значения своего фактического параметра.
Конструктор копирования вызывается автоматически (неявно) в каждом из случаев:
при описании объекта с инициализацией другим объектом;
при передаче объекта в функцию по значению;
при возврате объекта из функции.
Объявление конструктора копирования:
ИмяТипаКласс( const ИмяТипаКласс & prm );
Конструктор копирования вызывается неявно в вышеописанных ситуациях, а также явно, как и любой другой конструктор. При этом создается объект и выполняется тело конструктора, которое обычно устанавливает значение нового объекта (подходящим более полноценным способом, чем «побитовое копирование»).
... пока всё...
Program\PRGOOP\Project1.dpr
Program\C(C++)\prgoop\prgoopC.dsw
(*) Интуитивно достаточно ясно, что наличие памяти позволяет процессу: многократно повторять в выходном потоке некоторые данные входного, а также передавать некоторые данные в выходной поток не в том порядке, в котором они поступали из входного, например задерживать передачу одних данных, пропуская вперед другие.
(*) А возможно, в этом и есть их «истинная суть» по происхождению, содержанию и программистской трактовке.
(**) Книги красиво живут на стеллажах - к каждой имеется прямой доступ, но это… пока они не нужны… А когда они нужны, книги имеют привычку перемещаться к месту использования и там складываться в стопки… и теперь доступ к ним уже стековый… Странно, но факт…
(**) В общем случае, размер «окна просмотра» может со временем изменяться - скорость движения передней границы может иногда быть меньше или больше скорости движения задней границы окна.
(*) Синтаксические конструкции многомодульного программирования появились в «американских» языках даже раньше, чем в «европейских». В европейском языке AlgoL-60 ещё нет ничего такого, а в американском ForTran уже предусмотрена раздельная компиляция и для организации межмодульной связи имеется языковая конструкция common-блок.
(*) При большом желании эту ситуацию можно трактовать точно также как вариант объявления локальной переменной, но ощутимой пользы из такой трактовки не выжмешь...
(*) Идея последовательности и натурального ряда видимо происходит из нашего желания всегда иметь возможность от текущего перейти к «следующему» текущему. Так появляется «потенциально бесконечный счет», а далее «прибавить» и «умножить» - повторение и повторное повторение. Желание иметь обратную полноценно симметричную возможность - перейти к «предыдущему», дает идею «целых чисел» и далее «отнять». Но обращение операции «умножить» уже порождает идею рациональных чисел... с совсем непростым порядком на них... путем пополнения не просто приписыванием слева, как в случае отрицательных чисел, а «вставками»...
Однако вышеперечисленные желания можно в определенном смысле удовлетворить и другим «магическим» способом - замкнув конечную последовательность в кольцо. В арифметике «по модулю p» всего p чисел, операция «перейти к следующему» однажды «возвращает на круги своя». Однако имеются не только «прибавить» и «умножить», но и «отнять». А если p - простое число (еще одно «магическое» понятие), то и «умножить» обратимо.
(*) Ниже, во-первых не оговорены условия применимости операций, а во-вторых не оговорены ограничения на порядок выполнения операций, которые имеются в языке Паскаль.
(**) В стандарте Паскаль (и у Н.Вирта) эта операция называется GET.
(***) Read реализуется: PROCEDURE Read(VAR x:TVal;VAR F:TFile);
BEGIN x:=Retrieve(F); Next(F:TFile) END, а операции Retrieve в стандарте соответствует понятие «буферная переменная» - F^.
(*) которая имеется не только в случае файлов, но и в случае очередей - благодаря тому, что перезапоминанием можно в определенном смысле промоделировать «неразрушающее» чтение...
(*) см. гл.2. в А.В. Ахо, Дж.Д. Хопкрофт, Дж.Д. Ульман. Структуры данных и алгоритмы. М.: Вильямс, 2001. - 384 с.
(*) Стоит обратить внимание на то, что последовательность не обязана иметь элементы только простого и одинакового типа, а если её элементами могут быть последовательности, то мы имеем последовательность последовательностей, иначе говоря дерево...
(**) Муки, через которые прошла теория и методология программирования, в процессе рождения этого понятия ярко демонстрирует «родовое пятно» языка С – массивы, которые в языке имеются как структуры данных, но отсутствуют как тип данных.
(*) Сложно устроенные объекты, обычно имеют компоненты динамического типа (реализованные с использованием указателей), побитовое копирование сильно запутывает смысл присваивания для таких объектов.
Если посмотреть определения классов, например в библиотеке визуальных компонентов Borland, то сразу обращаешь внимание - в Delphi (Object Pascal 2) поля класса обычно имеют тип класс, а в C++Builder поля того же самого класса обычно объявлены указателями на класс. Этот технический приём позволяет унифицировать смысл побитового копирования полей класса, сделать его не зависящим от типа полей. Для так определенных классов семантика присваивания по значению фактически эквивалентна семантике присваивания по ссылке.