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.

  1.  Дан файл F. Отсортировать его в алфавитном порядке.

9. Дано слово p и файл F. Найти в файле F все слова, которые можно составить из букв слова p.