4773

Сложные типы данных: записи и файлы

Реферат

Информатика, кибернетика и программирование

Сложные типы данных: записи и файлы Сложные типы данных в языке Pascal. Записи. Примеры. Записи с вариантами. Оператор присоединения. Строки и средства их обработки. Процедуры и функции типа String. Файлы. Управление файлами. Основные ...

Русский

2012-11-26

146 KB

26 чел.

Сложные типы данных: записи и файлы

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.


 

А также другие работы, которые могут Вас заинтересовать

85201. Изменения в социально-экономической и политической картине мира в конце XX - начале XXI в. Распад Восточного блока 27.13 KB
  Положив в основу общественного прогресса прежде всего эк. фактор и поставив человека в положение лишь средства для достижения своих целей, Советское гос-во все более отставало от передовых стран мира в научно-технолог. плане, в повышении производит-ти труда. В рез-те общество оказалось скованным жесткими предрассудками...
85202. Распад СССР и оформление государственного суверенитета Республики Беларусь 32.92 KB
  Собственностью республики объявлялись предприятия организации и учреждения союзного подчинения размещенные на ее территории. было принято решение об изменении символики республики и переименовании Белорусской Советской Социалистической Республики в ldquo;Республику Беларусьrdquo; или ldquo;Беларусьrdquo;. в Министерстве юстиции Республики было зарегистрировано 34 пол партии.
85203. Государственные программы развития Республики Беларусь 27.14 KB
  Геополитическое положение Республики Беларусь 1990е 2012 г. Республика Беларусь независимое государство. Республика Беларусь по своему географическому положению находится в центре Европы а также занимает срединную часть Евразийского континента в целом.
85204. Духовная и культурная жизнь белорусского народа (вторая половина 1980-х - 2012 г.) 27.56 KB
  В соответствии с законом правительство приняло программу развития белорусского языка и языков других национальностей, проживающих в республике. Программа расширяла сферы применения белорусского языка в государственных структурах, на производстве, в учебных заведениях.
85205. Основные итоги и уроки исторического пути Беларуси 27.38 KB
  Бел. народ получил возможность с оптимизмом смотреть в будущее и самостоятельно писать свою историю. В своем историческом развитии белорусский народ должен надеяться только на собственные силы. Самым большим богатством Беларуси являются люди трудолюбивые мудрые талантливые рассудительные 3.
85206. Предмет и задачи исторической науки. Формационный и цивилизационный подходы к изучению истории. Источники и литература 29.87 KB
  История – наука комплексная интегральная так как изучает всю совокупность явлений общественной жизни на протяжении всей истории общества. Литература: Всемирная Истрия; история отдельных континентов и стран; история отдельных периодов и эпох; история разных общественных периодов; история выдающихся личностей.
85207. Этапы развития первобытного общества. Первобытное общество и начало расселения славян на территории Беларуси 33.43 KB
  В соответствии с исторической периодизацией история первобытного общества прошла следующие стадии становления и развития: 1.) первобытное человеческое стало, или праобщина; 2.) ранняя родовая община; 3.) поздняя родовая община; 4.) разложение первобытного общества и начало образования классов.
85208. Социально-экономическое развитие белорусских земель в раннем средневековье (VI - IX в.) 28.39 KB
  Распад родовой общины образование соседской общины. К трехпольной системе земледелия включающей посев яровых озимых и отдыхающий под паром клин привел к выделению крестьянских семей ведущих самостоятельное хозяйство в рамках соседской общины.
85209. Становление раннефеодальных государственных образований восточных славян. Полоцкое и Туровское княжества. Феодальная раздробленность (IX - первая половина XIII в.) 34.44 KB
  ПОЛОЦКОЕ КНЯЖЕСТВО среднее течение Западной Двины вся современная центральная и северная Беларусь. Во время правления Всеслава Полоцкое княжество достигло наибольшего могущества: за Полоцком закрепилось Нижнее Подвинье был построен Софийский собор основан Минск расширены восточные границы княжества. После смерти Всеслава Полоцкое княжество было разделено между тремя его сыновьями наиболее мощным стало Минское княжество где правил Глеб. ТУРОВСКОЕ КНЯЖЕСТВО юг Беларуси бассейн Припяти Туров 980г.