Структуры и организация данных в ЭВМ (стр. 1 из 2)
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
Логическая схема структуры вектора B
4. Алгоритмы обработки основных структур
procedure tform1.fill;
var
r : integer;
begin
rewrite(a);
for r:=1 to i do //наполнение файла
begin //случайными значениями
fval:=random(64000);
write(a, fval);
end;
end;
Данная процедура наполняет файл i значениями, сгенерированными датчиком Random.
Файл A после выполнения первой итерации.
Файл A после выполнения второй итерации.
Файл A после выполнения последней итерации.
procedure tform1.linfind; //линейный поиск
var
s1, s2 : word;
begin
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 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) – время поиска с накоплением запросов.
Вторая таблица имеет следующие графы: