Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11642
Последний выпуск: 19.06.2015

Лекции по программированию на Паскале

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=====-   ¦   ¦=====¦
                      pTop     L-->¦     ¦
                                   L=====-

                     г=====¬       г=====¬
  pTop^.pNext:=NIL;  ¦  *--¦---¬   ¦     ¦
                     L=====-   ¦   ¦=====¦
                      pTop     L-->¦ NIL ¦
                                   L=====-

                     г=====¬       г=====¬
  pTop^.D:=D1;       ¦  *--¦---¬   ¦ D1  ¦
                     L=====-   ¦   ¦=====¦
                      pTop     L-->¦ NIL ¦
                                   L=====-

    Последний оператор или группа операторов записывает  содержимое
поля данных первой компоненты.
    Добавление компоненты в стек призводится с использованием вспо-
могательного указателя:
    
                     г=====¬       г=====¬       г=====¬
  New(pAux);         ¦  *--¦---¬   ¦     ¦   ----¦--*  ¦
                     L=====-   ¦   ¦=====¦   ¦   L=====-
                      pTop     ¦   ¦     ¦<---    pAux
                               ¦   L=====-
                               ¦
                               ¦   г=====¬
                               ¦   ¦ D1  ¦
                               ¦   ¦=====¦
                               L-->¦ NIL ¦
                                   L=====-


                     г=====¬       г=====¬       г=====¬
  pAux^.pNext:=pTop; ¦  *--¦---¬   ¦     ¦   ----¦--*  ¦
                     L=====-   ¦   ¦=====¦<---   L=====-
                      pTop     ¦   ¦  *--¦-¬      pAux
                               ¦   L=====- ¦
                               ¦           ¦
                               ¦   г=====¬ ¦
                               ¦   ¦ D1  ¦ ¦
                               ¦   ¦=====¦ ¦
                               L-->¦ NIL ¦<-
                                   L=====-


                     г=====¬       г=====¬       г=====¬
  pTop:=pAux;        ¦  *--¦---¬   ¦     ¦   ----¦--*  ¦
                     L=====-   ¦   ¦=====¦<---   L=====-
                      pTop     L-->¦  *--¦-¬      pAux
                                   L=====- ¦
                                           ¦
                                   г=====¬ ¦
                                   ¦ D1  ¦ ¦
                                   ¦=====¦ ¦
                                   ¦ NIL ¦<-
                                   L=====-

                     г=====¬       г=====¬
  pTop^.D:=D2;       ¦  *--¦---¬   ¦ D2  ¦
                     L=====-   ¦   ¦=====¦
                      pTop     L-->¦  *--¦-¬
                                   L=====- ¦
                                           ¦
                                   г=====¬ ¦
                                   ¦ D1  ¦ ¦
                                   ¦=====¦ ¦
                                   ¦ NIL ¦<-
                                   L=====-

   Добавление последующих компонент производится аналогично.
   Рассмотрим процесс выборки компонент из стека. Пусть к моменту на-
чала выборки стек содержит три компоненты:
                     г=====¬       г=====¬
                     ¦  *--¦---¬   ¦ D3  ¦
                     L=====-   ¦   ¦=====¦
                      pTop     L-->¦  *--¦-¬
                                   L=====- ¦
                                           ¦
                                   г=====¬ ¦
                                   ¦ D2  ¦ ¦
                                   ¦=====¦ ¦
                                 --¦--*  ¦<-
                                 ¦ L=====-
                                 ¦
                                 ¦ г=====¬
                                 ¦ ¦ D1  ¦
                                 ¦ ¦=====¦
                                 L>¦ NIL ¦
                                   L=====-

   Первый оператор или группа операторов осуществляет  чтение  данных
из компоненты - вершины стека. Второй оператор изменяет значение ука-
зателя вершины стека:

                         г=====¬       г=====¬
  D3:=pTop^.D;           ¦  *--¦---¬   ¦ D3  ¦
  pTop:=pTop^.pNext;     L=====-   ¦   ¦=====¦
                          pTop     ¦   ¦     ¦
                                   ¦   L=====-
                                   ¦
                                   ¦   г=====¬
                                   ¦   ¦ D2  ¦
                                   ¦   ¦=====¦
                                   L-->¦  *--¦-¬
                                       L=====- ¦
                                               ¦
                                       г=====¬ ¦
                                       ¦ D1  ¦ ¦
                                       ¦=====¦ ¦
                                       ¦ NIL ¦<-
                                       L=====-

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

   Пример. Составить программу,  которая формирует стек,  добавляет в
