Программирование

   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 - указатель  вершины стека;