ВУЗ: Пермский национальный исследовательский политехнический университет
Категория: Лекция
Дисциплина: Программирование
Добавлен: 19.10.2018
Просмотров: 5242
Скачиваний: 10
СОДЕРЖАНИЕ
Лабораторная работа №11, вариант № 5.
9.3.1. Слияние упорядоченных последовательностей.
9.3.2. Сортировка сбалансированным слиянием
9.3.3. Сортировка простым слиянием
9.3.4. Сортировка естественным слиянием.
9.3.5. Сортировка многофазным слиянием.
Выполнение операций над списковыми структурами.
Выполнение операций над списковыми структурами.
Работа со стеками и очередями.
Работа со стеками и очередями.
11. Организация меню с использованием средств среды Turbo Pascal
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.
Сортировка файлов.
Цель работы:
-
Ознакомление с возможностями сортировки файлов на внешних носителях в ЭВМ.
-
Получение навыков работы с внешними файлами.
Постановка задачи:
Подготовить данные об абитуриентах, поступающих в институт. Информацию о каждом абитуриенте оформить в виде записи, содержащей следующие поля:
-
ФИО.
-
Год рождения.
-
Год окончания школы.
-
Оценки в аттестате.
-
Признак - нуждается ли в общежитии.
-
Оценки вступительных экзаменов.
Разработать программу сортировки подготовленных данных во внешнем файле, методом заданном в варианте, и распечатать записи в файле.
Содержание отчёта:
-
Постановка задачи.
-
Анкетные данные абитуриентов.
-
Тексты программ.
-
Распечатка результатов выполнения программы.
Методические указания.
При подготовке исходных данных необходимо учесть, что выходная информация программы обработки внешнего файла должна составлять не менее одной четверти от входной.
Образец выполнения задания.
Лабораторная работа №12.
Сортировка файлов.
Постановка задачи:
Подготовить данные об абитуриентах, поступающих в институт. Информацию о каждом абитуриенте оформить в виде записи, содержащей следующие поля:
-
ФИО.
-
Год рождения.
-
Год окончания школы.
-
Оценки в аттестате.
-
Признак - нуждается ли в общежитии.
-
Оценки вступительных экзаменов.
Разработать программу сортировки подготовленных данных во внешнем файле по фамилии, методом сортировки естественным слиянием, и распечатать фамилии и даты рождения и даты окончания школы, до сортировки и после.
Методические указания.
При подготовке исходных данных необходимо учесть, что выходная информация программы обработки внешнего файла должна составлять не менее одной четверти от входной.
Анкетные данные на абитуриентов в конце методического пособия.
Текст программы:
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 ! |
Варианты заданий.
-
Сортировать файл с данными по оценкам на вступительных экзаменах и средней оценке в атестате, методом многофазного слияния, распечатать файл с данными до сортировки и после: фамилия имя отчество, год рождения, оценки на вступительных экзаменах и атестате.
-
Сортировать файл с данными по году окончания школы, методом сбалансированного слияния, распечатать файл с данными до сортировки и после: фамилия имя отчество, год рождения, год окончания школы и надобность в общежитие.
-
Сортировать файл с данными по году рождения, методом простого слияния, распечатать файл с данными до сортировки и после: фамилия имя отчество, год рождения и оценки в атестате.
-
Сортировать файл с данными по оценкам на вступительных экзаменах, методом естественного слияния, распечатать файл с данными до сортировки и после: фамилия имя отчество, оценки на вступительных экзаменах и надобность в общежитие.
-
Сортировать файл с данными по фамилиям, методом многофазного слияния, распечатать файл с данными до сортировки и после: фамилия имя отчество, год рождения, год окончания школы и надобность в общежитие.
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 состоит из двух компонентов: индентифицирующего номера и указателя на следующий элемент. Из этих переменных, связав их указателями, можно создать линейный список.