него произвольное количество компонент, а затем читает все компоненты
и выводит их на экран дисплея,  В качестве данных взять строку симво-
лов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка
символов END.
    
 Program STACK;
  uses Crt;
  type
   Alfa= String[10];
   PComp= ^Comp;
   Comp= Record
           sD: Alfa;
           pNext: PComp
          end;
  var
   pTop: PComp;
   sC: Alfa;
  Procedure CreateStack(var pTop: PComp; var sC: Alfa);
   begin
    New(pTop);
    pTop^.pNext:=NIL;
    pTop^.sD:=sC
   end;
  Procedure AddComp(var pTop: PComp; var sC: Alfa);
   var pAux: PComp;
   begin
    NEW(pAux);
    pAux^.pNext:=pTop;
    pTop:=pAux;
    pTop^.sD:=sC
   end;
  Procedure DelComp(var pTop: PComp; var sC:ALFA);
   begin
    sC:=pTop^.sD;
    pTop:=pTop^.pNext
   end;
  begin
   Clrscr;
   writeln('  ВВЕДИ СТРОКУ ');
   readln(sC);
   CreateStack(pTop,sC);
   repeat
    writeln('  ВВЕДИ СТРОКУ ');
    readln(sC);
    AddComp(pTop,sC)
   until sC='END';
   writeln('****** ВЫВОД  РЕЗУЛЬТАТОВ ******');
   repeat
    DelComp(pTop,sC);
    writeln(sC);
   until pTop = NIL
  end.
                                     
39.   О Ч Е Р Е Д И
    
   Очередью называется динамическая структура данных, добавление ком-
поненты в которую производится в один конец, а выборка осуществляется
с другого конца. Очередь работает по принципу:

        FIFO (First-In, First-Out) -

поступивший первым, обслуживается первым.
   Для формирования очереди и работы с ней необходимо иметь три пере-
менные типа указатель,  первая из которых определяет начало  очереди,
вторая - конец очереди, третья - вспомогательная.
   Описание компоненты очереди и переменных типа указатель дадим сле-
дующим образом:
    
  type
   PComp=^Comp;
   Comp=record
         D:T;
         pNext:PComp
        end;
  var
   pBegin, pEnd, pAux: PComp;

где pBegin - указатель начала очереди, pEnd - указатель конца  очере-
ди, pAux - вспомогательный указатель.
   Тип Т определяет тип данных компоненты очереди.
   Начальное формирование очереди выполняется следующими операторами:


                       г=====¬       г=====¬       г=====¬
 New(pBegin);          ¦  *--¦---¬   ¦     ¦       ¦     ¦
                       L=====-   ¦   ¦=====¦       L=====-
                       pBegin    L-->¦     ¦         pEnd
                                     L=====-


                       г=====¬       г=====¬       г=====¬
 pBegin^.pNext:=NIL;   ¦  *--¦---¬   ¦     ¦       ¦     ¦
                       L=====-   ¦   ¦=====¦       L=====-
                       pBegin    L-->¦ NIL ¦         pEnd
                                     L=====-


                       г=====¬       г=====¬       г=====¬
 pBegin^.D:=D1;        ¦  *--¦---¬   ¦ D1  ¦       ¦     ¦
                       L=====-   ¦   ¦=====¦       L=====-
                       pBegin    L-->¦ NIL ¦         pEnd
                                     L=====-


                       г=====¬       г=====¬       г=====¬
 pEnd:=pBegin;         ¦  *--¦---¬   ¦ D1  ¦   ----¦--*  ¦
                       L=====-   ¦   ¦=====¦   ¦   L=====-
                       pBegin    L-->¦ NIL ¦<---     pEnd
                                     L=====-


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

 New(pAux);
    
г=====¬       г=====¬       г=====¬       г=====¬       г=====¬
¦  *--¦---¬   ¦ D1  ¦   ----¦--*  ¦       ¦     ¦   ----¦--*  ¦
L=====-   ¦   ¦=====¦   ¦   L=====-       ¦=====¦   ¦   L=====-
pBegin    L-->¦ NIL ¦<---    pEnd         ¦     ¦<---     pAux
              L=====-                     L=====-

 pAux^.pNext:=NIL;
    
г=====¬       г=====¬       г=====¬       г=====¬       г=====¬
¦  *--¦---¬   ¦ D1  ¦   ----¦--*  ¦       ¦     ¦   ----¦--*  ¦
L=====-   ¦   ¦=====¦   ¦   L=====-       ¦=====¦   ¦   L=====-
pBegin    L-->¦ NIL ¦<---    pEnd         ¦ NIL ¦<---     pAux
              L=====-                     L=====-
 pBegin^.pNext:=pAux;
    
г=====¬       г=====¬       г=====¬       г=====¬       г=====¬
¦  *--¦---¬   ¦ D1  ¦   ----¦--*  ¦       ¦     ¦   ----¦--*  ¦
L=====-   ¦   ¦=====¦   ¦   L=====-       ¦=====¦   ¦   L=====-
pBegin    L-->¦  *  ¦<---    pEnd         ¦ NIL ¦<---     pAux
              L=====-                     L=====-
                 ¦                           ^
                 ¦                           ¦
                 L----------------------------
 pEnd:=pAux;

