![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Пример программы работы с файлом данных.
Пусть каждая запись файла данных содержит два поля: табельный номер сотрудника и его Ф.И.О. Требуется добавлять, удалять и просматривать файл данных. После каждой операции добавления записи в файл (или удаления???) необходимо его записи сортировать в порядке увеличения табельного номера. При этом сортировка записей должна производится с помощью индекса. Особенности алгоритма: 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 |
|