Объектная реализация контейнера на основе комбинированной структуры - Курсовая работа

программирование модуль контейнер

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Стек

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

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

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

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

Полезными могут быть также вспомогательные операции: · определение текущего числа элементов в стеке;

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

· неразрушающее чтение элемента из вершины стека, которое может быть реализовано, как комбинация основных операций: pop(); push().

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

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

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

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

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

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

При представлении стека в статической памяти для стека выде