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

Абстрактные типы данных.

Ключевые моменты концепции абстрактных типов данных:

1)Теория абстрактных типов данных(АТД) применяет необходимость в точности и полноте спецификации с желанием избежать лишних деталей спецификации.

2)Спецификация абстрактного типа данных является формальным математическим описанием, а не текстом программы. Она апликативна, то есть не включает в явном виде изменений.

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

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

5)Объектно-ориентированная система - это совокупность классов, каждый класс основан на некотором абстрактном типе данных и задаёт частичную или полную реализацию этого абстрактного типа данных.

6)Класс является эффективным если он полностью реализован, в противном случае он называется отложенным.

7)Классы должны разрабатываться в наиболее общем виде допускающем повторное использование, процесс их объединения в систему чаще всего идёт снизу вверх.

Абстрактные типы данных являются скорее неявными, чем явными описаниями. АТД вектор расширяет конкретную структуру данных массива, он содержит методы досупа к обычным элементам последовательности, а также методы обновления обеспецивающие удаление и добавление элементов с определённым индексом.

Для отличия от процесса доступа к элементам конкретной структуры данных массива при обозначении индекса элемента вектора используется термин "разряд".

Пусть S - это линейная последовательность из элементов. Каждый элемент e последовательности S имеет уникальный индекс выраженный целым числом В интервале от нуля до n-1, равный числу элементов предшествующих e. Таким образом определим что разряд элемента е последовательности S равен количеству элементов находящихся в S перед е, то есть разряд первого элемента последовательности равен нулю, а последний равен n-1. Линейная последовательность элементов в которой доступ к элементам осуществляется по их разряду называется вектором с помощью разряда определяется место добавления нового элемента или удаления элемента вектора. Вектор S является абстрактным типом данных, который поддерживает следующие основные методы.

Рассмотрим реализацию с помощью массива.

Самым очевидным способом реализации векторного абстрактного типа данных является его реализация на основе массива A, где A[i] содержит ссылку на элемент разряда i. Здесь считаем, что длина N массива А, достаточно большая, а для обозначения количества элементов вектора используем переменную n<N.

Абстрактный тип данных(список).

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