г=====¬       г=====¬       г=====¬       г=====¬       г=====¬
¦  *--¦---¬   ¦ D1  ¦       ¦  *--¦---¬   ¦     ¦   ----¦--*  ¦
L=====-   ¦   ¦=====¦       L=====-   ¦   ¦=====¦   ¦   L=====-
pBegin    L-->¦  *  ¦        pEnd     L-->¦ NIL ¦<---     pAux
              L=====-                     L=====-
                 ¦                           ^
                 ¦                           ¦
                 L----------------------------

 pEnd^.D:=D2;
    
г=====¬       г=====¬                     г=====¬       г=====¬
¦  *--¦---¬   ¦ D1  ¦                     ¦ D2  ¦   ----¦--*  ¦
L=====-   ¦   ¦=====¦                     ¦=====¦   ¦   L=====-
pBegin    L-->¦  *--¦-------------------->¦ NIL ¦<---    pEnd
              L=====-                     L=====-
                                              
                                              


   Добавление последующих компонент производится аналогично.
    
   Выборка компоненты  из  очереди  осуществляется из начала очереди,
одновременно компонента исключается из очереди.  Пусть в  памяти  ЭВМ
сформирована очередь, состоящая из трех элементов:


г=====¬       г=====¬       г=====¬       г=====¬       г=====¬
¦  *--¦---¬   ¦ D1  ¦       ¦ D2  ¦       ¦ D3  ¦   ----¦--*  ¦
L=====-   ¦   ¦=====¦       ¦=====¦       ¦=====¦   ¦   L=====-
pBegin    L-->¦  *--¦------>¦  *--¦------>¦ NIL ¦<---     pEnd
              L=====-       L=====-       L=====-


   Выборка компоненты выполняется следующими операторами:

 D1:=pBegin^.D;
 pBegin:=pBegin^.pNext;
    
г=====¬       г=====¬       г=====¬       г=====¬       г=====¬
¦  *--¦---¬   ¦ D1  ¦       ¦ D2  ¦       ¦ D3  ¦   ----¦--*  ¦
L=====-   ¦   ¦=====¦       ¦=====¦       ¦=====¦   ¦   L=====-
pBegin    ¦   ¦     ¦   --->¦  *--¦------>¦ NIL ¦<---     pEnd
          ¦   L=====-   ¦   L=====-       L=====-
          ¦             ¦
          L--------------
    
   Пример. Составить программу,  которая формирует очередь, добавляет
в нее произвольное количество компонент, а затем читает все компонен-
ты и выводит их на экран дисплея. В качестве данных взять строку сим-
волов. Ввод    данных  - с клавиатуры дисплея,  признак конца ввода -
строка символов END.

  Program QUEUE;
  uses Crt;
  type
   Alfa= String[10];
   PComp= ^Comp;
   Comp= record
          sD:Alfa;
          pNext:PComp
         end;
  var
   pBegin, pEnd: PComp;
   sC: Alfa;
  Procedure CreateQueue(var pBegin,pEnd: PComp; var sC: Alfa);
   begin
    New(pBegin);
    pBegin^.pNext:=NIL;
    pBegin^.sD:=sC;
    pEnd:=pBegin
   end;
  Procedure AddQueue(var pEnd:PComp; var sC:Alfa);
   var pAux: PComp;
   begin
    New(pAux);
    pAux^.pNext:=NIL;
    pEnd^.pNext:=pAux;
    pEnd:=pAux;
    pEnd^.sD:=sC
   end;
  Procedure DelQueue(var pBegin: PComp; var sC: Alfa);
   begin
    sC:=pBegin^.sD;
    pBegin:=pBegin^.pNext
   end;
  begin
   Clrscr;
   writeln(' ВВЕДИ СТРОКУ ');
   readln(sC);
   CreateQueue(pBegin,pEnd,sC);
   repeat
    writeln(' ВВЕДИ СТРОКУ ');
    readln(sC);
    AddQueue(pEnd,sC)
   until sC='END';
   writeln(' ***** ВЫВОД РЕЗУЛЬТАТОВ *****');
   repeat
    DelQueue(pBegin,sC);
    writeln(sC);
   until pBegin=NIL
  end.

Часть 1 | Часть 2 | Часть 3 | Часть 4 | Часть 5 | Часть 6

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 

Комментарии

1.
25K
02 января 2007 года
sletor
0 / / 02.01.2007
+1 / -1
Мне нравитсяМне не нравится
2 января 2007, 20:24:00
спасибо большое за лекции про pascal
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог