Абстрактные структуры данных

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

Например, модуль как абстрактная структура данных на метаязыке может быть описан так:

Имя_модуля: module

Описание внутренней структуры данных

Fcn1: function

Begin

…

end;

fcn2: function

Begin

…

end;

…

end;

Такое описание модуля позволяет рассматривать его в качестве абстрактной структуры данных, если все обращения к внутренней структуре данных осуществляются только через вызовы функций (процедур) модуля. Абстрактная структура данных абстрактна в том смысле, что она не привязана к машинному представлению данных. Работа со структурой данных абстрагирована от деталей её внутренней реализации.

Внутренняя структура данных может быть изменена произвольным образом, и это никак не скажется на использовании модуля, если не изменены спецификации абстрактных операций.

Описание модуля:

Unit Имя_модуля;

Interface

Описание видимых элементов Видимая часть (1)

Implementation

Описание невидимых элементов

Begin Невидимая часть (2)

Инициализация

End.

Модуль рассматривается как отдельно компилируемая программная единица; он является хранилищем описаний различных элементов программы: процедур, функций, переменных, констант, типов и т.д.

Пример:

Два модуля с одинаковым интерфейсом:

1. Стек на основе массива
2. Стек на основе динамических переменных

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.

Дата добавления: 2014-01-07