Современные технологии программирования
Конспект лекций
назад | содержание | вперед

Лекция 4. Абстракции данных

Содержание

Спецификации для абстракций данных *

Реализация абстракций данных *

Реализация множества intset на языке Object Pascal *

Использование абстракций данных *

Изменяемость *

Классы операций *

Полнота *

Аназиз типов данных *

Мы обсуждали один из основных видов используемых в программировании абстракций — абстракций процедур. Процедуры дают нам возможность добавлять в базовый язык новые операции. Кроме операций, однако, базовый уровень предусматривает различные типы данных, например целые, вещественные, логические, строки и массивы. Нам необходимо иметь возможность добавлять в базовый уровень не только новые операции, но и новые типы данных. Эта необходимость удовлетворяется абстракцией данных.

Какие новые типы данных необходимы, зависит от области применения программы. Например, при реализации компилятора или интерпретатора полезны стеки и символьные таблицы, в то время как в банковской системе естественной абстракцией являются счета. В символической системе вычислений возникают полиномы, а при определении пакета численных функций — матрицы. В каждом конкретном случае абстракция данных состоит из набора объектов, например стеков или полиномов, и набора операций. Например, матричные операции включают в себя сложение, умножение и т. д., а операции над счетами — снятия и вклады.

Новые типы данных должны включать в себя абстракции, как через параметризацию, так и через спецификацию. Абстракции через параметризацию могут быть осуществлены точно так же, как и для процедур, — использованием параметров там, где это имеет смысл. Абстракции через спецификацию достигаются за счет того, что мы представляем операции как часть типа. Чтобы понять, почему операции необходимы, посмотрим, что получится, если будем рассматривать тип просто как набор объектов. В этом случае все, что необходимо сделать для реализации типа, — это выбрать представление памяти для объектов. Тогда все программы могут быть реализованы в терминах этого представления. Однако если представление изменяется (или даже если изменяется интерпретация этого представления), все программы, которые используют этот тип, должны быть изменены.

С другой стороны, предположим, что мы включаем операции в тип следующим образом:

абстракция данных = (объекты, операции)

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

Если обеспечено большое количество операций, отсутствие доступа к представлению не будет создавать для пользователей никаких трудностей — все, что они хотят сделать с объектами, может быть сделано (и при том сделано эффективно) при помощи использования операций. Обычно имеются операции для создания и модификации объектов, а также для получения информации об их значениях. Конечно, пользователи могут увеличивать набор операций определением процедур, но такие процедуры не должны использовать представление.

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

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

Абстракции данных также полезны при модификации и эксплуатации программ. Чаще предпочтительнее изменить структуры данных, чем улучшать производительность или приспосабливаться к изменяющимся требованиям. Абстракции данных сводят все изменения к изменениям в реализации типа — модули же нет необходимости изменять.

Здесь мы рассмотрим задание и реализацию абстракций данных. Кроме того, мы поговорим о том, как можно судить о корректности программ, которые используют реализованные типы, а также рассмотрим некоторые вопросы, которые возникают при проектировании новых типов.

Спецификации для абстракций данных

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

ADT <имя абстрактного типа данных>

Данные

<Здесь приводится описание типа данных>

Операции

<Здесь приводится описание операций на типе данных>

 

Наименование операции

Описание

Вход:

 

Предусловия:

 

Процесс:

 

Выход:

 

Постусловия:

 

end ADT

Рис. 1. Общий вид спецификации абстракции данных.

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

В секции операций содержатся спецификации для всех операций. Если операция — процедура, то ее спецификация будет процедурной спецификацией. (Операция также может быть абстракцией через итерацию.) В этих спецификациях могут использоваться концепции, введенные в секции описания.

На рис. 2 представлена спецификация абстракции данных intset. Наборы целых чисел intset — это ограниченные множества целых чисел с операциями создания нового, пустого набора, проверки данного целого числа на принадлежность данному набору intset и добавления или удаления элементов. Заметим, что в секции описания мы описали наборы целых чисел в терминах математических наборов. Там же мы отметили, что наборы целых чисел — изменяемые, и перечислили все изменяющие операции. В секции операций мы задали каждую операцию в терминах математических наборов.

Спецификация типа данных “Множество”

ADT intset

Данные

Множества - это изменяемые ограниченные наборы элементов (неотрицательных целых чисел). Содержимое множества изменяется следующими операциями:

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

Операции

Операции могут вызываться только объектом “Множество” (тип intset), указатель на который передаётся в них по умолчанию. При описании операций этот объект в разделе “Вход” не указывается.

Наименование операции

Описание

Конструктор

 

Начальные значения:

Максимальное число элементов во множестве newSize.

Процесс:

Инициирует поле Size значением newSize.

 

Опустошить

 

Вход:

Нет.

Предусловия:

Нет.

Процесс:

Удаляет из множества все элементы.

Выход:

Нет.

Постусловия:

Множество - пусто.

 

Добавить

 

Вход:

d – элемент.

Предусловия:

Элемент можно поместить во множество.

Процесс:

Добавляет d во множество, если в нем нет такого элемента.

Выход:

Нет.

Постусловия:

Множество содержит элемент d.

 

Удалить

 

Вход:

d – элемент.

Предусловия:

Нет.

Процесс:

Удаляет элемент d из множества, если d принадлежит множеству.

Выход:

Нет.

Постусловия:

Множество не содержит элемент d.

 

Пусто

 

Вход:

Нет.

Предусловия:

Нет.

Процесс:

Определяет, содержит ли множество элементы. Возвращает значение True, если множество не пусто, False – в противном случае.

Выход:

Булевское значение.

Постусловия:

Нет.

 

Принадлежит

 

Вход:

d – элемент.

Предусловия:

Нет.

Процесс:

Определяет, принадлежит ли элемент d множеству. Возвращает True, если d принадлежит множеству, False - в противном случае.

Выход:

Булевское значение.

Постусловия:

Нет.

 

Объединить

 

Вход:

Множество q.

Предусловия:

Нет.

Процесс:

Создаёт множество, полученное в результате объединения множества с множеством q.

Выход:

Множество.

Постусловия:

Нет.

 

Вычесть

 

Вход:

Множество q.

Предусловия:

Нет.

Процесс:

Создаёт множество, полученное в результате вычитания из множества множество q.

Выход:

Множество.

Постусловия:

Нет.

 

Умножить

 

Вход:

Множество q.

Предусловия:

Нет.

Процесс:

Создаёт множество, являющееся пересечением множества с множеством q.

Выход:

Множество.

Постусловия:

Нет.

 

Элементов

 

Вход:

Нет.

Предусловия:

Нет.

Процесс:

Подсчитывает и возвращает количество элементов во множестве, если множество пустое - ноль

Выход:

Целое - количество элементов во множестве.

Постусловия:

Нет.

 

Элемент

 

Вход:

Нет.

Предусловия:

Нет.

Процесс:

Обеспечивает доступ к элементу множества для чтения так, что если эту операцию поместить в цикл, то можно просмотреть все элементы множества.

Выход:

Элемент множества.

Постусловия:

Множество не модифицируется.

end intset

Рис. 2. Спецификация типа данных intset.

В этой спецификации мы полагаемся на то, что читателю известно, что такое математические наборы; в противном случае спецификация не будет понятна. В общем случае неформальное описание — слабое место неформальных спецификаций. Разумно, конечно, ожидать, что читатель знаком с определенными математическими концепциями (например, с наборами, последовательностями и целыми числами), однако не все типы могут быть хорошо описаны в терминах таких концепций. Если концепции неадекватны, мы должны описать тип настолько хорошо, насколько возможно, даже с использованием рисунков, но, тем не менее, все равно остается опасность, что читатель не поймет описания или истолкует его в другом, чем мы имели в виду, смысле. Этой слабости можно избежать, если использовать формальные спецификации.

Реализация абстракций данных

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

Например, возможное представление для объекта intset — это массив целых чисел, где каждое целое число набора intset соответствует элементу массива. Мы должны решить — должен ли каждый элемент набора встречаться в массиве только один раз или же он может встречаться много раз. В последнем случае операция insert будет работать быстрее, однако операции delete и member будут выполняться медленнее. Если операция member используется часто, мы должны остановиться на первом случае.

Заметим, что здесь мы говорим о двух разных типах: новом абстрактном типе intset, который мы реализуем, и массиве целых, который используется как представление. Каждая реализация будет иметь два таких типа: абстрактный тип и тип представления (reptype). Предполагается, что с типом представления мы имеем дело только при реализации. Все, что мы можем делать с объектами абстрактного типа, — это применять к ним соответствующие данному типу операции.

В следующем разделе мы рассмотрим, как реализовать абстракции данных на языке Object Pascal.

Реализация множества intset на языке Object Pascal

