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

Добавлен: 19.10.2018

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

Скачиваний: 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.

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

until eof(f0)and(kolser=(ser1+ser2+ser3));

close(f0);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 mergerun(var d,a,b,c:filetype;var serd,sera,serb,serc,zerod,zeroa,zerob,zeroc:integer);

{слияние серий из А и В и С в D}

var bufa,bufb,bufc:item;

zapis:boolean;

begin

repeat

eora:=true;eorb:=true;eorc:=true;

serd:=serd+1;sera:=sera-1;serb:=serb-1;serc:=serc-1;

if zeroa<>0 then begin eora:=false;zeroa:=zeroa-1;end;

if zerob<>0 then begin eorb:=false;zerob:=zerob-1;end;

if zeroc<>0 then begin eorc:=false;zeroc:=zeroc-1;end;

if (not eora)and(not eorb)and(not eorc) then zerod:=zerod+1;

while (eora or eorb or eorc) do

begin

bufa.key:=1999;bufb.key:=1999;bufc.key:=1999;

if eora then begin read(a,bufa);seek(a,filepos(a)-1);end;

if eorb then begin read(b,bufb);seek(b,filepos(b)-1);end;

if eorc then begin read(c,bufc);seek(c,filepos(c)-1);end;

if bufa.key<bufb.key then

if bufa.key<bufc.key then

begin

copy(a,d);

if eor then eora:=false;

end

else

begin

copy(c,d);

if eor then eorc:=false;

end

else

if bufb.key<bufc.key then

begin

copy(b,d);

if eor then eorb:=false;

end

else

begin

copy(c,d);

if eor then eorc:=false;

end;

end;

until (sera=0)or(serb=0)or(serc=0);

end;

procedure merge;

begin

reset(f0);reset(f1);reset(f2);reset(f3);

while (ser0+ser1+ser2+ser3)<>1 do

begin

if (ser0=0) then begin rewrite(f0);mergerun(f0,f1,f2,f3,ser0,ser1,ser2,ser3,zero0,zero1,zero2,zero3);reset(f0);end;

if (ser1=0)and((ser0+ser1+ser2+ser3)<>1) then

begin

rewrite(f1);mergerun(f1,f2,f3,f0,ser1,ser2,ser3,ser0,zero1,zero2,zero3,zero0);reset(f1);

end;

if (ser2=0)and((ser0+ser1+ser2+ser3)<>1) then

begin

rewrite(f2);mergerun(f2,f3,f0,f1,ser2,ser3,ser0,ser1,zero2,zero3,zero0,zero1);reset(f2);

end;

if (ser3=0)and((ser0+ser1+ser2+ser3)<>1) then

begin

rewrite(f3);mergerun(f3,f0,f1,f2,ser3,ser0,ser1,ser2,zero3,zero0,zero1,zero2);reset(f3);

end;

end;

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

end;

begin

clrscr;

assign(f0,'c:\tp\file0');

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

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

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

sortrun;

merge;

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 для продолжения !


Файл в котором будут отсортированные данные в зависимости от количества данных будут будет меняться(file0 или file1 или file2 или file3).

Итак, мы рассмотрели основные методы внешней сортировки.


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



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


1.Между алгоритмом и структурой данных существует тесная связь: структура данных оказывает большое влияние на вид программы.


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

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

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

Цель работы:

  1. Ознакомление с возможностями сортировки файлов на внешних носителях в ЭВМ.

  2. Получение навыков работы с внешними файлами.

Постановка задачи:

Подготовить данные об абитуриентах, поступающих в институт. Информацию о каждом абитуриенте оформить в виде записи, содержащей следующие поля:

  1. ФИО.

  2. Год рождения.

  3. Год окончания школы.

  4. Оценки в аттестате.

  5. Признак - нуждается ли в общежитии.

  6. Оценки вступительных экзаменов.

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

Содержание отчёта:

  1. Постановка задачи.

  2. Анкетные данные абитуриентов.

  3. Тексты программ.

  4. Распечатка результатов выполнения программы.

Методические указания.

При подготовке исходных данных необходимо учесть, что выходная информация программы обработки внешнего файла должна составлять не менее одной четверти от входной.


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

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

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

Постановка задачи:

Подготовить данные об абитуриентах, поступающих в институт. Информацию о каждом абитуриенте оформить в виде записи, содержащей следующие поля:

  1. ФИО.

  2. Год рождения.

  3. Год окончания школы.

  4. Оценки в аттестате.

  5. Признак - нуждается ли в общежитии.

  6. Оценки вступительных экзаменов.

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

