Реферат: Основные понятия алгоритмического языка

лены также операторы обращения к процедурам:

   ReadLn(T) - пропускает строку до начала следующей;

   WriteLn(T) -  завершает  строку файла,  в которую производится за-

пись, признаком конца строки и переходит к началу следующей.

   Для работы с текстовыми файлами введена расширенная форма операто-

ров ввода и вывода. Оператор

    Read(T,X1,X2,...XK)

 эквивалентен группе операторов

    begin

      Read(T,X1);

      Read(T,X2);

      ...........

      Read(T,XK)

    end;

   Здесь Т - текстовый файл, а переменные Х1, Х2,...ХК могут быть ли-

бо  переменными  целого, действительного или символьного  типа,  либо

строкой. При чтении значений переменных из файла они преобразуются из

текстового представления в машинное.

   Оператор

    Write(T,X1,X2,...XK)

эквивалентен группе операторов

    begin

      Write(T,X1);

      Write(T,X2);

      ...........

      Write(T,XK)

    end;

   Здесь Т  -  также текстовый файл,  но переменные Х1,Х2,...ХК могут

быть целого, действительного, символьного, логического типа или стро-

кой. При записи значений переменных в файл они преобразуются из внут-

реннего представления в текстовый.

   К текстовым файлам относятся стандартные файлы INPUT, OUTPUT.

   Рассмотренные ранее операторы ввода - вывода являются частным слу-

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

дартные файлы ввода - вывода INPUT, OUTPUT.

   Работа с этими файлами имеет особенности:

   -имена этих файлов в списках ввода - вывода не указываются;

   -применение процедур  Reset,  Rewrite и Close к стандартным файлам

ввода - вывода запрещено;

   -для работы с файлами INPUT,  OUTPUT введена разновидность функции

EOLn без параметров.

   TURBO PASCAL вводит дополнительные процедуры и функции, применимые

только к текстовым файлам,  это SetTextBuf,  Append, Flush, SeekEOLn,

SeekEOF.

   Процедура SetTextBuf( var f: Text; var Buf; BufSize: Word ) служит

для увеличения  или уменьшения буфера ввода - вывода текстового файла

f. Значение  размера буфера для текстовых файлов по  умолчанию  равно

128 байтам.  Увеличение размера буфера сокращает количество обращений

к диску.  Рекомендуется изменять разиер буфера до открытия файла. Бу-

фер файла начнется с первого байта переменной Buf.  Размер буфера за-

дается в необязательном параметре BufSize,  а если этот параметр  от-

сутствует, размер буфера определяется длиной переменной Buf.

   Процедура Append( var f:  Text )  служит для специального открытия

выходных файлов. Она применима к уже существующим физическим файлам и

открывает из для дозаписи в конец файла.

   Процедура Flush(  var  f: Text )  применяется  к открытым выходным

файлам. Она  принудительно записывает данные из буфера в файл незави-

симо от степени его заполнения.

   Функция SeekEOLn( var f: Text ): Boolean возвращает значение True,

если до конца строки остались только пробелы.

   Функция SeekEOF( var f:  Text ): Boolean возвращает значение True,

если до конца файла остались строки, заполненные пробелами.

32.   К О М П О Н Е Н Т Н Ы Е   Ф А Й Л Ы

   Компонентный или типизированный файл - это файл с объявленным  ти-

пом его компонент. Компонентные файлы состоят из машинных представле-

ний значений переменных,  они хранят данные в том же виде,  что и па-

мять ЭВМ.

   Описание величин файлового типа имеет вид:

         type M= File Of T;

где М - имя файлового типа, Т - тип компоненты. Например:

         type

           FIO= String[20];

           SPISOK=File of FIO;

         var

           STUD, PREP: SPISOK;

   Здесь STUD,   PREP  - имена файлов,  компонентами которых являются

строки.

   Описание файлов можно задавать в разделе описания переменных:

         var

            fsimv: File of Char;

            fr: File of Real;

   Компонентами файла могут быть все скалярные типы,  а из структури-

рованных - массивы, множества, записи. Практически во всех конкретных

реализациях языка ПАСКАЛЬ конструкция "файл файлов" недопустима.

   Все операции  над  компонентными  файлами  производятся  с помощью

стандартных процедур:

   Reset, Rewrite, Read, Write, Close.

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

     Read(f,X);

     Write(f,X);

   где f - имя логического файла,  Х - либо переменная,  либо массив,

либо строка,  либо множество, либо запись с таким же описанием, какое

имеет компонента файла.

    Выполнение процедуры  Read(f,X)  состоит в чтении с внешнего уст-

ройства одной компоненты файла и запись ее в X.  Повторное применение

процедуры Read(f,X) обеспечит чтение следующей компоненты файла и за-

пись ее в X.

   Выполнение процедуры Write(f,X) состоит в записи X на внешнее уст-

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

обеспечит запись X как следующей компоненты файла.

   Для работы  с компонентными файлами введена расширенная форма опе-

раторов ввода и вывода:

    Read(f,X1,X2,...XK)

    Write(f,X1,X2,...XK)

   Здесь f - компонентный файл, а переменные Х1, Х2,...ХК должны

иметь тот-же тип, что и объявленный тип компонент файла f.

33.   Б Е С Т И П О В Ы Е   Ф А Й Л Ы

   Бестиповые файлы позволяют записывать на диск произвольные участки

пвмяти ЭВМ и считывать их с диска в память.  Операции обмена с бести-

повыми   файлами   осуществляется   с  помощью  процедур  BlokRead  и

BlockWrite. Кроме  того,  вводится расширенная форма процедур Reset и

Rewrite. В остальном принципы работы остаются такими же, как и с ком-

понентными файлами.

   Перед использованием логический файл

   var  f: File;

должен быть  связан  с  физическим с помощью процедуры Assign.  Далее

файл должен быть открыт для чтения или для  записи  процедурой  Reset

или Rewrite, а после окончания работы закрыт процедурой Close.

   При открытии файла длина буфера устанавливается по умолчанию в 128

байт. TURBO  PASCAL  позволяет изменить размер буфера ввода - вывода,

для чего следует открывать файл расширенной записью процедур

   Reset(var f: File; BufSize: Word )

или

   Rewrite(var f: File; BufSize: Word )

   Параметр BufSize задает число байтов, считываемых из файла или за-

писываемых в него за одно обращение. Минимальное значение BufSize - 1

байт, максимальное - 64 К байт.

   Чтение данных из бестипового файла осуществляется процедурой

  BlockRead( var f: File; var X; Count: Word; var QuantBlock: Word );

   Эта процедура осуществляет за одно обращение чтение в переменную X

количества блоков,  заданное параметром Count,  при этом длина  блока

равна длине  буфера.  Значение Count не может быть меньше 1.  За одно

обращение нельзя прочесть больше, чем 64 К байтов.

   Необязательный параметр  QuantBlock возвращает число блоков (буфе-

ров), прочитанных текущей операцией BlockRead. В случае успешного за-

вершения операции чтения QuantBlock = Count, в случае аварийной ситу-

ации параметр QuantBlock будет  содержать  число  удачно  прочитанных

блоков. Отсюда  следует,   что  с  помощью параметра QuantBlock можно

контролировать правильность выполнения операции чтения.

   Запись данных в бестиповой файл выполняется процедурой

   BlockWrite( var f: File; var X; Count: Word; var QuantBlock: Word );

которая осуществляет  за  одно обращение запись из переменной X коли-

чества блоков,  заданное параметром Count, при этом длина блока равна

длине буфера.

   Необязательный параметр  QuantBlock возвращает число блоков (буфе-

ров), записанных успешно текущей операцией BlockWrite.

34.  П О С Л Е Д О В А Т Е Л Ь Н Ы Й   И   П Р Я М О Й

Д О С Т У П

   Смысл последовательного  доступа  заключается в том,  что в каждый

момент времени доступна лишь одна компонента из  всей  последователь-

ности. Для  того,  чтобы обратиться (получить доступ)  к компоненте с

номером К,  необходимо просмотреть от начала файла К-1 предшествующую

компоненту. После обращения к компоненте с номером К можно обращаться

к компоненте с номером К+1. Отсюда следует, что процессы формирования

(записи) компонент   файла и просмотра (чтения)  не могут произвольно

чередоваться. Таким  образом, файл вначале строится при помощи после-

довательного добавления  компонент в конец,  а затем может последова-

тельно просматриваться от начала до конца.

   Рассмотренные ранее  средства работы с файлами обеспечивают после-

довательный доступ.

   TURBO PASCAL  позволяет применять к компонентным и бестиповым фай-

лам, записанным  на диск, способ прямого доступа. Прямой доступ озна-

чает возможность   заранее определить в файле блок,  к которому будет

применена операция ввода - вывода.  В случае бестиповых  файлов  блок

равен размеру буфера,  для компонентных файлов блок - это одна компо-

нента файла.

   Прямой доступ  предполагает,  что файл представляет собой линейную

последовательность блоков.  Если файл содержит n блоков, то они нуме-

руются от 1 через 1 до n.  Кроме того, вводится понятие условной гра-

ницы между блоками, при этом условная граница с номером 0 расположена

перед блоком с номером 1,  граница с номером 1 расположена перед бло-

ком с номером 2 и,  наконец,  условная граница с номером n  находится

после блока с номером n.

   Реализация прямого доступа осуществляется с помощью функций и про-

цедур FileSize, FilePos, Seek и Truncate.

   Функция FileSize( var f ):  Longint возвращает количество блоков в

открытом файле f.

   Функция FilePos( var f ):  Longint возвращает  текущую  позицию  в

файле f. Позиция в файле - это номер условной границы. Для только что

открытого файла текущей позицией будет граница с номером 0.  Это зна-

чит, что  можно записать или прочесть блок с номером 1.  После чтения

или записи первого блока текущая позиция переместится  на  границу  с

номером 1,  и можно будет обращаться к ьлоку с номером 2. После проч-

тения последней записи значение FilePos равно значению FileSize.

   Процедура Seek( var f; N: Longint) обеспечивает назначение текущей

позиции в файле (позиционирование).  В параметре N должен быть  задан

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

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

необходимо задать значение N, равное 3. Процедура Seek работает с от-

крытыми файлами.

   Процедура Truncate( var f )  устанавливает в текущей позиции приз-

нак конца файла и удаляет (стирает) все последующие блоки.

   Пример. Пусть на НМД имеется текстовый файл ID.DAT, который содер-

жит числовые   значения  действительного  типа  по два числа в каждой

строке - значения аргумента и функции соответственно.  Количество пар

чисел не более 200.  Составить программу, которая читает файл, значе-

ния аргумента и функции записывает в одномерные массивы, подсчитывает

их количество,    выводит на экран дисплея и записывает в файл компо-

нентного типа RD.DAT.

   Program F;

    var

     rArg, rF: Array[1..200] of Real;

       inf: Text;

       outf: File of Real;

       n, l: Integer;

    begin

      Assign(inf,'ID.DAT');

      Assign(outf,'RD.DAT');

      Reset(inf);

      Rewrite(outf);

      n:=0;

      while not EOF(inf) do

        begin

          n:=n+1;

          ReadLn(inf,rArg[n],rF[n])

        end;

      for l:=1 to n do

       begin

        WriteLn(l:2,rArg[l]:8:2,rF[l]:8:2);

        Write(outf,rArg[l], rF[l]);

       end;

      close(outf)

    end.

35.   У К А З А Т Е Л И.

   Операционная система MS - DOS все адресуемое пространство делит на

сегменты. Сегмент - это участок памяти размером 64 К байт.  Для зада-

ния адреса необходимо определить адрес начала сегмента и смещение от-

носительно начала сегмента.

   В TURBO  PASCAL определен адресный тип Pointer - указатель.  Пере-

менные типа Pointer

   var p: Pointer;

содержат адрес какого - либо элемента программы и занимают  4  байта,

при этом   адрес хранится как два слова,  одно из них определяет сег-

мент, второе - смещение.

   Переменную типа указатель можно описать другим способом.

  type NameType= ^T;

  var p: NameType;

   Здесь p - переменная типа указатель, связанная с типом Т с помощью

имени типа NameType.  Описать переменную типа указатель можно  непос-

редственно в разделе описания переменных:

   var p: ^T;

   Необходимо различать  переменную  типа указатель и переменную,  на

которую этот указатель ссылается.  Например если p - ссылка на  пере-

менную типа Т, то p^ - обозначение этой самой переменной.

   Для переменных  типа  указатель  введено стандартное значение NIL,

которое означает,  что указатель не ссылается ни  к  какому  объекту.

Константа NIL используется для любых указателей.

   Над указателями не определено никаких операций,  кроме проверки на

равенство и неравенство.

   Переменные типа указатель могут быть записаны в левой части опера-

тора присваивания,  при этом в правой  части  может  находиться  либо

функция определения адреса Addr(X), либо выражение @ X, где @ - унар-

ная операция взятия адреса,  X - имя переменной любого типа,   в  том

числе процедурного.

   Переменные типа указатель не могут быть элементами списка ввода  -

вывода.

36.   Д И Н А М И Ч Е С К И Е   П Е Р Е М Е Н Н Ы Е

   Статической переменной (статически размещенной) называется описан-

ная явным образом в программе переменная, обращение к ней осуществля-

ется по имени.  Место в памяти для размещения статических  переменных

определяется при компиляции программы.

   В отличие от таких статических переменных в программах, написанных

на языке ПАСКАЛЬ,  могут быть созданы динамические переменные. Основ-

ное свойство динамических переменных заключается в том,  что они соз-

даются и   память  для  них выделяется во время выполнения программы.

Размещаются динамические переменные  в  динамической  области  памяти

(heap - области).

   Динамическая переменная не указывается явно в описаниях переменных

и к   ней нельзя обратиться по имени.  Доступ к таким переменным осу-

ществляется с помощью указателей и ссылок.

   Работа с динамической областью памяти в TURBO PASCAL реализуется с

помощью процедур и функций New,  Dispose,  GetMem,   FreeMem,   Mark,

Release, MaxAvail, MemAvail, SizeOf.

   Процедура New( var p:  Pointer ) выделяет место в динамической об-

ласти памяти   для  размещения  динамической переменной p^ и ее адрес

присваивает указателю p.

   Процедура Dispose(  var p:  Pointer )  освобождает участок памяти,

выделенный для размещения динамической переменной процедурой  New,  и

значение указателя p становится неопределенным.

   Проуедура GetMem( var p:  Pointer; size:  Word )  выделяет участок

памяти в   heap - области,  присваивает адрес его начала указателю p,

размер участка в байтах задается параметром size.

   Процедура FreeMem( var p:  Pointer; size: Word ) освобождает учас-

ток памяти,  адрес начала которого определен указателем p, а размер -

параметром size. Значение указателя p становится неопределенным.

   Процедура Mark( var p:  Pointer )  записывает в указатель p  адрес

начала участка свободной динамической памяти на момент ее вызова.

   Процедура Release( var p: Pointer ) освобождает участок динамичес-

кой памяти,   начиная с адреса,  записанного в указатель p процедурой

Mark,  то-есть,  очищает ту динамическую память,  которая была занята

после вызова процедуры Mark.

   Функция MaxAvail: Longint возвращает длину в байтах самого длинно-

го свободного участка динамической памяти.

   Функция MemAvail:  Longint полный объем свободной динамической па-

мяти в байтах.

   Вспомогательная функция SizeOf( X ):  Word возвращает объем в бай-

тах, занимаемый  X, причем X может быть либо именем переменной любого

типа, либо именем типа.

   Рассмотрим некоторые примеры работы с указателями.

    var

     p1, p2: ^Integer;

   Здесь p1 и p2 - указатели или пременные ссылочного типа.

    p1:=NIL;  p2:=NIL;

   После выполнения этих операторов присваивания указатели p1 и p2 не

будут ссылаться ни на какой конкретный объект.

    New(p1);  New(p2);

   Процедура New(p1) выполняет следующие действия:

   -в памяти ЭВМ выделяется участок для  размещения  величины  целого

типа;

   -адрес этого участка присваивается переменной p1:

                г=====¬          г=====¬

                ¦  *--¦--------->¦     ¦

                L=====-          L=====-

                  p1               p1^

   Аналогично, процедура New(p2)  обеспечит выделение участка памяти,

адрес которого будет записан в p2:

                г=====¬          г=====¬

                ¦  *--¦--------->¦     ¦

                L=====-          L=====-

                  p2               p2^

   После выполнения операторов присваивания

        p1^:=2;   p2^:=4;

в выделенные  участки  памяти  будут записаны значения 2 и 4 соответ-

ственно:

                г=====¬          г=====¬

                ¦  *--¦--------->¦  2  ¦

                L=====-          L=====-

                  p1               p1^

                г=====¬          г=====¬

                ¦  *--¦--------->¦  4  ¦

                L=====-          L=====-

                  p2               p2^

   В результате выполнения оператора присваивания

       p1^:=p2^;

в  участок памяти,  на который ссылается указатель p1, будет записано

значение 4:

                г=====¬          г=====¬

                ¦  *--¦--------->¦  4  ¦

                L=====-          L=====-

                  p1               p1^

                г=====¬          г=====¬

                ¦  *--¦--------->¦  4  ¦

                L=====-          L=====-

                  p2               p2^

   После выполнения оператора присваивания

      p2:=p1;

оба указателя будут содержать адрес первого участка памяти:

                г=====¬          г=====¬

                ¦  *--¦--------->¦  4  ¦

                L=====-      --->L=====-

                  p1         ¦   p1^ p2^

                             ¦

                г=====¬      ¦

                ¦  *--¦-------

                L=====-

                  p2

   Переменные p1^, p2^ являются динамическими, так как память для них

выделяется в процессе выполнения программы с помощью процедуры New.

   Динамические переменные  могут входить в состав выражений,  напри-

мер:

      p1^:=p1^+8;    Write('p1^=',p1^:3);

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

 Program DemoPointer;

  var p1,p2,p3:^Integer;

  begin

   p1:=NIL;  p2:=NIL;  p3:=NIL;

   New(p1);  New(p2);  New(p3);

   p1^:=2;  p2^:=4;

   p3^:=p1^+Sqr(p2^);

   writeln('p1^=',p1^:3,'  p2^=',p2^:3,'  p3^=',p3^:3);

   p1:=p2;

   writeln('p1^=',p1^:3,'  p2^=',p2^:3)

  end.

на экран дисплея будут выведены результаты:

p1^=  2  p2^=  4  p3^= 18

p1^=  4  p2^=  4

37.   Д И Н А М И Ч Е С К И Е    С Т Р У К Т У Р Ы

Д А Н Н Ы Х

   Структурированные типы данных,  такие, как массивы, множества, за-

писи, представляют   собой статические структуры,  так как их размеры

неизменны в течение всего времени выполнения программы.

   Часто требуется, чтобы структуры данных меняли свои размеры в ходе

решения задачи.   Такие структуры данных называются динамическими,  к

ним относятся стеки,  очереди, списки, деревья и другие. Описание ди-

намических структур  с помощью массивов,  записей и файлов приводит к

неэкономному использованию памяти ЭВМ и увеличивает время решения за-

дач.

   Каждая компонента любой динамической структуры представляет  собой

запись, содержащую   по крайней мере два поля:  одно поле типа указа-

тель, а  второе - для размещения данных.  В общем случае запись может

содержать не   один,  а несколько укзателей и несколько полей данных.

Поле данных может быть переменной,  массивом, множеством или записью.

   Для дальнейшего рассмотрения представим отдельную компоненту в ви-

де:

                               г=====¬

                               ¦  D  ¦

                               ¦=====¦

                               ¦  p  ¦

                               L=====-

где поле p - указатель;

    поле D - данные.

   Описание этой компоненты дадим следующим образом:

   type

    Pointer = ^Comp;

    Comp = record

            D:T;

            pNext:Pointer

         end;

здесь T - тип данных.

   Рассмотрим основные правила  работы  с  динамическими  структурами

данных типа стек, очередь и список, базируясь на приведенное описание

компоненты.

38.   С Т Е К И

   Стеком называется динамическая структура данных, добавление компо-

ненты в которую и исключение компоненты из  которой  производится  из

одного конца, называемого вершиной стека. Стек работает по принципу

      LIFO (Last-In, First-Out) -

поступивший последним, обслуживается первым.

   Обычно над стеками выполняется три операции:

    -начальное формирование стека (запись первой компоненты);

    -добавление компоненты в стек;

    -выборка компоненты (удаление).

   Для формирования стека и работы с ним необходимо иметь  две  пере-

менные типа указатель,  первая из которых определяет вершину стека, а

вторая - вспомогательная. Пусть описание этих переменных имеет вид:

    var pTop, pAux: Pointer;

где pTop - указатель вершины стека;

    pAux - вспомогательный указатель.

   Начальное формирование стека выполняется следующими операторами:

                     г=====¬       г=====¬

  New(pTop);         ¦  *--¦---¬   ¦     ¦

                     L=====-   ¦   ¦=====¦

Страницы: 1, 2, 3, 4, 5