4773
Сложные типы данных: записи и файлы
Реферат
Информатика, кибернетика и программирование
Сложные типы данных: записи и файлы Сложные типы данных в языке Pascal. Записи. Примеры. Записи с вариантами. Оператор присоединения. Строки и средства их обработки. Процедуры и функции типа String. Файлы. Управление файлами. Основные ...
Русский
2012-11-26
146 KB
31 чел.
Сложные типы данных: записи и файлы
1.Сложные типы данных в языке Pascal.
2.Записи.
Примеры.
3.Записи с вариантами.
4.Оператор присоединения.
5.Строки и средства их обработки.
Процедуры и функции типа String.
6.Файлы. Управление файлами.
7.Основные задачи обработки файлов.
8.Сортировка файлов.
Алгоритм сортировки слиянием.
9.Задача корректировки файла.
10.Задачи и упражнения.
1.Сложные типы данных в языке Pascal.
Мы уже получили представление о некоторых типах данных, которые используются при программировании на Паскале. Простые типы данных либо предопределены как стандартные, либо определяются в программе.
Стандартные типы Типы, определяемые программистом
Integer; Перечисляемый тип;
Real; Скалярный тип.
Char:
Boolean.
С понятием простого типа связаны:
имя типа;
множество допустимых значений типа;
набор операций, определенных на типе;
набор отношений, определенных на типе;
набор функций, определенных или принимающих значения на типе;
Из данных простых типов можно конструировать данные сложных типов. Единственным (пока) примером сложных типов являются регулярные типы (значения - массивы). С понятием сложного типа связаны:
имя типа;
способ объединения данных в данное сложного типа;
способ доступа к данным, образующим сложное данное типа;
Так, определение
Type Vector = array [1..N] of Integer;
Var X : Vector;
задает N целых чисел, объединенных в единое целое - массив c именем X. Доступ к компоненте массива осуществляется по его имени X и значению индексного выражения : X[i].
Кроме регулярных типов, в языке определены еще некоторые сложные типы. Каждое такое определение задает свой, характерный механизм объединения данных в единое целое и механизм доступа к данным - компонентам сложного данного.
Это - комбинированный тип (записи), файловый тип (файлы), множественный тип (множества) и ссылочный тип (ссылки).
2. Записи.
Значениями так называемого комбинированного типа данных являются записи. Комбинированный тип задает образ структуры объекта - данного этого типа, каждая часть которой (поле) может иметь совершенно различные характеристики.
Таким образом, запись - это набор разнотипных данных, объединенных общим именем. Более формально, запись содержит определенное число компонент, называемых полями.
В определении типа записи задается имя и тип каждого поля записи:
<комбинированный тип>::= Record < список описаний полей > End
<список полей>::= <фиксир. часть> | <фиксир. часть>;<вариант. часть> | <вариант. часть>
<фиксированная часть>::= <секция записи> {,<секция записи>}
< секция записи >::= <имя поля>{,<имя поля>}:< тип > <пусто>
Синтаксис записей, содержащих вариантную часть - записей с вариантами - мы определим ниже. Соответствующие синтаксические диаграммы записей с вариантами:
Комбинированный
тип
Фиксированная секция
часть записи
Примеры.
Пример 1
Type Complex = Record
Re, Im : Real
end;
Var z1, z2 : Complex;
Пример 2
Type Name = array [1..15] of Char;
Student = Record
F1,F2,F3 : Name;
Day : 1..31;
Month : 1..12;
Year : integer;
StudDoc : integer
end;
Var Group : array [1..25] of student;
S : Student;
При обозначении компоненты записи в программе следом за именем записи ставится точка, а затем имя соответствующего поля. Таким образом осуществляется доступ к этой компоненте Например:
1) z1.Re := 2; z1.Im := 3;
M := sqrt(sqr(z1.Re) + sqr(z1.Im));
2) S.F1 := Group[i].F1;
S.Year := Group[i + 1].Year;
writeln( Group[i].StudDoc);
Запись может входить в состав данных более сложной структуры. Можно говорить, например, о массивах и файлах, состоящих из записей. Запись может быть полем другой записи.
Пример 3
Type Name = array[1..20] of Char;
FullName = Record
Name1, Name2, Name3 : Name
end;
Date = Record
Day : 1..31;
Month : 1..12;
Year : integer
end;
Student = Record
StudName: FullName;
BirthDay: Date;
StudDoc: integer
end;
Var StudGroup : Array [1..30] of Stugent;
A, B : Student;
Например, доступ к полю day переменной A возможен по имени A.BirthDay.Day, а к первой букве поля Name2 имени студента с номером 13 переменной StudGroup - по имени StudGroup[13].StudName.Name2[1]
3. Записи с вариантами.
Синтаксис комбинированного типа включает и вариантную часть, предполагающую, что можно определить тип, содержащий определения нескольких вариантов структуры. Например, запись в компьютерном каталоге библиотеки может иметь следующую структуру:
Фиксированная часть
Фамилия Имя Отчество |
{автора} |
Название |
{книги} |
Издательство |
{его атрибуты} |
Шифр |
{библиотеки} |
Состояние |
(выдана, в фонде, в архиве) |
Вариантная часть
Значение признака |
выдана |
в фонде |
в архиве |
Поля Вариантной части |
Фамилия И.О N% {чит.билета} Дата {выдачи} |
адрес {хранения} |
имя {архива} адрес {хранения} дата {архивации) |
Синтаксис вариантной части:
<вариантная часть >::= case <поле признака> <имя типа> of < вариант >{;<вариант>}
<вариант>::=<список меток варианта>:(<список полей>) _ <пусто>
<список меток варианта>::=<метка варианта>{;<метка варианта>}
<метка варианта>::=<константа>
<поле признака>::=<имя>:<пусто>
Соответствующие синтаксические диаграммы:
Вариантная
часть
поле
признака вариант
Описание типа записи в рассмотренном примере может иметь вид:
Пример 4
Book = record
Author : FullName; {фиксированная часть}
BookName: String;
BookCode: Code;
Station : (Readed, inFile, inArchive);
case Station of {поле признака}
Readed: Reader : FullName; {вариантная часть}
ReadCode : Integer;
ReadDate : Date;
inFile: FilAdress : Adress;
inArc : ArcName : Srting;
ArcAdress: Adress
end
end;
В нашем примере на варианты указывает поле Station. В зависимости от значения этого поля запись имеет ту или иную структуру. Это частая ситуация. Обычно на вариант записи указывает одно из полей фиксированной части этой записи. Поэтому синтаксисом допускается сокращение: описание определяющей вариант компоненты, называемой полем признака (дискриминантом), включается в сам заголовок варианта. В нашем примере 4 это выглядит так:
Type BookStation = (Readed, inFile, inArc);
Book = record
Author : FullName;
BookName : String;
BookCode : Code;
case Station : BookStation of
Readed : Reader : FullName;
ReadCode : Integer;
ReadDate : Date;
inFile : FilAdress: Adress;
inArc : ArcName : String;
ArcAdress: Adress
end
end;
Все имена полей должны быть различными, даже если они встречаются в различных вариантах. (Например, Author, Reader - имена людей, а FilAdress и ArcAdress - адреса, указывающие на местонахождение книги на полках хранилища). В случае, когда один из вариантов не содержит вариантной части, он должен быть оформлен следующим образом:
EmptyVariant :( ) {EmptyVariant - метка пустого варианта}
4. Оператор присоединения.
Если A - переменная типа Student из примера 1, ee значение можно изменить группой операторов:
A.F1 := 'Иванов '; A.F2 := 'Илья '; A.F3 := 'Иннокентьевич ';
A.Day := 14; A.Month := 9; A.Year := 1976;
A.StudDoc := 123;
Приведенные выше обозначения можно сократить с помощью оператора присоединения. Заголовок этого оператора открывает область действия "внутренних" имен полей записи, которые могут быть использованы как имена переменных. Оператор присоединения имеет вид:
With <переменная-запись> {,<переменная-запись>} do <оператор>
Пример 5
with A do begin
F1 := 'Иванов '; F2 := 'Илья '; F3 := 'Иннокентьевич ';
Day := 14; Month := 9; Year := 1976;
StudDoc := 123;
end { оператора with }
Более того, в группе операторов обработки переменной StudGroup[i] (пример 3) запись может быть сформирована следующим образом:
With StudGroup[3], StudName do begin
Name1 := 'Иннокентьева'; Name2 := 'Инна '; Name3 := 'Ивановна ';
BirthDay.Day := 14; BirthDay.Month := 9; BirthDay.Year := 1976;
StudDoc := 123
end;
Таким образом, оператор вида
With r1,...,rn do S
эквивалентен оператору
With r1 do with r2 ... with rn do S.
Замечание: В операторе With R do S выражение R не должно содержать переменных, изменяемых в операторе S. Например, оператор With S[j] do j := j + 1 недопустим!
В качестве примера рассмотрим программу, которая обрабатывает массив записей, каждая из которых содержит сведения о человеке, необходимые для связи с ним по почте. Обработка записи заключается в поиске всех лиц, родившихся в данный день.
Запись имеет вид:
Полное имя (Фамилия Имя Отчество)
День рождения (День, Месяц, Год)
Адрес (Индекс, Страна, Город, Улица, N дома, N кварт)
Program Adress;
Const n = 100;
Type
{ описания типов Name, FullName, Date из примера 3 }
Mail = Record Index : LongInt; { длинное (4 байта) целое число }
Country, Sity, Street : Name;
House, Flat : Integer
end;
Person = Record
Who : FullName;
When : Date;
Where : Mail
end;
Var
Today : Date;
Department : array [1..N] of Person;
i : Integer;
Function theSame(var X : Date, var Y : Person): Boolean;
Begin
With Y, When do
theSame := (X.Day = Day) and (X.Month = Month)
End;
{Procedure ReadDepartment - ввод массива записей}
Procedure ReadDate(var Z : Date);
Begin
With Z do Read(Day, Month)
End;
Procedure WriteMail(var X : Person);
Begin
With X, Who do Writeln(Name1, ' ', Name2, ' ', Name3);
With X, Where do begin
Writeln(Street, ' ',House, ' ', Flat);
Writeln(Index, ' ', Sity, ' ', Country);
end
End;
Begin
ReadDepartment; { ввод массива записей }
ReadDate(Today);
For i := 1 to N do
if theSame(Today, Department[i])
then WriteMail(Department[i])
End;
5.Строки и средства их обработки
Значением строкового типа данных являются строки. Стандарт языка предусматривает использование строк только как констант, используемых в операторах вывода Write, Writeln. В расширении языка Turbo-Pascal строковый тип данных определен гораздо полнее.
Определение строкового типа следует диаграмме:
Здесь целое принадлежит диапазону 1..255 и означает максимальное количество символов в строке этого типа. Если описание типа String используется без указания максимального количества символов, это (по умолчанию) означает, что под этот тип резервируется 255 символов.
Например:
Type Name = String[20]; { строки из 20-ти символов }
Post = String; { строки из 255-ти символов }
Процедуры и функции типа String.
Над строками определена операция конкатенации "+", результат которой - строка, в которой операнды соединены в порядке их сле-дования в выражении. Например:
'Turbo' + 'Pascal' = 'TurboPascal'; 'Turbo_' + 'Pascal ' + 'System' = 'Turbo_Pascal System';
Поэтому результатом выполнения серии операторов
X := 'Пример'; У := 'сложения'; Z := 'строк';
Writeln(X + Y + Z); Writeln(Y + ' ' + Z + ' ' + X)
будут выведенные на экран строки
Примерсложениястрок
сложения строк Пример
Тип String допускает и пустую строку - строку, не содержащую символов: EmptyStr := '' {подряд идущие кавычки}. Она играет роль нуля (нейтрального элемента) операции конкатенации: EmptyStr + X = X + EmptyStr = X
Над строками определены также отношения (операции логического типа)
" = ", " <> ", " < ", " > ", " <= ", " >= ".
Таким образом, каждый из строковых типов упорядочен, причем лексикографически. Это означает, что
а) порядок на строках согласован с порядком, заданным на символьном типе (Char);
б) сравнение двух строк осуществляется посимвольно, начиная с первых символов;
в) если строка A есть начало строки B, то A < В;
г) пустая строка - наименьший элемент типа.
Например:
а) 'с' < 'k', так как Ord(c) < Ord(k);
б) 'abс' < 'abk', так как первые два символа строк совпадают, а сравнение третьих дает Ord(c) < Ord(k);
в) 'abс' < 'abkd', так как первые два символа строк совпадают, а сравнение третьих дает Ord(c) < Ord(k);
г) 'ab' < 'abсd', так как строка 'ab'- начало строки 'abсd'.
На строковом типе данных определены:
Функции:
a) Length(X: String): Byte; - длина строки X; { Length(EmptyStr) = 0 }
б) Pos(Y:String; X:String):Byte; - позиция первого символа первого слева вхождения подстроки Y в строку X. Если X не содержит Y, Pos(Y, X) = 0.
в) Copy(X:String; Index, Count: Integer):String - подстрока строки X, начинающаяся с позиции Index и содержащая Count символов.
г) Concat(X1, X2, .., Xk: String): String; - конкатенация строк Х1, X2, .., Xk. Другая форма записи суммы X1+X2+ .. +Xk.
Процедуры:
д) Delete(var X: String; Index, Count: Integer); Из строки X удаляется Сount символов, начиная с позиции Index. Результат помещается в переменную X.
e) Insert(Y:string; var X: String; Index: Integer); В строку X вставляется строка Y, причем вставка осуществляется начиная с позиции Index.
Стандартные процедуры ввода-вывода Паскаля расширены для ввода-вывода строк. Отметим, однако, что для ввода нескольких строковых данных следует пользоваться оператором Readln. Оператор Read в этих случаях может вести себя непредсказуемо.
Пример 2. Дан массив A[1..n] of string[20]. Составить программу замены всех первых вхождений подстроки L в A[i] на подстроку R. Строки L и R вводятся с клавиатуры в виде равенства L = R. Результат замен отобразить в массив, элементы которого - равенства вида A[i]=результат замены L на R в A[i].
Program RewriteArray;
Const n = 100; Single = 20; Double = 41;
Type
Sitem = string[Single]; Ditem = string[Double];
SWordArray = array[1..n] of Sitem; DWordArray = array[1..n] of Ditem;
Var
A: SWordArray; B: DWordArray;
L, R: Sitem; X : Sitem;
i, Index : Integer;
Procedure InpWord(var U, V : Sitem);
Var X : Ditem;
j : Integer;
Begin
Writeln('________ Ввод равенства L = R __________');
Read(X); j := Pos('=', X);
U := Copy(X, 1, j - 1);
V := Copy(X, j + 1, Length(X))
End;
Procedure InpArray;
begin
Writeln('====== Ввод массива слов ======');
For i:=1 to n do Readln(A[i])
end;
Procedure OutArray;
begin
Writeln('====== Вывод массива слов ====');
For i:=1 to n do Writeln(B[i])
end;
Begin
InpArray; {ввод массива слов с клавиатуры}
InpWord(L, R); {ввод и анализ равенства L = R}
For i := 1 to n do begin
X := A[i]; Index := Pos(L, X);
If Index <> 0
then begin
Delete(X, Index, Length(L));
Insert(R, X, Index)
end;
B[i] := A[i] + '=' + X
end;
OutArray; {вывод массива слов на печать }
End.
6.Файлы. Управление файлами.
Программа, написанная на языке Pascal, должна каким-то образом обмениваться данными с внешними устройствами (получать данные с клавиатуры, магнитного диска, выводить данные на экран, принтер и т.д.) Для работы с внешними устройствами используются файлы. Файлы - это значения файлового типа данных - еще одного стандартного сложного типа в языке.
(Последовательный) файл - это последовательность однотипных компонент, снабженная признаком конца и обрабатываемая последовательно - от начала к концу.
Порядок компонент определяется самой последовательностью, подобно тому, как порядок следования очередного кадра кинофильма определяется его расположением на кинопленке. В любой момент времени доступен только один элемент файла (кадр кинофильма). Другие компоненты доступны только путем последовательного продвижения по файлу.
В результате выполнения программы происходит преобразование одного текстового файла (называемого Input) в другой текстовый файл (называемый Output). Оба эти файла являются стандартными и служат для ввода/вывода данных.
Над файлами можно выполнять два явных вида действий:
1.Просмотр (чтение) файла.
2.Создание (запись) файла - выполняется путем добавления новых компонент в конец первоначально пустого файла.
Файлы, с которыми работает программа, должны быть описаны в программе. Часть файлов (представляющих собой физические устройства) имеет в операционной системе стандартные имена. Например, для чтения данных с клавиатуры и вывода результатов на экран монитора мы пользуемся стандартными файлами Input и Output. Файл - принтер имеет имя Prn:
Имена нестандартных файлов, используемых в программе, необходимо описывать в разделе переменных. Описание файлового типа соответствует диаграмме:
файловый тип
Файл, компоненты которого являются символами, называется текстовым и имеет стандартный тип Text:
Type Text = File of Char;
Примеры:
Type
ExtClass = File of Person;
CardList = File of Integer;
Var
F : Text;
Data : File of real;
List1, List2 : CardList;
Class10A, Class10B : ExtClass;
Для работы с нестандартными файлами имя файла должно быть отождествлено с реально существующим объектом - внешним устройством. Именно, если нам необходимо обработать данные из файла, находящегося на магнитном диске и имеющего (внешнее) имя D:\ExtName.dat, мы должны сообщить системе, что работая с файлом IntName (читая из него данные или записывая в него данные), мы работаем с файлом ExtName.dat, находящимся на диске D:.
Для отождествления внутреннего имени файла со внешним именем используется процедура Assign(< внутреннее имя >, < 'внешнее имя'>).
После того, как имя файла описано и определено, можно приступить к работе с файлом. При использoвании нестандартных файлов следует помнить, что перед работой необходимо открыть их, т.е. сделать доступными из программы. Для этого нужно применить одну из двух следующих процедур:
Процедура Rewrite(<имя файла>) - открывает файл для записи. Если файл ранее существовал, все данные, хранившиеся в нем, уничтожаются. Файл готов для записи первой компоненты.
Процедура Reset(<имя файла>) - открывает файл для чтения. Файл готов для чтения из него первой компоненты.
По окончании работы с файлом (на запись) он должен быть закрыт. Для этого используется процедура Close(<имя файла>). Эта процедура выполняет все необходимые машинные манипуляции, обеспечивающие хранение данных в файле.
Для обмена данными с файлами используют процедуры Read и Writе.
Процедура Read(<имя файла>, <список ввода>) читает данные из файла (по умолчанию имя файла - Input). Список ввода - это список переменных.
Процедура Write(<имя файла>, <список вывода>) записывает данные в файл (по умолчанию имя файла - Output). Список вывода - это список выражений.
Если F - файл типа Text, то в списке ввода/вывода допустимы переменные/выражения типа Integer, Real, Char, String[N]. В других случаях типы всех компонент списка должны совпадать с типом компоненты файла.
При работе с файлами применяют стандартные логические функции:
Eof(F) (end of file) - стандартная функция - признак конца файла. Если файла F исчерпан, то Eof(F) = True, в противном случае Eof(F) = False.
Eoln(F) (End of line) - стандартная функция - признак конца строки текстового файла. Если строка текстового файла F исчерпана, то Eoln(F) = True, в противном случае Eoln(F) = False. Функция Eoln определена только для файлов типа Text. Обычно в программах используют либо текстовые файлы, либо файлы, компонентами которых являются структурированные данные (например, записи).
Следует помнить, что данные файловых типов нельзя использовать в качестве компонент других структур данных. Например, нельзя определить массив, компонентами которого являются файлы, запись, полем которой является файл.
Пример 3. Программа формирования файла как выборки из компонент другого файла.
Пусть F - файл записей вида (поле ключа, поле данных). Требуется сформировать файл G, содержащий те компоненты F, ключи которых удовлетворяют условию: значение ключа - целое число из интервала ]Max, Min [.
Program FileForm;
Type Component = Record
Key: Integer; { поле ключа }
Data: String[20] { поле данных}
End;
OurFile = File of Component;
Var F, G : OurFile;
Max, Min : Integer;
X: Component;
Function Correct(var U: Component): Boolean;
begin
Correct := (U.Key < Max) and (U.Key > Min)
end;
Begin
Read(Max, Min);
Assign(F, 'D:InpFile.dat'); {определено значение F }
Assign(G, 'D:OutFile.dat'); {определено значение G }
Reset(F); {файл F открыт для чтения}
Rewrite(G); {файл G открыт для записи}
While not(Eof(F)) do begin {цикл чтения F - записи G}
Read(F, X);
If Correct(X) then Write(G, X)
end;
Close(G) {файл G закрыт}
End;
7.Основные задачи обработки файлов.
Специфика файлового типа, связанная с последовательным доступом к компонентам и расположением файлов на внешних носителях, накладывает жесткие ограничения на способы решения задач обработки файлов. Рассмотрим некоторые такие задачи. Для определенности будем считать, что все файлы имеют тип OurFile из примера 3 и упорядочены по значению ключевого поля Key (ключу).
Задача 1. Добавление элемента к файлу. Дан файл F и элемент X типа Component. Расширить F, включив в него компоненту X с сохранением упорядоченности.
Вот, наверное, единственно возможное решение:
Переписывать покомпонентно F в новый файл G до тех пор, пока F^.Key < X.Key ;
Записать X в G;
Переписать "хвост" файла F в G;
Переименовать G в F.
Задача 2. Удаление элемента из файла. Дан файл F и число K - значение ключа удаляемых элементов. Сократить F, удалив из него все компоненты с ключом K.
Решение аналогично решению задачи 1:
Переписывать покомпонентно F в новый файл G до тех пор, пока F^.Key < X.Key ;
Пока F^.Key = K читать F;
Переписать "хвост" файла F в G;
Переименовать G в F.
Отметим, что:
- Решения этих задач потребовали последовательного поиска места элемента X как компоненты файла. Эффективное решение задачи поиска (например, бинарный поиск) невозможно.
- В качестве выходного используется новый файл, поскольку чтение/запись в один и тот же файл невозможны!
Следующие задачи посвящены обработке двух файлов.
Задача 3. Слияние файлов. Даны файлы F и G. Требуется сформировать файл H, содержащий все компоненты как F, так и G.
Алгоритм состоит в последовательном и поочередном просмотре файлов F и G и записи очередной компоненты в H. Очередность определяется сравнением значений ключей компонент F и G. Оформим алгоритм в виде процедуры:
Procedure FileMerge(var F, G, H: OurFile);
Var X, Y : Component;
Flag : Boolean;
Procedure Step(var U:OurFile; var A, B:Component);
begin
Write(H, A);
If Eof(U)
then begin Write(H, B); Flag := False end
else Read(U, A)
end;
Procedure AppendTail(var U: Ourfile);
Var A: Component;
Begin
While not(Eof(U)) do begin
Read(U, A); Write(H, A)
end
end;
Begin
Reset(F); Reset(G); Rewrite(H);
Flag := True;
Read(F, X); Read(G, Y);
While Flag do
If X.Key < Y.Key
then Step(F, X, Y)
else Step(G, Y, X);
AppendTail(F);
AppendTail(G);
Close(H)
End;
Задача 4. Пересечение файлов. Даны файлы F и G. Требуется сформировать файл H, содержащий все компоненты, входящие как в F, так и в G.
Задача 5. Вычитание файлов. Даны файлы F и G. Требуется сформировать файл H, содержащий все компоненты входящие в F, но не входящие в G.
Решение этих задач аналогично решению задачи слияния файлов.
8.Сортировка файлов.
Упорядоченность компонент файла по одному или нескольким ключевым полям - одно из основных условий эффективной реализации задач обработки файлов. Так, задача распечатки файла в определенном порядке следования компонент, если файл не упорядочен соответствующим образом, решается с помощью многократных просмотров (прогонов) файла. Количество прогонов при этом пропорционально количеству компонент.
Отсутствие прямого доступа к компонентам приводит к тому, что рассмотренные выше алгоритмы сортировок массива невозможно эффективно адаптировать для сортировки файла. В отличие от массивов, основные критерии эффективности алгоритма сортировки файла - количество прогонов файлов и количество промежуточных файлов.
Так, например, алгоритм сортировки простыми обменами требует N прогонов сортируемого файла (N - количество компонент файла). Алгоритм быстрой сортировки вообще не имеет смысла рассматривать, поскольку при его реализации необходимо было бы читать файл от конца к началу!
Рассмотрим поэтому новый для нас алгоритм - алгоритм сортировки слиянием, который наиболее эффективен при сортировке файлов и относится к быстрым алгоритмам при сортировке массивов, хотя и требует дополнительной памяти.
Алгоритм сортировки слиянием.
Пусть сортируемая последовательность F = { f1, ..., fN } представлена в виде двух уже отсортированных половин - F1 и F2. Тогда для сортировки F достаточно слить (т.е. применить аналог алгоритма слияния FileMerge) последовательности F1 и F2 в выходную последовательность G. Поскольку упорядоченные половинки F1 и F2 можно получить с помощью тех же действий, мы можем описать алгоритм сортировки слияниями рекурсивно. При этом, очевидно, необходимо использовать оптимальное количество промежуточных файлов. Поскольку слияния нужно начинать с однокомпонентных файлов, точная реализация описанного алгоритма потребует 2N дополнительных файлов, что, конечно, неприемлимо. Поэтому мы должны использовать один файл для хранения нескольких сливаемых подпоследовательностей. Уточним эту идею:
Пусть сортируемый файл F содержит k-элементные упорядоченные подпоследовательности A1, A2, ..., A2l, k = 2l.
1.Разделение F заключается в переписи подпоследовательностей Aj с четными номерами в файл F1, а с нечетными номерами - в файл F2.
Пусть файл F1 содержит k-элементные упорядоченные подпоследовательности B1, B3, ..., B2l-1, а F2 - k-элементные упорядоченные подпоследовательности B2, B4, ..., B2l.
2.Слияние F1 и F2 заключается в слияниях пар <Bi, Bi+1> в подпоследовательности A(i+1) div 2 в файл F. После обработки F будет содержать l 2k-элементных подпоследовательностей Aj.
Если N - степень 2-x (N = 2m), то после m-кратного повторения разделения-слияния, начиная с A1={f1}, ..., AN={fN}, файл F будет содержать отсортированную последовательность. В общем случае, когда N 2m, управление слияниями-разделениями немного усложняется:
- при разделении количество подпоследовательностей может оказаться нечетным;
- при слиянии последняя по счету подпоследовательность одного из файлов может иметь меньшее, чем все другие, количество элементов.
Program MergeSort;
Type Component = Record
Key: Integer; { поле ключа }
Data: String[20] { поле данных}
End;
OurFile = File of Component;
Var F, F1, F2 : OurFile;
k, L, t, SizeF: Integer;
{Procedure FileOut(var F :OurFile);}
{Procedure FileInp(var F: Ourfile);}
Procedure CopyBlock(Var U, V: OurFile; k: Integer);
Var i: Integer;
X: Component;
Begin
For i := 1 to k do begin
Read(U, X); Write(V, X)
end
End;
{ разделение блоками по k компонент F ==> F1, F2 }
Procedure Partition(k: Integer);
Var i: Integer;
Begin
Reset(F); Rewrite(F1); Rewrite(F2);
For i:= 1 to L do
If Odd(i)
then CopyBlock(F, F1, k)
else CopyBlock(F, F2, k);
If Odd(L)
then CopyBlock(F, F2, t)
else CopyBlock(F, F1, t);
Close(F1); Close(F2)
End;
{ слияние блоками по k компонент F1, F2 ==> F }
Procedure Merge(k: Integer);
Var i: Integer;
Procedure MergeBlock(t: Integer);
Var count1, count2: Integer;
X1, X2: Component;
Flag: Boolean;
Procedure AppendTail(var U: Ourfile; var p: Integer; s: Integer);
Var A: Component;
Begin
While p <= s do begin
Read(U, A); Write(F, A); p := p + 1
end;
End { AppendTail };
Procedure Step(var U: OurFile; Var A, B: Component; var p, q: Integer; s: Integer);
begin
Write(F, A); p := p + 1;
If p <= s
then Read(U, A)
else begin Write(F, B); q := q + 1; Flag := False end
end { Step };
Begin { MergeBlock }
count1 := 1; count2 := 1; Flag := True;
Read(F1, X1); Read(F2, X2);
While Flag do
If X1.Key < X2.Key
then Step(F1, X1, X2, count1, count2, k)
else Step(F2, X2, X1, count2, count1, t);
AppendTail(F1, count1, k); AppendTail(F2, count2, t);
end { MergeBlock };
Begin { Merge }
Rewrite(F); Reset(F1); Reset(F2);
For i := 1 to (L div 2) do MergeBlock(k);
If t<> 0
then if Odd(L)
then MergeBlock(t)
else CopyBlock(F1, F, t)
else if Odd(L)
then CopyBlock(F1, F, k)
End { Merge };
Procedure FirstPartition;
Var X : Component;
Begin
Reset(F); Rewrite(F1); Rewrite(F2);
SizeF := 0;
While not(Eof(F)) do begin
Read(F, X); SizeF := Succ(SizeF);
If Odd(SizeF)
then Write(F1, X)
else Write(F2, X)
end;
Close(F1); Close(F2)
End { FirstPartition };
Begin {Определение внешних имен файлов F, F1, F2}
FileInp(F);
FirstPartition; {первое разделение с подсчетом SizeF}
L := SizeF; t := 0;
Merge(1); {первое слияние 1-блоков}
k := 2;
While k < SizeF do begin
L := SizeF div k; {количество полных k-блоков в F}
t := SizeF mod k; { размер неполного k-блока }
Partition(k);
Merge(k);
k := 2*k
end;
FileOut(F);
End.
Оценим сложность алгоритма в терминах С(n), M(n), L(n), где L(n) - число прогонов файла F и n = SizeF.
1.Оценка L(n).
L(n)= число разделений + число слияний. Каждое разделение - вызов процедуры Partition, а слияние - вызов Merge. Поэтому L(n) - удвоенное число повторений тела цикла While. Отсюда, поскольку переменная k, управляющая циклом, каждый раз увеличивается вдвое, на L-том шаге k = 2L, и, следовательно, L - наибольшее число такое, что 2L < n, т.е. L = [log2 n].
L(n) = 2[log2n]
2.Оценка С(n).
Сравнения копонент по ключу производятся при слиянии. После каждого сравнения выполняется процедура Step, которая записывает одну компоненту в F. Поэтому при каждом слиянии количество сравнений не превосходит n. Отсюда C(n) L(n)*n/2, т.е.
С(n) n [log2 n]
3.Оценка M(n).
Процедуры Partition и Merge пересылают компоненты файлов. Независимо от значений ключей вызов каждой из них либо читает F, либо записывает F. Поэтому M(n) = nL(n), т.е.
M(n) = 2n[log2 n]
Полученные оценки позволяют классифицировать алгоритм как эффективный алгоритм сортировки последовательных файлов. Его также можно адаптировать к сортировке массивов.
Алгоритм сортировки слиянием может быть улучшен несколькими способами. Рассмотрим только некоторые из них:
а. Заметим, что процедура Partition носит вспомагательный характер. Не анализируя ключей, она просто формирует файлы F1 и F2 для слияния. Поэтому ее можно исключить, если процедуру Merge заставить формировать не F, а сразу F1 и F2. При этом, конечно, количество файлов в программе увеличится. Именно:
1.F разделим на (F1, F2).
2.Определим вспомогательные файлы G1, G2
3.Основной цикл алгоритма:
Слияние (F1, F2) ===> (G1, G2);
Слияние (G1, G2) ===> (F1, F2);
(Нечетные пары блоков сливаем на 1-ый файл, четные - на 2-ой).
Временная сложность алгоритма улучшается почти вдвое.
б. Заметим, что на начальной стадии работы алгоритма размеры блоков малы. Их можно сортировать в оперативной памяти, используя представление в виде массива и быстрые алгоритмы сортироки массивов. Таким образом, следует изменить процедуру FirstPartition, определив ее как процедуру внутренней сортировки k0-блоков при некотором (максимально возможном) значении k0. Цикл While основной программы теперь можно начинать с k = k0.
в. В реальных файлах часто встречаются уже упорядоченные участки компонент. Поэтому файл можно изначально рассматривать как последовательность упорядоченных участков, и сливать не блоки фиксированного размера, а упорядоченные участки. Такие сортировки называют естественными.
9.Задача корректировки файла.
Задача корректировки файла является одной из основных задач обработки файлов. Рассмотрим ее формулировку:
Исходные данные задачи - корректируемый файл F, файл корректировок G. Результат - откорректированный файл H. Будем считать, что файл F имеет тип OurFile. Тогда файл H имеет тот же тип. Файл корректировок G состоит из записей с вариантами:
Type
CorСomponent = record
Key: Integer;
job: (Include, Change, Exclude); {включить, изменить, исключить}
Case job of
Include, Change: Data: String[20]; Exclude: ()
end
End;
CorFile = File of CorComponent;
Var G : CorFile;
Это означает, что файл корректировок содержит компоненты, которые нужно включить в основной файл, компоненты, которые нужно исключить из файла и компоненты, содержание которых нужно изменить (с учетом содержания как основного файла, так и файла корректировок).
Файл F предполагается упорядоченным (по ключу), а файл G, вообще говоря, нет. Результатом должен быть упорядоченный откорректированный файл H.
Решение задачи обычно содержит два этапа:
а) Сортировка файла корректировок G по ключу;
б) Обобщенное слияние файлов F, G в H.
На практике файл G может быть небольшим. В этом случае применяют внутреннюю сортировку.Обобщенный алгоритм слияния производит все три варианта обработки файла F за один прогон.
В заключение заметим, что современные ЭВМ редко активно используют внешние носители с последовательным доступом в решениях задач управления базами данных, поэтому структуры данных, в которых хранится информация, как правило, более сложны, чем последовательные файлы.
10.Задачи и упражнения.
Файлы.
1.Разработайте программу Добавление элемента к файлу.
2.Разработайте программу Удаление элемента из файла.
3.Разработайте программу Пересечение файлов.
4.Разработайте программу Вычитание файлов.
5.Разработайте программу Корректировка файлов.
6.Разработайте программу корректировки упорядоченных файлов, в которой производитя изменение значений ключевых полей. Файл корректировок содержит пары
< старый ключ, новый ключ >.
7.Реализуйте улучшение a) алгоритма сортировки слиянием.
8.Реализуйте улучшение в) алгоритма сортировки - сортировку естественным слиянием.
Записи.
1.Опишите тип записи - клетки расписания занятий на факультете для своей специальности и курса. Сформируйте файл двухнедельного расписания для своей подгруппы. Разработайте программу, которая определяет количество лекционных, практических и лабораторных занятий в двухнедельном цикле для своей подгруппы по указанию дисциплины.
2.Опишите тип записи - сведения о студенте группы, необходимые декану факультета. Сформируйте файл студентов своей подгруппы. Разработайте программу, которая определяет состояние успеваемости в подгруппе.
3.Опишите тип записи - сведения о родителях учеников класса, необходимые классному руководителю. Сформируйте файл, состоящий не менее, чем из восьми учеников "Вашего" класса. Разработайте программу, которая по фамилии и имени ученика распечатывает сведения о его родителях.
4.Опишите тип записи - сведения об успеваемости ученика, необходимые для учителя-предметника по своему предмету. Сформируйте файл, состоящий не менее, чем из восьми учеников "Вашего" класса. Разработайте программу, которая определяет самого слабого и самого сильного ученика класса.
5.Опишите тип записи - строчку зачетной книжки (экзаменационная часть). Сформируйте файл экзаменов, сданных Вами. Разработайте программу, которая определяет средний балл, составляет список экзаменаторов и по номеру семестра распечатывает результаты Вашей сессии.
6.Опишите тип записи - строчку зачетной книжки (зачетная часть). Сформируйте файл зачетов, сданных Вами. Разработайте программу, которая определяет дни, когда Вы сдавали по два и более зачетов.
7.Опишите тип записи - сведения о возрасте, росте и весе ученика. Сформируйте файл, состоящий не менее, чем из восьми учеников "Вашего" класса. Разработайте программу, которая определяет всех учеников, родившихся в данный промежуток времени, указанный датами начала и конца и определяет средний рост и средний вес этой группы учеников.
8.Опишите тип записи - сведения о книге (например, по информатике. Сформируйте файл книг, необходимых учителю информатики. Составьте программу, которая подбирает книги для курса, номер которого вводится, печатает имена их авторов и год издания.
9.Опишите тип записи - сведения о товаре в магазине. Сформируйте файл товаров, имеющихся в магазине. Разработайте программу корректировки массива товаров и определяет выручку магазина к данному моменту времени.
10.Опишите тип записи - строчку в телефонной книге. Сформируйте файл записей - вашу телефонную записную книжку. Разработайте программу поиска номера телефона по фамилии и поиска адреса по номеру телефона.
Файлы строк (слов).
1.Найти в файле F все слова-перевертыши и составить из них файл G.
2.Найти в файле F вхождения слова p, заменить их на слово q, получив новый файл G.
3.Найти в файле F все слова, представляющие числа (в десятичной записи) и получить числовой файл G, содержащий найденные числа.
4. Найти в файле F все однобуквенные слова и лишние пробелы, и, удалив их, получить новый файл G.
5. Найти в файле F все слова, встречающиеся более одного раза, и составить файл G, исключив из F найденные слова.
6. В файле F найти все слова, содержащие сдвоенные буквы и составить из них файл G.
7. Найти в файле F все слова, содержащие подслово p и составить из них файл G.
9. Дано слово p и файл F. Найти в файле F все слова, которые можно составить из букв слова p.
А также другие работы, которые могут Вас заинтересовать | |||
75701. | Коллективный договор и порядок его заключения | 13.99 KB | |
Коллективный договор и порядок его заключения Коллективный договор правовой акт регулирующий социально-трудовые отношения в организации и заключаемый работниками и работодателем в лице их представителей. Содержание и структура коллективного договора определяется сторонами. В коллективный договор могут включаться взаимные обязательства работников и работодателя по следующим вопросам: формы системы и размеры оплаты труда; выплата пособий и компенсаций; занятость переобучение; рабочее время и время отдыха включая вопросы... | |||
75702. | Обязанности и права работодателя в обеспечении здоровых и безопасных условий труда | 13.27 KB | |
Обязанности и права работодателя в обеспечении здоровых и безопасных условий труда Основами законодательства Российской Федерации об охране труда определены обязанности работников по соблюдению требований охраны труда и ответственность за нарушение законодательства об охране труда. Работники обязаны: соблюдать нормы правила и инструкции по охране труда; правильно применять средства коллективной и индивидуальной защиты; немедленно сообщать своему непосредственному руководителю о любом несчастном случае происшедшем на производстве... | |||
75703. | Обязанности ИТР в обеспечении здоровых и безопасных условий труда | 17.81 KB | |
Обязанности ИТР в обеспечении здоровых и безопасных условий труда. Инженер по охране труда относится к категории специалистов. Инженер по охране труда назначается на должность перемещается и освобождается от нее приказом руководителя организации по представлению руководителя структурного подразделения. На должность: инженера по охране труда назначается лицо имеющее высшее профессиональное техническое образование без предъявления требований к стажу работы или среднее специальное техническое образование и стаж работы в должности техника... | |||
75704. | Обязанности работников в обеспечении здоровых и безопасных условий труда | 11.27 KB | |
Обязанности работников в обеспечении здоровых и безопасных условий труда. Законодательство об охране труда предусматривает и обязанности работников. Они обязаны соблюдать нормы правила и инструкции по охране труда устанавливающие правила выполнения работ и поведения в производственных помещениях и на строительных площадках использовать и правильно применять коллективные и индивидуальные средства защиты специальную одежду и обувь маски очки респираторы и др. Если правила по охране труда предусматривают что обязательным условием допуска... | |||
75705. | Служба инженера по охране труда на лесохозяйственном предприятии | 14.1 KB | |
Служба инженера по охране труда на лесохозяйственном предприятии В соответствии со статьей 217 Трудового кодекса Российской Федерации в каждой организации осуществляющей производственную деятельность с численностью более 50 работников создаётся служба охраны труда или вводится должность специалиста по охране труда. В организациях с численностью 50 и менее работников решение о создании службы охраны труда принимает работодатель с учётом специфики деятельности данной организации. В случае отсутствия службы охраны труда специалиста... | |||
75706. | Управление риском | 11.43 KB | |
Методы защиты от опасности на производстве: 1 инженерный метод реализуется путём дистанционного управления опасными и вредными процессами. Приёмы защиты человека от опасности: 1 осуществление организации мер защиты 2 создание техники с максимальным уровнем безопасности 3 средства коллективной защиты 4 разработка средств индивидуальной защиты 5 обучение воспитание психологическое воздействие. | |||
75707. | Организация работы уполномоченного (доверенного) лица по охране труда профсоюзной организации предприятия или трудового коллектива | 16.38 KB | |
Организация работы уполномоченного доверенного лица по охране труда профсоюзной организации предприятия или трудового коллектива. Институт уполномоченных создается для организации общественного контроля за соблюдением законных прав и интересов работников в области охраны труда на предприятиях всех форм собственности независимо от сферы их хозяйственной деятельности ведомственной подчиненности и численности работников. Не рекомендуется избирать уполномоченными работников которые по занимаемой должности несут ответственность за состояние... | |||
75708. | Комитет (комиссия) по охране труда л/х предприяти | 13.12 KB | |
Комитет комиссия по охране труда л х предприятия КОМИТЕТ КОМИССИЯ ПО ОХРАНЕ ТРУДА рабочий орган управления охраной труда в организации обеспечивающий согласованные действия работодателя и работников направленные на создание здоровых и безопасных условий труда в организации Комитеты комиссии по ОТ далее К. В их состав на паритетной основе входят представители работодателей профессиональных союзов или иного уполномоченного работниками представительного органа Если в организации нет ни одной первичной профсоюзной организации то в... | |||
75709. | .ОБЩИЕ ПОЛОЖЕНИЯ. | 15.12 KB | |
Задачи функции и права комитета комиссии по охране труда л х предприятия. Комитет создается на паритетной основе из представителей работодателей и уполномоченных работниками по охране труда и осуществляют свою деятельность в целях организации сотрудничества и регулирования отношений работодателей и работников их представителей уполномоченных.Численность комитета равно удвоенной численности уполномоченных по охране труда от работников. Председателем комитета не может быть избран работник который по своим служебным обязанностям ... | |||