Файл: 2. Лекции Паскаль (Часть 2).doc

Добавлен: 19.10.2018

Просмотров: 4362

Скачиваний: 8

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

Оглавление

9. Файловые типы данных

9.1. Инициализация файла

9.2. Файлы и работа с ними

Лабораторная работа №11.

Работа с внешними файлами

Лабораторная работа №11, вариант № 5.

Работа с внешними файлами

Варианты заданий.

9.3. Сортировка файлов.

9.3.1. Слияние упорядоченных последовательностей.

9.3.2. Сортировка сбалансированным слиянием

9.3.3. Сортировка простым слиянием

9.3.4. Сортировка естественным слиянием.

9.3.5. Сортировка многофазным слиянием.

Лабораторная работа №12.

Сортировка файлов.

Лабораторная работа №12.

Сортировка файлов.

10. Динамическая память.

10.1. Указатели.

10.2. Списки.

Лабораторная работа № 13.

Исключение элементов списка.

Образец выполнения работы.

Лабораторная работа № 13.

Исключение элементов списка.

Варианты задания.

Лабораторная работа № 14.

Работа со списками.

Образец выполнения работы.

Лабораторная работа № 14.

Работа со списками.

Варианты задания.

Лабораторная работа № 15.

Выполнение операций над списковыми структурами.

Образец выполнения работы.

Лабораторная работа № 15.

Выполнение операций над списковыми структурами.

Варианты заданий.

10.3. Деревья.

10.4. Стеки, очереди.

Образец выполнения работы.

Лабораторная работа № 16.

Работа со стеками и очередями.

Лабораторная работа № 16.

Работа со стеками и очередями.

11. Организация меню с использованием средств среды Turbo Pascal

Лабораторная работа №17.

Составления меню.

Образец выполнения работы.

Лабораторная работа № 17.

Составления меню.

4) список абитуриентов, имеющих средний балл меньше 4 (N=1).

5) список абитуриентов, нуждающихся в общежитии (N=3).

6) список абитуриентов, сдавших вступительные экзамены только на оценки 5 (N=4).

7) список абитуриентов, сдавших вступительные экзамены на оценки 4 и 5 (N=2).

8) список абитуриентов, сдавших экзамены с 2-мя оценками 4 и остальными оценками 5 (N=3).

9) список абитуриентов, имеющих средний балл в аттестате 4,5(N=3).

10) список абитуриентов, имеющих в аттестате две оценки 4, а остальные 5(N=2).

11) список абитуриентов, имеющих средний балл меньше 4(N=3).

12) список абитуриентов, у которых все экзамены сданы на 4 (N=4).

13) список абитуриентов, у которых одна оценка 4, а остальные 5(N=3).

14) список абитуриентов, у которых одна оценка 5, а остальные 4(N=5).

15) список абитуриентов, у которых одна оценка 3 в аттестате. (N=3).

16) список абитуриентов, имеющих больше двух оценок 3 в аттестате. (N=2).

17) список абитуриентов, имеющих две оценки 3 в аттестате(N=4).

18) список абитуриентов, имеющих средний балл в аттестате ниже 4,5 (N=3).

19) список абитуриентов, у которых две оценки 3 за экзамены и отличный аттестат (N=2).

20) список абитуриентов, у которых нет ни одной оценки 5 в аттестате (N=4).

21) список абитуриентов, у которых отличный аттестат и средний балл за экзамены меньше 4(N=3).

22) список абитуриентов, имеющих средний балл больше 4 и оценки 3 в аттестате (N=4).

23) абитуриентов возраст которых больше 18 лет и все оценки 5 за экзамены(N=2).

24) абитуриентов, у которых средний балл больше 4,5 и одна оценка 3 в аттестате(N=3).


9.3. Сортировка файлов.

9.3.1. Слияние упорядоченных последовательностей.