Хотя, конечно, возможно реализовать типы на языках, которые специально не приспособлены для этой цели, более удобно, если тип может быть реализован как отдельный программный модуль. Язык Object Pascal предоставляет такую программную единицу. Эта единица называется модуль (unit). Для реализации же абстрактных типов данных в язык включены классы.

unit USet;

interface

uses SysUtils;

const

n = 5;

type

Intmass = array[0..n-1] of integer;//массив целых переменных размером n

pIntmass = ^Intmass;//указатель на массив

Eoutofrange = class (Exception);//исключение:индекс вышел за пределы диапазона

//---------------------------------------------------------------------------

intset = class //элемент i в множестве, если компонент массива m[i] не равен 0.

private

m: PIntmass;//указатель на динамический массив целых переменных

capacity: integer;//количество компонентов в массиве

function getSet():AnsiString;//возвращает содержимое множества в формате строки

public

//---------------------------------------------------------------------------

property SetStr: AnsiString read getSet;

//---------------------------------------------------------------------------

function enumber(): integer; //мощность множества

//---------------------------------------------------------------------------

function size():integer; // элементов во множестве

//---------------------------------------------------------------------------

function isempty():boolean; // множество пусто

//---------------------------------------------------------------------------

procedure empty();//опустошить множество

//---------------------------------------------------------------------------

function Mul ( b: intset): intset;//умножение множеств

//---------------------------------------------------------------------------

function Sub ( b: intset): intset;//вычитание множеств

//---------------------------------------------------------------------------

function Add ( b: intset): intset;//сложение множеств

//---------------------------------------------------------------------------

function Copy:intset; //конструктор копирования

//---------------------------------------------------------------------------

constructor Create();//конструктор

//---------------------------------------------------------------------------

destructor Destroy;//деструктор

//---------------------------------------------------------------------------

procedure insert(i: integer);//поместить элемент i в множество

//---------------------------------------------------------------------------

function member(i: integer):boolean;

//---------------------------------------------------------------------------

end;

implementation

//---------------------------------------------------------------------------

function intset.getSet():AnsiString;//возвращает содержимое множества в формате строки

var

i: integer;

s: AnsiString;

begin

s:= '[';

for i:= 0 to capacity - 1 do

if m^[i] <> 0 then begin s:= s + IntToStr(i); s:= s + ','; end;

if (s[Length(s)] = ',') then Delete(s,Length(s),1);

s:= s + ']';

result:= s;

end;

//---------------------------------------------------------------------------

function intset.member(i: integer):boolean;

begin result:= m^[i]= 1 end;//элемент i в множестве

//---------------------------------------------------------------------------

procedure intset.insert(i: integer);//поместить элемент i в множество

begin

if ((i < capacity) and (i >= 0)) then m^[i]:= 1

else raise Eoutofrange.Create('i out of range') ;

end;

//---------------------------------------------------------------------------

destructor intset.Destroy;//деструктор

begin

dispose(m);

end;

//---------------------------------------------------------------------------

constructor intset.Create();//конструктор

var

i: integer;

begin

capacity:= n;

new(m);

for i:= 0 to capacity - 1 do m^[i]:= 0;

end;

//---------------------------------------------------------------------------

function intset.Copy:intset; //конструктор копирования

var

i: integer;

t: intset;

begin

t.capacity:= self.capacity;

dispose(m);

new(m);

for i:= 0 to capacity - 1 do t.m^[i]:= m^[i];

end;

//---------------------------------------------------------------------------

function intset.Add ( b: intset): intset;//сложение множеств

var

i: integer;

c: intset;

begin

c:= intset.Create;

for i:= 0 to capacity - 1 do

if ((m^[i] = 1) or (b.m^[i]= 1)) then c.m^[i]:= 1;

result:= c;

end;

//---------------------------------------------------------------------------

function intset.Sub ( b: intset): intset;//вычитание множеств

var

i: integer;

c: intset;

begin

c:= intset.Create;

for i:= 0 to capacity - 1 do

if ((m^[i] = 1) and (b.m^[i]= 0)) then c.m^[i]:= 1;

result:= c;

end;

//---------------------------------------------------------------------------

function intset.Mul ( b: intset): intset;//умножение множеств

var

i: integer;

c: intset;

begin

c:= intset.Create;

for i:= 0 to capacity - 1 do

if ((m^[i] = 1) and (b.m^[i]= 1)) then c.m^[i]:= 1;

result:= c;

end;

//---------------------------------------------------------------------------

