21.2.3. Упорядочение записей в файле

Эта операция выполняется довольно часто. Ее можно произвести, используя известный метод "пузырька". Здесь возможны два подхода.

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

2. Информация упорядочивается непосредственно в наборе данных.

При значительном размере файла первый метод потребует большого объема памяти. Затраты оперативной памяти у второго подхода минимальны, но по быстродействию он проигрывает первому.

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

Рассмотрим алгоритм на примере, в котором используется более общая по сравнению с телефонным справочником структура записей.

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

Марка, Цена.

Упорядочить записи в наборе по возрастанию цены.

Алгоритм

1.1. Ввести имя набора данных.

1.2. Связать файл с набором данных.

2.1. Признак = "перестановки" (считаем, что перестановки будут).

2.2. Пока "перестановки" выполнить

2.2.1. Признак = " нет перестановок".

2.2.2. Номер записи (k) = 0.

2.2.3. Открыть файл для чтения.

2.2.4. Пока не конец файла выполнить

а) Установить в файле номер записи k;

б) Считать из файла Запись1 ( k-тую );

в) Если не конец файла, то

1)Считать из файла Запись2 ( k+1-вую );

2) Если Запись1.Цена > Запись2.Цена то

2,а) Установить в файле номер записи k;

2,б) Записать в файл Запись2 ( k+1-вую );

2,в) Записать в файл Запись1 ( k-тую );

2,г) Признак = "перестановка";

д) k = k + 1.

2.2.5. Закрыть файл

3. Закончить.

Программа для этого алгоритма будет иметь следующий вид.

Program Sort_File;

Type

Computer=Record

Marka : String[10];

Cena : Integer;

End;

Var

FilComp : File of Computer;

Comp1,Comp2 : Computer;

K : Integer;

Perest : Boolean; { Признак перестановок }

FilName : String; { Имя набора данных}

Begin

Writeln(’Введите имя набора данных’);

Readln(FilName);

Assign(Filan,FilName);

{ Упорядочение }

Perest := True;{ Перестановки будут }

While Perest do

Begin

Perest := False; {Перестановок еще не было}

K := 0;

Reset(FilComp); {Открытие файла}

While Not Eof(FilComp) do

Begin

Seek(FilComp,k);

Read(FilComp,Comp1);

If Not Eof(FilComp) then

Begin

Read(FilComp,Comp2);

If Comp1.Cena>Comp2.Cena then

Begin {Перестановка начинается}

Seek(FilComp,k);

Write(FilComp,Comp2);

Write(FilComp,Comp1);

Perest:=True; {Перестановка}

End;

End;

k:=k+1;

End;

Close(FilComp);

End;

Writeln(’Конец работы, нажмите клавишу Enter’);

Readln;

End.

21.2.4. Удаление записей из файла

Эта операция может быть двух типов:

а) логическое удаление;

б) физическое удаление.

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

Пример. В файле Ftel некоторые номера телефонов сняты. Для логического удаления необходимо добавить в запись Tel еще одно поле, например:

Type

Tel = Record

Nom = Integer;

Fam,Adr : String[15];

Act : Boolean; {Признак активная/пассивная (удаленная)}

end;

При создании файла Ftel поле Act всех записей имеет значение True – запись "активна" (не удалена), т.е. программа при начальном заполнении будет содержать такой фрагмент:

{Начальное заполнение}

Assign (Ftel,’tsprav’);

Rewrite(Ftel);

With Rtel do

Begin

Nom := 0;

Fam := ’’;

Adr := ’’;

Act := True;

end;

For k:=0 to n do

Begin

Seek(ftel,k);

Write(Ftel,Rtel);

end;

Удаление записи с номером Num выполняется как коррекция (изменяется содержимое поля Act на противоположное):

Writeln(’Введите удаляемый номер телефона’);

Read(num);

Seek(Ftel,num);

Read(Ftel,Rtel); {Указатель перешел к следующей записи: num+1}

Rtel.Act := False;

Seek(Ftel,num); { Вернем указатель к записи num }

Write(Ftel,Rtel);

При обработке файла в этом случае необходима дополнительная проверка наличия (активности) записи:

Seek(Ftel,k);

If Not Eof(Ftel) then

Begin

Read(Ftel,Rtel);

if Rtel.Act then {Запись не удалена}

Begin

.....{ обработка неудаленной записи }

end;

......

end;

При физическом удалении записи на ее место переписывается новая информация, т.е. запись стирается. Эта операция выполняется по схеме, приведенной на рис. 2.12, где показано удаление записи с номером 1.

Составим процедуру удаления записи с заданным номеромNum из файла f. Нужно учесть, что удаление сводится к переписи записей после номера Num на 1 место вперед. После переписи (или если для удаления сразу была назначена последняя запись), файл нужно урезать с помощью процедуры Truncate и таким образом убрать из него последнюю запись. Напомним, что после выполнения операций записи/чтения текущая позиция в файле перемещается к следующему элементу.

Считаем, что в программе описан тип Ft = File Of Zap. В процедуре используется функция FileSize(имя_файла), возвращающая размер файла. Описание этой функции приведено в следующем пункте (21.2.5).

Procedure RemoveF(Num : Integer; Var F : Ft);

{Удаление записи с номером num из файла f}

Var

K : Integer;

R : Zap;

Begin

If num<FileSize(f)-1 then {Удаляемая запись не последняя}

begin

K := num; {номер записи, в которую будем переписывать данные}

{Перепись записей на 1 вперед – в начало f}

Seek(f,k+1); {Следующая после удаляемой запись}

While not eof(f) do

Begin

Read(f,R);

Seek(f,k); {Возврат назад }

Write (f,R);

k:=k+1;

Seek (f,k+1);

end;

end;

{Урезаем файл f по последней записи}

Seek(f,FileSize(f)-1);

Truncate(f);

Close(f);

end;