Курсовая работа: Информационная система начальника жилищно-эксплуатационной службы
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-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов.
|
5. Руководство
пользователя
Данное программное обеспечение имеет интуитивно понятный интерфейс и использует все возможности среды 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.
Литература
| 1 | Структуры и организация данных в компьютере. Учебное пособие / Лакин В.И., Романов А.В. – Мн.: БНТУ, 2004 – 176 с. |
| 2 | Архангельский А.Я. Delphi 6. Справочное пособие. - М.: ЗАО «Издательсво БИНОМ», 2001. - 1024 с. |
| 3 | Вирт Н. Алгоритмы и структуры данных. - СПб: Невский диалект, 2001. – 352 с. |
| 4 | Ананий В. Левитин Глава 4. Метод декомпозиции: Быстрая сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. – М.: «Вильямс», 2006. – С. 174–179. |
| 5 | Кнут Д.Э. Искусство программирования, том 1. Основные алгоритмы. - М.: Издательский дом «Вильямс», 2002. -720 с. |
| 6 | Кнут Д.Э. Искусство программирования, том 3. Сортировка и поиск. - М.: Издательский дом «Вильямс», 2001. - 832 с. |
| 7 | Гофман В.Э., Хомоненко А.Д. Delphi. Быстрый старт. – СПб: БХВ-Петербург, 2003. – 288 с.: ил |
Приложение 1
Листинги программы
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls, ExtCtrls, math, Grids, Buttons, Mask, Calendar, ComCtrls,
Spin, MyTypes, Unit2;
Type
TInputForm = class(TForm)
BitBtn1: TBitBtn;
OpenDialog1: TOpenDialog;
SaveDialog1: TSaveDialog;
LoadButton: TButton;
SaveButton: TButton;
PageControl1: TPageControl;
TabSheet1: TTabSheet;
TabSheet2: TTabSheet;
TabSheet3: TTabSheet;
StringGrid1: TStringGrid;
DelBtn: TBitBtn;
AddBtn: TBitBtn;
StringGrid2: TStringGrid;
SortBtn: TBitBtn;
TabSheet4: TTabSheet;
TabSheet5: TTabSheet;
StringGrid3: TStringGrid;
StringGrid4: TStringGrid;
StringGrid5: TStringGrid;
Label1: TLabel;
KSpinEdit: TSpinEdit;
Label2: TLabel;
MSpinEdit: TSpinEdit;
FindBtn: TBitBtn;
CopyBtn: TBitBtn;
FButton: TButton;
procedure FormCreate (Sender: TObject);
procedure LoadButtonClick (Sender: TObject);
procedure SaveButtonClick (Sender: TObject);
procedure PageControl1Change (Sender: TObject);
procedure AddBtnClick (Sender: TObject);
procedure SGDblClick (Sender: TObject);
procedure DelBtnClick (Sender: TObject);
procedure SortBtnClick (Sender: TObject);
procedure KSpinEditChange (Sender: TObject);
procedure MSpinEditChange (Sender: TObject);
procedure SGKeyPress (Sender: TObject; var Key: Char);
procedure FormDestroy (Sender: TObject);
procedure CopyBtnClick (Sender: TObject);
procedure FindBtnClick (Sender: TObject);
procedure FButtonClick (Sender: TObject);
private
{Private declarations}
public
{Public declarations}
//Fz: file of TVector; // Файл типа запись
KPod, M: integer; // Количество подъездов и этажей
People: TVector; // Вектор – члены семей ГК
GK: TVector; // Вектор – главные квартиросъемщики
Scheme: TVector; // Вектор – СХЕМА
FlatAtr: TVector; // Вектор – Атрибуты квартир
KVART: TVector; // Вектор – КВАРТ
Ft: TextFile; // Текстовой файл
FileNameT: string[200]; // Имя файла
FSGVector: array [1..10] of TStringGrid;
procedure FillStringGrid (SG: TStringGrid; Vec: TVector);
function GetVec: TVector;
procedure ReadVec (var Vec: TVector);
procedure WriteVec (Vec: TVector); // Запись вектора в файл
end;
var
InputForm: TInputForm;
Implementation
{$R *.DFM}
procedure TInputForm. FormCreate (Sender: TObject);
begin
KPod:=2; M:= 3;
//
Kvart:= TVector. Create;
Kvart. Cols:= 7;
Kvart. Names[1]:= 'Номер квартиры';
Kvart. Names[2]:= 'число комнат';
Kvart. Names[3]:= 'номер этажа';
Kvart. Names[4]:= 'жилая площадь (кв. м.)';
Kvart. Names[5]:= 'общая площадь (кв. м.)';
Kvart. Names[6]:= 'стоимость квартиры';
Kvart. Names[7]:= 'Приват.';
//
Scheme:= TVector. Create;
Scheme. Cols:= 4;
Scheme. Names[1]:= 'Кв. 1';
Scheme. Names[2]:= 'Кв. 2';
Scheme. Names[3]:= 'Кв. 3';
Scheme. Names[4]:= 'Кв. 4';
//
GK:= TVector. Create;
GK. Cols:= 8;
GK. Names[1]:= 'Номер Квартиры';
GK. Names[2]:= 'Фамилия';
GK. Names[3]:= 'Имя';
GK. Names[4]:= 'Отчество';
GK. Names[5]:= 'Год рождения';
GK. Names[6]:= 'Место работы';
GK. Names[7]:= 'Льготы';
GK. Names[8]:= 'Долг (тыс. руб.)';
// –
// 1.5. Таблица А содержит список жильцов – членов семей главных квартиросъемщиков:
// 1) фамилия,
// 2) родственное отношение к ГК (мать / отец/муж/жена / дочь/сын),
// 3) номер квартиры,
// 4) признак «пенсионер / учащийся / работает / дошкольник».
People:= TVector. Create;
People. Cols:= 4;
People. Names[1]:= 'Фамилия';
People. Names[2]:= 'Родств.отн-ние';
People. Names[3]:= 'Номер квартиры';
People. Names[4]:= 'Признак';
People. Names[5]:= 'Место работы';
People. Names[6]:= 'Льготы';
People. Names[7]:= 'Долг (тыс. руб.)';
// –
// 1.6. Таблица С содержит следующие атрибуты квартир (в соответствии с числом комнат):
// 1) число комнат,
// 2) месячная квартплата,
// 3) площадь первой комнаты (кв. м.),
// 4) площадь второй комнаты (если она есть),
// 5) площадь третьей комнаты,
// 6) площадь четвертой комнаты,
// 7) площадь коридора,
// 8) площадь кухни,
// 9) общая площадь туалета и ванной комнаты.
FlatAtr:= TVector. Create;
FlatAtr. Cols:= 9;
FlatAtr. Names[1]:= 'Число комн.';
FlatAtr. Names[2]:= 'Квартплата';
FlatAtr. Names[3]:= 'Пл.ком. №1';
FlatAtr. Names[4]:= 'Пл.ком. №2';
FlatAtr. Names[5]:= 'Пл.ком. №3';
