Список как абстрактный тип данных.

¨ Множество возможных значений - (конечные) последовательности компонентов одинакового типа.

Пусть s₁, s₂,...s_l - список типа TList с компонентами типа TElement, l³ 0. Позиция компонента s_i - 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) класса, можно понимать как данное типа класс, а в самом ближнем контексте просто как переменную типа класс. Дело в том, что «объект» - понятие предельно абстрактного уровня, а здесь и сейчас нас интересует это понятие пусть и не в общефилосовском смысле, но уже в смысле – объект предметной области:

§ для которой нам предстоит разработать информационную модель, с целью решать задачи этой предметной области,

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

На это и нацелены методы и средства объектно-ориентированного проектирования и программирования.

И так, объект - это переменная типа класс, т.е. хранилище данных – информации об объекте предметной области:

¨ объект имеет обозначение (имя переменной...),

¨ имеет значение,

¨ но в семантике объектов еще больше динамики, объекты не просто хранилища данных (значения которых могут изменяться в периоде выполнения программы), но включают и операции над этими данными, поэтому об объектах принято говорить, выделяя понятия:

• состояние объекта – оно представлено полями и определяется хранимыми в них данными,
• структура объекта - структура хранимой информации о полях и методах объекта,
• поведение объекта - оно определяется методами класса, они общие для всех объектов (как переменных) одного класса, но это «линия поведения», а собственно поведение («история поведения») у каждого объекта индивидуальное – это последовательность осуществленных операций, протоколом которых является последовательность состояний этого объекта.

Определяющая характерная особенность классов – это средства инкапсуляции, позволяющие скрыть:

• способ представления значений такого типа, это абстракция данных – отвлечение от способа представления состояния объекта,
• способ реализации операций с такими значениями, это процедурная абстракция – отвлечение от способа реализации поведения объекта.

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

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

¨ Методы-селекторы – позволяют извлекать свойства объекта, например значения его полей, но не изменяют состояние объекта.

¨ Методы-модификаторы – позволяют изменять состояние объекта, но «стараются пресекать» изменения «правильного» состояния в «неправильное».

¨ Методы-генераторы – на базе существующего объекта (и параметров метода) позволяют создавать новые объекты этого класса, причем «правильные», и «стараются пресекать» попытки изменения состояния базового объекта. Конструкторы класса являются разновидностью генераторов, а точнее базовой основой реализации методов-генераторов.