procedure intset.empty();//опустошить множество

var

i: integer;

begin

for i:= 0 to capacity - 1 do m[i]:= 0;

end;

//---------------------------------------------------------------------------

function intset.isempty():boolean; // множество пусто

var

i: integer;

r: boolean;

begin

r:= True;

for i:= 0 to capacity - 1 do if (m[i] <> 0) then r:= False;

result:= r;

end;

//---------------------------------------------------------------------------

function intset.size():integer; // элементов во множестве

var

i: integer;

count: integer;

begin

count:= 0;

for i:= 0 to capacity - 1 do if (m[i] <> 0) then inc(count);

result:= count;

end;

//---------------------------------------------------------------------------

function intset.enumber(): integer; //мощность множества

begin

result:= capacity;

end;

//---------------------------------------------------------------------------

Рис. 2. Реализация типа данных intset.

Для представления наборов целых чисел мы использовали динамически создаваемый массив m^ целых чисел фиксированного размера capacity. Компонент массива с индексом i m^[i] представляет элемент множества i. Если элемент i во множестве присутствует, то соответствующий ему компонент массива с индексом i m^[i] содержит значение 1, 0 – в противном случае. Таким образом, пустому множеству соответствует массив, все компоненты которого хранят значения 0. Размер множества задаётся приего создании.

Использование абстракций данных

Если абстракция данных определена, то она не отличается от встроенных типов и ее объекты и операции должны использоваться точно так же, как объекты и операции встроенных типов. Насколько это возможно, зависит от используемого языка программирования. В языке Object Pascal могут быть объявлены переменные нового типа. Как, например,

program PSet;

{$APPTYPE CONSOLE}

uses

SysUtils,

USet in 'USet.pas';

var

a,b,c,d,g,p: intset;

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

begin

a:= intset.Create;//создаётся объект типа intset, указатель на него //заносится в a

b:= intset.Create;

writeln(a.Setstr,' ', a.isempty(), ' ' , a.size());//[] TRUE 0

writeln(b.Setstr);//[]

writeln(c.Setstr);//[]

c:= a.Add(b);//сложить a и b, результат занеcти в с

a.insert(1);//добавить 1 во множество a

writeln(a.Setstr);//[1]

a.insert(4); //добавить 4 во множество a

writeln(c.Setstr);//[]

writeln(a.Setstr);//[1,4]

a.insert(3); //добавить 3 во множество a

writeln(a.Setstr);//[1,3,4]

a.insert(4);

writeln(a.Setstr);//[1,3,4]

b.insert(2);

writeln(b.Setstr);//[2]

..c.Free;//освобождаем память из под объекта

c:= a.Add(b);//сложить a и b, результат занеcти в с

writeln(c.Setstr,' ',c.isempty(),' ', c.size());//[1,2,3,4] FALSE 4

d:= a.Add(b); //сложить a и b, результат занеcти в d

writeln(d.Setstr);//[1,2,3,4]

g:= b.Mul(c); //умножить b и c, результат занеcти в g

writeln(g.Setstr);//[2]

readln;

end.

 

Изменяемость

Абстракции данных либо изменяемы (с объектами, значения которых могут изменяться), либо неизменяемы. К определению этого аспекта типа следует относиться внимательно. В общем случае тип должен быть неизменяемым, если его объекты естественным образом имеют неизменяющиеся значения. Это, например, имеет место для таких математических объектов, как целые числа, полиномы и комплексные числа. Как правило, тип должен быть изменяемым, если моделируется что-то из реального мира, как, например, запоминающее устройство или автомобиль в имитационной системе, где значения объектов естественным образом изменяются с течением времени. Например, автомобиль может двигаться или стоять, в нем могут находиться или не находиться пассажиры. Однако мы можем все равно предпочесть использовать в этом случае неизменяемый тип, потому что он обеспечивает большую надежность. Вот почему списки неизменяемы.

Принимая решение об изменяемости, иногда необходимо учесть соотношение эффективности и надежности. Неизменяемые абстракции надежнее, чем изменяемые, так как не возникает никаких проблем при разделении объектов. Однако для неизменяемых абстракций объекты могут создаваться и уничтожаться чаще, что означает, что чаще будет необходима сборка мусора. Например, представлять наборы intset как списки, вероятно, не слишком хорошо, если часто используются операции insert и delete.

Заметим, что в любом случае изменяемость или неизменяемость—это свойство типа, а не его реализации. Реализация должна просто поддерживать это свойство абстракции.

Классы операций

Операции абстракции данных распадаются на четыре класса.

  1. Примитивные конструкторы. Эти операции создают объекты соответствующего им типа, не используя никаких объектов в качестве аргумента. Примерами таких операций являются операции create для наборов intset и списков.
  2. Конструкторы. Эти операции используют в качестве аргументов объекты соответствующего им типа и создают другие объекты такого же типа. Например, операции add и mul.
  3. Модификаторы. Эти операции модифицируют объекты соответствующего им типа. Например, операции insert и delete — модификаторы для наборов intset. Очевидно, что только изменяемые типы могут иметь модификаторы.
  4. Наблюдатели. Эти операции используют в качестве аргументов объекты соответствующего им типа и возвращают результат другого типа. Они используются для получения информации об объектах. Сюда относятся, например, операции size, member и chose для наборов intset.

Обычно примитивные конструкторы создают не все, а только некоторые объекты. Например, операция intset.create создает только пустой набор. Другие объекты создаются конструкторами или модификаторами. Например, операция intset.add может быть использована для получения множеств со многими элементами.

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

Полнота

Тип данных является полным, если он обеспечивает достаточно операций для того, чтобы все требующиеся пользователю работы с объектами могли быть проделаны с приемлемой эффективностью. Строгое определение полноты дать невозможно, хотя существуют пределы относительно того, насколько мало операций может иметь тип, оставаясь при этом приемлемым. Например, для наборов intset мы предоставили только операции create, insert и delete, и программы не могут получить никакой информации относительно элементов набора (так как не имеется наблюдателей). С другой стороны, если мы добавим к этим трем операциям только одну операцию size, то сможем иметь информацию об элементах набора (например, можем проверять на принадлежность, удаляя целые числа и анализируя, изменился ли размер), но тип в этом случае получится неэффективным и неприемлемым.

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

Полнота типа зависит от контекста использования, т. е. тип должен иметь достаточно богатый набор операций для его предполагаемого использования. Если тип предполагается использовать в ограниченном контексте (таком, как, например, одна программа), то должно быть обеспечено достаточно операций только для этого контекста. Если тип предназначен для общего использования, желательно иметь богатый набор операций. Вот почему встроенные типы языка C++, Object Pascal имеют много операций.

Чтобы решить, имеет ли абстракция данных достаточно операций, установите, прежде всего, все, что пользователи могут пожелать делать с ней. Затем продумайте, как эти вещи могут быть осуществлены с использованием данного набора операций. Если что-то окажется слишком неэффективным или слишком громоздким (или и то и другое вместе), исследуйте, может ли этому помочь какая-нибудь дополнительная операция. Иногда существенное улучшение в производительности можно получить, просто открыв доступ к представлению. Например, мы можем исключить операцию member для наборов intset, так как эта операция может быть реализована вне типа при помощи других операций. Однако проверка на принадлежность набору — операция общего использования, и будет работать быстрее, если выполняется внутри реализации. Следовательно, тип данных intset должен иметь эту операцию.

Может быть, также слишком много операций в типе. В этом случае абстракция будет менее понятной, а ее реализация и работа с ней — более сложными. Введение дополнительных операций должно быть соотнесено с затратами на реализацию этих операций. Если тип является полным, его набор операций может быть. расширен процедурами, функционирующими вне реализации типа.

Аназиз типов данных

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

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

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

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

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

Этот способ анализа называется индукцией типа данных. Индукция осуществляется по количеству вызовов процедур, используемых для получения текущего значения объекта. Первый шар индукции — это установить сохранение свойства для примитивных конструкторов. Индукционный шаг устанавливает сохранность свойства для конструкторов и модификаторов.

Отметим, что анализ осуществляется на абстрактном уровне, а не на уровне реализации. Нас не интересует, как реализован абстрактный тип данных. Вместо этого мы работаем прямо с их спецификацией. Работа на абстрактном уровне существенно упрощает анализ.

Индукция также используется для того, чтобы показать, что реализации операций сохраняют инвариант представления. Однако этот анализ производится на уровне реализации. Как и в нашем случае, первый шаг — это установить сохранение свойства для примитивных конструкторов. Если представление изменяемое, на индукционном шаге необходимо рассматривать все операции, так как любая из них может изменить представление. Если же представление неизменяемое, то на индукционном шаге необходимо рассмотреть только конструкторы.

 

 

наверх


назад | содержание | вперед