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

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

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

нентного типа 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:

 

                ╔═════╗          ╔═════╗

                ║  *──║─────────>║     ║

                ╚═════╝          ╚═════╝

                  p1               p1^

 

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

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

  

                ╔═════╗          ╔═════╗

                ║  *──║─────────>║     ║

                ╚═════╝          ╚═════╝

                  p2               p2^

 

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

   

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

   

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

ственно:

   

                ╔═════╗          ╔═════╗

                ║  *──║─────────>║  2  ║

                ╚═════╝          ╚═════╝

                  p1               p1^

 

                ╔═════╗          ╔═════╗

                ║  *──║─────────>║  4  ║

                ╚═════╝          ╚═════╝

                  p2               p2^

   

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

   

       p1^:=p2^;

 

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

значение 4:

   

   

                ╔═════╗          ╔═════╗

                ║  *──║─────────>║  4  ║

                ╚═════╝          ╚═════╝

                  p1               p1^

 

                ╔═════╗          ╔═════╗

                ║  *──║─────────>║  4  ║

                ╚═════╝          ╚═════╝

                  p2               p2^

 

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

   

      p2:=p1;

 

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

   

                ╔═════╗          ╔═════╗

                ║  *──║─────────>║  4  ║

                ╚═════╝      ┌──>╚═════╝

                  p1         │   p1^ p2^

                             │

                ╔═════╗      │

                ║  *──║──────┘

                ╚═════╝

                  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  ║

                               ╚═════╝

где поле 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);         ║ *──║───┐   ║     ║

                     ╚═════╝   │   ║═════║

                      pTop     └──>║     ║

                                   ╚═════╝

 

                     ╔═════╗       ╔═════╗

  pTop^.pNext:=NIL;  ║  *──║───┐   ║     ║

                     ╚═════╝   │   ║═════║

                      pTop     └──>║ NIL ║

                                   ╚═════╝

 

                     ╔═════╗       ╔═════╗

  pTop^.D:=D1;       ║  *──║───┐   ║ D1  ║

                     ╚═════╝   │   ║═════║

                      pTop     └──>║ NIL ║

                                   ╚═════╝

 

    Последний оператор или  группа операторов записывает  содержимое

поля данных первой компоненты.

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

могательного указателя:

   

                     ╔═════╗       ╔═════╗       ╔═════╗

  New(pAux);         ║  *──║───┐   ║     ║   ┌───║──*  ║

                     ╚═════╝   │   ║═════║   │   ╚═════╝

                      pTop     │   ║     ║<──┘    pAux

                               │   ╚═════╝

                               │

                               │   ╔═════╗

                               │   ║ D1  ║

                               │   ║═════║

                               └──>║ NIL ║

                                   ╚═════╝

 

 

                     ╔═════╗       ╔═════╗       ╔═════╗

  pAux^.pNext:=pTop; ║  *──║───┐   ║     ║   ┌───║──*  ║

                     ╚═════╝   │   ║═════║<──┘   ╚═════╝

                      pTop     │   ║  *──║─┐      pAux

                               │   ╚═════╝ │