Объектная реализация контейнера на основе комбинированной структуры «Динамический упорядоченный список массивов-стеков»

 

 р = null; (*начинаем с пустого списка*)

while( n > 0)

{

  q=new NodeDesc;

qànext = р; р = q;

  qàkey = n;

n--;

}

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

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

 Предположим, что элемент, на который ссылается указатель q,  нужно вставить в список после элемента, на который ссылается указатель р (рис.2).

qànext = pànext; pànext = q;

Рис.2

 

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

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

 

q=new NodeDesc;

qq=pp;

pàkey=k;

pànext=q;

 

 Теперь рассмотрим удаление из списка (list deletion). Нетрудно удалить элемент, стоящий сразу за pp. Эта операция показана здесь вместе с повторной вставкой удалённого элемента в начало другого списка (обозначенного переменной q). Здесь имеет место циклический обмен значений трёх указателей.

r = pànext; pànext = rànext; rànext = q; q = r;

Рис.3

 Удаление самого элемента, на который указывает ссылка (а не следующего), труднее, так как здесь возникает та же проблема, что и со вставкой: невозможно просто так перейти назад от элемента к предшествующему.

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

 

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

 

WHILE (список, на который ссылается р, не пуст)

{

 выполнить операцию Р;

 перейти к  следующему элементу;

}

 

 Из определения оператора while и структуры связей следует, что Р применяется ко всем элементам списка и ни к каким другим.

 Очень часто используемая со списками – поиск в списке элемента с заданным ключом.

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

 

Упорядоченные списки

 

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

 Если список упорядочен (скажем, по возрастанию ключей), то поиск может быть прекращен, как только встретился первый ключ, больший нового. Упорядочение списка достигается вставкой новых элементов в надлежащем месте, а не в начале списка. При этом упорядоченность получается практически бесплатно. Это достигается благодаря легкости вставки элемента в связный список, то есть благодаря полному использованию его гибкости. Такой возможности нет ни при работе с массивами, ни с последовательностями. (Однако заметим, что даже упорядоченные списки не дают возможности реализовать аналог двоичного поиска для массивов.)

 Поиск в упорядоченном списке даёт типичный пример ситуации, когда новый элемент нужно вставить перед заданным, в данном случае перед первым элементом, чей ключ оказался слишком большим. Однако мы применим здесь новый прием, который отличается от показанного ранее. Вместо копирования значений вдоль списка проходят два указателя: w2 отстает на шаг от w1 и поэтому указывает на правильное место вставки, когда w1 обнаруживает слишком большой ключ. Общий шаг вставки показан на рис.4.

Рис.4

 

 Организацию данных в связный список можно рекомендовать, когда число элементов относительно мало   (< 50), меняется и, более того, когда нет информации о частоте обращения к ним. Типичный пример - таблица имен в компиляторах языков программирования. Каждое объявление добавляет новое имя, которое удаляется из списка после выхода из его области видимости. Использование простых связных списков уместно в приложениях с относительно короткими программами. Но даже в этом случае можно добиться значительного ускорения доступа к данным с помощью очень простого приёма, который упоминается здесь прежде всего потому, что он представляет собой удачную иллюстрацию гибкости связных списков.

 

Описание основных понятий и механизмов ООП

Объекты

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

• понимание прикладной задачи (проблемы);

• введение основы для реализации на компьютере.

• Объект - это мыслимая или реальная сущность, обладающая характерным поведением, отличительными характеристиками и являющаяся важной в предметной области.
• Каждый объект имеет состояние, обладает некоторым хорошо определенным поведением и уникальной идентичностью.

Каждый программный объект имеет некоторый набор данных и некоторый программный код для обработки этих данных. Объект: данные “+” код.

Классы

 Формально класс - шаблон поведения объектов определенного типа с определенными параметрами, определяющими состояние.

 Все объекты одного и того же класса описываются одинаковыми наборами атрибутов. Однако объединение объектов в классы определяется не наборами атрибутов, а семантикой.

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

. Все экземпляры одного  класса (объекты, порожденные от одного класса)

• Имеют один и тот же набор свойств

• Общее поведение, одинаково реагируют на одинаковые сообщения

 

Инкапсуляция

 Инкапсуляция (encapsulation) - это сокрытие реализации класса и отделение его внутреннего представления от внешнего (интерфейса). При использовании объектно-ориентированного подхода не принято использовать прямой доступ к свойствам какого-либо класса из методов других классов. Для доступа к свойствам класса принято использовать специальные методы этого класса для получения и изменения его свойств.

 Внутри объекта данные и методы могут обладать различной степенью открытости (или доступности).

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

 

 

Агрегация

 Агрегация возникает в тех случаях, когда один объект включает в себя в качестве составных частей другие объекты. Агрегация моделирует отношение типа “часть-целое”.

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

 Обобщение моделирует отношение типа “общее-частное”.

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

 

Наследование

Наследование (inheritance) - это отношение между классами, при котором класс использует структуру или поведение другого(одиночное наследование) или других (множественное наследование) классов. Наследование вводит иерархию "общее/частное", в которой подкласс наследует от одного или нескольких более общих суперклассов. Подклассы обычно дополняют или переопределяют унаследованную структуру и поведение.

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

Производный класс включает в себя:

1)Унаследованные свойства  и методы (их определять не  надо);

2)Новые свойства и методы, отсутствующие в исходном классе, за счёт чего дочерний класс  имеет больше свойств и методов  по сравнению с его родителями  и поэтому описывает более  конкретное понятие.

Дополнительно есть возможность видоизменить (переопределить) некоторые из унаследованных родительских методов.

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

 

Полиморфизм

Полиморфизм (многоформность) - способность некоторой сущности в разных ситуациях по-разному проявлять себя.

Основные реализации полиморфизма в ООП:

1)Полиморфные (виртуальные) методы;

2) Полиморфные объектные указатели;

Переопределение (overriding) методов – это возможность объявления в дочерних классов методов, заголовки которых полностью совпадают с базовым родительским методом, но этим методам в дочерних классах даётся своя программная реализация.

Полное совпадение заголовков - это совпадение имён методов, количества, порядка и типов формальных параметров.

Полиморфные методы – это методы, которые в разных классах некоторой иерархии имеют одинаковые заголовки, но разную программную реализацию.

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