Методические указания.

При подготовке исходных данных необходимо учесть, что выходная информация программы обработки внешнего файла должна составлять не менее одной четверти от входной.

Анкетные данные на абитуриентов в конце методического пособия.
Текст программы:

program sortirovka;

uses crt;

type data=record

fio:string[30];

godr,godo:integer;

ates:record

mat,fiz,rus:integer;

end;

haus:boolean;

ekz:record

mat,fiz,rus:integer;

end;

end;

filetype=file of data;

var files,a,b,c:filetype;

z,n:integer; {для подсчета числа серий}

eor:boolean; {индикатор конца серии}

keys:char;

buf,stu:data;

procedure copys(var x,y:filetype);

var buf1:data;

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.fio<buf.fio;

end;

end;

procedure copyrun(var x,y:filetype);

{переписать серии из x в y}

begin

repeat

copys(x,y);

until eor;

end;

procedure mergerun;

{слияние серий из А и В в С}

var bufa,bufb:data;

begin

repeat

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

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

if bufa.fio<bufb.fio

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

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

until eor

end;

procedure distribute; {из С в А и В}

begin

reset(c);rewrite(a);rewrite(b);

repeat

copyrun(c,a);

if not eof(c) then copyrun(c,b);

until eof(c);

close(a);close(b);close(c);

end;

procedure merge;

begin

reset(a);reset(b);rewrite(c);

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

begin

mergerun;z:=z+1;

end;

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;

close(a);close(b);close(c);

end;

procedure sort;

begin

repeat

distribute;z:=0;

merge;

until z=1;

erase(b);erase(a);

end;

procedure print;

begin

reset(c);

while not eof(c) do

begin

read(c,stu);

writeln(stu.fio,'--',stu.godr,'--',stu.godo);

end;

writeln('Для продолжения нажмите Enter !');

readln;

end;

begin {main}

assign(c,'c:\data.dat'); {файл с данными}

assign(b,'c:\temp1');

assign(a,'c:\temp2');

clrscr;

writeln('Не отсортированные данные');

print;

writeln('Сортировка данных по фамилии');

writeln('Отсортированные данные');

sort;

print;

end.

Результат выполнения программы:

Неотсортированные данные:

Анисимов Пётр Иванович--1982--1999

Синилов Сергей Иванович—1983--2000

Шарапов Евгений Владимирович--1984--2001

Бажин Никита Андреевич--1983--2000

Созинов Алексей Петрович—1984--2001

Малышев Василий Владимирович--1982--1999

Тихонов Сергей Геннадьевич—1982--1999

Еговцев Иван Артурович--1983--2000

Михайлов Артём Егорович—1983--2000

Ползунова Елена Андреевна—1982--1999

Смирнов Никита Владимирович--1984--2001

Мельникова Лариса Анатольевна--1984--2001

Токарева Надежда Александровна--1983--2000

Маслова Нина Михайловна—1984--2001

Молчановский Ильнар Ирекович--1982--1999

Корягина Нина Плахова--1984—2001

Егорова Пелагея Луповна--1983--2000

Гаспер Валентина Александровна--1982--1999

Теплоухов Юрий Леонидович—1982--1999

Кирьянов Антон Алексеевич—1983--2000

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



Сортировка данных по фамилии

Отсортированные данные

Анисимов Пётр Иванович--1982--1999

Бажин Никита Андреевич--1983--2000

Гаспер Валентина Александровна--1982--1999

Еговцев Иван Артурович--1983--2000

Егорова Пелагея Луповна--1983--2000

Кирьянов Антон Алексеевич--1983--2000

Корягина Нина Плахова--1984--2001

Малышев Василий Владимирович--1982--1999

Маслова Нина Михайловна--1984--2001

Мельникова Лариса Анатольевна--1984--2001

Михайлов Артём Егорович--1983--2000

Молчановский Ильнар Ирекович--1982--1999

Ползунова Елена Андреевна--1982--1999

Синилов Сергей Иванович--1983--2000

Смирнов Никита Владимирович--1984--2001

Созинов Алексей Петрович--1984--2001

Теплоухов Юрий Леонидович--1982--1999

Тихонов Сергей Геннадьевич--1982--1999

Токарева Надежда Александровна--1983--2000

