Информационная система начальника жилищно-эксплуатационной службы

Информационная система начальника жилищно-эксплуатационной службы

47

КУРСОВОЙ ПРОЕКТ

по курсу «Структуры и организация данных в ЭВМ»

на тему

«Информационная система начальника жилищно-эксплуатационной службы»

Данный проект состоит из двух форм: InputForm и ReportForm:

На форме InputForm расположены следующие компоненты (см. рис1):

- компонент AddBtn - верхняя кнопка кнопка в правой части формы для добавления записей данных.

- компонент CopyBtn - кнопка для копирования записей данных.

- компонент DelBtn - кнопка для удаления записей данных.

- компонент SortBtn - кнопка для сортировки выделенного столбца в таблице данных.

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

- компонент SaveBtn - кнопка для сохранения всех табличных данных на форме в текстовых файл.

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

- компонент SaveBtn - кнопка для сохранения всех табличных данных на форме в текстовых файл.

- компонент FBtn - кнопка для отображения формы ReportForm и формирования отчета Ф5.

- компонент BitBtn1 - кнопка для закрытия приложения.

- компонент MSpinEdit - поле ввода для задания количества этажей M.

- компонент KSpinEdit - поле ввода для задания количества подъездов К.

На форме также находятся компоненты Label1, Label2 для отображения подсказок для ввода информации и невизуальные компоненты OpenDialog1, SaveDialog1 для вызова стандартных окон открытия и сохранения файлов.

- компонент PageControl1 - содержит вкладки TabSheet 1-5 на которых отражены данные (соответственно «Квартиры», «СХЕМА», «ГК (Р)», «Жители члены семей ГК (А)», и «Атрибуты квартир (С)»).

Компоненты TabSheet 1-5 содержат в себе элементы таблиц StringGrid 1-5, которые связаны с векторами данных, соответственно «Kvart», «Scheme», «GK», «People», «FlatAtr»).

Рис. 1 - Главная форма программы

На форме ReportForm расположены следующие компоненты (см. рис 2):

- компоненты Panel1, Panel2 - панели на форме для разделения формы на отчет и панель кнопок.

- компонент OkBtn - кнопка для закрытия формы.

- компонент ListBox1 - список для отображения отчета.

Рис. 2 - форма для формирования отчета Ф5.

1.2 Основные модули и процедуры, входящие в состав программного комплекса

Список модулей:

Программа содержит следующие модули:

Unit1 - модуль главной формы проекта.

Unit2 - модуль отчетной формы проекта.

MyTypes - модуль с описаниями классов данных.

Список основных процедур, входящих в состав программного комплекса:

- procedure LoadButtonClick - процедура загрузки данных из файла в векторы.

- procedure SaveButtonClick - процедура сохранения данных в файл.

- procedure FillStringGrid - процедура инициализации таблиц и заполнения их в соответствии с массивами.

- procedure PageControl1Change - процедура выбора необходимой страницы с данными и вызова перезаполнения соответствующей таблицы.

- procedure SGDblClick - процедура ввода / редактирования данных в текущей ячейки таблицы данных.

- procedure AddBtnClick - процедура добавления строки в текущую таблицу данных и вектор данных.

- procedure DelBtnClick - процедура для удаления записей данных.

- procedure SortBtnClick - процедура для сортировки выделенного столбца в таблице данных.

- procedure KSpinEditChange - процедура для изменения значения количества подъездов К в соответствии с полем ввода.

- procedure MSpinEditChange - процедура для изменения значения количества этажей M в соответствии с полем ввода.

- procedure CopyBtnClick - процедура ввода новой строки данных копированием текущей строки.

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

- procedure SortBtn - кнопка для сортировки выделенного столбца в таблице данных.

- procedure FButtonClick - процедура для отображения формы ReportForm и формирования отчета Ф5.

- procedure ReadVec - процедура чтения вектора данных из текстового файла.

- procedure WriteVec - процедура записи вектора данных из текстового файла.

Базовой структурой данного проекта является класс TVector в котором для хранения данных использовался вектор векторов FArr и организованы свойства и методы для доступа и обработки данных класса.

Объявление вектора FArr выглядит следующим образом:

FArr: array [1..100] of TVarMas, где TVarMas = array [1..MaxN] of Variant;

Вектор (array) - это линейная структура данных (список) с элементами одинакового размера в которой адрес элемента однозначно определяется его номером.

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

Логическая схема структуры вектора векторов FArr:

Каждый элемент одного вектора занимает 16 байт памяти. Соответственно FArr будет занимать (100*100)*16=160000 байт.

Логическая схема структуры вектора имен FNames:

Каждый элемент вектора занимает 101 байт памяти. Соответственно вектор FNames будет занимать 100*101 =10100 байт.

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

Быстрая сортировка (quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си - широко известный алгоритм сортировки, разработанный английским Информатиком Чарльзом Хоаром. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем О (n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.

Алгоритм

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.

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

1. Два индекса - l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.

2. Вычисляется индекс опорного элемента m.

3. Индекс l последовательно увеличивается до m до тех пор, пока l-й элемент не превысит опорный.

4. Индекс r последовательно уменьшается до m до тех пор, пока r-й элемент не окажется меньше опорного.

5. Если r = l - найдена середина массива - операция разделения закончена, оба индекса указывают на опорный элемент.

6. Если l < r - найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.

3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

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

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

Этот алгоритм в применении к нашему вектору FArr реализован следующи методом класса TVector:

 // Процедура сортировки вектора по индексу SortId с режимом xMode

 // xMode = 1 - по возрастанию

 // xMode = 2 - по убыванию

 // xMode = 0-использовать текущий режим SortMode и затем поменять его

procedure TVector. Sort (xMode: integer = 0);

procedure QSort (l, r: Integer);

function Less (var x, y: Variant): boolean;

begin

if (X < Y) and (SortMode=1) // по возрастанию

then Less:=true

else Less:=false;

end;

var

i, j, x: integer;

y: TVarMas; //Variant;

begin

i:= l; j:= r; x:= (l+r) DIV 2;

repeat

while Less (FArr[i] [SortId], FArr[x] [SortId]) do i:= i + 1;

while Less (FArr[x] [SortId], FArr[j] [SortId]) do j:= j - 1;

if i <= j then

begin

y:= FArr[i];

FArr[i]:= FArr[j];

FArr[j]:= y;

i:= i + 1; j:= j - 1;

end;

until i > j;

if l < j then QSort (l, j);

if i < r then QSort (i, r);

end;

begin {QuickSort};

if xMode<>0

then SortMode:= xMode;

QSort (1, Size);

if xMode=0 then // Поменяем режим сортировки

begin

if SortMode = 1

then SortMode:=2 else SortMode:=1;

end;

end;

Оценка эффективности

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

· Лучший случай. Для этого алгоритма самый лучший случай - если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения CN = 2CN/2+N. Это дало бы наименьшее время сортировки.

· Среднее. Даёт в среднем O (n log n) обменов при упорядочении n элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.

· 2CN/2 покрывает расходы по сортировке двух полученных подмассивов; N - это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно CN = N lg N.

· Худший случай. Худшим случаем, очевидно, будет такой, при котором на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.
Худший случай даёт O (n?) обменов, но количество обменов и, соответственно, время работы - это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов.

Данное програмное обеспечение имеет интуитивно понятный интерфейс и использует все возможности среды Delphi.

Программа имеет пять вкладок. При первоначальном запуске активируется первая - вкладка «Квартиры» (см. рис. 3).

Рис. 3 - Вкладка таблицы квартир

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

На вкладке «Квартиры» можно изменить только колонки: «Номер квартиры», «Стоимость квартиры», «Признак приват.». Остальные колонки рассчитываются по таблицам «Атрибуты квартир (С)» и «СХЕМА» следующим образом:

Три первых колонки определяются исходя из данных таблицы «СХЕМА». Колонка «Жилая площадь» = сумма площадей всех комнат, взятых из таблицы С.

Колонка «Общая площадь» =атр. 4 + атрибуты 7-9 из таблицы С.

Одновременно после ввода / изменения номера квартиры выдается информационное сообщение (см. рис. 4)

Рис. 4 - Информационное сообщение

В случае попытки редактирования колонок №№2-5 выдается следующее сообщение (см. рис. 5).

Рис. 5 - Сообщение о невозможности редактирования ячейки

При переходе на вкладку «СХЕМА» отображается следующее окно (см. рис. 6)

Рис. 6 - Вкладка схемы квартир «СХЕМА»

Третья вкладка «ГК (Р)» содержит атрибуты таблицы главных квартиросъемщиков квартир (см. рис. 7).

Рис. 7 - Вкладка таблицы главных квартиросъемщиков ГК(Р)

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

В четвертой вкладке находится таблица жителей квартир - членов семей главных квартиросъемщиков (А). (см. рис. 8)

Рис. 8 - Вкладка таблицы жителей квартир - членов семей главных квартиросъемщиков (А)

На пятой вкладке находится таблица (С) с атрибутами квартир (С). (см. рис. 9)

Рис. 9 - Вкладка таблицы (С) с атрибутами квартир

Из всех вкладок доступны кнопки «Сохранить в файл» и «Загрузить из файла» с помощью которых можно сохранить данные всех вкладок в текстовый файл *.dat и загрузить данные из файла.

Для формирования отчета формы Ф5 необходимо нажать на кнопку «Отчет Ф5», при этом открывается новое окно с отчетными данными (см. рис. 10). Закрыть окно можно нажав на кнопку «ОК».

Рис. 9 - Вкладка таблицы (С) с атрибутами квартир

Заключение

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

Тестирование данного продукта показало полноту реализованных функций и отсутствие ошибок и недочётов в программе. Были изучены базовая структура данных типа вектор и метод быстрой сортировки QuickSort.

Литература