Пример программы работы с файлом данных.

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

сотрудника и его Ф.И.О. Требуется добавлять, удалять и просматривать

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

индекса.

Особенности алгоритма:

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 |