Пример программы работы с файлом данных.
Сортировка таблицы адресов (индексная сортировка)
Объем данных, помещенных в каждую из записей файла, может
быть столь большим, что при сортировке перемещение самих записей
является нецелесообразным из-за больших накладных расходов.(рис.1)
а – файл до сортировки, б – файл после сортировки.
При индексной сортировке создается вспомогательная таблица указателей (файл) на записи файла данных(информационного). Вместо перемещения записей в информационном файле перемещаются указатели в индексном файле.
Этот метод называется сортировкой таблицы адресов(индексная сортировка).
Таким образом, сортировке подвергается не сам информационный файл, а вспомогательный файл, каждая запись которого состоит из поля указателя на запись информационного файла и поля ключа этой записи.
Рис.2
Первоначально элемент в позиции j индексного файла указывает на j-ю запись. После окончания сортировки первый указатель указывает на запись файла с наименьшим ключом. Второй указатель - на запись файла со следующим по порядку сортировки ключом и т.д.
Сортировку таблицы указателей можно выполнять одним из методов внутренней сортировки.
Преимущество – скорость;
недостаток – дополнительная память для хранения индексного файла.
Пусть каждая запись файла данных содержит два поля: табельный номер
сотрудника и его Ф.И.О. Требуется добавлять, удалять и просматривать
файл данных. После каждой операции добавления записи в файл необходимо его записи сортировать в порядке увеличения табельного номера. При этом сортировка записей должна производится с помощью
индекса.
Особенности алгоритма:
1. Удаление реализуем таким образом, что на место удаляемой записи переписываем следующую и т.д., а последнюю запись отсекаем.
2. Сортируем информацию в ОЗУ для чего индексный файл считываем в ОЗУ, сортируем и записываем вновь.
3. Информационный файл Data.dat, индексный файл Index.dat
{ Программа является примером работы с индексными файлами }
Program Index;
Uses Dos,Crt;
Const
M = 5; число пунктов меню
Type
Ft = Record
Tn: Word; структура записи информационного файла
Fio: String
End;
It = Record
Tn: Word; структура записи индексного файла
Pos: Word
End;
Var
DataF: File Of Ft;
IndexF: File Of It;
bCase: Byte;
X:Array[1..4096] of It; - рабочий массив
Procedure Browse; (3)
{ Процедура выводит на экран записи из файла Data.Dat
в порядке храниения на диске (без использования Index.Dat)}
Var
VarDF:Ft;
wI:Word;
Begin
Writeln('Номер записи Таб.номер Фамилия И.О.');
Writeln;
wI:=1;
Seek(DataF,0);
While Not(Eof(DataF)) Do Begin
Read(DataF,VarDF);
With VarDF Do позволяет работать с именами полей как с
обычными переменными, т.е без указания перед
идентификаторм поля имени переменной,
определяющей запись
Writeln(wI:5,' ',Tn,' ',Fio);
wI:=wI+1;
End;
End;
Procedure BrowseI; (4)
{ Процедура выводит на экран записи из файла Data.Dat
с использованием Index.Dat}
Var
VarDF:Ft;
VarIF:It;
wI:Word;
Begin
Writeln('Номер записи Таб.номер Фамилия И.О.');
Writeln;
Seek(IndexF,0);
While Not(Eof(IndexF)) Do Begin
Read(IndexF,VarIF);
Seek(DataF,VarIF.Pos-1); потому, что записи нумеруются с 0
Read(DataF,VarDF);
wI:=VarIF.Pos;
With VarDF Do
Writeln(wI:5,' ',Tn,' ',Fio);
End;
End;
Procedure Reindex;
{ Процедура пересоздает файл Index.Dat }
{ Алгоритм:
Считываем табельный номер из Data.Dat в массив X,
сортируем массив методом пузырька и записываем результат
в Index.Dat
}
Var
VarDF:Ft;
VarIF:It;
Wf,wI,wJ:Word;
Begin
{ Очищаем IndexF }
Rewrite(IndexF);
{ Заполняем массив X }
Wf := FileSize(DataF);
wI:=1;
Seek(DataF,0);
While Not(Eof(DataF)) Do Begin
Read(DataF,VarDF);
X[wI].Tn := VarDF.Tn;
X[wI].Pos := wI;
wI := wI+1;
End;
{ Сортируем X }
If Wf > 1 Then Begin
For wI:=1 To Wf-1 Do Begin
For wJ:=1 To Wf-wI Do Begin
If X[wJ+1].Tn < X[wJ].Tn Then Begin
VarIF:=X[wJ+1];
X[wJ+1]:=X[wJ];
X[wJ]:=VarIF;
End;
End;
End;
End;
{ Теперь записываем получившийся массив в Index.Dat }
For wI:=1 To Wf Do Begin
Write(IndexF,X[wI]);
End;
End;
Procedure Append; (1)
{ Процедура добавляет запись в файл Data.Dat }
Var
VarDF:Ft;
Begin
ClrScr;
Write('Табельный номер:');
Readln(VarDF.Tn);
Write('Фамилия:');
Readln(VarDF.Fio);
Seek(DataF,FileSize(DataF));
Write(DataF,VarDF);
Reindex;
Writeln;
Write('Запись добавлена. Нажмите <Enter>...');
Readln;
End;
Procedure Delete; (2)
{ Процедура удаляет запись из файла Data.Dat }
Var
Old,Curr:Ft;
Wz, wI:Word;
Begin
ClrScr;
Browse;
Writeln;
Write('Введите номер удаляемой записи:');
Readln(Wz);
If (Wz<1) Or (Wz>FileSize(DataF)) Then Begin
Writeln;
Writeln('Нет записи с таким номером. Нажмите <Enter>...');
Readln;
End
Else Begin
Old.Tn := 0;
Old.Fio := '';
For wI:=FileSize(DataF) Downto Wz Do Begin
Seek(DataF,wI-1);
Read(DataF,Curr);
Seek(DataF,wI-1);
Write(DataF,Old);
Old:=Curr;
End;
Seek(DataF,FileSize(DataF)-1);
Truncate(DataF);
Reindex;
Writeln;
Write('Запись удалена. Нажмите <Enter>...');
Readln;
End;
End;
Begin
Assign(DataF,'Data.Dat');
Assign(IndexF,'Index.Dat');
{$I-}
Reset(DataF);
{I+}
If IOResult<>0 Then Rewrite(DataF);
{$I-}
Reset(IndexF);
{I+}
If IOResult<>0 Then Rewrite(IndexF);
{ Меню }
bCase := 0;
Repeat
ClrScr;
Writeln('1. Добавить запись в файл');
Writeln('2. Удалить запись из файла');
Writeln('3. Просмотреть файл без использования индекса');
Writeln('4. Просмотреть файл с использованием индекса');
Writeln('5. Выход');
Writeln;
Write('Номер пункта:');
ReadLn(bCase);
Case bCase Of
1:Append;
2:Delete;
3:Begin
ClrScr;
Browse;
Writeln;
Write('Просмотр закончен. Нажмите <Enter>...');
Readln;
End;
4:Begin
ClrScr;
BrowseI;
Writeln;
Write('Просмотр закончен. Нажмите <Enter>...');
Readln;
End;
End;
Until bCase = M;
End.
Пример.
Data.dat
| Попов | |
| Сидоров | |
| Петров | |
| Иванов |
x[1] = 25,1
x[2] = 13,2
x[3] = 11,3
x[4] = 36,4
x[1] = 11,3
x[2] = 13,2
x[3] = 25,1
x[4] = 36,4
Index.dat
11,3
13,2
25,1
36,4
Внешняя сортировка
Внешняя сортировка, как правило производится для наборов данных,
хранящихся на ВЗУ в файлах. Эти наборы данных не помещаются це-
ликом в оперативной памяти.
Для выполнения внешней сортировки производятся следующие операции:
1. Находятся во внешней памяти нужные записи для сравнения их ключей.
2. Производится считывание данныз в ОЗУ.
3. В ОЗУ осуществляются операции сравнения и перестановки, т.е.
ссортировка.
4. Выполняется запись во внешнюю память в соответствии с 1 и 3.
При выборе алгоритма сортровки необходимо учитывать следующие
параметры:
- объем ОЗУ, используемой в качестве рабочей области
- объем внешней памяти, используемой в качестве рабочей области
- число записей и их длину
- время выполнения операций в ОЗУ.
Наиболее общей формой внешней сортировки является сортировка слия-
нием. Процесс внешней сортировки состоит из 2-х этапов:
- этап сортировки
- этап сляиния.
Пусть весь исходный набор данных первоначально размещен в одном
месте (массиве НБ3).
НБ3
-----------------------------------------
| 5 6 1 3 2 8 7 11 10 12 4 9 13 16 15 14|
-----------------------------------------
Этот набор данных разбивается на два НБ1 и НБ2, например нечетные
записи переписываются в НБ1, а четные в НБ2 (рис.)
Сортировка производится в два этапа:
1) из записей, которые хранятся в каждом из наборов данных с помощью
внутренней сортировки формируются упорядоченные цепочки записей.
Длина цепочек L такая, чтобы все записи размещались в ОП. Пусть
L=2, т.е. в ОП размещается только 2 логических записи. В резуль-
тате 1- го этапа в наборах данных будут размещенгы упорядоченные
цепочки по две записи. Здесь может быть использован любой метод
внутренней сортировки.
НБ3 НБ4
|1 5 | 2 7 | 4 10 | 13 15| |3 6| 8 11 | 9 12 | 14 16|
L
2)Слияние полученных наборов. Слияние происходит в несколько циклов.
После каждого цикла длина цепочки увеличивается.
После 1-го цикла
НБ1 НБ2
| 1 3 5 6 | 4 9 10 12| | 2 7 8 11 | 13 14 15 16 |
2L
После 2-го цикла
НБ3 НБ4
| 1 2 3 5 6 7 8 11 | | 4 9 10 12 13 14 15 16 |
4 L
После последнего слияния
НБ1
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |