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

 

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

Схематически изобразим  класс TElement.

 

 

Класс TElement

FBook: TBook (приватное поле) FNext: TElement (приватное поле, указатель на след. элемент)

constructor Create(const Book: TBook)     destructor Destroy; override     function GetNext: TElement (получаем следующий элемент стека) procedure SetNext(const Value: TElement) (задаем следующий элемент стека)     function GetBook: TBook (возвращаем значение поля FBook)

 

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

 

Схематически изобразим  класс TLibrary.

 

 

Класс TLibrary

FFirst: TElement(приватное поле, вершинный элемент) FNum: integer (приватное поле, номер библиотеки)

constructor Create(const Num: integer) destructor Destroy; override function GetFirst: TElement (получаем головной элемент) function GetNum: integer (получаем номер библиотеки) procedure SetNum(const Value: integer) (задаем номер библиотеки) procedure AddBook(const Book: TBook) (добавляем элемент в стек) function DelFirst: TElement (удаляем вершинный элемент) procedure Clear (очищаем стек)

 

Закончим, созданием четвёртого класса – «Библиотечная сеть» - состоящего из списка библиотек. Список будет храниться в виде массива, упорядоченного по номеру библиотеки. Здесь используем поле для хранения массива экземпляров класса TLibrary – это будет динамический массив – массив изменяемой длины. Также понадобятся методы для работы с этим массивом – добавление и удаление элементов. Также класс должен иметь методы, позволяющие сохранить всё содержимое списка в файл, с дальнейшей загрузкой из файла.

Схематически изобразим  класс TSomeLibrary.

 

Класс TSomeLibrary

FSome: array of TLibrary (динамический массив экземпляров класса TLibrary) FCount: integer (приватное поле, количество библиотек)

constructor Create(InitialCount) destructor Destroy; override function GetLibrary(Index: integer): TLibrary (возвращаем объект класса TLibrary) function GetCount: integer (получаем количество книг в библиотеке) function LibraryNo(No: integer): TLibrary function AddSL(No: integer): integer (добавляем в массив библиотеку) function DeleteSL(No: integer): integer (удаляем из массива библиотеку) procedure SaveFile(const FileName: string) (сохраняем список в файле) procedure LoadFile(const FileName: string) (загружаем список из файла)

 

Все классы будут потомками  стандартного базового класса Delphi – TObject.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Алгоритмы реализации основных операций

 

Контейнер для хранения экземпляров  класса TBook по заданию организован в виде стека. Стек (англ. stack — стопка) — структура данных, в которой доступ к элементам организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.

Добавление элемента, называемое также проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху). Удаление элемента, называемое также выталкиванием (pop), тоже возможно только из вершины стека, при этом второй сверху элемент становится верхним.

 

Алгоритм добавления элемента:

- Создаём новый элемент  типа TElement

- Следующим элементом  стека делаем вершинный элемент

- Вершинным элементом  делаем новый созданный элемент

Алгоритм удаления элемента:

- Создаём временный элемент  типа TElement

- Временному элементу  присваиваем значение вершинного  элемента

- Вершинным элементом  делаем следующий элемент

- Уничтожаем временный  элемент

Данный алгоритм перед  использованием должен совершить проверку на наличие элементов в стеке.

Алгоритм полной очистки  стека совпадает с удалением  элемента, только происходит в цикле  до момента, когда стек будет пуст.

Теперь рассмотрим работу упорядоченного массива. Для упорядочивания достаточно хранить только номер.  

Добавление в массив.

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

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

Прежде всего, если удаляем  элемент с индексом i, то скопируем значение из ячейки с индексом i+1 в неё, затем – в ячейку с индексом i+1 скопируем значение ячейки с индексом i+2 и так далее. После этого уменьшим длину массива на 1.

Представление данных в файле.

По заданию требуется  обеспечить сохранение списка в файле  и обратную загрузку из файла. Формат представления данных будет следующим. Запись информации о каждой библиотеке будет отделяться от других записей пропуском строки, а начинаться она будет с её номера. Далее, остальные строки будут содержать название книги и количество экземпляров. Разделителем будет символ «*».

 

Файл будет иметь следующий  вид:

Номер_библиотеки1

Название_книги1*количесво_экземпляров1

Название_книги2*количесво_экземпляров2

…

Название_книгиN*количесво_экземпляровN

 

…

 

Номер_библиотекиN

Название_книги1*количесво_экземпляров1