Шарапов Евгений Владимирович--1984--2001

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



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

  1. Сортировать файл с данными по оценкам на вступительных экзаменах и средней оценке в атестате, методом многофазного слияния, распечатать файл с данными до сортировки и после: фамилия имя отчество, год рождения, оценки на вступительных экзаменах и атестате.



  1. Сортировать файл с данными по году окончания школы, методом сбалансированного слияния, распечатать файл с данными до сортировки и после: фамилия имя отчество, год рождения, год окончания школы и надобность в общежитие.


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


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


  1. Сортировать файл с данными по фамилиям, методом многофазного слияния, распечатать файл с данными до сортировки и после: фамилия имя отчество, год рождения, год окончания школы и надобность в общежитие.

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


Все переменные, объявляемые в программе, размещаются в одной непрерывной области оперативной памяти - сегменте данных, длина которого определяется архитектурой микропроцессора.

Динамическая память (ДП) - оперативная память персонального компьютера(ПК), предоставляемая программе при ее работе за вычетом сегмента данных стека и тела программы. Ее размер определяется всей доступной памятью ПК.

ДП - единственная возможность обработки массивов данных большой размерности.

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

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


Turbo Pascal предоставляет гибкое средство управления динамической памятью - так называемые указатели .

Указатель - это переменная, которая в качестве своего значения содержит адрес байта памяти.

В ТР указатель связывается с некоторым типом данных, их называют типизированными. Для объявления типизированного указателя используется значок ^ , который помещается перед типом:


var p1:^integer;

p2:^real;

Также можно объявлять указатель, не связывая его при этом с конкретным типом данных. Для этого существует стандартный тип POINTER:

var pp: pointer;

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

var

pp: pointer;

p1,p2: ^integer;

p3: ^real;

.........

p1:=p2; - связь указателей одного типа данных.

p1:=p3; - запрещено.


pp:=p3; p1:=pp; - с нетипизированными указателями таких ограничений не существует.

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

HEAРORG - начало кучи хранится в этой переменной.

HEAPEND - конец кучи.

HEAPPTR - текущая граница незанятой динамической памяти.


Память под любую динамически размещаемую переменную выделяется процедурой NEW. Параметром обращения к этой процедуре является типизированный указатель. В результате обращения указатель приобретает значение , соответствующее динамическому адресу, начиная с которого можно разместить данные:


var

i: ^integer;

j: ^real;

begin

new(i);

...................

После выполнения этого фрагмента указатель i приобретает значение, которое перед этим имел указатель кучи HEAPPTR, а сам HEAPPTR увеличивает свое значение на 2 , так как внутреннее представление типа integer, с которым связан указатель i, составляет 2 байта.

После того как указатель приобрел некоторое значение, т. е. стал указывать на конкретный физический адрес памяти, по этому адресу можно разместить любое значение соответствующего типа. Для этого сразу за указателем без пробелов ставится значок ^, например:

i^:=2;{в область памяти i помещено значение 2}.

Значением любого указателя является адрес, а чтобы указать что речь идет не об адресе, а о тех данных, которые расположены по этому адресу, за указателем ставится ^.

Чтобы вернуть байты обратно в кучу, используется процедура DISPOSE.

DISPOSE(i) - возвращает в кучу 2 байта, которые ранее были выделены указателем i.

Для работы с нетипизированными указателями используются процедуры:

GETMEM(P,SIZE) - резервирование памяти.

FREEMEM(P,SIZE) - освобождение памяти.

Указательная переменная Р может быть в 3 –х состояних:

1. Содержать адрес какой-либо переменной, память под которую уже выделена.

2. Содержать постоянный пустой адрес nil.

3. Находится в неопределенном состоянии.

В неопределённом состоянии указатель бывает в начале работы программы до первого присвоения ему или конкретного адреса или пустого адреса nil , а также после освобождения области памяти на которую он указывает.

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

Type

TPtr = ^Telem;

Telem = record

Inf: Real;

Link: TPtr

End;

10.2. Списки.

Указатели являются простым механизмом, позволяющим строить данные со сложной и меняющейся структурой. Используя указатели можно создавать и обрабатывать структуры данных, компоненты которых связаны явными ссылками. Самый простой способ связать множество элементов – это расположить их линейно в списке. В этом случае каждый элемент содержит только один указатель на следующий элемент списка.

Пусть тип point описан следующим образом:

Type point = ^ item;

item = record

number: integer;

next: point

end;

Каждая переменная типа point состоит из двух компонентов: индентифицирующего номера и указателя на следующий элемент. Из этих переменных, связав их указателями, можно создать линейный список.