|
Страница 15 из 60
Сортировка дисковых файлов произвольного доступа
Дисковые файлы с произвольным доступом, которые используются
в большинстве баз данных на микро-ЭВМ, обладают двумя основными
преимуществами над последовательными дисковыми файлами. Во-пер-
вых, их легко поддерживать. Обновление информации может произво-
диться без копирования всего списка. Во-вторых, их можно рассмат-
ривать как большие массивы, расположенные на диске, что в
значительной мере упрощает сортировку.
Последнее преимущество позволяет использовать алгоритм быст-
рой сортировки в некоторыми его модификациями для поиска различ-
ных записей на диске аналогично индексированию массива. В отличие
от сортировки последовательного файла при сортировке дискового
файла с произвольным доступом не требуется иметь на диске прост-
ранство одновременно как для отсортированного, так и для неотсор-
тированного массива.
В каждом конкретном случае алгоритм сортировки должен моди-
фицироваться в соответствии со структурой сортируемых данных и
выбранным ключом сортировки. Однако основные принципы сортировки
дисковых файлов произвольного доступа можно понять, изучая прог-
рамму сортировки записей с адресами почтовых корреспонденций /за-
пись "address" определялась раньше/. В приводимом ниже примере,
предполагается, что число элементов фиксированно и равно восьми-
десяти. На практике счетчик записей должен поддерживаться динами-
чески
{ пример программы сортировки списка почтовых адресов }
programm MlistSort;
type
address = record
name: string[30];
street: string[40];
sity: string[20];
state: string[2];
zip: string[9];
end;
str80 = string[80];
DataItem = addres;
DataArray = array [1..80] of DataItem
recfil = file of DataItem
var
test: DataItem;
t, t2:integer;
testfile: recfil;
{ найти запись в файле }
function Find(var fp:recfil; i:integer): str80
var
t:address;
begin
i := i-1;
Seek(fp, i)
Read(fp, t)
Find := t.name;
end;
procedure QsRand(var var fp:recfil; count:integer)
procedure Qs(l, r:integer)
var
i, j, s:integer ;
x, y, z:DataItem;
begin
i := l; j := r;
s := (l+r) div 2;
Seek(fp,s-1); { получить запись }
Reed(fp,x);
repeat
while Find(fp, i) < x.name do i := i+1;
while x.name < Find(fp, j) do j := j-1;
if i<=j then
begin
Seek(fp,i-1); Reed(fp,y);
Seek(fp,j-1); Reed(fp,z);
Seek(fp,j-1); Write(fp,y);
Seek(fp,i-1); Write(fp,z);
i := i+1; j := j-1;
end;
until i>y;
if l<j then qs(l, j)
if l<r then qs(i, r)
end;
begin
qs(1,count);
end; { конец быстрой сортировки файла произвольного
доступа }
begin
Assign(testfile, 'rectest.dat');
Reset(testfile);
t := 1;
while not EOF(testfile) do begin
Read(testfile,test); { подсчет числа записей в
файле}
t := t+1;
end;
t := t-1;
QsRand(testfile,t)
end.
Функция Find используется для того, чтобы оставить в основ-
ном неизменным программу быстрой сортировки. Результатом этой
функции является символьная строка "name" из записи, расположен-
ной на диске. Необходимо постоянно вычитать единицу из аргументов
функций Seek и Find, так как записи дискового файла нумеруются
начиная с нуля, а массивы нумеруются с единицы. |