К последовательному файлу нельзя непосредственно применить метод внутренней сортировки (сортировки массивов). Это объясняется тем, что в последовательном файле в каждый момент имеется доступ только к одному элементу. Это строгое ограничение, по сравнению с возможностями, которые даёт массив, поэтому для файлов приходится применять другие методы сортировки.

Разумеется, в этом случае, когда размер файла не велик и объём оперативной памяти достаточен для его размещения, можно прочитать файл в память, отсортировать полученный массив одним из методов внутренней сортировки, а затем отсортированный массив записать в файл. Однако, это не является типичным случаем; более того, в системах обработки данных такая ситуация встречается крайне редко.

Далее мы рассмотрим общий случай, когда сортируемый файл имеет объём значительно больше, чем объём доступный оперативной памяти. Такой файл сортируется поэтапно.

Все методы внешней сортировки сначала применяют внутреннюю сортировку, а затем используют стратегию слияния. Общая идея состоит в том, чтобы прочесть в оперативную память как можно больше записей, отсортировать их одним из методов внутренней сортировки, записать их во внешнюю память как уже отсортированный блок и повторять этот процесс до тех пор, пока весь файл не превратится в последовательность отсортированных блоков. Затем производится слияние в более крупные блоки до тех пор, пока не останется один блок, на этом сортировка файла завершится.


Итак, основным методом внешней сортировки является слияние упорядоченных последовательностей. Рассмотрим слияние более подробно.

Пусть даны две упорядоченные последовательности (файл) А и В со следующими значениями числовых ключей:


А: 06 12 18 42 44 56

В: 07 14 15 17 19


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


А: 12 18 42 44 55

В: 07 14 15 17 19

С: 06


Повторяем данную операцию:


А: 12 18 42 44 55

В: 14 15 17 19

С: 06 07


Эта операция повторяется до тех пор, пока один из исходных файлов не закончится:

А: 42 44 55

В: пустой

С: 06 07 12 14 15 17 18 19


После этого оставшиеся элементы непустого файла переписываются в файл С, который будет иметь окончательный вид:


С: 06 07 12 14 15 17 18 19 42 44 55


Таким образом, мы получили отсортированный файл С. рассмотренная схема называется двухпутевым слиянием. Обобщая эту схему, можно получить р-путевое слияние для упорядоченных последовательностей, размещённых в Р-файлах.


Алгоритм Р-путевого слияния

  1. Установить г:=Р.

  2. Если г>1, то перейти к следующему пункту, иначе к пункту 5.

  3. Прочитать начальные элементы оставшихся г непустых последовательностей, записать минимальный элемент в выходной файл, а на его место прочитать следующий элемент из соответствующего файла.

  4. Если последовательность, из которой читался элемент, станет пустой, запомнить этот и уменьшить г на 1. Перейти к пункту 2.

  5. Переписать оставшиеся элементы непустой последовательности в выходной файл.

Закончить выполнения алгоритма.

Нетрудно видеть, что использование для сортировки файла Р-путевого слияния требует предварительно разделения исходного файла на Р частей, сортировки каждого из частей в оперативной памяти и размещение их во внешней памяти в виде Р файлов. Если размещать каждый файл на отдельном устройстве (ленте), то потребуется Р лент. Поэтому приходится на одной ленте (в одном файле) размещать несколько отсортированных в оперативной памяти блоков. Такие блоки, записи в которых упорядочены, будем называть сериями.

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


А: 44 55 18 15 17 07

В: 12 42 94 06 67 14 15 19


Используя алгоритм 2х-путевого слияния, выполним слияние первой серии файла А и первой серии файла В. получим следующее значение файла С:


С: 12 42 44 55 94


Далее выполним слияние вторых серий файлов А и В, запишем полученную последовательность в файл С.


С: 12 42 44 55 94 06 18 67


Аналогично работаем с третьими сериями, итак до тех пор, пока один из файлов не окажется пустым (в нашем примере файл В). Оставшуюся серию непустого файла (четвёртую серию файла А) переписываем в выходной файл С. В результате получим файл:



С: 12 42 44 55 94 06 18 67 14 15 15 17 19 07


Мы получили выходной файл, состоящий из упорядоченных последовательностей (серий).


Алгоритм слияния серий двух файлов


  1. Прочитать начальные элементы каждого файла. Если один из файлов пустой, перейти к пункту 5.


  1. Сравнить два элемента и записать минимальный в выходной файл, а на его место прочитать следующий элемент.



  1. Если конец серии не достигнут, перейти к пункту 2.


  1. Если достигнут конец серии, переписать элементы другого файла до окончания серии и перейти к пункту 1.



  1. Если в другом файле имеются серии (хотя бы одна) переписать элементы этих серий в выходной файл. Закончить выполнения алгоритма.


В отличие от предыдущего алгоритма в рассмотренном необходимо обнаружить конец серии.

Это можно сделать одним из следующих способов:


Ключ прочитанной записи сравнивается с ключом следующей записи. Если значение ключа следующей записи меньше, то серия закончена.

В качестве метки, указывающей на конец серии, вставляют специальную запись с определённым значением ключа. Это значение не должно входить в диапазон значений ключей записи файла. Как только будет прочитано это значение, конец серии достигнут.

Серии в файлах делают фиксированной длины.


Вернёмся к последнему примеру. В результате слияний серий мы получили файл С, состоящий из нескольких серий. Однако, в целом файл ещё не отсортирован.


Как продолжить его сортировку? Необходимо разделить этот файл на два файла, переписывая в них поочерёдно серии. В результате такого разделения мы получим новые файлы А и В, состоящие из серий в среднем в два раза большей длины, чем исходные. Затем вновь выполняем слияние и разделение и так до тех пор, пока не получим выходной файл С, состоящий из одной серии. Естественно, такой файл будет отсортирован.


Алгоритм внешней сортировки


  1. Используя оперативную память, сформировать как можно более длинные серии из элементов заданного файла. Распределить эти серии на несколько файлов.


  1. Сформировать более длинные серии путём слияния серий нескольких файлов. Вновь распределить эти серии на несколько файлов. Повторять эту операцию.


  1. Если в конце образуется одна серия, закончить сортировку.


9.3.2. Сортировка сбалансированным слиянием


Сортировка сбалансированным слиянием является наиболее простым методом сортировки, предполагающим многократное распределение и слияние серий.


Для того, чтобы представить себе как выполняется сортировка, рассмотрим следующий пример.


Пусть исходный файл содержит 1700 записей. Допустим, что в оперативной памяти можно разместить не более 100 записей. Предположим также, что мы можем использовать для сортировки 4 файла, которые мы обозначим f1 f2 f3 f4. Исходным является файл f1. Будем использовать 2-путевое слияние. Начинаем сортировку. Считываем 100 записей, сортируем их одним из методов внутренней сортировки и записываем в файл f2. Затем считываем следующие 100 записей, сортируем и записываем в файл f3, следующие 100 сортированных записей снова записываем в файл f2 и т.д. В результате мы получим 9 серий по 100 записей в файле f3.


Далее серии файлов f2 и f3 сливаем и вновь в процессе слияния попеременно записываем, формируя новые серии, на файле f1 и f4. В итоге в файле f1 мы будем иметь 4 серии по 200 записей и 1 серию из 100 записей, а в файле f4 – 4 серии по 200 записей.

Аналогичный цикл слияний серий с f1 и f4 и записи на f2 и f3 приведёт к 2 сериям по 400 записей и 1 серии из 100 записей в f2 и к 2 сериям по 400 записей в f3.

После ещё трёх циклов в f1 окажется полностью отсортированный файл.

Процесс сортировки изображён на рисунке:

F1

Внутренняя сортировка, распределение



1 (1700)

F2

F3



8(100) 9(100)

Слияние:1

Распределение:1




F4

F1



4 (200) 4(200) 1(100)

Слияние:2

Распределение:2





F2

F3



2(400) 1(100) 2(400)

Слияние:3

Распределение:3





F4

F1




Слияние:4

Распределение:4


1(800) 1(800)1(100)



F2

F3


1(1600) 1(100)

1(1700)

F1

Слияние:5

Распределение:5






Программа: Сортировка сбалансированным слиянием.

Программа использует уже готовый файл содержащий не отсортированные данные и не распечатывает отсортированный файл (программа только сортирует файл file1).


program balans;

const n=10;{количество записей в сериях при внутренней(начальной) сортировке и распределении}

type item=record

key:integer;

{описание других полей}

end;

filetype=file of item;

var f1,f2,f3,f4:filetype;

z,l,all:integer;

eor,per:boolean;

mas:array[1..n]of integer;

data:item;

{z-для подсчёта числа серий}

{eor-индикатор конца серии}

procedure readfile;{процедура считывает 100 записей в массив mas}

begin

l:=0;

while not eof(f1)and not(l=n) do

begin l:=l+1;read(f1,data);mas[l]:=data.key;end;

all:=l;

end;

procedure massort;{процедура сортировки массива mas}

var buf,units:integer;

m:boolean;

begin

units:=all;

repeat

m:=true;;

units:=units-1;

for l:=1 to units do

begin

if mas[l]>mas[l+1]

then begin buf:=mas[l];mas[l]:=mas[l+1];mas[l+1]:=buf;m:=false;end;

end;

until m or (units=1);

end;

procedure sort(var x:filetype);{процедура считывает, сортирует а затем записывает на ленту серии по 100 записей}

begin

readfile;massort;

for l:=1 to all do begin data.key:=mas[l];write(x,data);end;

end;

procedure sortrun;{прцедура первоночальной (внутренней) сортировки и распределении}

begin

reset(f1);rewrite(f2);rewrite(f3);

while not eof(f1) do

{распределяем сначала на ленту f2 а затем на ленту f3 и т.д.}

begin sort(f2);if not eof(f1) then sort(f3);end;

close(f1);close(f2);close(f3);

end;

procedure copy(var x,y:filetype);{процедура копирования записи и определения конца серии}

var buf,buf1:item;

begin

read(x,buf);write(y,buf);

if eof(x) then eor:=true

else begin

{заглядываем вперёд}

read(x,buf1);

{возвращаемся на исходную запись}

seek(x,filepos(x)-1);

eor:=buf1.key<buf.key

end;

end;

procedure copyrun(var x,y:filetype);{процедура копирования серий}

{переписать серии из X в Y}

begin

repeat

copy(x,y);

until eor;

end;

procedure merge(var a,b,c:filetype);{процедура слияния серии}

var bufa,bufb:item;

begin

repeat

read(a,bufa);seek(a,filepos(a)-1);

read(b,bufb);seek(b,filepos(b)-1);

if bufa.key<bufb.key

then begin;copy(a,c);if eor then copyrun(b,c);end

else begin;copy(b,c);if eor then copyrun(a,c);end;

until eor

end;

procedure ende(var a,b,c:filetype);

begin

while not eof(a) do begin;copyrun(a,c);z:=z+1;end;

while not eof(b) do begin;copyrun(b,c);z:=z+1;end;

end;

procedure mer(var a,b,d,e:filetype);{процедура сливает серии из a и b и распределяет между d и e}


var con:boolean;

begin

con:=false;

reset(a);reset(b);rewrite(d);rewrite(e);

while (not eof(a))and(not eof(b)) do

begin

merge(a,b,d);z:=z+1;con:=true;

if (not eof(a))and(not eof(b)) then begin merge(a,b,e);z:=z+1;con:=false;end;

end;

if con then ende(a,b,e);

ende(a,b,d);

close(a);close(b);close(d);close(e);

