Материал: Объектная реализация полиморфного контейнера на основе линейного списка

Объектная реализация полиморфного контейнера на основе линейного списка

Курсовая работа

По объектно-ориентированному программированию

На тему:

"Объектная реализация полиморфного контейнера на основе линейного списка"

Оглавление

Введение

1. Теоретическое описание линейного списка с алгоритмами реализации основных операций

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

История

Главные понятия и разновидности

Основные понятия

Абстракция данных

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

Сокрытие данных

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

Полиморфизм

Определение ООП

Концепции

Особенности реализации

Поля данных

Методы

3. Описание всех разработанных классов

4. Описание демонстрационного модуля с характеристикой использованных стандартных компонентов

Перечень использованных компонентов

Описание использованных компонентов

5. Описание структуры программы

Заключение

Список использованной литературы

Введение

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

База данных способна хранить пользователей трёх типов:

·        Гость

·        Пользователь

·        Администратор

Требуется создать программу для вывода информации о пользователях

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

·        Добавление пользователя

·        Удаление пользователя

·        Вывод информации о пользователе

·        Сохранение информации во внешнем файле

·        Загрузка сохраненных данных из файла

Контейнер должен быть реализован на основе линейного списка с заголовком.

1. Теоретическое описание линейного списка с алгоритмами реализации основных операций

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

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

Необходимые объявления:

type pDinItem = ^ TDinItem; {ссылочный тип для адресации элементов списка}

TDinItem = record

{базовый тип, определяющий структуру элемента списка}

inf: <тип информационной части>;

next: pDinItem; {адрес следующего элемента}

end;

var pHead: pDinItem;

Создание пустого списка включает:

·        выделение памяти под заголовок: new (pHead);

·        установку пустой ссылочной части заголовка: pHead^. next: = nil;

Проход по списку от первого элемента к последнему практически не отличается от прохода по очереди.

Поиск заданного элемента включает:

·        установку вспомогательного указателя в адрес первого элемента списка

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

·        после завершения цикла проверить значение вспомогательного указателя и сделать вывод об успешности поиска

pCurrent: = pHead^. next;

while (pCurrent <> nil) and (pCurrent^. inf <> ‘заданное значение’)

do pCurrent: = pCurrent^. next;

if pCurrent = nil then ‘Элемента нет’ else ‘элемент найден’;

Удаление заданного элемента включает:

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

·        если удаляемый элемент найден, то изменяется ссылочная часть его предшественника:

pPrev^. next: = pCurrent^. Next

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

Добавление нового элемента ПОСЛЕ заданного включает:

·        поиск заданного элемента с помощью вспомогательного указателя pCurrent

·        выделение памяти для нового элемента с помощью еще одного указателя pTemp

·        формирование полей нового элемента, в частности - настройка ссылочной части

pTemp^. next: = pCurrent^. next;

·        изменение ссылочной части текущего элемента на адрес нового элемента

pCurrent^. next: = pTemp;

Добавление нового элемента ПЕРЕД заданным включает:

·        поиск заданного элемента с одновременным определением элемента-предшественника (используются указатели pCurrent и pPrev)

·        выделение памяти для нового элемента с помощью еще одного указателя pTemp

·        формирование полей нового элемента, в частности - настройка ссылочной части: pTemp^. next: = pCurrent;

·        изменение ссылочной части элемента-предшественника на адрес нового элемента: pPrev^. next: = pTemp;

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

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

контейнер пользователь линейный список

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

История

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

Первым языком программирования, в котором были предложены принципы объектной ориентированности, была Симула. В момент своего появления (в 1967 году), этот язык программирования предложил поистине революционные идеи: объекты, классы, виртуальные методы и др., однако это всё не было воспринято современниками как нечто грандиозное. Тем не менее, большинство концепций были развиты Аланом Кэйем и Дэном Ингаллсом в языке Smalltalk. Именно он стал первым широко распространённым объектно-ориентированным языком программирования. В настоящее время количество прикладных языков программирования (список языков), реализующих объектно-ориентированную парадигму, является наибольшим по отношению к другим парадигмам. В области системного программирования до сих пор применяется парадигма процедурного программирования, и общепринятым языком программирования является язык C. Хотя при взаимодействии системного и прикладного уровней операционных систем заметное влияние стали оказывать языки объектно-ориентированного программирования. Например, одной из наиболее распространенных библиотек мультиплатформенного программирования является объектно-ориентированная библиотека Qt, написанная на языке C++.

Главные понятия и разновидности

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

Наличие инкапсуляции достаточно для объектности языка программирования, но ещё не означает его объектной ориентированности - для этого требуется наличие наследования.

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

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

Основные понятия

Абстракция данных

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

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

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

Сокрытие данных

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

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

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

Полиморфизм

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

Определение ООП

По мнению Алана Кея, создателя языка Smalltalk, которого считают одним из "отцов-основателей" ООП, объектно-ориентированный подход заключается в следующем наборе основных принципов (цитируется по вышеупомянутой книге Т. Бадда).

Всё является объектом.

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

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

Каждый объект является представителем (экземпляром) класса, который выражает общие свойства объектов.

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

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

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

Устойчивость и управляемость системы обеспечивается за счёт чёткого разделения ответственности объектов (за каждое действие отвечает определённый объект), однозначного определения интерфейсов межобъектного взаимодействия и полной изолированности внутренней структуры объекта от внешней среды (инкапсуляции).

Концепции

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