Название_книги2*количесво_экземпляров2

…

Название_книгиN*количесво_экземпляровN

 

В случае, если библиотека не содержит книг, то тогда сразу после «Номер_библиотеки» будет идти пропуск строки, а затем запись о следующей библиотеки.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Описание  демонстрационного модуля

 

Для решения задачи, я  использовал Borland Delphi 7 – интегрированную среду разработки ПО для Microsoft Windows на языке Delphi. Разработанный демонстрационный модуль имеет вид:

 

 

Интерфейс разработан довольно просто. В левой части окна расположен отсортированный список библиотек,

 

 

 

 

 

 

 

 

 

в правой – имеющиеся  книги.

 

 

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

 

 

либо выбрать пункт  меню:

 

 

Дизайн меню имеет классический вид, и не отличается от большинства  приложений для операционной системы  Windows.

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

Предупреждение, если поле ввода  пустое:

 

 

Предупреждение, если поле ввода  содержит недопустимые символы:

 

 

Предупреждение, если поле ввода  содержит отрицательное значение или  ноль:

 

 

 

 

 

 

 

 

 

 

 

 

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

 

В приложении используются компоненты следующих классов (типов):

Класс TForm – служит предком для всех пользовательских форм.

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

Класс TButton – кнопка с надписью. Основное назначение – выполнять определённые действия при нажатии. Событие OnClick обрабатывает двойной щелчок по компоненте.

Класс TPanel – панель, служит для визуального логического объединения других компонент.

Классы TOpenDialog и TSaveDialog – служат для организации удобного интерфейса чтения и записи файлов.

Класс TMainMenu – стандартное меню.

Класс TEdit – поле для ввода определённого текста или чисел.

Класс TListBox – компонент для вывода списков. Позволяет выделять отдельные компоненты списка и вызывать события при их выделении.

Класс TLabel – метка, служит для создания надписей на форме.

Класс TXPManifest – используется для визуального оформления формы в стиле XP.

Используемые  компоненты:

OpenDialog1 – компонент типа TOpenDialog. Служит для загрузки файлов со списком библиотек и книг.

SaveDialog1 – компонент типа TSaveDialog. Служит для сохранения списка библиотек и книг в файл.

Panel1 – компонент типа TPanel. Левая часть окна приложения – на него помещаются те остальные компоненты, которые участвуют в отображении списка библиотек.

Panel2 - компонент типа TPanel. Правая часть окна приложения – на него помещаются другие компоненты, которые участвуют в отображении списка книг для выбранной библиотеки.

Button1 – компонент типа TButton. По его нажатию осуществляется добавление библиотеки с номером, введённым в EditNum, в список. Событие нажатия кнопки называется OnClick.

Button3 – компонент типа TButton. При нажатии удаляет из списка библиотеку, номер которой введен в EditNum.

N2 – компонент типа TMenuItem. При нажатии вызывает диалог OpenDialog1 для загрузки информации о сети библиотек.

N3 - компонент типа TMenuItem. При нажатии вызывает диалог SaveDialog1 для сохранения информации о сети библиотек.

N8 – компонент типа TMenuItem. По его нажатию осуществляется добавление библиотеки с номером, введённым в EditNum, в список.

N9 - компонент типа TMenuItem. При нажатии удаляет из списка библиотеку, номер которой введен в EditNum.

N10 – компонент типа TMenuItem. По нажатию добавляет в список книгу.

N11 - компонент типа TMenuItem. По нажатию удаляет ту запись об книге, которая находится в голове стека.

EditNum – компонент типа TEdit. Сюда следует вводить номер новой библиотеки.

ListLibr – компонент типа TListBox. Выводит список номеров библиотек.

ListBook – компонент типа TListBox. Выводит список книг выбранной библиотеки.

Button2 – компонент типа TButton. По нажатию добавляет в список книгу.

Button4 – компонент типа TButton. По нажатию удаляет ту запись об книге, которая находится в голове стека.

EditBook и EditCopy – компоненты типа TEdit. Служат для ввода информации о новой добавляемой книге.

Label4 и Label5 – компоненты типа TLabel. Служат для отображения вершинного элемента стека.

 

 

 

 

 

 

 

 

 

 

 

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

 

Классический проект Delphi  имеет, по крайней мере, шесть файлов, связанных с ним. Три из них относятся к управлению проектом из среды и напрямую программистом не меняются. Это файлы: