Подпрограмма – поименованная логически законченная группа операторов языка, которую можно вызвать для выполнения по имени любое количество раз из различных мест проги. Блок может содержать в себе другие блоки. Блок, который не входит в другой блок, называется глобальным. Блок, входящий в состав другого блока – локальный. Объявление называется докальным для подпроги, если оно создается данной подпроге. Глобальное объявление – оно создается в объемлющей проге или в глобальном блоке. С каждым объявлением имени связана область его действия и вне своей области действия имя не существует. Областью действия имени явяляется часть блока от точки объявления до конца текущего уровня вложенности, включая вложенные подпроги, за исключнием тех вложенных подпрог, в которых имеются другие объявления того же имени. Не допускаются повторные объявления имени на одном уровне вложенности. Сущ 2 вида подпрог: процедуры и функции. Подразделяются: встроенные и определенные пользователем. Встроенные процедуры и функции являются частью языка и используются без их предварительного описания в проге. Процедуры и функции пользователя организуются програмером и являются локальными блоками. Их предварительное описание обязательно.
Принцип локализации.
С целью организации коллективной работы паскаль разрешает в любой подпроге или модуле вводить для внутренних потребностей любые типы значений и программные элементы. Принцип локализации заключается в том, что имена, вводимые в употребеление в подпроге имеют силу только только в данной подпроге. Если такое имя описано вне тела модуля, то область действия данного описания на подпрогу не распространяется.
Program q; var y:real; x:chat; const c=10; procedure al(x,z:real); var c:real;
Begin c:=x+z; x:=2*x; y:=1; writeln (c,x,y); end; begin x:=’a’; y:=0.5; al(y,0.1);
Формальные параметры определяют тип данных, передаваемых процедуре при ее вызове и способ передачи данных. Тело процедуры состоит из объявлений локальных идентификаторов и сотавного оператора, описывающего действия данной процедуры.
Осуществляется с помощью оператора вызова процедуры. Оператор вызова вызывает процедуру с указанным именем и передает ей фактические параметры, если они заданы. Выполнение процедуры прекращается при достижении конца составного оператора тела программы. Для прекращения выполнения процедуры до достижения конца ее тела используется оператор EXIT. Такое выполнение процедуры называется синхронным.
Процедуры без параметров.
Если нет параметров, то связь по данным между вызывающими и вызываемыми блоками возожна только через одноименные переменные, область действия которых охватывает оба блока.
Пример: program R; var x1,x2,y1,y2,d:real; i:integer; const N=10;
procedure rast1; begin d:=sqrt(sqr(x1-x2)+sqr(y1-y2)); end;
Begin for I:=1 to N do begin readln(X1,Y1,X2,Y2); Rast1; writeln(D); end; end.
Недостаток: жесткая фиксация исходных данных.
Если процедуру без параметров приходится использовать в различных частях программы, для различных имен переменных, то перед вызовом процедуры необходимо произвести переприсваивание имен.
Вопрос №7.
Процедуры с параметрами.
Формальные параметры – это идентификаторы переменных или имена подпрограмм, используемых в операторах внутри подпрог, заменяемые аргументами при вызове подпроги.
5 типов ф. параметров: п.значения, п-переменные, п-константы, п без типа, п процедурного типа.
Параметры-значения – группа параметров, перед которыми не используются зарезервированные слова var или const и за которыми следует тип. Запрещается использовать параметры значения файловых типов. Для каждого параметра-значения создается локальная переменная. Они существуют только во время выполнения подпроги. При входе в подпрогу этим переменным присваивается значение соответствующих фактических параметров оператора вызова процедуры.
В качестве фактического параметра может использоваться любое выражение, тип которого совместим по присваиванию с типом параметра значения.
Процедура не может изменять значение переменной, являющейся фактическим параметром. С помощью параметров-значений Нельзя представить результаты выполнения процедуры, которые используются вне ее тела.
Var x1,x2,y1,y2,D: real; i: integer; const n=10;
Procedure Rast2(XX1,XX2,YY1,YY2);
Begin D:=sqrt(sqr(xx1-xx2)+sqr(yy1-yy2) end;
Begin for i:=1 to n do
Begin readln(x1,x2,y1,y2); rast2(x1,x2,y1,y2) ; writeln(D) ; end ;
End.
Вопрос №8.
Параметры – переменные это группа параметров, перед которой стоит слово VAR и за которой следует тип. Фактическим параметром может быть только переменная того же типа, что и тип формального параметра.
−−−−−−−−−−−−−→<ид.>−−−−−−−−−−−−−−−→
→VAR→ →,→ →:→<тип>→
→CONST→
В подпрогу передается адрес этой переменной, поэтому процедура может непосредственно использовать и изменять значение этой переменно, т.е. передавать в основную прогу вычисленные результаты. Изменения формального параметра переменной приводит к изменению соответствующей переменной.
Параметры-константы
– описываются с помощью CONST. В подпрогу передается адрес фактического параметра. Фактическим параметром может быть константа или переменная. При входе в процедуру локальные переменные не создаются. Процедура выполняется гораздо быстрее.
Вопрос №9.
Параметры-переменные без типа
– группа параметров, перед которыми стоит VAR, но после которой не следует тип параметра. Фактическими параметрами м.б. переменные любого типа.
Поскольку у нетипизированных параметров переменных тип отсутствует, то изначально они не совместимы с переменными всех типов. Обеспечение совместимости с фактическими параметрами достигается двумя способами: 1) внутри подпроги объявляется локальная переменная нужного типа, наложенная на переданный фактический параметр. Для описания налагаемой переменной используется ABSOLUTE.
{сравниваются любые 2 переменные SO и DE любого типа и любого размера SIZE}
var N:integer;
s:array [0..maxint] of byte absolute so;
d:array [0..maxint] of byte absolute de;
begin N:=0; while (N<size) and (s[N]=d[N]) do inc (N);
rez:=N=size; end;
begin...readln (N);
equale1 (vec1,vec2,sizeof(integer)*N,rez);
--------------------------------
equale1 (vec1,vec2[3], sizeof(integer)*2,rez);
--------------------------------
equale1 (vec1[5],p,4,rez);
2) способ: внутри процедуры вводится нужный тип. Данный тип ставится в соответствие параметру переменной без типа с помощью присваивания типа переменной.
Procedure equale (...);
Type bytes=array[0..maxint] of byte;
var N:integer; begin N:=0;
while (N<size) and (bytes(de)[N]=bytes(so)[N]) do inc (N); Rez:=N=size; End;
Вопрос №10.
Параметры процедурного типа
. Это группа параметров, перед которыми не используется слова Varили Const. Позволяют организовать процедуры, использующие в качестве параметра другие процедуры или функции. С этой целью применяются процедурные типы. Описание процедурного типа вводится в разделе TYPE.
Type pr=procedure (x:integer,var y:real);
Pr1=procedure (a,b:string,p:pr);
Допускается использовать в любом контексте. Varp:pr; P1:pr1;
Параметры процедуры м.б. присвоено значение другой процедурной переменной, имя процедуры или функции. Для обеспечения такой совместимости, процедура, если ее нужно присвоить процедурной переменной, должна удовлетворять следующим требованиям: она должна компилироваться в состоянии far {$f+}; не д.б. стандартной процедурой или функцией; не д.б. вложенной; не д.б. процедурой типа Inline; не д.б. процедурой прерывания Interrupt.
На физическом уровне при присваивании процедурной переменной значения процедуры в данную переменную заносится адрес процедуры, поэтому процедурная переменная аналогично указателям. Занимает 4 байта. Если процедура д. передаваться в качестве фактического параметра, она должна удовлетворятьтем же правилам совместимости типа, что и при присваивании.
Const r=4; type mas=array[1..r] of real;
Proc=procedure (x:mas;var x1:mas);
Var vec1:mas; i:integer;
------------------
{$f+}
procedure loc(y:mas;var y1:mas);
begin for i:=1 to r do y1[i]:=ln(y[i]);
end;
procedure step (y:mas;var y1:mas);
begin for i:=1 to r do y1[i]:=exp(y[i]);
end; {$f-}
procedure vizov (g:mas;poced:proc);
var n:1..r; rez:mas;
begin proced (g,rez);
for n:=1 to r do write (rez[n]);
end; begin vizov (vec1,log); vizov (vec1,step); end.
Вопрос №11.
Использование производных типов в качестве параметров процедур.
Могут использоваться как параметры-переменные, п-значения или п-константы. Во всех случаях фактическими параметрами м.б. только переменные соответствующего типа, но не выражения и не константы (за исключением строковых констант). При использовании массива в качестве параметра-значения при входе в процедуру образуется локальная переменная массив, куда заносится значение фактического параметра массива, т.е. осуществляется копирование массива.
Вопрос №12.
Функции.
→FUNCTION→<ид>→<список_форм_пар>→:→<ид_типа>→
-----------------------
Функция может изменять значения глобальных переменных и параметров-переменных. Каждая функция вычисляет значение, называемое возвращаемым значением функции. Чтобы установить это значение необходимо присвоить это значение идентификатору функции. В теле ф-ции должен присутствовать оператор присваивания, в левой части которого записано имя описываемой функции (без параметров). Типы возвращаемых значений: скалярные, string,тип-указатель. Вызов ф-ции представляет собой возвращаемое значение. Оно используется в качестве операндов. М.б. использован везде, где по синтаксису допускается использование выражений.
Вопрос №13.
Рекурсивные функции.
Особенность: в их теле содержится обращение к этой же подпроге. 2 вида: явная – обращение к подпроге содержится в теле самой подпроги; неявная – обращение содержится в теле другой подпроги, к которой производится обращение изданной подпроги. Возможность рекурсивного обращения обеспечивается специальными средствами, которые при каждом повторном вызове подпроги создают новый экземпляр ее памяти и делают временно недоступным прежний экземпляр памяти. Экземпляр памяти – значения локальных переменных и фактических параметров, существующих на момент рекурсивного вызова подпроги. Все экземпляры памяти помещаются в стэк. В стэке всегда доступен только текущий экземпляр памяти, содержащийся последним. При каждом возврате из рекурсивной подпроги, текущий экземпляр памяти удаляется из стека и делается доступным предыдущий экземпляр. Рекурсивность – свойство описания подпроги. Недостаток – дополнительная память, существенно замедляется работа проги.
EXTERNAL – подключать в качестве тела подпроги фрагменты Assembler
INLINE – подключать в качестве разделов операторов инструкции в машинных кодах
FORWARD – опережающее описание. После этого прога д.б. описана с помощью определяющего описания – описание, содержащее заголовок подпроги, тело подпроги.
Между опережающим и определяющим описагиями м.б. описаны другие подпроги, которые могут обращаться к подпрогам с опережающим описанием → взаимная рекурсия
form_xi(i-1,xi); form_pi(i-1,pi); pi:=xi-pi; end end;
procedure form_xi; var pi:real; begin if i=0 then xi:=1 else form_xi(i-1,xi);
form_pi (i-1,pi); xi:=0.5*(xi+pi) end end;
begin read (n); form_xi(n,xi); form_pi(n,pi); writeln (‘x’,n,’=’,xi); writeln (‘p’,n,’=’,pi);
end.
Вопрос №17.
Процедуры ввода из стандартного текстового файла Input. Допустимые типы вводимых переменных. Особенности ввода. Пример.
По умолчанию устройство ввода связано со стандартным входным файлом Input. Устройство вывода связано со стандартным выходным файлом Оutput.
Устр-во ввода: клавиатура; вывода: экран.
1. Read(x1,x2,..,xn);
список ввода
2. ReadLn(x1,x2,..,xn);
Пр-ры читают символьные данные из файла Input и присваивают их переменным хi, при этом символьн. данные пробразуются к типу переменной xi. Допустимы следующие типы хi:
1. целочисленны и их диапазоны;
2. веществен.;
3. сhar и его диапазон;
4. string;
5. array of char;
Пр-ра ReadLn после чтения эл-тов списка ввода осущ. переход к следующей строке файла Input.
Var a,b,c:integer;
18
-16
41
543
-251
Readln(A,B): A→18; B→-16
17
18
25
Readln(C): C→17
Пр-ра Read после чтения эл-тов списка ввода осущ. переход на число символов данной строки.
18
-16
41
543
-251
Read(A,B): A→18; B→-16
17
18
25
Readln(C): C→41
Особенности ввода.
Тип вводимого данного должен соответств. типу хi.
Если в процедуре ввода в списке имеются несколько переменных, то во входном файле они должны отделятся друг от друга разделителями.
1)При вводе чисел в качестве разделителя исп-ся пробел.
2)При вводе данных типа char данные во входной файл записывают без разделителей и апострофов.
3)При вводе типа string чтение символов продолжается пока не достигнут конец строки файла или мах длина переменной xi. Переход на новую строку Read не осуществляет. При переходе типа string лучше исп-ть ReadLn.
4)Для переменных типа arrayofchar каждому элементу массива соответствует символ.
Вопрос №18.
Процедуры вывода в стандартный текстовый файл Output. Допустимые типы вводимых переменных. Размещение информации в строке по умолчанию. Управление размещением информации.
1. Write(E1,E2,..,En);
список ввода
2. WriteLn(E1,E2,..,En);
В общем случае Еi – выражение. Допускается строковая константа или переменная.
Допускаются следующие типы:
1. целочисленные и их диапазоны;
2. веществен.;
3. сhar и его диапазон;
4. boolean;
5. string;
6. array of char;
Данные типы при пердаче в вых. фал преобраз. к симв. типу и разбиваются на строки фикс. длины.
При выводе на экран длина строки: 80 символов.
При выводе на печать длина строки: 128(186) символов.
Для вывода исп-ся буфер, в котором предварительно формируется строка вывода.
Если мы работаем с Write, строка выводится только после заполнения буфера; WriteLn – переход на следующую строчку вывода осущ. после вывода всех эл-тов из списка параметров.
Кол-во позиций, отводимых строке вых. файла для выходных данных равно минимально необходимым.
Если тип boolean, выводится ‘true’ или ‘false’. Для веществе. чисел отвод. 23 символа в форме мантиссы и порядка.
Недостаток:
жесткая фиксация выводимых значений по позиции в строке. Поэтому для управления выводом по позиции строки исп-ся:
Ei:L1; Ei:L1:L2; , L1 – длина поля, отводимого для вывода Ei.
Если L1> миним.необходимого, то выводимое значение прижимается к правому полю; если < , то расширяется до min необходимого.
L2 – исп-ся только для вывода вещественных данных.
Если при выводе веществ. данных L2 отсутствует, значение будет выведено в виде мантиссы (zm
m0
.m1
m2
…mr
.Ezp
pu…
).
Записи
– это структура данных, состоящая из иерархически упорядоченных разнородных компонентов.
Компоненты записей м. иметь различный тип, доступ осуществляется по именам. Компоненты записи называются полями. На тип поля записей нет ограничений. Макс. уровень вложенности записей =9.
Тип поля м.б. задан предварительно либо при объявлении записи.
Type data=record
God:1900..2000;
Mes:(yan,fev);
Den:1..31;
End;
Anketa=record
Fio=record
Fam:string[20];
Im:string[10];
Ot:string[20];
End; ...
Var an1,an2:anketa; d1,d2:data; Spisok:array [1..N] of anketa;
Обращение к значению поля осуществляется с помощью ижентификатора поля, разделенных точкой. Для полных переменных типа запись существует операция присваивания.
Вопрос №20.
Запись с вариантной частью.
Позволяют объединить описания записей, которые похожи, но не идентичны по форме.
Активный вариант определяется признаком варианта-самостоятельное поле общей части записи. Если признак варианта отсутствует, то программист обязан следить за тем, какой вариант записи является активным.
Case i:integer of
-------------------
case integer of
type anketa1=record
fio:record
fam:string[20];
im:string[10];
ot:string[20];
end; case pol:(man,woman) of
man:(vozr1:20..30);
woman:(vozr2:18..25);
end;
type vbr=record
case integer of
1: (i1:1..10);
2: (y1:char);
3: (k1:boolean);
end;
varv:vbr;
В вариантной части все имена полей д.б. уникальны, даже если они встречаются в разных вариантах. Запись м. иметь одну вариантную чать, но вариантная часть м.б. вложена в другую вариантную часть. Если поле, соответствующее какому-либо значению признака является пустым, то данный вариант не опускается. <диапазон>:( )
Объем памяти, необходимый для записей с вариантами складывается из объемов полей общей части и максимальной по объему суммы полей переменной части. Поля записи помещаются в памяти последовательно в том порядке, как объявлены.
Вопрос №21.
Оператор WITH.
Используется для сокращения составного имени поля.
WITH →<перем>→DO→<опер>→
------,-------
Переменные типа запись. Облегчает доступ к полям записи и минимизирует повторные адресные вычисления. Внутри оператора WITH к полям записи, записанным в его заголовке можно обращаться как к простым переменным. Идентификатор поля в сокращенной записи оператора WITH обозначает компоненту записи из ближайшего объемлющего оператора WITH, в котором указана переменная с таким полем. withan1,fio,datadobegin
Fam:=’...’; Im:=’...’; God:=1970; Mes:=yan; End;
Если 2 переменные из списка записей оператора WITH имеют поля с одним и тем же именем, то внутри оператора WITH это имя обозначает поле той записи, которая указана в списке последней. Имена отдельных полей могут совпадать с именами переменных.
Вопрос №22.
Множественный тип (Set).
Максимальное количество элементов = 256. Все элементы множества д.б. одного типа. Базовым типом множества м.б. любой скалярный тип кроме вещественных типов. Границы базового типа – 0 до 255. Объем памяти, занимаемые переменными множественного типа – 1 до 32 байт. Данные типа Set хранятся в унитарном коде (в любом значении которого м.б. не более одной единицы, остальные нули).
1000000000000000 – «0»
0010000000000000 – «2»
0000000000000001 – «15»
1001000000000001 – «0,3,15» - множество их 3х чисел
Конкретное значение множественного типа задается с помощью конструктора множества. Порядок перечисления элементов значения не имеют.
→SET→OF→<баз_скал_тип>→
аналогично
array [баз_скал_тип] ofboolean;
a:set of 1..3; {a→[],[1],[2],[3]+любаякомбинация}
type ned=(pon,vt,sr,ch,pytn,sub,vos);
denned=set of ned;
log=set of boolean;
var den:denned; l1,l2:log; b:boolean; i,i1,i2:set of 1..10;
Вопрос №23.
Операции над множествами.
Операция
Описание
Тип результата
=
<>
Равно
Не равно
boolean
<=
Меньше-равно. Результат равен true, если левое множество является подмножеством правого
boolean
>=
True, если правое множество является подмножеством левого
boolean
IN
True, если некоторое скалярное значение, являющееся левым операндом, является элементом множества
boolean
NOT
Дополнение множества (одноместная)
set
+
Объединение множеств
set
*
Пересечение множеств
set
-
Разность множеств A-B=A*(notB)
set
xor
Исключающее объединение множеств AxorB=A+B-A*B
set
Одна встроенная ф-ция – sizeof (x).
Операция IN – левый операнд д. принадлежать базовому типу, правый – множественному типу, построенному на основе этого базового типа.
I:=[1,3,5];
B:=2 in I; B:=[3,5]<=I; {true}
B:=[3,4] <= I; {false}
I1:=[1,2,3]; I:=[1,3,5];
I2:=I1+I ; {объединение}
I2:=I1*I; {пересечение}
I2:=I1-I; {разность}
Старшинство операций аналогично старшинству в арифметических выражениях.
Ввод-вывод множественных переменных.
Varb:char; Mn:setof ‘a’..’z’;
Begin mn:=[]; Repeat Read (b); Mn:=mn+B; Until b=’.’
For B:=‘a’ to ‘z’ do If b in mn then write (b:5);
Вопрос №24.
Типизированная константа запись.
→(→<поле>→:→<типиз_конст>→)→
---;----------←-----------------------
type fam=(ivanov,petrov);
data = record
god:1900..2000;
mes:yan,fev,dec;
end; ank=array[fam] of data;
const d:data=(god:1950;mes:dec);
a:ank=((god:1970;mes:dec),(god:1945;mes:yan));
Поля должны указываться в том же порядке, как они следуют в объявлении типа запись. Если запись содержит вариант, то можно указывать только поля выбранного варианта. Если вариант содержит поле признака, его значение д.б. определено.
Вопрос №25.
Файлы.
Файловый тип – это произвольная последовательность элементов, длина которой заранее не определена, а конкретизируется в процессе выполнения программы. Физический файл – поименованная область памяти на внешнем носителе, в которой хранится некоторая инфа. При последовательном доступе по файлу можно двигаться только последовательно, начиная с первого элемента файла. При прямом доступе можно обратиться к элементу N. В Паскале есть 3 типа фалов: текстовые, типизированные, без типа.
→FILE →OF→<тип>→
---------→------
-------
→TEXT→--------
Над значениями файлового типа не определены никакие операции. Для доступа к отдельным элементам файла существуют стандартные процедуры ввода-вывода. Понятие «окно файла» или «указатель файла» определяет позицию доступа, т.е. тот элемент файла, который доступен для чтения или записи Позиция файла, следующая за последним элементом помечается маркером конца файла (EOF)
Вопрос №26.(Assign)
Assign (F,Name:string);
Организует связь с конкретным физическим файлом на носителе и файловой переменной программы.
Макс. ПОЛНОЕ имя файла – 79 символов.
Вместо имени физическогот файла может использоваться любое устройства ввода-вывода. Доступны следующие логические имена: CON (консоль); LPT1, LPT2, LPT3, LST1, LST2, PRN (печать); COM1, COM2 (усройства последовательного ввода-вывода); AUX; NUL (нулевое устройство, при выводе не осуществляется никаких действий, при чтении – ситуация конца файла); CRT (устройство текстового ввода-вывода); ‘’ (связывается с консолью).
Assign – нельзя применять к открытому файлу.
Вопрос №27.
Файлы с типом.
Состоит из однотипных компонент, тип которых указан при объявлении файла. Длина любого компонента типизированного файла строго постоянна, что дает возможность организовать прямой доступ к каждому из них(т.е. доступ к компоненту по порядковому номеру).
Синтаксис задания: <имя>=Fileof<тип>
Перед первым обращением к процедурам ввода-вывода указатель файла стоит в его начале и указывает на первый компонент с номером 0. После каждого чтения или записи указатель сдвигается к следующему компоненту файла. Переменные в списках ввода-вывода должны иметь тот же тип, что и компоненты файла. Если этих переменных в списке несколько, указатель будет смеяться после каждой операции обмена данными между переменными и дисковым файлом.
Assign(<ф.п.>,<имя файла>) - Организует связь с конкретным физическим файлом на носителе и файловой переменной программы.
ReWrite (F) – создает и открывает новый файл, если файл существует, то он удаляется.
Write (F,E) – записывает в ту позицию файла очередной элемент, равный значению выражения E, окно файла сдвигается на следующую позицию. Файл должен быть открыт.
Reset (F) – открывает существующий файл
READ (F,X) – чтение текущего элемента файла F в переменную X и сдвиг окна на следующую позицию. Для открытого файла. Файлы с типом допускают чтение и запись независимо от способа их открытия (ReWrite, ReSet).
Вопрос №28.
Длина любого компонента типизированного файла строго постоянна, что дает возможность организовать прямой доступ к каждому из них(т.е. доступ к компоненту по порядковому номеру).
Перед первым обращением к процедурам ввода-вывода указатель файла стоит в его начале и указывает на первый компонент с номером 0. После каждого чтения или записи указатель сдвигается к следующему компоненту файла. Переменные в списках ввода-вывода должны иметь тот же тип, что и компоненты файла. Если этих переменных в списке несколько, указатель будет смеяться после каждой операции обмена данными между переменными и дисковым файлом.
EOF (F) – используется для определения факта выхода при чтении за пределы файла.
SEEK (F,N) – осуществляет прямой доступ к элементам файла F. N- номер элемента файла, типа Longint. Позиционирует файл на указанный номер элемента. Текстовые файлы не обрабатываются.
FilePos (F) – номер текущей позиции. Если указатель установлен на конец файла, возвращает значение, равное размеру файла. Не для txt файлов
FILESIZE (F) – текущий размер файла longint(не для txt файлов).
CLOSE (F) – явное закрытие открытого файла F, однако связь файловой переменной с именем файла, установленная процедурой Assignсохраняется.
Вопрос №29.
Текстовые файлы.
Т. ф. предст. собой послед. символов. Fileofchar не эквивалентен т. ф. Особен. т. ф. то, что содержащиеся в нем симвлы разбив. на строки (которые могут быть различной длины в том чисе и пустые). В конце каждой строки помещ. маркер конца строки (#13 ^M) и перевод строки (#10 ^I), наличием этого маркера связ. раб. ф-ции EOLn(F): boolean. Т. ф. относ. к группе предопред. стр. типов и опред. с указанием имени VarF:text;
Input, Output – т. ф.(открыв. автоматически).
Процедуры и функции:
1). Assign (f, name)
2). AssignCrt (f)
– связ. т. ф. с CRT, аналогична Assign. Данная пр-ра опред. в модуле CRT.
uses crt;
var f:text;
k:(P,C);
…………………
begin
if k=P then assign (f, ‘PRN’)
else assigncrt (f);
…………………
3). Append (f)
(опред. только для т. ф.) – открывает сущ-щий т. ф. для добавления. Если файл f был предварит. открыт, то его необход. закрыть. В рез-те выполнения пр-ры окно файла устанавл. в конец файла. После вызова пр-ры Append файл f станов. доступным только для записи.
4). Rewrite (f)
– отличия: файл f открыт только для записи. После вызова пр-ры значение EOF (f) всегда = true.
5). Reset (f) –
отличия: файл открыв. только для чтения.
6). Read ([f], v1 [v2, v3,…vn])
– считывает одно или несколько знач. Отлич.: файл должен быть открыт только для чтения; 1-й параметр может быть опущен; при выполнении пр-ры осущ. преобр. эл-та файла из символьного представления к типу переменной Vi (Vi может иметь тип char, целочисл., вещетств. или строковый). Если V – char, то из файла в V счит. очередной символ, включая символы-разделители. Если в цифр. встрет. запрещенный символ, возник. сообщение об ошибке ввода-вывода. Если V – string, то V передается…
7). Readln [([f][,v1,v2,…vn])]
Вопрос №30(процедуры и функции для записи в текстовый файл).
1).Write ([f] e1 [, e2…en])
обеспечивает вывод информации в текстовый файл или передачу ее на логическое устройство. Сдесь е1,е2…en выражения типа char,string,Boolean, а также любого целого или вещественного типа. fдолжна быть типа text.
2). Writeln [([f][,][e1, e2,…en])]
3). Close (f)
var f:text;
………………
begin
assign (f, ‘Data.txt’);
rewrite (f);
………………
write (f, a);
………………
reset (f);
………………
read (f, b);
………………
close (f);
append (f);
write(f, c);
………………
close (f);
………………
Вопрос №31.
1). SetTextBuf (f, buf [, size])
– определяет буфер для текстового файла. Следует вызывать после assign. f – файловая переменная; buf – переменная любого типа; size – выражение типа word. Обмен информацией между прогой и внешним набором данных осущ. через буфер ввода-вывода. Размер станд. буфера в.-в. = 128 байт. Пр-ры write и writeln запис. очередные эл-ты файла последовательно в буфер. При чтении из внешнего файла одновременно считывается кол-во эл-тов, помещ. в буфер. А затем read и readln послед. счит. эл. данных из буфера. Исп-ние буфера в.-в. позвол. повысить скорость обмена информацией с внеш. файлами. Если в проге имеется большое кол-во операций в.-в., то более эффект. оказ. исп-ние буфера большого размера. Размер буфера опред-ся параметром size. Если size отсутствует, то размер = размеру памяти, заним. переменной buf.
☻Пример:
var f:text;
c:char;
buf:array [1..10240] of char;
begin
assign(f, ‘hsfkjsdhf .txt’);
settextbuf(f, buf);
reset(f);
while not eof(f) do
begin
read(f, c);
…………………
end;
…………………
12). Flush (f)
– очищаетбуферт. ф., открытогодлявыводапр-ройRewrite илиAppend. По этой пр-ре инфо из буфера, независимо от степени его заполненности, записывается во внешний файл. Данная пр-ра исп-ся редко.
13). EOF (f)
;
14). EOLn (f)
;
15). SeekEOF (f)
– устанавливает файл в состояние конец файла (аналог EOF, но пропускает все пробелы, метки, табуляции и маркеры конца строки). Обычно исп-ся при считывании числовых значений из т. ф. Определена только для т. ф.
16). SeekEOLn (f)
– аналог 11), но пропускает пробелы и метки табуляции. Исп-ся при считывании цифровой информации из т. ф.
Вопрос №32.
Сравнительная характеристика файлов с типом и текстовых файлов.
1) Представление численной инфы:
…в txt файле – код ASCII – 1 байт под каждую цифру
Если работаем с числовой инфой, и ее не нужно выводить на экран, то эффективней использовать файл с типом – меньше места в памяти; скорость работы выше (отсутствует преобразование инфы, прямой доступ).
2) Представление текстовой инфы
…в txt файле:
|Э|К|З|А|М|Е|Н|#13|#10|
|П|О|#13|#10| 31 байт
|П|Р|О|Г|Р|А|М|М|И|Р|О|В|А|Н|И|Ю|#13|#10|
...file of string [16]
|#17|Э|К|З|А|М|Е|Н|#0|#0|#0|#0|#0|#0|#0
|#2 |П|О|#0|#0|#0|#0|#0|#0|#0|#0|#0|#0|#0 51 байт
|#16|П|Р|О|Г|Р|А|М|М|И|Р|О|В|А|Н|И|Ю
меньше места занимает txt файл
большая скорость работы – fileofstring (прямой доступ, не отслеживаются управляющие символы).
Вопрос №33.
Файлы без типа. Синаксис задания. Назначение. Факторы повышения скорости обмена информацией. Процедуры и функции, определенные над файлами без типа. Пример.
Файл без типа состоит из компонентов одинакового размера. Структура этих компонентов не известна или не имеет значения, и это стирает все различия между файлами любых типов. Любой файл, независимо от того как он был создан, можно работать с ним, как с файлом без типа.
Назначение. Мах повысить скорость обмена информацией с внешним набором данных. Скорость обмена информацией повышается за счет:
- В ф.без типа отсутствует преобраз. типа компонент;
- не выполняется поиск управляющих символов;
- обмен информации с внешними наборами данных может осуществлятся с внешними блоками;
- к ф.без типа возможна организация прямого доступа.
Для ф.без типа определены те же процедуры и функции, что и для ф.с типом, за исключением Read и Write.
Проц. Reset и Rewrite имеют особенности.
Reset (F[ , Resize]);
Rewrite (F[ , Resize]);
Параметр Resize (размер записи) – это необязат. выраж. (word) определяется размер записи в байтах используемый при передачи данных. Если Resize опущен, то длина записи =128 байт.
*Вместо Read используется BlockRead
:
BlockRead (F, Buf, Count [ , Result]);
Buf – переменная любого типа;
Count – выражение типа Word, определяет кол-во считываемых записей;
Result – переменная типа Word.
BlockRead(F,Buf,Count[Rezult]); считывает блок информации длиной Count или меньше записей в области памяти занимаемой переменной Buf.
Действительное число считываемых полных записей ≤Count, заностися в параметр Result.
Если Result<Count следовательно достигнут конец файла. В этом случае, если Result отсутствует, возникает сообщение об ошибке ввода/вывода. В результате выполнения окно файла переместится на число Result.
Объем блока информации считывается проц. Read в Buf, заним. Result*Resize файла. Размер блока не должен превышать 64 кбайт.
*Вместо Writeиспользуется BlockWrite:
BlockWrite (F, Buf, Count [ , Result]);
Процедура записывает одну или несколько записей из области памяти, занимаемых переменой Buf файл F, переметр Result возвращает кол-во полных записанных записей.
Если Result<Count – диск переполнен.
Программа быстрого копирования ф.F1 в ф.F2:
Program Copy File;
Var F1,F2:File;
Buf: array[1..2048] of char;
Nr,Nw:Word;
Begin
Assign (F1, ‘Data1’);
Assign (F2, ‘Data2’);
Reset (F1,1);
Rewrite (F2,1);
Repeat
BlockRead (F1, Buf, Sizeof(Buf), Nr);
BlockWrite (F2, Buf, Nr,Nw);
Until (NR=0) or (NR< >1);
Close (F1);
Close (F2);
End.
Вопрос №34.
Проверка операций ввода-вывода. Пример.
По умолчанию при выполнении операций ввода-вывода осуществляется их стандартная проверка системными средствами. Длэ этого служит дирректива компилятира {$I+}. При этом, если возникла ошибка, она сообщает, но если это нежелательно, то необходимо отключить стандартную проверку ввода-вывода. С этой целью исп-т {$I-}. Для контроля ввода-вывода в сост. {$I-} служит ф-ция IOResult (ф-ция без параметров). Ф-ция возвращает целое значение типа Word, которая является состоянием послед. выполн. операции ввода-вывода, если ошибки не было ф-ция возвращиет значение 0, в противном случае возвращает код ошибки. Если $I в состоянии (-) и при некоторой операции ввода-вывода произошла ошибка, то все последние операции ввода-вывода использованные до вызова IOResult будут гнорироваться. Не желательно использовать один вызов ф-ции IOResult на несколько операций ввода-вывода, т.к. не ясно в какой из них произошла ошибка. При вызове IOResult возвращенное значение ф-ции устанавливается в 0, следовательно нельзя повторно считать.
Var F:File of char;
Begin
Assign (F,’Primer’);
{$I-}
Reset (F);
{$I+}
if IOResult =0 then
WriteLn (‘Размерфайла’, Filesize (F),’_ Байт’);
else
WriteLn (‘Файлненайден’);
end.
Вопрос №35.
Ссылочный тип.
Автоматич. переменные – это перем., порождаемые перед выполнением проги или подпроги, котоые сущ-ют в течение всего времени ее выполнения. Объем памяти, необход. для хранения автом. перем., не изменяется в ходе выполнения проги. Автом. перем. опред. в var. Обращение к ним осущ-ся с пом. их имен.
Дин. переменные – это перем., кот порождаются и уничтож. в процессе выполнения проги, размер значений которых опред. или измен. при выполнении проги.
Для работы с дин. перем. исп-ся ссылочный тип (указателей), значением этого типа явл. ссылка на некоторую перем., и уже по данной ссылке осущ-ся доступ к самой переменной.
<Тип_указателей>::=
→^→<ид._типа>→
└→→Pointer→→┘
В кач-ве ссылки исп-ся адрес соотв. переменной в памяти машины. Ид. типа – это дин. размещаемой перемен. В кач-ве типа может исп-ся имя станд. или отдельно описанного типа.
type mas=array [1..10] of integer;
admas=^mas;
p1=^integer;
var p:^integer;
q:^char;
pp:p1;
pt:pointer;
adrm:admas;
Сами указатели явл. автом. перемен. ссылочного типа. Указатель занимает 4 байта. Дин. переменные в проге не объявляются => единств. средством доступа к ним явл. указатели. Иногда необход. в кач-ве значения указателя принять пустую ссылку (не связывать с данным указателем дин. переменную). Для этого исп-ся nil. константа nil совместима с любым типом указателя.
Над значениями ссылочного типа нет операций, которые давали бы результат того же типа. Определены только присваевание и 2 операции сравнения (:=, <,>).
Два значения ссылочного типа равны, если они оба есть nil либо указывают на одну и ту же динамическую переменную. В правой части оп-ра :=-ния исп-ся ссылочное выражение того же типа, что и переменная в левой части. В качестве ссылочного выражения может исп-ся:
1. nil;
2. ссылочная переменная;
3. ссылочная функция;
Объявление ссылочной переменной в разделе Var не порождает самой динамической переменной. По этому объявлению транслятор только отводит место в памяти для размещения указателя.
Вопрос №36.
Процедуры New и Dispose.
Для порождения дин. переменной исп-ся проц-ра new(p), р – ссылочная переменная любого типа. New размещает дин. переменную типа указатель. Переменной выделяется память, достаточная для хранения наиболее длинного значения типа указателя. Адрес начала данного места памяти присваивается р. Для дин. переменных new играет ту же роль, что раздел var для автоматических переменных. Никакого значения new дин. переменной не присваивает. Для обращения к дин. перем. исп-ся
<переменная_с_указателем>::=
<ссыл._перем.> ^.
☻Пример:
var p:^integer; x:integer;
………….
new(p);
p^:=15;
x:=x+p^;
p^:=p^ mod 5;
adrm^[p^+2]:=14;
Над переменными с указателями определены любые операции, допустимые для переменных того же типа, что и тип дин. переменной.
Возможна организация массивов указателей:
typep1=^integer;
var a:array[1..20] of integer;
……………..
for i:=1 to 20 do
new(a[i]);
……………..
a[i]^:=25;
!!! Идентификатор типа в определении ссыл. типа может быть объявлен как до, так и после его исп-ния, в отличие от всех других типов.
Пример:
type admas=^mas;
mas=array [1..10] of integer;
Пример:
varx,y:^integer;
begin
new(x);
new(y);
x^:=5;
y^:=10;
x:=y;
y:=nil;
Переменная типа указатель может являтся параматром ф-ции ord(p). Рез-татом этой ф-ции явл. целое значение, равное адресу дин. переменной, на которую ссылается указатель р. Обратное преобразование не допускается.
Для уничтожения дин. переменной исп-ся dispose(p). В рез-те ее выполнения дин. преременная, связанная с указателем р уничтожается. Занимаемая ею память считается свободной. Значение р становится неопределенным (= nil). Dispose уничтожает только дин. перем., но не указатель на нее..
Вопрос №37.
Процедуры Getmem и Freemem.
getmem (p,size)
freemem (p,size)
р – указатель любого типа
size – выражение типа word.
getmem выделяет из области дин. памяти (heap-область) блок памяти длиной size байт и адрес этого блока присваивается р. Макс. размер блока: 64 кбайт–(минус) смещение. Для освобождения блока памяти исп-ся freemem, кот. уничтожает дин. переменную p^, заним. ею память счит. свободной, значение p=nil.
type T=<тип>;
var p:=^T;
…………….
new(p);
…………….
dispose(p);
_________________
getmem (p, sizeof(T));
……………..
freemem (p, sizeof(T));
В общем случае getmem и freemem дают большую свободу действий по сравнению с new и dispose, т.к. позволяют работать без привязки к конкретному типу переменных:
type zap=record
x,y:integer;
end;
st=string [20];
var p:pointer;
begin getmem (p,100); zap(p^).x:=124; zap(p^).y:=47; ………………
real(p^):=0.213; ……………….
st (p^):= ‘Привет’; ……………….
freemem(p,100);
Вопрос №38.
Процедуры mark и release.
Пр-ры dispose/freemem освобождают участок того же размера, кот. был выделен пр-рами new/getmem. Эти участки могут исп-ся для хранения дин. переменных. Однако в ряде версий Pascal с-ма не выполняет автоматических действй по поиску и объединению разрозненных фрагментов памяти в одну непрерывную область. Пр-ры mark и release были разработаны для более эффективного размещения дин. переменных и устранения фрагментации памяти.
mark(p1);
p1 – перем. типа указатель
mark присваивает параметру р1 адрес начала свободной области дин. памяти. Помеченная область с пом. new/getmem исп-ся для размещения дин. переменных. Когда данные дин. переменные окажутся ненужными, занимаемую ими память можно освободить: release(p1).
release освобождает память, начиная с адреса, полученного в рез-те выполнения последней пр-ры mark, значение р1=nil.
mark (p1)
new (p)
release (p1)
new(p2)
……….
……….
Параметр пр-ры mark нельзя исп-ть в кач-ве параметра пр-ры new/getmem и его нельзя изменять до использования в проге release.
Возможна вложенность пр-р mark, тогда каждой mark соответствует своя release.
☻Пример:
var p1,p2:^integer;
………………
mark(p1); ……………… new(p); new(q); ……………… mark(p2);
new(x); ……………… release(p2);……………… release(p1);
!!! В одной и той же проге не рекомендуется исп-ть одновременно dispose/freemem и mark/release.
Вопрос №39.
Динамические цепочки. Объявление. Алгоритм формирования цепочки.
Д. цеп. – аналог строк текущей длины.
Эл-ты строки можно размещать в памяти произвольно, если каждый эл-т снабдить явным указанием места, где находится след. эл-т. В этом случае каждый эл-т строки должен состоять из двух полей: в одном – символ строки, в другом – адрес след. эл-та. Каждая такая пара полей наз. звеном. Ссылки сцепляют звенья в единую цепочку. Такой способ представления упорядоченной послед-сти эл-тов наз. сцеплением. Оно применяется для представления дин. структур любой сложности. Тело звена – информац. часть, справочная часть звена – адрес звена (след., пред., и т.д.).
Для представления звена цепочки необход. исп-ть запись их 2-х полей.
type adr=^zveno;
zveno=record
element:char;
adrsled:adr;
end;
Последнее звено цепочки должно быть снабжено ссылкой nil. Для работы с цепочкой должна исп-ся ссылка на 1-е звено
varadr1:adr;
1-й элемент
adr1
Для удобства работы с цепочкой в нее включается заглавное (нулевое) звено. В поле adrsled заглав. звена содержится адрес первого звена цепочки.
☻Пример (формирование цепочки):
type -//-;
varadr1, adrzv:adr; {adr1 – адрес 1-го звена, adrzv – адрес текущего звена}
simv:char;
begin
new(adr1);
adrzv:=adr1;
adrzv^.adrsled:=nil; {при формировании цепочки текущее звено всегда явл. последним}
read(simv);
while simv<>’.’ do
begin
{1} new(adrzv^.adrsled);
{2} adrzv:=adrzv^.adrsled;
{3} adrzv^.element:=simv;
{4} adrzv^.adrsled:=nil;
{5} read(simv);
end;
Алгоритм формирования цепочки (в примере):
1. Отвести область памяти для очередного звена. Его адрес занести в адресную часть текущего звена.
2. Новое звено сделать текущим звеном.
3. В поле element текущ. звена занести прочитанный символ.
4. В адресную часть текущ. звена занести nil.
5. Прочитать очередной символ и перейти к п.1.
Вопрос №40.
Операции, определенные над динамическими цепочками.
Над цепочкой опред. 3 операции:
1. Поиск эл-тов в цепочке.
2. Вставка эл-тов в произвольное место в цепочке.
3. Удаление заданного эл-та.
¬ Для перехода от одного звена цепочки к след. необход. в цикле выполнять оператор: adrzv:=adrzv^.adrsled
. Этот оператор аналогичен i:=i+1 для обычных статических цепочек.
…………………
adrzv:=adr1;
k:=0;
read(bukva);
while adrzv^.adrsled<>nil do
begin
adrzv:=adrzv^.adrsled;
if adrzv^.element=bukva then k:=k+1;
end;
® Удаляемый эл-т задается ссылкой на пред. звено, при этом учитывается, что если какое-либо звено сущ-ет, но на него нет ссылки из другого звена, то оно не доступно
Для исключения эл-та из строки необходимо изменить ссылку у предшествующего ему эл-та. В кач-ве новой ссылки у этого эл-та необход. принять ссылку из исключаемого эл-та.
adrzv^.adrsled:=adrzv^.adrsled^.adrsled.
procedure Del (zv:adr);
var a:adr;
begin
a:=zv^.adrsled;
zv^.adrsled:=zv^.adrsled^.adrsled;
dispose(a);
end;
Вставка основывается на объединении отдельных звеньев в единую цепочку.
Алгоритм вставки:
1. Создать новую дин. переменную типа zveno.
2. В поле element этой переменной занести вставляемый эл-т.
3. В поле adrsled этой переменной занести ссылку, взятую из поля adrsled пред. звена.
4. В поле adrsled пред. звена занести адрес вставляемого звена.
procedure Insert (zv:adr; el:char);
var q:adr;
begin
{1} new(q);
{2} q^.element:=el;
{3} q^.adrsled:=zv^.adrsled;
{4} zv^.adrsled:=q;
end;
Дин. цепочка явл. частным случаем линейного однонаправленного списка. В цепочке информационными эл-тами явл. символы (char). В общем случае информац. эл-тами могут быть значения любого типа. Принцип организации информац. эл-тов в список тот же.
typeadres1=^zveno1;
zveno1=record
adrsled:adres1;
element:<тип_эл-та_списка>;
end;
Вопрос №41.
Двунаправленные списки. Объявление. Способы организации колец. Формирование кольца (по первому способу).
Недостатки
линейного однонаправленного списка: по нему можно двигаться только в одном направлении (от начала к концу).
2-направл. списки позволяют двигаться по списку в любом направлении. Каждое звено 2-нопраленного списка списка содержат 2 поля ссылочного типа: на последнее и на предыдущее звено.
Структура опред. следующим описанием.
Объявление
.
Type
Adr2=^Zveno2;
Zveno2 = Record
Adrcled: Adr2;
Adrpred: Adr2;
Element: <Тип_элемента_списка>;
End;
Кольцевые списки.
(1 способ) На осн. 2-направленного списка могут быть организованы 2-направленные кольцевые списки.
В кольц. списке значение поля Adrcled последнего звена – ссылка на начальное звено, а Adrpred начального звена – ссылка на последнее звено.
(2 способ) заглавное звено не включают в кольцо.
Достоинство
: проще реализуется вставка нового звена, как в начало списка, так и в конец.
Недостатки
: 1 способа: при циклических обработках, элементы списка необходимо проверять: не является ли очередное звено заглавным звеном.
У 2 способа данный недостаток отсутствует, но труднее реализовать добавление звена в конец списка.
Над 2-направленными списками определены операции: поиск элемена в списке, вставка и удаление.
Вопрос №43.
Операции, определенные над двунаправленными кольцевыми списками. Примеры (для 1-го способа организации колец).
1)Встака эл-та
Алгоритм – порождение нового звена;
- занесение вставленного элемента в информационное поле порожденного звена.
1) записать в поле Аdrcled ссылки на след эл-т из звена предшествующему вставляемому;
2) занести в Аdrpred ссылки на предшеств.эл-т из звена следующ. вставляемому;
3) занести в Аdrpred след. за вставл. звено ссылки на вставляемое звено;
4) в Аdrpred предшествующего звена ссылки на вставляемое звено;
Procedure Vstsv
(Elem: <Тип_элемента>)
{1} New (Q);
{2} Q^.Element:=Elem;
{3} Q^.Adrcled:=PredZV^.Adrcled;
{4} Q^.Adrpred:=PredZV;
{5} PredZV^.Adrcled^. Adrpred:=Q;
{6} PredZV^.Adrcled:=Q;
End;
Создание 2-направленного кольцевого списка с заглавным звеном.
Для создания кольцевого списка, после создания любого звена, список нужно закольцевать.
Var
Ring: Adr2; (адрес заглавного звена)
Bykva: Char;
Begin
New(Ring);
Ring^.Adrcled:=Ring;
Ring^.Adrpred:=Ring;
While Bykva< >’.’do
begin
Vstav(Bykva, Ring^.Adrcled);
Read(Bykva);
End.
Удаление элемента
.
1. занес. в Аdrpred след. за удаляемым звеном ссылку на предшествующий удаляемому звену;
2. в Аdrcled предшеств. удаляемому звену ссылки на след. за удаляемым звеном;
3. уничтожение удаляемого звена.
{1} Adrzv^.Adrcled^. Аdrpred:=Ydzv^. Аdrpred;
{2} Ydzv^. Аdrpred^. Аdrcled:= Ydzv^. Аdrcled;
{3} Dispose(Ydzv);
Поиск элемента.
Аналогичен поиску элементов в цепочке, но в кольцевом списке формально нет последнего элемента.
Q:=P^. Аdrcled; (Р-адрес заглавного звена)
While (P< >Q) and not B do (Q-адрестекущегозвена)
Вопрос №45.
Очередь FIFO. Объявление. Операции, определенные над очередью FIFO. Организация очереди FIFO.
Очередь (FIFO).
Для организации такой очереди исп-ся 2 ссыл. переменные типа
adr1:Left – указывает на начало очереди;
adr2:Right - указывает на конец очереди.
Добавление осуществляется в соответствии со значением right. Затем это значение изменяется и указывает на последний занесенный эл-т.
Выборка осуществляется в соответствии со значением Left. Затем изменяется и указывает на след. эл-т очереди. Если в очереди всего 1 эл-т, то Right=Left. Обычно это исп-ся как прзнак окончания очереди при выборе.
1. Занесение эл-та в очередь
.
Алгоритм.
1. создание нового звена;
2. занесание в послед. звено адреса нового звена;
3. занесание nil в поле адреса нового звена;
4. занесание эл-тов в новое звено;
5. созданное звено сделать концом очереди.
{1} new(q);
{2} Right^.adrcled:=q;
{3} q^.adrcled:=nil;
{4} q^.element:=el;
{5} right:=q
2. Выбор эл-та из очереди
.
Алгоритм.
1. прочитать значение из начала очереди;
2. запомнить ссылку на начало очереди;
3. исключить 1-е звено из начала очереди;
4. уничтожить 1-е звено.
{1} elem:=Left^.element;
{2} q:=Left;
{3} Left:=Left^.adrcled;
{4} dispose(q);
Вопрос №46.
Очередь LIFO. Объявление. Операции, определенные над очередью LIFO. Организация очереди LIFO.
Очереди и стеки.
Над очередью опр. 2 операции:
- занесение элемнта в очередь,
- выбор элемента (выбранный элемент из очреди исключается).
В очереди доступны 2 позиции: начало и конец, где помещаются заносимый элемент.
Различают 2 вида:
(FIFO) заказ, поступивший в очередь 1-ым, выбирается 1-ым и удаляется;
(LIFO-стек) последний заказ выбирается и удаляется.
Стек (LIFO).
В стеке доступна одна позиция – вершина стека, которая находится последней по времени занесения элемента. Наиболее быстрое выполнени операциинад стеком обеспечивает его представление в виде однонаправленного списка. Загланое звено в стеке не используется. При использовании однонаправленного спискастек задается с помощью описания типа (*). Дополнительно вводится тип указателя, представляющего стек кк единую структуру.
TypeStak=Adres1;
varSt: Stak;
К началу исп-ния стека его нужно сделать пустым.
1. Занесение элемента в стек
.
Алгоритм:
1. создание нового звена;
2. занесение в новое звено элемента;
3. занесение в новое звено адреса предыдущей вершины стека;
4. созданное звено сделать вершиной стека.
{1} new(q);
{2} q^.element:=el;
{3} q^.adrcled:=st;
{4} st:=q;
2. Выбор элемена из стека.
Алгоритм.
1. прочитать значение вершины стека;
2. заполнить ссылку на вершину стека;
3. исключить 1-е звено из стека;
4. уничтожить 1-е звено.
{1} a:=st^. element;
{2} q:=st;
{3} st:=st^.adrcled;
{4} dispose(q);
Вопрос №47.
Таблицы.
Основная задача – организация выдачи по запросу любой из записей независимо от того, какая запись выдавалась перед ней.Используются структуры данных (таблицы). Каждой записи соответствует свое имя (ключ записи). Для организации эффективного поиска записи необходимо, чтобы наж ключами м.б. реализовывать операции сравнения, поэтому ключи д.б. упорядоченного типа. Наиболее удобно использовать целые числа или строки символов одинаковой длины. Определены следующие операции: поиск записи с заданным ключом, включение в таблицу записи с заданным ключом, исключение записи.
1й способ: Представление таблицы с помощью однонаправленнго списка. Каждое звено списка д. содержать ключ записи, текст записи и ссылку на следующее звено. Достоинтсва: эффективное использование памяти, простой алгоритм перебора записей, простота включения в таблицу заведомо новой записи, как новое звено в конец списка. Недостаток: большое время поиска нужной инфы.
2й срособ: Однонаправленный список с упорядоченными записями. Достоинтсва: меньшее время поиска записи, недостаток: усложняется включение новой записи в таблицу.
3й способ: цепочка с отдельным хранением текста записи. Для ускорения поиска записи. Тексты записей хранятся отдельно от ключей.
*→| * | → | * | → …
| кл1 | |кл2 |
| * | | * |
↓ ↓
|зап1| |зап2|
4й способ: представление в виде массива.
|кл1| |кл2| …
| * | | * |
↓ ↓
|зап1| |зап2|
typeindex=1..N;
tekst=<тип_текст_зап>;
adr=^tekst;
element=record
kl:integer;
adrzap:adr;
end;
mas=array [index] of element;
vartab1:mas;
Для организации эффективного поиска необходимо, чтобы элементы массива были упорядочены по возрастанию ключей. tab1[i].adrzap^.
Для поиска элемента с заданным ключом используется метод дихотомического поиска: берется средний элемент массива, если искомый ключ меньше ключа в элементе с номером n/2, то требуемый элемент находится в 1й половине массива. На следующем этапе нужная половина массива опять делится пополам. Кол-во шагов: 1+log2N Недостаток: реализация включения и исключения записей.
Вопрос №48.
5й способ: двоичное дерево. Позволяет эффективно реализовать все 3 операции над таблицами. Из каждой вершины выходит не более 2х вертвей. В каждую вершину входит только одна ветвь. Вершина, в которую не входит ни одна ветвь.называется корнем. Вершины, из которых не выходи ни одна ветвь –листья. При представлении таблицы в виде дерева тексты записей храниятся отдельно, каждая вершина дерева является записью, состоящей из 4х полей: ключ записи, ссылка на вершину влево-вниз, вправо-вниз, ссылка на текст записи.
Принцип: первая запись делается корнем дерева. Если ключ следующей записи меньше ключа корня, то этой записи ставится в соответствие левая вершина иначе – правая. Ключ каждой последующей записи сравнивается последовательно с ключом корня, а затем с ключами тех записей, которые находятся на соответствующей вершине дерева.
Typetekst=<тип_записи>
Adrt=^tekst;
Adrzv=^zveno;
Zveno=record
Kl:integer;
Lev,prav:adrzv;
Adr:adrt;
End;
Var dvder:adrzv;
Вопрос №49.
Поиск.
k-ключ искомой записи; d-ссылка на дерево; rez – присваевымая ссылка на найденное звено или ссылка на вершину после обработки которой которой; P-адрес вершины, подлежащей обработке; Q- адрес последней обработанной вершины.
Var P,Q:adrzv;
D,rez:adr;
B:boolean;
K:integer;
Begin........
B:=false;
P:=d;
Q:=nil;
If d<>nil then
repeat
Q:=p;
If p^.kl=k then b:=true else
If k<p^.kl then p:=p^.lev else p:=p^.prav
Until b or (p=nil);
Rez:=q;
Скорость поиска приблизительно равна скорости дихотомии.
Вопрос №50.
Операция включения записи дерево.
Для включения записи в таблицу нужно найти в дереве, к кот. можно присоединить новую вершину, соответствующую включаемой записи.
Алгоритм поиска нужной вершины аналогичен поиску вершины с заданным ключом. Нужная вершина найдена если в кач-ве очередной ссылки, определяющей ветвь продолжения поиска, окажется nil. Для поиска вершины можно исп-ть алгоритм поиска вершины с заданным ключом (т.е. такая вершины найдена, если b=false). В этом случае rez – адрес вершины, к кот. можно присоединить включаемую вершину.
var zap: terst;
s: adrzv;
t: adrt;
begin----
new(t);
t^:=zap;
new(s);
s^.kl:=k;
s^.adr:=t;
s^.adr:=t;
s^.lev:=nil;
s^.prav:=nil;
if d=nil then d:=s
else if k<q^.kl then q^.lev:=s
elseq^.prav:=s;
Вопрос №51.
Операция удаленияния записи дерево.
Если удаляемая вершина явл. листом дерева или из нее выходит только одна ветвь, то для удаления записи достаточно скоректировать соответ. ссылку у вершины предшедствующей удаляемой. В этих случаях в соответств. поле Lev или prav предшественника нужно занести содержимое поля Lev или prav удаляемой вершины.
Если из удаляемой вершины выходит две ветви, то нужно найти подходящее звено, которое можно было бы вставить на мести удаляемого. Таким звеном является:
а) самый правый эл-т левого поддерева.
Для достижения этого звена необходимо перейти в следующую под удаляемой вершину по левой ветви, а затем переходить в очередные вершины только по правой ветви до тех пор, пока очередная такая ссылка не будет равна nil.
б) самый левый элемент правого поддерева.
Для достижения этого звена необходимо перейти в след. под удал. вершину по правой ветви, а затем переходить в очередные вершины только по левой ветви, пока очередная ссылка не будет равна nil.
При исключении из дерева вершины с заданным ключом необходимо учеть:
1. звена с заданным ключом в дереве нет;
2. звено с заданным ключом имеет не более одной ветви;
3. звено с заданным ключом имеет две ветви.
Пример (случ.а).
Procedure Del (var d:adrzv; k:integer);
var q: adrzv;
Procedure Udal (var R:adrzv); begin
if R^.prav=nil then
begin
q^.kl:=R^.kl;
q^.adr:=R^.adr;
q:=R;
R:=q^.lev
end;
else Udal(R^.prav);
end;
begin
if d=nil then writeln (‘звенанет’);
else if k<d^.kl then Del (d^.lev, k);
else if k>d^.kl then Del (d^.prav, k);
else begin
q:=d;
if d^.prav=nil then d:= d^.lev
else if d^.lev=nil then d:= d^.prav
else Udal(q^.lev);
end;
end;
Вопрос №1. Строковые константы.
Это последовательность любых символов, заключенных в апострофы.
Правила записи:
1) Если в строке необходимо поместить апостроф, то его повторяют 2-жды. При просчете длины строки 2 рядом стоящих апострофа считаются одним.
2) При подсчете длины строки учитываются пробелы.
3) Допускаются пустые символьные константы. ‘’
4) Турбо П. разрешает вставлять в строку управляющие символы. Используется символ # и константа целого знака от 0..255 (#13-возврат каретки, #10-перевод строки). Управляющие символы пишутся вне апострофа.
Например,
‘TURBO’#13#10’TEKST’
Здесь #13#10 – это управляющие символы, осуществляющие переход к началу следующей строки.
Строковые переменные постоянной длины
: строк. пер. = одномерный массив симв. Обладают всеми свойствами массивов. Возможно обращение к отдельным символам, используя индексы.
Форматзадания:
Array[1..10] of char;
Особенности строк. переменных:
1) Строковым переменным могут быть присвоены значения строковых констант, если длина строки равна длине литерала.
2) Над значениями строковых переменных одинаковой длины можно выполнять операции сравнения. Сравнение производится посимвольно слева до первого несовпадающего символа.
Считается большей та строка, в которой первый несовпадающий символ имеет больший номер в коде обмена информацией (ASCII).
Вопрос №2 Строки переменной длины.
<Задание_типа_String> ::=
→string→[→<N>→]→
↓____→___↑
С помощью типа String определяются строки переменной длины. N после слова String определяет максимальную длину строки. N должно иметь положительное целочисленное значение, не превышающее 255 (≥1).
Если N в определении опущено (по умолчанию), то считается, что максимальная длина строки равна 255 = 28 – 1.
Переменной типа String может быть присвоено значение другой строки любой длины. Если длина присваиваемой строки меньше или равна максимальной длине данной строки, то данная переменная типа String имеет текущую (динамическую) длину. Текущая длина строки определяется длиной последнего занесенного в нее значения.
Если длина присваиваемого значения превышает указанную в объявлении максимальную длину, то лишние символы справа отсекаются.
Переменной типа String выделяется количество байтов памяти на единицу превышающее максимальную длину, указанную в определении типа. В левом байте (с номером 0) хранится текущая длина строки в двоичном коде.
Возможен доступ к отдельным символам строки типа String. При этом используются индексные переменные. Правила индексации аналогичны массиву символов с диапазоном индексов.
Если при обращении к отдельным символам строки произойдет выход за текущую длину строки, то считанные из строки символы будут случайными, а присваивания элементам строки, находящимся вне текущей длины, не повлияют на значение строковой переменной.
Над данными типа String определены операции сравнения (=, <>, >, <, >=, <=) и операция конкатенации (сцепления). Операция конкатенации имеет более высокий приоритет чем операции сравнения.
Сравнение производится в соответствии с упорядочением символов в коде ASCII. Сравниваются символы строк последовательно слева направо до первого несовпадающего символа. Большей считается строка, у которой первый несовпадающий символ имеет больший код в таблице ASCII. Если строки имеют разную длину и их символы совпадают в общей части, то более короткая строка считается меньшей. Строки считаются равными, если они имеют одинаковую текущую длину и одни и те же символы.
Операция сцепления обозначается символом +. При ее выполнении две строки соединяются в одну результирующую строку. Длина результирующей строки не должна превышать 255 символов.
Var ST1 : String [100]; {максимальная длина равна 100}
ST3, ST2 : String; {по умолчанию максимальная длина равна 255} L: Boolean;
BeginST1 := ‘Ми’; {текущая длина ST1 равна 3} ST2 := ‘н’; {текущая длина ST2 равна 1} ST3 := ‘ск’; {текущая длина ST3 равна 2} ST3 := ST1 + ST2 + ST3; {сцепление (конкатенация) строк: в ST3 значение ‘Минск’; текущая длина равна 4}L := ST3 > ST1; {в Lзапишется True} ST3[2] := ‘e’; {в ST3 значение ‘Менск’}
Вопрос №3 Процедуры и функции, определенные над строками переменной длины.
Функции:
1) Copy (St, Poz, N)
Выделяет из строки St подстроку длиной N символов, начиная с позиции Poz. Если Poz больше длины строки, то результат – пустая строка. Если Poz + N больше текущей длины St, результатом будут последние символы St, начиная с позиции Poz. Если Poz больше 255, возникает ошибка выполнения.
2) Concat (St1[, St2, ..., StN] )
Выполняет сцепление строк в том порядке, в каком они указаны в списке параметров: St1 + St2 + ... + StN. S1 ÷ SN – выражения типа String. Длина результирующей строки не должна превышать 255 символов
3) Length (St)
Возвращает текущую длину строки St. Результат имеет целочисленный тип.
4) Pos (St1, St2)
Обнаруживает первое появление подстроки St1 в строке St2. Результат имеет целочисленный тип и равен номеру той позиции, где находится первый символ подстроки St1. Если в строке St2 подстроки St1 не найдено, то результат равен нулю.
5) UpCase (Ch)
Преобразует строчную латинскую букву в прописную. В остальных случаях возвращает аргумент Ch. Параметр и результат имеют тип Char.
Процедуры:
1) Delete (St, Poz, N)
Удаляет N символов строки St, начиная с позиции Poz. Значение Poz не должно превышать 255. Если Poz больше текущей длины строки, строка St не изменяется. Если Poz + N больше текущей длины строки, то удаляется конец строки, начиная с позиции Poz.
2) Insert (St1, St2, Poz)
Вставляет строку St1 в строку St2, начиная с позиции Poz. Если значение Poz больше текущей длины St2, то результат равен сцеплению строк St2 + St1.
3) Str (I, St)
Преобразует числовое значение величины I и помещает результат в строку St. Величина I должна иметь целочисленный или вещественный тип.
4) Val (St, I, Cod)
Преобразует значение St в величину целочисленного или вещественного типа (в зависимости от типа параметра I) и помещает результат в I. Значение St может содержать незначащие пробелы в начале и не может в конце. Cod – целочисленная переменная. Если во время операции преобразования ошибки не обнаружено, то значение Cod равно нулю. Если ошибка обнаружена (например, символьное значение переводится в цифровое), то Cod будет содержать номер позиции первого ошибочного символа, а значение I будет неопределено.
Вопрос №4 Оператор CASE
Является производным оператором. Относится к группе выбирающих операторов.
Используется в разветвляющихся программах, если процесс нужно разветвить более чем по двум возможным направлениям. Является обобщением условного оператора If.
Оператор Case позволяет выбрать для исполнения один из входящих в него операторов, в зависимости от значения выражения, расположенного после зарезервированного слова Case. Это выражение называется селектором (переключателем). Оно может иметь любой перенумерованный тип, кроме типов Longint, Word и строкового типа.
Каждый оператор помечен списком констант выбора и (или) диапазонов констант выбора:
Диапазон::=→<Константа_1>─┬─────────────┬─→
└→..→<Константа_2>┘
Последний оператор может быть помечен зарезервированным словом Else (иначе). Если несколько констант выбора относятся к одному и тому же оператору, то они отделяются друг от друга запятой. Константы выбора должны иметь тот же тип, что и селектор.
Оператор Case выполняется следующим образом. Сначала вычисляется значение селектора. Затем выполняется тот оператор, для которого значение константы выбора совпадает со значением селектора. Если ни одна константа выбора не совпадает со значением селектора, то будет выполнен оператор, помеченный зарезервированным словом Else. На этом выполнение оператора Case заканчивается.
Если значению селектора не соответствует ни один из допустимых вариантов выполнения (ветвь Else отсутствует), то выполняется оператор, следующий за Case.
Пример 1.
Case 2 * I - KOf{Cелектор целочисленного типа} -100 .. -1: Writeln('<0'); 0: Writeln ('=0'); 1 .. 100: Writeln('>0') End
Пример 2.
Case A Of 'A' .. 'Z': X := 0; '#', '_', ':': X := 1;селектортипа Char '+': X := 2 Else: X := 3 End
Вопрос №14 Библиотечные модули пользователя.
Это результат трансляции в режиме Compileструктурной единицы Unit с установленной директивой Destination=Disk. Введение Tpuфайлов позволяет создавать программы, превышающие 64КБ. Модули являются основой модульного программирования, в отличие от подпрограммы модуль не может быть запущен самостоятельно. Модули компилируются независимо от использующей их программы. Чтобы подключить модуль к программе необходимо указать его в USES.
{заголовок подпрог с указанием используемых параметров}
procedure … function…
Implementation
<описание лок. типов, переменных, процедур и функций, описанных в секции interfaceи внутр. проц. и функц.>
begin <операторы> end.
<Заголовок модуля>::=→Unit→<имя_модуля>
Имя должно совпадать с именем файла, где хранится исх. текст модуля.
В секции Interfaceописываются внешние элементы (глоб. типы, константы, переменные, подпрогр.)
Основная программа и другимодули имеют доступ к элементам описанных в интерфейсной части.
<Интерфейсный раздел>::=
<раздел_заголовков>::=
Описание заголовков в интерфейсной секции является аналогом опережающего описания.
Если при объявлении глобальных элементов используются константы или типы введенные в других модулях, то эти модули должны быть перечислены в директиве USESпосле Interface. Здесь рекомендуется указывать только те модули, которые необходимы только в этой секции.
Секция Implementation. В этой секции описываются локальные элементы. Здесь же содержаться тела процедур и функций, заголовки которой описаны в секции Interface. Для данных процедур и функций заголовок содержит только имя.
<раздел_реализации>::=
В секции реализации содержится полное описание внутренних процедур и функций модуля.
Внутренние подпрограммы недоступны вызывающей программе или другим модулям. Все элементы, описанные в интерфейсной секции доступны в секции реализации.
Если в телах подпрогр., или при объявлениях в разделе реализации испольуются имена, объявленные в других модулях и эти модули не попали в директиву uses раздела interface, то они перечисляются в директиве usesпосле implementation.
<раздел инициализации>::=
В секции инициализации содержаться операторы, которые выполняются до операторов из тела программы. <раздел_инициал.> ::= →END---------------------------------→begin→<операт.>---- →end→
--------→<раздел_операт.>------- ------- ;←-----
.
!!!пример см. в вопросе№15!!!
Вопрос №15 Организация связи главной программы с библиотечными модулями пользователя.
Если программный модуль использует несколько модулей UNIT, то их части инициализируются в порядке их перечисления в USESпрограммы.
Все разделы модуля Unitявляются необязательными, но служебные слова, начинающие модуль UNITдолжны присутствовать обязательно.
Unit Hollow;
Interface
Implementation
End.
Пример(может быть неточным, писался с моего конспекта -):
Unit U1;
Interface
Uses DOS;
Const MyValue=724 ;
Type Ned=(pon,vtor...) ;
Var D: Ned;
Procedure Set_Ned(var den: ned);
Function Weekend: Boolean;
Implementation
Uses U2;
Var D1,D2,D3: ned;
Procedure set_ned;
Begin <телопроцедуры> end;
Function weekend
Begin <телоф-ции> end;
Begin
D:=pon;
End.
Program MAIN;
Uses U1;
Var x: ned;
Begin
---------
set_ned(x);
---------
end.
Файл U1.pas должен быть скомпилирован с дир. компилятора destination=diskU1.tpu
Чтобы найти модуль, указанный в предложении Usesпрограммой компилятор вначале просматривает turbo.tpl . Если нужного модуля здесь нет, то он ищется в текущем каталоге. Затем он ищется в каталоге, заданном Options\directories \units\directories
Если файл модуля находится в другом месте или имя файла не совпадает с именем модуля, то компилятору следует передать нужное имя файла с путем, с помощью дирекивы компилятора {$N<имя_файла>}. Данная директива помещается непосредственно перед именем модуля в предложении Uses.
Вопрос №16 Особенности работы с библиотечными модулями.
1) Перечисление модулей происходит в порядке их перечисления слева направо, в этом же порядке срабатывают разделы инициализации модулей. Инициализация происходит только при работе программы. При подключении модуля к модулю инициализация не выполняется. Порядок подключения модулей влияет на доступность типов данных, процедур и функций. Чтобы обеспечить доступ к содержимому другого модуля используются составные имена(U1.Ned, U1.D, U1.Set_Ned)
Решение проблемы закольцованности:
Зависит от того, в каком месте проги наблюдается закольцованность. Если оба модуля подключают друг друга в разделе реализации, то закольцованность автоматически разрешается компилятором.
2) Если хотя бы один модуль подключает другой в разделе interface, то проблема закольцованности должна разрешаться самим программистом. В этом случае используется третий модуль, и в него помещаются все типы, переменные, подпроги и затем они удаляются из первых 2-ух модулей и к данным модулям подключается 3-ий.
Достоинства:
а)Наличие модулей позволяет использовать модульное программирование.
б)Модули компилируются независимо друг от друга. При подключении они заново не компилируются.
в)Наличие модулей позволяет создавать большие программы с суммарным размером исполняемого кода больше 64кб.