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

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

 

Государственное образовательное учреждение высшего профессионального образования

 

«Казанский Национальный Исследовательский Технический Университет им. А. Н. Туполева»

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

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

 

 

 

Дисциплина:

Структуры и алгоритмы обработки данных

 

 

 

 

 

 

 

 

        Работа выполнена студентом группы

Преподаватель:

 

 

 

Оглавление

 

 

Постановка задачи (цель работы, исходные данные, ожидаемый результат, требования к реализации)……………………………………………………………………………………….2

Теоретическое описание используемых структур данных с алгоритмами реализации основных операций…………………………………………………………….…………….......3

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

Описание всех разработанных классов (объектная модель)……………………………...…11

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

Описание структуры проекта…………………………………………………………………27

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

 

Ожидаемый результат : «Квартирный фонд»

• информационные объекты: квартиры жилого дома (свойства: Номер Квартиры, Площадь)

• квартиры объединяются в рамках объекта Дом (свойство: Номер Дома)

• дома объединяются в рамках объекта-контейнера Управляющая Компания (свойство – Название)

 

Требования:

1. Полная объектная реализация  с определением классов для  всех элементов реализуемой структуры: информационные объекты (обязательно!), объекты-элементы списка (динамическая  реализация), объекты-списки, объект-контейнер

2. Имена классов, свойств  и методов должны носить содержательный  смысл и соответствовать информационной  задаче

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

4. Реализация в классах  всех необходимых методов: конструкторы, методы доступа к свойствам, методы  добавления и удаления на каждом  из двух уровней, метод поиска (при необходимости)

5. Возможность сохранения  всей структуры во внешнем  файле с обратной загрузкой

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

7. Язык и среда разработки  – по выбору: Delphi, Java, C++, С#

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

Стек

 

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

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

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

 Основные операции над стеком - включение нового элемента (английское название push - заталкивать) и исключение элемента из стека (англ. pop - выскакивать).

 Полезными могут быть также вспомогательные операции:

• определение текущего числа элементов в стеке;

• очистка стека;

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

        pop();      push().

 Некоторые авторы рассматривают также операции включения/исключения элементов для середины стека, однако структура, для которой возможны такие операции, не соответствует стеку по определению.

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

• а) пустого;

• б - г) после последовательного включения в него элементов с именами 'A', 'B', 'C';

• д, е) после последовательного удаления из стека элементов 'C' и 'B';

• ж) после включения в стек элемента 'D'.

Рис.1

 Как видно из рис.1, стек можно представить, например, в виде стопки книг (элементов), лежащей на столе. Присвоим каждой книге свое название, например A,B,C,D. Тогда в момент времени, когда на столе книг нет, про стек аналогично можно сказать, что он пуст, т.е. не содержит ни одного элемента. Если же мы начнем последовательно класть книги одну на другую, то получим стопку книг (допустим, из n книг), или получим стек, в котором содержится n элементов, причем вершиной его будет являться элемент n+1. Удаление элементов из стека осуществляется аналогичным образом, т. е. удаляется последовательно по одному элементу, начиная с вершины, или по одной книге из стопки.

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

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

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

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

 Определение размера стека сводится к вычислению разности указателей: указателя стека и адреса начала области.

 

 

Связный список

 

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

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

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

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

-Это пустая (null) ссылка, не указывающая на какой-либо узел.

-Ссылка указывает на фиктивный узел (dummy node), который не содержит элементов.

-Ссылка указывает на первый узел, что делает список циклическим.

 

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

 Список, отражающий отношения соседства между элементами, называется линейным.  Если ограничения на длину списка не допускаются, то список представляется в памяти в виде связной структуры. Линейные связные списки являются простейшими динамическими структурами данных.

 

Линейные списки

 

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

 Пусть тип NodeDesc (desc от descriptor) определены, как показано ниже. Каждая переменная типа NodeDesc содержит три компоненты, а именно идентифицирующий ключ key, указатель на следующий элемент next и, возможно, другую информацию. Для дальнейшего нам понадобятся только key и next.

 

struct NodeDesc {

  int Info;

  int key;

  NodeDesc * next;

};

NodeDesc * p;

NodeDesc * q; 

p,q – указательные переменные

 

 На рис.1 показан список узлов, причём указатель на первый элемент хранится в переменной р. Вероятно, простейшая операция со списком, показанным на рисунке - это вставка элемента в голову списка. Сначала размещается элемент типа NodeDesc, при этом ссылка (указатель) на него записывается во вспомогательную переменную, скажем q. Затем простые присваивания указателей завершают операцию. Отметим, что порядок этих трех операторов менять нельзя.

q=new NodeDesc;

qànext = р; р = q;

Рис.1

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