end;

begin

assign(f1,'c:\tp\file1');

assign(f2,'c:\tp\file2');

assign(f3,'c:\tp\file3');

assign(f4,'c:\tp\file4');

sortrun;

per:=false;

repeat

z:=0;

if per then begin mer(f1,f4,f2,f3);per:=false;end

else begin mer(f2,f3,f1,f4);per:=true;end;

until z=1;

end.

Результат работы:

0 3 86 20 27 67 32 16 37 43 8 47 7 84 6 29 92 37 77 33 70

84 72 31 16 33 47 25 83 28 48 15 87 29 77 98 49 89 83 2 14 1

4 50 2 59 1 77 65 77 71 56 21 68 59 96 64 100 24 68 30 9 77

50 88 51 57 95 68 34 1 71 99 77 75 20 14 91 78 59 86 69 29

9 63 28 88 16 27 54 96 17 16 27 18 58 50 29 16 61 74

Нажмите Enter для продолжения !


0 1 1 2 2 3 6 7 8 9 9 14 14 14 15 16 16 16 16 16 17 18 20

20 21 24 25 27 27 27 28 28 29 29 29 29 30 31 32 33 33 34 37

37 43 47 47 48 49 50 50 50 51 54 56 57 58 59 59 59 61 63 64

65 67 68 68 68 69 70 71 71 72 74 75 77 77 77 77 77 77 78 83

83 84 84 86 86 87 88 88 89 91 92 95 96 96 98 99 100

Нажмите Enter для продолжения !


Рассмотренный пример позволяет нам сделать ряд выводов. Процесс сортировки можно разделить на два существенно различных этапа. На первом этапе выполняется внутренняя сортировка записей и формирование из них серий возможно большего размера. Эти серии распределяются по двум или нескольким лентам, причём точный способ распределения зависит от конкретного метода последующего слияния.


На втором этапе выполняется несколько циклов слияния этих серий во всё большие и большие серии, пока все записи не окажутся в одной серии.


Возможно ли при сортировке обойтись только тремя магнитными лентами?


Да, возможно. Для этого начальные серии распределяем на файлы Т2 и Т3 сливаем в файл Т1. Затем полученные серии снова распределяем по файлам Т2 и Т3, до тех пор, пока не получим в файле Т1 одну серию.


Недостатком такого метода является излишнее копирование, что увеличивает время сортировки.


Анализируя рассмотренный алгоритм сортировки, мы можем выделить в нём повторяющиеся операции, которые однократно обрабатывают все записи. Такие операции называются фазой, а наименьший процесс, который, повторяясь, образует процесс сортировки, называют проходом. В приведённом примере сортировка производится за пять проходов, каждый проход состоит из фазы распределения и фазы слияния.


Сколько требуется файлов для сбалансированного Р-путевого слияния?


В общем случае требуется 2Р файлов. Однако, если после распределения серий сливать их в один файл, то количество требуемых файлов сократится почти в два раза и будет равно Р+1, но за это приходится расплачиваться увеличением времени сортировки вдвое, за счёт дополнительного копирования, о чём уже говорилось.


9.3.3. Сортировка простым слиянием


Рассмотрим простой метод, когда не обращая внимания на содержимое заданного исходного файла, его рассматривают как состоящий из серий длиной 1. Разделяя этот файл на два и производя их слияние, получают упорядоченные пары, т.е. серии длиной 2. На следующих шагах упорядоченные пары сливаются в упорядоченные четвёрки, четвёрки сливаются в восьмёрки и т.д. Весь процесс повторяется до тех пор, пока не будет упорядочен весь файл. Таким образом на каждом проходе длина серии удваивается, причём если длина исходного файла Н не является степенью 2, то последняя серия будет иметь число элементов равное Н-2^к. В данном случае не требуется выполнения первого этапа сортировки, т.е. внутренней сортировки для формирования начальных серий. Такой метод называется простым слиянием.