Абстрактные структуры данных
В современных языках программирования структурам данных уделяется особое внимание (вследствие усложнения решаемых задач). Появляются дополнительные конструктивные элементы (модули, объекты). Возможность использования сложных структур данных позволяет максимально точно описывать реальные объекты внешнего мира и решать сложные задачи. С другой стороны, применение сложных структур данных усложняет отладку и является источником дополнительных ошибок. В качестве решения этих проблем был предложен принцип информационной локализованности. Идея принципа: сложная структура данных локализуется в одном модуле и становится невидимой для других модулей, использующих её, т.е. сложная структура данных перестаёт быть глобальной. Этот принцип нашёл своё воплощение в модулях и объектах. Появление модулей можно рассматривать как технологическое усовершенствование языков программирования, появление объектов – как революционное усовершенствование.
Например, модуль как абстрактная структура данных на метаязыке может быть описан так:
Имя_модуля: module
Описание внутренней структуры данных
Fcn1: function
Begin
…
end;
fcn2: function
Begin
…
end;
…
end;
Такое описание модуля позволяет рассматривать его в качестве абстрактной структуры данных, если все обращения к внутренней структуре данных осуществляются только через вызовы функций (процедур) модуля. Абстрактная структура данных абстрактна в том смысле, что она не привязана к машинному представлению данных. Работа со структурой данных абстрагирована от деталей её внутренней реализации.
Внутренняя структура данных может быть изменена произвольным образом, и это никак не скажется на использовании модуля, если не изменены спецификации абстрактных операций.
Описание модуля:
Unit Имя_модуля;
Interface
Описание видимых элементов Видимая часть (1)
Implementation
Описание невидимых элементов
Begin Невидимая часть (2)
Инициализация
End.
Модуль рассматривается как отдельно компилируемая программная единица; он является хранилищем описаний различных элементов программы: процедур, функций, переменных, констант, типов и т.д.
Пример:
Два модуля с одинаковым интерфейсом:
- Стек на основе массива
- Стек на основе динамических переменных
1. Unit Stack;
interface
type
NameStr=string[15];
Procedure Push(NM:NameStr; M:integer);
Procedure Pop(Var NM:NameStr; Var M:integer);
Function Empty: Boolean;
Implementation
{Описываем внутреннюю изолированную структуру данных}
Const StackSize=100;
Type
Student=record
Name: NameStr;
Mark: integer;
End;
Var
List: array[1..StackSize]of Student;
SP: integer;
Procedure Push; {добвление}
Begin
If SP>StackSize then Exit;
List[SP].Name:=NM;
List[SP].Mark:=M;
SP:=SP+1;
End;
Function Empty; {проверка пустоты стека}
Begin
If SP=1 then Empty:=true
Else Empty:=false
End;
Procedure Pop; {извлечение}
Begin
If Empty then Exit;
SP:=SP-1;
NM:=List[SP].Name;
M:=List[SP].Mark;
End;
{инициализация}
begin
SP:=1
End.
2. Unit Stack;
interface
type
NameStr=string[15];
Procedure Push(NM:NameStr; M:integer);
Procedure Pop(Var NM:NameStr; Var M:integer);
Function Empty: Boolean;
Implementation
Type
Link=^Student
Student=record
Name: NameStr;
Mark: integer;
Next: Link
End;
Var
First: Link;
A: Link;
Procedure Push; {добавление элемента}
Begin
New(A); {создание динамической переменной}
{запись формальных параметров процедуры во внутреннюю структуру}
A^.Name:=NM;
A^.Mark:=M;
A^.Next:=First;
First:=A
End;
Function Empty: Boolean;
Begin
If First=nil then Empty:=true
Else Eempty:=false
End;
Procedure Pop; {извлечение элемента}
Begin
If Empty then Eexit;
A:=First;
First:=First^.Next;
NM:=A^.Name;
M:=A^.Mark;
Dispose(A) {физическое удаление}
End;
{инициализация}
begin
First:=nil
End.
Пример программы, использующей эти модули:
Program UsingStack;
Var
uses Stack;
Name: NameStr;
Mark: integer;
Begin
…
readln (Name, Mark);
push (Name, Mark);
…
end.