Подпрограммы
Необходимость оформления части программы в подпрограмму может быть вызвана:
Необходимостью применения этого куска программы несколько раз.
Разработкой программы несколькими исполнителями.
Структура любой подпрограммы:
<заголовок>
<деклар.часть>
<тело подпрогр.>
Декларативная часть: описание модулей, констант и переменных, используемых в программе, а также описания ее подпрограмм.
|
Заголовок | |
|
Procedure<имя> (<список форм и параметров>) |
Function<имя>(<…>):тип возвращаемого результата |
Переменные:
Областью действия(сферой видимости) идентификатора наз. часть программы, в которой он может быть использован;ОД идентификатора определяется местом его обьявления. Если идентификатор допускается к использованию только в одной подпрограмме, то он наз. локальным, Иначе – глобальным.
Пример:
Program p1;
Var
A0,B0,C0:integer;
Procedure p2;
Var
A1,B1,C1:integer;
Procedure p3;
Var
A2,B2,C2:integer;
Begin…End;{p3}
Begin…End;{p2}
Begin…End;{p1}
{для p1глобальны A0,B0,C0 и A1,B1,C1, а локальны A2,B2,C2}
Правила, по которым опр. ОД идентиф. для подпрограмм.
действуют все идентиф., опр. внутри процедуры/функции.
действуют все идентиф. окружающего текста, если их имена отличны от имен, объявленных внутри процедуры/функции.
лок. идентиф. процедуры/функции во внешнем окружении не действуют.
в случае совпадения имен глоб.и лок. идентификаторов, действовать будет лишь внутренний лок. идентиф..
Передача параметров
C помощью механизма формальных и фактических параметров.
C помощью глоб.и лок. параметров.
Список формальных параметров:
Используется в описании функции или процедуры.
Фактический параметр:
Вызывает процедуру или ф-цию в основной программе.
При передаче параметров необходимо обеспечить выполнение некотрых условий:
Число формальных и фактических параметров должно совпадать.
Порядок перечисления формальных и фактических параметров должен совпадать.
ОД формальных параметров такая же как и у лок. параметров.
Формальный и фактический параметр должны совпадать по типу.
По способу передачи
по ссылке
по способу взаимодействия вызываемый вызывающий
входной
Входной+ выходной
выходной
по механизму передачи
по значению
Если входной параметр скалярный, то он может быть передан как по значению, так и по ссылке. Иначе- только по ссылке.
Procedure s(a,b:integer) –по значению.
(var a,b:integer)-по ссылке.
Когда по значению, программа работает с дубликатом(т.е. когда нужно возвращать, то var)
По значению-и константы, и переменные.
По ссылке-только переменные.
Program p1;
Var
i:integer;
Procedure p;
Begin
Writeln(i);
End;
BEGIN
i:=1;
P;
Writeln(i);
END.
Program p2;
Var
i:integer;
Procedure p3(i:integer);
Begin
inc(i);
Writeln(i);
End;
BEGIN
i:=1;
P3(i);
Writeln(i);
END.
Сортировки
Индексная.
Procedure sort_index(var f4:mas);
Var
i,j,k,t:integer;
m:array[1..n] of integer;
BEGIN
For i:=1 to n do
m[i]:=i;
For i:=n downto 2 do
For j:=1 to (i-1) do
If f4(m[j])>f4(m[j+1]) then
Begin
t:=m[j];
m[j]:=m[j+1];
m[j+1]:=t;
End;
For i:=1 to n do
Begin
j:=m[i];
Write(f4[j],’ ‘);
End;
END.
Выбор.
Procedure sort_choise(var f5:mas);
Var
i,j,max,imax:integer;
BEGIN
For i:=n downto 2 do
Begin
imax:=f5[1];
imax:=1;
For j:=2 to i do
If max<f5[i] then
Begin
max:=f5[i];
imax:=i;
End;
f5[imax]:=f5[i];
f5[i]:=max;
End;
END.
Пузырек.
Procedure sort_buble(var f3:mas);
Var
i,j,x:integer;
BEGIN
For i:=n downto 2 do
For j:=1 to (i-1) do
If f3[j]>f3[j+1] then
Begin
x:=f3[j];
f3[j]:=f3[j+1];
f3[j+1]:=x;
End;
END.
Вставка.
Program SORTIROVKA;
Uses
Crt;
Const
n=10;
Type
mas:array [1..n] of integer;
Var
a:mas;
Procedure VVOD;(var b:mas);
Var
i:integer;
Begin
Randomize;
For i:=1 to n do
b[i]:=random(50)-25;
End;
Procedure VIVOD(var b:mas);
Var
i:=integer;
Begin
For i:=1 to n do
Write(b[i],’ ‘);
End;
Procedure SORT_INSERT(var d:integer);
Var
i,j,x:integer;
Begin
For i:=2 to n do
Begin
x:=d[i];
j:=i-1;
while (x<d[j]) and (j>=1) do
Begin
d[j+1]:=D[j];
j:=j+1;
End;
End;
End.
ФАЙЛЫ
… байт байт eof байт
f
Целое со знаком … Целое со знаком eof
|
Массив |
Файл |
|
Фиксированное кол-во эл-тов |
Кол-во эл-тов может изменяться в процессе работы программы |
|
Целиком размещен в ОЗУ |
Расположен на внешнем носителе |
|
Нумерация эл-тов выполняется согласно верхней и нижней граням индекса, указанных при объявлении. |
Нумерация эл-тов начинается с нуля (текст- с единицы) |
|
|
Неизвестно кол-во эл-тов файла в данный момент |
|
|
В конце-спецсимвол конца-EOF(end of file) |
Классификацияфайлов в Pascal:
1) По типу
а) Типизированные
б)Нетпизированные
с) Текстовые
2) По методу доступа
а) Последовательного (любого типа)
б) Прямого (только типизированные и нетпизированные)
Объявление файла:
При необходимости работы с файлами –объявить логический тип; вводится файловая переменная , с помощью которой осуществляется связь между процедурами программы и файлами
var <файловая переменная>:<тип файла>;
Begin
Assign(<файловая переменная >,< имя файла >);
Пример
Assign(f,’data.txt’);assign(f,’a:\data.txt’);
Описание типа
Если файл типизированный, то f:file of integer;
Если файл типизированный, то f:FILE;
Если файл текстовой, то f:TXT;
Также необходимо указать, в каком направлении открыть и закрыть файл. Для указания направления надо открыть в этом направлении и, соответственно, закрыть.
Операции открытия файла:
на запись REWRITE(f);
на чтение RESET(f);
Операция закрытия файла:
CLOSE(f);
Операции записи и чтения из файла файла:
Запись WRITE(f,<список ввода>);
Чтение READ(f,< список вывода >);
При открытии файла-стоим на нулевом элементе. При каждом обращении образ сдвигается на следующий элемент.
Задача: создать файл типа Integer; найти сумму его эл-тов.
Program SUM_FILE;
Uses
Crt;
Type
fl:file of integer;
Var
f:fl;
i,j,l,z:integer;
name:string;
Procedure OUT(var f1:fl);
Begin
reset(f1);
while not EOF(f1) do
Begin
read(f1,j);
write(j,’ ‘);
End;
Close(f1);
End;{OUT}
Procedure INP(var f1:fl;l1:integer);
Begin
For i:=1 to l1 do
Begin
readln(j);
write(f,j);{j-буферная переменная}
End;
End;{INP}
Procedure WORK(var f1:fl);
{считает сумму эл-тов и записывает в конец f1}
Var
Sum:integer;
Begin
sum:=0;
reset(f1);
while not EOF(f1) do
Begin
read(f1,j);
sum:=sum+j;
End;
write(f1,sum);
close(f1);
End;{WORK}
BEGIN
ClrScr;
writeln(‘введите имя файла’);
readln(name);
assign(f,’name’);
writeln(‘введите число компонентов файла’);
readln(l);
rewrite(f);
INP(f,l);
writeln;
OUT(f);
writeln;
WORK(f);
OUT(f);
END.
Seek(<файловая переменная >,<номер эл-та>)-перемещает указатель текущей позиции в файле на эл-т с заданным номером(счет от нуля).
FilePos(<файловая переменная >)-возвращает номер текущей позиции в файле(счет от нуля).
FileSize(<файловая переменная >)- возвращает текущий размер файла(счет от единицы).
Truncate(<файловая переменная >)-удаляет все элементы после текущей позиции.
Текстовые файлы
Т.Ф.-совокупность строк ; каждая строка имеет признак конца(EoLn)
|
|
EoLn |
| |||||
|
|
EoLn |
| |||||
|
|
EoLn |
| |||||
|
|
EoLn | ||||||
Задача создать текстовый файл, в начале которого находится запись кол-ва эл-тов файла.
Program filetext1;
Var
a:array[1..50]of integer;
i,na;integer;
f:text;
name:string;
BEGIN
Writeln(‘введите размер массива’);
Readln(na);
Randomize;
For i:=1 to na do
a[i]:=Random(25);
Writeln(‘введите имя файла’);
Readln(name);
Assign(f,name);
Rewrite(f);
write(f,na);
Writeln(f,i);
for i:=1to na do
Begin
If (imod3)<>0 then
Begin
Write(f,a[i]);
Write(f,’ ‘);
End;
Else
Begin
Write(f,a[i]);
Writeln(f,’ ‘);
End;
End;
END.
Нетипизированные файлы по структуре совпадают с физическими.
{
Работа с файлами
Тип-файл представляет собой последовательность компонент одного типа, расположенных на внешнем устройстве (например, на диске). Элементы могут быть любого типа, за исключением самого типа-файла. Число элементов в файле при описании не объявляется. Работа с физическими файлами происходит через так называемые файловые переменные.
Для задания типа-файла следует использовать зарезервированные слова FileиOf, после чего указать тип компонент файла.
Пример: Type
N = File Of Integer; {Тип-файл целых чисел} C = File Of Char; {Тип-файл символов}
Есть заранее определенный в Паскале тип файла с именем Text. Файлы этого типа называют текстовыми.
Введя файловый тип, можно определить и переменные файлового типа: Var
F1 : N; F2 : C; F3 : Text;
Тип-файл можно описать и непосредственно при введении файловых переменных: VarZ : File Of Word;
Файловые переменные имеют специфическое применение. Над ними нельзя выполнять никаких операций (присваивать значение, сравнивать и т.д.). Их можно использовать лишь для выполнения операций с файлами (чтение, запись и т.д.).
Элементы файла считаются расположенными последовательно, то есть так же, как элементы линейного массива. Отличие же состоит в том, что, во-первых, размеры файла могут меняться, во-вторых, способ обращения к элементам совсем другой: невозможно обратиться к произвольному элементу файла; элементы его просматриваются только подряд от начала к концу, при этом в каждый момент времени доступен только один элемент. Можно представить себе, что для каждого файла существует указатель, показывающий в данный момент на определенный компонент файла. После проведения операции чтения или записи указатель автоматически передвигается на следующий компонент.
Перед тем, как осуществлять ввод-вывод, файловая переменная должна быть связана с конкретным внешним файлом при помощи процедуры Assign.
Формат: Assign(<Имя файловой переменной>,<Имя файла>);
Имя файла задается либо строковой константой, либо через переменную типа Sting. Имя файла должно соответствовать правилам работающей в данный момент операционной системы. Если строка имени пустая, то связь файловой переменной осуществляется со стандартным устройством ввода-вывода (как правило - с консолью).
После этого файл должен быть открыт одной из процедур: Reset(<Имя файловой переменной>); Открывается существующий файл для чтения, указатель текущей компоненты файла настраивается на начало файла. Если физического файла, соответствующего файловой переменной не существует, то возникает ситуация ошибки ввода-вывода.
Rewrite(<Имя файловой переменной>); Открывается новый пустой файл для записи, ему присваивается имя, заданное процедуройAssign. Если файл с таким именем уже существует, то он уничтожается.
После работы с файлом он, как правило, должен быть закрыт процедурой Close.Close(<Имя файловой переменной>);
Это требование обязательно должно соблюдаться для файла, в который производилась запись.
Теперь рассмотрим непосредственную организацию чтения и записи.
Для ввода информации из файла, открытого для чтения, используется уже знакомый вам оператор Read. Правда, в его формате и использовании вы заметите некоторые изменения: Read(<Имя файловой переменной>, <Список ввода>); Происходит считывание данных из файла в переменные, имена которых указаны в списке ввода. Переменные должны быть того же типа, что и компоненты файла.
Вывод информации производит, как можно догадаться оператор Write(<Имя файловой переменной>, <Список вывода>);
Данные из списка вывода заносятся в файл, открытый для записи. Для текстовых файлов используются также операторы ReadlnиWritelnс соответствующими дополнениями, относящимися к файловому вводу-выводу. Любопытно, что вывод данных на монитор и ввод с клавиатуры в языке Паскаль тоже являются действиями с файлами. Они даже имеют свои предопределенные файловые переменные текстового типа: Output и Input соответственно. Переменная Output всегда открыта для записи, Input - для чтения. Если не указывать файловые переменные в операторах ввода-вывода (придем к формату, рассмотренному в теме "Операторы ввода-вывода"), то в случае записи по умолчанию выбирается файлOutput, в случае чтения -Input. Как вы знаете, любой файл конечен и продолжать чтение из него информации можно лишь до определенного предела. Как этот предел установить? Проверить, окончен ли файл, можно вызовом стандартной логической функцииEof(<Имя файловой переменной>) Она вырабатывает значениеTrue, если файл окончен, иFalse- в противном случае.
Решим следующую задачу: "Написать программу, которая вводит с клавиатуры список фамилий учащихся, а затем распечатывает его, кроме тех учащихся, у которых фамилия начинается с буквы 'Ш'".
Так как заранее количество данных не известно, то для их хранения используем файл. Тип элементов - строковый.
Program L; Var
I,N : Integer; F : File Of String; S : String;
Begin
Assign(F,'Spis.lst'); {Связываем переменную F с файлом Spis.lst} Writeln('Введите количество учащихся'); Readln(N); {Вводим количество учащихся} Rewrite(F); {Создаем файл для записи в него данных} For I:=1 To N Do {Для всех учащихся} Begin
Writeln('Введите фамилию'); Readln(S); Write(F,S)
End; Close(F); Reset(F); Writeln; Writeln('Список учащихся:'); While Not(Eof(F)) Do Begin
Read(F,S); If S[1]<>'Ш' Then Writeln(S)
End; Close(F)
End.
}
Методы разработки алгоритма
Пытаемся найти заввисимость задачи от некотрого параметра и решить для меньших значений параметров; затем применяем рекурсию.
1 опред:
1n: 0,1натуральные числа;
2n:n-натуральное, n+1-натуральное.
2 опред:
бинарным деревом называется
вершина дерева
если Т1-дерево, то вершина, реброТ1-тоже дерево.
Если Т1,Т2 деревья, то их образ явл.бин.деревом.
Задача быстрая сортировка.
Метод:
в массиве выбрать произвольный элемент.
Все остальные эл-ты делятся на две части.
Дальше эта процедура происходит с частью массива.
Var
a:array of integer;
Procedure S;
Procedure SORT(l,r:integer);
Var
i,j,temp,x:integer;
Begini:=l;
j:=r;
x:=a[(f+r)div2];
Repeat
While a[i]<x do
i:=i+1;
While a[j]>x do
j:=j+1;
If i<j then
Begin
temp:=a[j];
i:=i+1;
j:=j+1;
End;
Until i>1;
If l<j then SORT(l,j);
If j<r then SORT(j,r);
End;
BEGIN
SORT(t,n);
End;
END.
Сортировка «сорт-дерева»(пирамидальная)
Метод: 2я идея- представление массива в виде:
1
1 A[i] A[2i] A[2i+1]
2 3 4 5 6 7
3 4 5 2 6 7
Сортировка «сорт-дерева»(пирамидальная) основана на 2-х фактах:
Сортировка.
Представление массива в виде бинарного дерева.
Пирамида: бинарное дерево обладает следующими свойствами:
если i-й вершине дерева приписан некий эл-т, то эл-ты массива, приписанные левому и правому «сыну» должны быть меньше «отца».
Все концевые вершины должны быть расположены на высоте n и n-1, где n- высота дерева.
Все концевые вершины должны быть максимально сдвинуты влево.
Метод преобразования пирамиды будет состоять в следующем:
поменять последний эл-т с max.
Исключить max эл-т.
Восстановить пирамиду.
Процесс восстановления пирамиды, если нарушение состоит в одной точке, а именно в корне будет состоять в следующем:рассмотрим всех сыновей, и если он больше отца, поменяем их местами.
Алгоритм восстановления пирамиды.
{процедура сортировки}
Procedure heapsoft;
Var
left, right,x:integer;
Procedure SIFT;
Var
i,j:integer;
Begin
i:=left;
j:=2*i;
x:=mas[i];
While j<right do
Begin
If x<right then
If mas[j]<mas[j+1] then
j:=j+1;
If x<mas[j] then
Begin
mas[i]:=mas[j];
mas[j]:=x;
i:=j;
j:=1*i;
End;
Else j:=right+1;
End;
End;
Процедура, которая восстанавливает пирамиду:
из массива построить пирамиду
отсортировать
Из теории графов => ,что ровно ½ вершин бинарного дерева является концевыми вершинами. Поэтому построение: берем вершину, применяем процедуру, затем другую…, т.е. цикл.
Begin
left:=(ndiv2)+1;
right:=n;
While left>1 do
Begin
left:=left-1;
SIFT;
End;
While r>1 do
Begin
x:=mas[1];
mas[1]:=mas[right];
mas[right]:=x;
right:=right-1;
End;{while}
End;{heapsoft}
Файловая сортировка
Идея: Сортировка методом естественного слияния. Эл-ты 1-го файла сравниваются с 1-м эл-том 2-го.
a,b,c-файлы. c-содержит исходную информацию. a,b-вспомогательные.
Разбиваем с на отсортированные куски:
c[i]<=c[i+1]
c[k]…c[j]
c[k-1]>c[k]
c[j+1]<c[j]
Списки
Список-конечная упорядоченная последовательность элементов.
Операции над списками:
Доступ к к-му эл-ту.
Включение нового эл-та.
Исключение эл-та.
Объединение нескольких списков в один.
Разбиение на несколько списков.
Определение числа эл-тов.
Сортировка.
Копирование.
ИТД
Типы списков:
СТЕК- список, доступ к эл-там к-рого осуществляется только с одного конца
ОЧЕРЕДЬ- все включения- с одного конца, а исключения-с другого
ДЕК- включения и исключения-с двух концов.
Динамические информационные структуры
Указатели-
динамические переменные, которые создаются в процессе работы программы по ее запросу.размещаются не при создании программы, а при ее построении в динамической области.
Адрес памяти распределенной для другой переменной.
УКАЗАТЕЛИ
Типизированные(^ТИП) Нетипизированные(pointer)
(x:integer;y:^integer)
|
Простейшие действия с указателями |
Type Plnt=^integer;Var a,b:Plnt; |
New(a);New(b); |
a^:=1;b^:=2; |
a^:=b^; |
|
5а)копирование адреса a:=b; |
|
5б)Dispose(a); a:=b; |
|
6) b:=nil; |
Var
p1,p2:^integer;
p3:real;
p4:byte;
b:integer;
pp:pointer;
Begin
b:=70;
p1:=@b;
Writeln(b);{70}
p1^:=311;
Writeln(b);{311}
p2:=p1;
pp:=p1;
Writeln(p1^);{311}
Writeln(p4^);{55}
p3:p;{необходимо знать,куда записывать.Если нет адреса=>ошибка}
Const
p:^real=nil;
Списки
Списки - это дискретные, связанные, динамические, рекурсивные информационные структуры.
Для списков характерно:
Состоят из элементов одного и того же типа. Тип элементов может быть любым.
Связь между элементами и доступ к спискам осуществляется при помощи типизированных указателей. По этому на ряду с информацией каждый элемент списка должен иметь указатели на последующий, или предшествующий, или на последующий и предшествующий элементы списка.
Количество элементов списка за ранее не задаётся. Оно может изменяться в процессе выполнения программы. Размер одного элемента списка не может превышать 64 Кбайт.
При описании типа - список, используется рекурсия.
Доступ к элементам списка последовательный.
Type
plist=^list;
list=record;
data:char;
next:plist;
end;
Var
head:plist;
last:plist;
Procedure newlist(var head:plist);
Begin
head:=nil;
End;
Function addhead(var i:char;head:plist);
Var
pp:plist;
Begin
new(pp);
pp^data:+c;
pp^next:=head;
head:=pp;
End;
Procedure print(head:plist);
Var
p:=plist;
Begin
p:=head;
While p<>nil do
Begin
Writeln(p^data);
p:=p^next;
End;
End;
Function remove(c:char;var head:plist:boolean);
Var
pp:=plist;
Begin
If head^data=c then
Begin
pp:=head;
head:=head^next;
dispose(pp);
REMOVE:=true;
End;
Else
Begin
pp:=head;
While (pp<>nil) and (pp^next^data<>c) do
pp:=pp^next;
if pp^next^data=c then
Begin
pp:= pp^next;
pp^next:= pp^next^next;dispose(p)
;REMOVE:=true;
End;
Else REMOVE:=false;
End;
End;
Создание пустого списка:
Var
p:pointer;
Begin
mark(p);
newlist(head);
addhead(‘a’head);
addhead(‘b’head);
addhead(‘c’head);
print(head);
release(p);
END.