Энциклопедия Turbo Pascal. Главы 1-4
Страница 15. Сортировка дисковых файлов произвольного доступа


Сортировка дисковых файлов произвольного доступа

     Дисковые файлы с произвольным доступом, которые используются
в  большинстве баз данных на микро-ЭВМ,  обладают двумя основными
преимуществами над последовательными дисковыми  файлами.  Во-пер-
вых,  их легко поддерживать. Обновление информации может произво-
диться без копирования всего списка. Во-вторых, их можно рассмат-
ривать  как  большие  массивы,  расположенные  на  диске,  что  в
значительной мере упрощает сортировку.
     Последнее преимущество позволяет использовать алгоритм быст-
рой сортировки в некоторыми его модификациями для поиска  различ-
ных записей на диске аналогично индексированию массива. В отличие
от сортировки последовательного файла  при  сортировке  дискового
файла  с произвольным доступом не требуется иметь на диске прост-
ранство одновременно как для отсортированного, так и для неотсор-
тированного массива.
     В каждом конкретном случае алгоритм сортировки должен  моди-
фицироваться  в  соответствии  со структурой сортируемых данных и
выбранным ключом сортировки.  Однако основные принципы сортировки
дисковых файлов произвольного доступа можно понять,  изучая прог-
рамму сортировки записей с адресами почтовых корреспонденций /за-
пись  "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,  так как записи дискового  файла  нумеруются
начиная с нуля, а массивы нумеруются с единицы.

 
« Предыдущая статья