Структуры и организация данных в ЭВМ
1. Состав Dеlphi-проекта Программа включает одну форму: главную, на которой и реализован интерфейс программы На форме пристутствуют следующие компоненты: 2 компоненты TstringGrid: для отображения результатов работы программа в виде двух таблиц со значениями; 6 компонент TLabel: для отображения поясняющих надписей; 1 компонента TButton: для включения режима поиска; 1 компонента: TBitBtn: для закрытия формы и выхода из приложения; 4 компоненты TRadioButton: для выбора режима отображения кривых на компонентах Tchart (вывод графиков вместе и по отдельности); 4 компоненты TEdit: для ввода данных пользователем; 2 компоненты TChart: для отображения графиков функций; 2 компоненты TComboBox: для выбора графика, отображаемого на компоненте Tchart в режиме «показывать по отдельности»; 2 компоненты TPanel: для группировки компонент TRadioButton. Программа содержит два модуля: главный модуль программы Project.dpr и модуль MainForm.pas, в котором непосредственно реализуются действия, связанные с поиском. 2. Статические данные и структурыA: file of Word - файл из N элементов, интерпретируется как таблица, содержащая только целые ключи (N изменяется от Nmin до Nmax )(N*2 байта);B : array of Word - вектор из К элементов, представляет собой набор аргументов поиска (K*2 байта);arA : array of Word - массив для временного хранения данных в процедуре сортировки файла A (N*2 байта);Nmin : Word - минимальное число элементов в таблице A (2 байта); Nmax : Word - максимальное число элементов в таблице A (2 байта);Step : Word - шаг изменения числа элементов в таблице A (2 байта);K : Word - число элементов в векторе B (2 байта);T, i: Word - счётчики (2 байта); rnd : Word - переменная, содержащая случайное значение, генерируемое датчиком RANDOM случайных чисел из диапазона [0, 64000] (2 байта); Fval : Word - значение текущего элемента файла A (2 байта);SortA1, SortA2, SortAB : array [0..1, 1..4, 1..65535] of Word - значения текущего времени перед выполнением сотвуетствующего вида сортировки в цикле (2*4*65536*2 байта = 1048560 байт);LinF1, LinF2, BinF, LinFAcc: array [0..1, 1..4, 1..65535] of Word значения текущего времени перед очередным циклом и после него в соответствующих видах поиска (2*4*65535*2 байта = 1048560 байт);TSortA1, TSortA2, TSortAB array [1..65535] of Word - значения периодов времени, затраченного на соответствующий вид сортировки в цикле (65535*2 байта = 131070 байт); TLinF1, TLinF2, TBinF, TLinFAcc: array [1..65535] of Word - значения периодов времени, затраченного на соответствующий вид поиска в цикле (65535*2 байта = 131070 байт);Acc : array [1..3, 1..65535] of Word - массив, накапливающий запросы (3*65535*2 байта = 393210 байт).3. Логические структуры данныхЛогическая схема структуры файла A:Количество элементов в файле N в процессе выполнения программы изменяется от Nmin до Nmax, т.е. создаётся файл из N=Nmin элементов, затем после необходимых процедур уничтожается и создаётся файл изNmin+1 элементов и так, пока N не достигнет значения NmaxЛогическая схема структуры вектора B4. Алгоритмы обработки основных структурprocedure tform1.fill;varr : integer;beginrewrite(a);for r:=1 to i do //наполнение файлаbegin //случайными значениямиfval:=random(64000);write(a, fval);end;end;Данная процедура наполняет файл i значениями, сгенерированными датчиком Random.Файл A после выполнения первой итерации.Файл A после выполнения второй итерации.Файл A после выполнения последней итерации.procedure tform1.linfind; //линейный поискvars1, s2 : word;beginfor s1:=0 to k-1 dofor s2:=0 to i-1 dobeginseek(a, s2);read(a, fval);if (b[s1]=fval) then exit;end;end;Процедура перебирает значения из вектора В, сранивая их поэлементно со значениями из файла А. Состояние вектора и файла при: первой итерации второй итерации i-й итерации 1*i+1-й итерации 1*i+2-й итерации 1*i+3-й итерации k*i+1-й итерации k *i+2-й итерации k*i+3-й итерации procedure tform1.binfind; //двоичный поиск var s1, cou, cou1, cou2 : integer; label 1; begin for s1:=0 to k-1 do begin cou1:=0; cou2:=i-1; while cou1<=cou2 do begin cou:=(cou2+cou1) div 2; seek(a, cou); read(a, fval); if (fval=b[s1]) then goto 1 else if fval<b[s1] then cou1:=cou+1 else cou2:=cou-1; end; 1 : end; end; Процедура перебирает значения из вектора В, сранивая их поэлементно со значениями из файла А (файл А должен быть предварительно отсортирован), причём делит файл А пополам и сравнивает значения. Если значение из вектора В больше значения из файла А, то таким же образом исследуется левая половина файла, в противном случае - правая и т.д. Состояние вектора и файла при: первой итерации второй итерации procedure tform1.linfindacc; //линейный поиск с накоплением var s1, s2, cou : word; begin cou:=1; for s1:=0 to k-1 do for s2:=0 to i-1 do begin seek(a, s2); read(a, fval); if (b[s1]=fval) then begin acc[1, cou]:=s2; acc[2, cou]:=s1; acc[3, cou]:=fval; cou:=cou+1; end; end; end; Алгоритм процедуры аналогичен алгоритму процедуры tform1.linfind с той разницей, что при совпадении значения в векторе и файле в двухмерный массив аcc записываются индексы файла и вектора, а также совпавшее значение. procedure tform1.sorta; //сортировка файла a var r, d : integer; tmp, val : word; begin setlength(ara, i); for r:=0 to i-1 do begin seek(a, r); read(a, val); ara[r]:=val; end; for r:=0 to i-2 do for d:=r+1 to i-1 do begin if (ara[r]>ara[d]) then begin tmp:=ara[r]; ara[r]:=ara[d]; ara[d]:=tmp; end; end; rewrite(a); for r:=0 to i-1 do write(a, ara[r]); end; Процедура перебирает значения файла, одновременно организуя второй цикл и перебирает значения этой же таблицы, начиная со следующего элемента. Встречая во втором цикле меньшее значение пересылает его во временный файл, значение из первого цикла пересылается в освободившуюся ячейку второго цикла. А его место, в свою очередь, занимает значение из временного файла. procedure tform1.sortb; //сортировка вектора b var r, d : integer; tmp : word; begin for r:=0 to k-2 do for d:=r+1 to k-1 do begin if (b[r]>b[d]) then begin tmp:=b[r]; b[r]:=b[d]; b[d]:=tmp; end; end; end; Алгоритм сортировки вектора аналогичен вышеописанному методу сортировки файла. 5 Руководство пользователяОписывается сценарий интерфейсного диалога пользователя с программой. Изложение подробно иллюстрируется копиями диалоговых форм, полученных в ходе выполнения программы. 1. Ввод необходимых данных. Для правильной работы программы необходимо ввести следующие данные: минимальное число элементов в файле A, максимальное число элементов в файле A, шаг изменения количества элементов в файле A от минимального до максимального, число элементов в векторе B. В случае введения неверной информации программа выдаст соответствующее диалоговое окно: а) при незаполнении одного из полей: б) при введении в одно из полей символа(ов), не являющегося(ихся) цифрой(ами): в) при введении в поле Nmin значения, превышающего значение в поле Nmax: г) при введении неположительного числа(чисел) либо числа(чисел), превышающего(их) максимально допустимое значение - 65535: 2. Поиск и вычисление времени, затраченного на поиск и сортировку Для включения режима поиска необходимо нажать кнопку с надписью «ПОИСК» При верно введенных данных режим поиска успешно начнёт работу, о чём будет свидетельствовать отсутствие диалоговых окон после нажатия кнопки «ПОИСК». После окончания вышеуказанного процесса результаты будут представлены в таблицы 1 и 2, а также выведены в виде графиков соответствующих функций для дальнейшего анализа. 3. Анализ. Как уже было сказано ранее, данные для анализа будут представлены в таблицах 1 и 2, а также в виде кривых. Таблица 1 состоит из следующих граф: N (длина таблицы), tЛП1(N) - время первого линейного поиска, tлп2(N) - время второго линейного поиска, tДП(N) - время двоичного поиска, tЛП-М(N) - время поиска с накоплением запросов. Вторая таблица имеет следующие графы: N, tлп2(N)+ tсА(N), где tСА(N) - время сортировки файла А, tДп(N)+ tсА(N), tлп-М(N)+ tсА(N)+ tсВ(N). Справа от каждой таблицы изображены графики соответствующих функций, которые можно просматривать как вместе, так и по отдельности, для чего необходимо выбрать соответствующее положение кнопки(ок) RadioButton: или так: Для просмотра определённого графика необходимо выбрать соответствующее название в выпадающем списке справа от панели с кнопками переключения режима вывода графиков (при этом, конечно, должен быть включен режим «ПО ОТДЕЛЬНОСТИ»). При удовлетворительных результатах можно перейти к завершению приложения, в противном случае же - ввести новые данные и начать новый поиск (см. п.1). 4. Выход из программы. Для завершения приложения необходимо нажать на кнопку «ЗАКРЫТЬ» или на крестик в правом верхнем углу. ЗАКЛЮЧЕНИЕ Приложение (исходные тексты всех модулей) Исходный текст модуля Project.dpr: program Project; uses Forms, MainForm in 'MainForm.pas' {Form1}; {$R *.res} begin Application.Initialize; Application.CreateForm(TForm1, Form1); Application.Run; end. Исходный текст модуля MainForm.pas: unit MainForm; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, ExtCtrls, TeeProcs, TeEngine, Chart, Buttons, Grids, Series; type TForm1 = class(TForm) sgTb2: TStringGrid; sgTb1: TStringGrid; Label1: TLabel; Label2: TLabel; btFind: TButton; btClose: TBitBtn; rbTog1: TRadioButton; rbEve1: TRadioButton; cbSel1: TComboBox; edNmin: TEdit; edNmax: TEdit; edLen: TEdit; Label4: TLabel; Chart1: TChart; Series1: TLineSeries; Series2: TLineSeries; Series3: TLineSeries; Series4: TLineSeries; edStep: TEdit; Label5: TLabel; Label6: TLabel; Label7: TLabel; Chart2: TChart; rbTog2: TRadioButton; rbEve2: TRadioButton; cbSel2: TComboBox; Series5: TLineSeries; Series6: TLineSeries; Series7: TLineSeries; Panel1: TPanel; Panel2: TPanel; procedure rbEve1Click(Sender: TObject); procedure rbTog1Click(Sender: TObject); procedure btFindClick(Sender: TObject); procedure LinFind; procedure BinFind; procedure LinFindAcc; procedure SortA; procedure SortB; procedure Verify; procedure rbValClick(Sender: TObject);
Страницы: 1, 2
|