b>4. Алгоритмы обработки основных структур Основной операцией обработки структуры в данном программном обеспечении является сортировка 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-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. 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;interfaceusesWindows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,StdCtrls, ExtCtrls, math, Grids, Buttons, Mask, Calendar, ComCtrls,Spin, MyTypes, Unit2;TypeTInputForm = 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);
Страницы: 1, 2, 3
|