Процедуры для работы с упорядоченными файлами

11.3.8.1 Процедура сортировки файла

Алгоритмы сортировки файлов подобны алгоритмам сортировки массивов. Но особенность состоит в том, что при обращении к нужной записи в файле приходится вызывать процедуру seek(), кроме того, приходится учитывать, что файловая позиция смещается после выполнения операции чтения или записи.

Ниже приведена процедура пузырьковой сортировки по фамилии студента для открытого файла записей с результатами аттестации. Так как сортировку записей можно производить и по другим признакам, например, по баллу, но в этом случае в процедуре нужно заменить выражение для сравнения записей.

Внешний цикл сортировки такой же, как и для массива, а во внутреннем цикле последовательно считываются две записи файла и сравниваются. Если порядок их следования нарушен, они записываются в обратном порядке.

//Пузырьковая сортировка файла по фамилии студента

procedure sortAttFile(var f: TAttFile);

var i, k: integer; ri1, ri2: TAttRec; ok: boolean;

Begin

k:= FileSize(f)-1;

Repeat

ok:= true;

k:= k - 1;

for i:= 0 to k do

Begin

//Переходим на i-ю запись

seek(f,i);

//Читаем две подряд идущих записи

read(f,ri1);

read(f,ri2);

//сравниваем эти записи

if ri1.name > ri2.name then

Begin

//Записываем в обратном порядке

seek(f,i);

write(f,ri2);

write(f,ri1);

ok:=false;

end;

end;

until ok;

end;

11.3.8.2 Поиск записи в отсортированном файле

Для поиска записи в упорядоченном файле можно метод дихотомии, который рассматривался при поиске в упорядоченном массиве.

function findPosInSortFile(fam: TName; var f: TAttFile): integer;

var pos, left, right: integer; r: TAttRec;

Begin

result:= -1; // Если элемент не будет найден

//Начальные значения левой и правой границ

left:= 0; right:= FileSize(f)-1;;

while left <= right do begin //Ищем, пока left не правее right

// Находим индекс середины массива

pos:= (right+left)div 2;

seek(f, pos);

read(f, r);

if fam = r.Name then begin

//Элемент найден, и мы выходим из подпрограммы

result:= pos;

exit;

end;

if fam < r.Name

then right:= pos – 1 // Будем искать левее

else left:= pos+1; // Будем искать правее

end;

end;

11.3.8.3 Добавление записи в отсортированный файл

Процедура добавления в отсортированный файл также подобна вставке в отсортированный массив. Записи, начиная с последней, поочередно сдвигаются на одну позицию к последней, создавая место для вставляемой записи. Процесс продолжается до тех пор, пока не будет найдено место для новой записи, соответствующее порядку в файле. Сравнение записей должно производиться по правилу, в соответствии с которым проводилась сортировка. Поэтому в процедуру вставки в качестве параметра передается та же функция сравнения, что использовалась при сортировке.

//Добавить запись в отсортированный файл

procedure addToSortFile(var f:TAttFile; r:TAttRec);

var pos:integer; rf:TAttRec;

Begin

//Начинаем с конца файла

pos:= fileSize(f);

repeat //Повторяем пока не найдем, куда вставить

pos:=pos-1;

if pos = -1 then break; // значит надо вставлять в начало

//Сдвигаем очередную запись на одну позицию вниз

seek(f, pos);

read(f, rf);

write(f, rf);

until rf.name < r.name;

// Нашли место для вставки

seek(f,pos+1);

write(f,r);

end;

11.3.8.4 Удаление записи из отсортированного файла

В процедуре удаления записи из файла используется функция поиска позиции искомой записи в файле. После определения позиции, все записи, начиная со следующей за найденной и до самой последней, сдвигаются на одну позицию в сторону начала файла. После этого последняя запись обрезается.

//Удалить запись из отсортированного файла

procedure delFromSortFile(var f: TAttFile; fam: TName);

var pos: integer; rf: TAttRec;

Begin

// Ищем позицию записи с заданной фамилией

pos:= findPosInSortFile(fam, f);

if pos < 0 then begin

showMessage(fam+' не найдено');

exit;

end;

//Сдвигаем все записи начиная со следующей за найденной

while pos < fileSize(f) - 1 do begin

pos:=pos + 1;

seek(f, pos);

read(f, rf);

seek(f, pos-1);

write(f, rf);

end;

// Обрезаем последнюю запись

seek(f, fileSize(f) - 1);

truncate(f);

end;