МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

``МАТИ'' — РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ им. К.Э. ЦИОЛКОВСКОГО


Кафедра ``Моделирование систем и информационные технологии''






















МОДЕЛИРОВАНИЕ СТРУКТУР ДАННЫХ СРЕДСТВАМИ

ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАММИРОВАНИЯ

С ДИНАМИЧЕСКИМ РАСПРЕДЕЛЕНИЕМ ПАМЯТИ




Методические указания к лабораторной работе по курсу

``Алгоритмические языки и технология программирования''













Составитель В.В. Лидовский













Москва 1998




Владимир Викторович Лидовский

МОДЕЛИРОВАНИЕ СТРУКТУР ДАННЫХ СРЕДСТВАМИ

ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАММИРОВАНИЯ

С ДИНАМИЧЕСКИМ РАСПРЕДЕЛЕНИЕМ ПАМЯТИ






Методические указания к лабораторной работе по курсу

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


























Редактор Соколова М.А.




















Под. в печ. Объем 1,75 п.л. Тираж 50 экз. Зак.

Ротапринт РГАТУ, Берниковская наб. 14



ВВЕДЕНИЕ

Настоящие методические указания предназначены для обеспечения учебного процесса студентов второго курса дневной формы обучения специальности 220200 "АСОИиУ" при выполнении лабораторной работы по курсу "Алгоритмические языки и технология программирования".

Цель лабораторной работы: изучить возможности средств объектно-ориентированного программирования для моделирования структур данных, используя динамическое управление распределением памяти.

1. СИСТЕМНЫЕ ТРЕБОВАНИЯ

Для выполнения лабораторной работы необходимы следующие системные компоненты: а)IBM PC совместимый компьютер, работающий под управлением операционной системы Linux; б)система программирования Free Pascal версии 0.95 или выше.

2. ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ И ЗАДАЧИ МОДЕЛИРОВАНИЯ

Объектно-ориентированный подход является идеальным для задач моделирования: каждая моделируемая сущность отображается в моделирующей программе отдельным объектом. Кроме того, объектно-ориентированный подход позволяет скрыть внутрипрограммный способ реализации моделируемой сущности от пользователя, предоставив ему только интересующие его в данной сущности компоненты: свойства сущности и методы воздействия на нее. При традиционном подходе к программированию моделей каждая такая сущность представляла собой совокупность часто очень большого числа разнообразных чисто программных, трудных для восприятия пользователем компонент (процедур, функций, массивов, указателей и т.п.), связь между которыми явно не обозначивалась.

3. СТРУКТУРЫ ДАННЫХ

При программировании наиболее часто используются следующие структуры данных: стеки, очереди, одно- и двунаправленные списки, деки и бинарные деревья. Каждая такая структура должна представляться в программе одной переменной объектного типа. Закрытая для доступа пользователя часть (private) такого объекта должна содержать переменные и подпрограммы, реализующие в совокупности машинное представление моделируемой структуры. Открытая для доступа пользователя часть (public) такого объекта должна содержать методы типичные для моделируемой структуры и, возможно, некоторые свойства. Важно чтобы использование как методов, так и свойств не приводило к нарушению целостности моделируемой структуры. Машинное представление структур должно использовать динамические переменные, т.к. моделироваться будут идеальные структуры, которые могут содержать неограниченное число элементов. Таким образом, в закрытой части объекта, представляющего моделируемую структуру, должны быть только несколько полей типа указателей и полей-счетчиков целого типа. В качестве данных моделируемые структуры должны хранить целые числа в диапазоне от 0 до 65535 (тип Word): каждый элемент структуры должен хранить одно такое число. Память под собственно объект нужно также выделить динамически (стандартной процедурой New).

3.1. Стеки

Стек — структура данных, доступ к элементам которой организуется по правилу "первый пришел — последним ушел" (алгоритм LIFO/FILO). Использование стека является непременным атрибутом любой вычислительной машины, т.к. стек необходим для организации вызовов подпрограмм и обработки прерываний. Стек можно представить как комбинацию циклического двунаправленного списка и указателя на элементы этого списка, который называется указателем стека. Стек должен реализовывать следующие операции:

    1. инициализация стека: создание циклического двунаправленного списка заданной длины и присвоение указателю стека указателя на начало этого списка;
    2. помещение в стек элемента: помещение в позицию указателя стека элемента и сдвиг указателя стека на одну позицию в сторону конца списка;
    3. извлечение элемента из стека: сдвиг указателя стека на одну позицию в сторону начала списка и извлечение из позиции указателя стека элемента;
    4. уничтожение стека.

Все перечисленные операции могут быть реализованы следующими методами, где StackPointer — указатель на текущий элемент, PList2 — указатель на двунаправленный список (объект, см. п. 3.5):

    
    Constructor TStack.Init (Size: Word);
      Begin
      (* создание списка для представления стека *)
        New(PList2, Init);
        While Size>0 do begin
          PList2^.Insert(0); dec(Size) end;
          PList2^.PLast^.Next:=PList2^.PFirst;
          PList2^.PFirst^.Previous:=PList2^.PLast;
          (* инициализация указателя стека *)
          StackPointer:=PList2^.PFirst
        End;
    Procedure TStack.Push (Element: Word);
      Begin
        StackPointer^.Data:=Element;
        StackPointer:=StackPointer^.Next
      End;
    Function TStack.Pop: Word;
      Begin
        StackPointer:=StackPointer^.Previous;
        Pop:=StackPointer^.Data
      End;
    Destructor TStack.Done;
      Begin
        (* освобождение динамической памяти, выделенной для
           представления объектной переменной-списка *)
        Dispose(PList2, Done)
      End;
    

Объект-стек можно описать так:

    
    TStack = Object
      Private
        StackPointer: PList2Record;
        PList2: ^TList2;
      Public
        Constructor Init (Size: Word);
        Procedure Push (Element: Word);
        Function Pop: Word;
        Destructor Done;
    End;
    

3.2. Очереди

Очередь — структура данных, доступ к элементам которой организуется по правилу: "первый пришел — первый ушел" (алгоритм FIFO/LILO). Использование очередей является почти непременным атрибутом любой вычислительной системы, т.к. очереди необходимы для организации взаимодействия асинхронных устройств. Очередь можно представить в виде кольцевой ограниченной последовательности элементов данных с двумя указателями: на текущие начальную и конечную позиции в последовательности (начальный и конечный указатели), ее длины и количеством занесенных в нее элементов. Начальный и конечный указатели могут сдвигаться только в одном направлении, например, против часовой стрелки. Очередь должна реализовывать следующие операции:

    1. инициализация очереди: создание циклического однонаправленного списка заданной длины и присвоение начальному и конечному указателям позиции начала списка;
    2. помещение в очередь элемента: если количество элементов в очереди меньше длины списка, то помещение в позицию конечного указателя элемента, сдвиг конечного указателя на следующую незанятую позицию в списке и увеличение количества элементов в очереди на 1;
    3. извлечение элемента из очереди: если количество элементов в очереди больше 0, то извлечение из позиции начального указателя элемента, сдвиг начального указателя на следующую позицию в последовательности и уменьшение количества элементов в очереди на 1;
    4. уничтожение очереди.

При попытке выполнить недопустимую операцию (извлечь элемент из пустой очереди или поместить элемент в заполненную очередь) должно генерироваться соответствующее сообщение об ошибке.

Все перечисленные операции могут быть реализованы следующими методами, где QueueBegin — указатель на 1-ю позицию, QueueEnd — указатель на последнюю позицию, QueueLength — текущая длина очереди, PList — указатель на однонаправленный список (объект, см. п. 3.4), ErrorFlag — переменная, сигнализирующая об ошибке:

    
    Constructor TQueue.Init (Size: Word);
      Begin
        ErrorFlag:=false;
        (* создание списка для представления очереди *)
        New(PList, Init);
        While Size>0 do begin
          PList^.Insert(0);
          dec(Size)
        end;
        PList^.PCurrent^.Next:=PList^.PFirst;
        (* инициализация параметров очереди *)
        QueueLength:=0;
        QueueBegin:=PList^.PFirst;
        QueueEnd:=QueueBegin
      End;
    Procedure TQueue.Put (Element: Word);
      Begin
        If QueueLength<PList^.Size then begin
          QueueEnd^.Data:=Element;
          QueueEnd:=QueueEnd^.Next;
          Inc(QueueLength)
        end else writeln('Очередь - заполнена!')
      End;
    Function TQueue.Get: Word;
      Begin
        ErrorFlag:=(QueueLength<=0);
        If ErrorFlag then
          writeln('Очередь - пуста!')
        else begin
          Get:=QueueBegin^.Data;
          QueueBegin:=QueueBegin^.Next;
          Dec(QueueLength)
        end
      End;
    Destructor TQueue.Done; (* аналогичен TStack.Done из п. 3.1*)
    

Объект-очередь можно описать так:

    
    TQueue = Object
      Private
        QueueBegin,QueueEnd: PListRecord;
        QueueLength: Word;
        PList: ^TList;
      Public
        ErrorFlag: Boolean;
        Constructor Init (Size: Word);
        Procedure Put (Element: Word);
        Function Get: Word;
        Destructor Done;
    End;
    

3.3. Деки

Дек — структура данных, состоящая из двух соединенных стеков. Дек позволяет реализовать либо двунаправленную очередь, либо два стека. Дек можно представить как циклическую последовательность элементов данных с двумя указателями: на 1-й элемент ("1-я вершина" дека) и на последний элемент ("2-я вершина" дека). Дек должен реализовывать следующие операции:

    1. инициализация дека: создание циклического двунаправленного списка заданной длины и присвоение указателям дека указателей на смежные элементы этого списка;
    2. помещение в дек элемента в позицию 1-го указателя: если 1-й указатель дека не равен 2-му, то помещение в позицию 1-го указателя элемента и сдвиг этого указателя на одну позицию в сторону от 2-го указателя;
    3. помещение в дек элемента в позицию 2-го указателя: если 2-й указатель дека не равен 1-му, то помещение в позицию 2-го указателя элемента и сдвиг этого указателя на одну позицию в сторону от 1-го указателя;
    4. извлечение элемента из дека с позиции 1-го указателя: если дек не пуст, то сдвиг 1-го указателя на одну позицию в сторону 2-го указателя и извлечение из позиции 1-го указателя элемента;
    5. извлечение элемента из дека с позиции 2-го указателя: если дек не пуст, то сдвиг 2-го указателя на одну позицию в сторону 1-го указателя и извлечение из позиции 2-го указателя элемента;
    6. уничтожение дека.

При попытке выполнить недопустимую операцию (извлечь элемент из пустого дека или поместить элемент в заполненный дек) должно генерироваться соответствующее сообщение.

Все перечисленные операции могут быть реализованы следующими методами, где PDEQ1 — 1-й указатель дека, PDEQ2 — 2-й указатель дека, PList2 — указатель на двунаправленный список (объект, см. п. 3.5), DEQLength — текущая длина дека, ErrorFlag — переменная, сигнализирующая об ошибке:

    
    Constructor TDEQ.Init (Size: Word);
      Begin
        ErrorFlag:=false;
        (* создание списка для представления дека *)
        New(PList2, Init);
        While Size>0 do begin
          PList2^.Insert(0);
          dec(Size)
        end;
        PList2^.PLast^.Next:=PList2^.PFirst;
        PList2^.PFirst^.Previous:=PList2^.PLast;
        (* инициализация параметров дека *)
        PDEQ2:=PList2^.PFirst;
        PDEQ1:=PDEQ2^.Next;
        DEQLength:=0
      End;
    Procedure TDEQ.Push1 (Element: Word);
      Begin
        If DEQLength=PList2^.Size then
          writeln('Дек - полон!')
        else begin
          PDEQ1^.Data:=Element;
          PDEQ1:=PDEQ1^.Next;
          inc(DEQLength)
        end
      End;
    Procedure TDEQ.Push2 (Element: Word);
      Begin
        If DEQLength=PList2^.Size then
          writeln('Дек - полон!')
        else begin
          PDEQ2^.Data:=Element;
          PDEQ2:=PDEQ2^.Previous;
          inc(DEQLength)
        end
      End;
    Function TDEQ.Pop1: Word;
      Begin
        ErrorFlag:=(DEQLength=0);
        If ErrorFlag then
          writeln('Дек - пуст!')
        else begin
          PDEQ1:=PDEQ1^.Previous;
          Pop1:=PDEQ1^.Data;
          dec(DEQLength)
        end
      End;
    Function TDEQ.Pop2: Word;
      Begin
        ErrorFlag:=(DEQLength=0);
        If ErrorFlag then
          writeln('Дек - пуст!')
        else begin
          PDEQ2:=PDEQ2^.Next;
          Pop2:=PDEQ2^.Data;
          dec(DEQLength)
        end
      End;
    Destructor TDEQ.Done; (* идентичен Stack.Done из п. 3.1 *)
    

Объект-дек можно описать так:

    
    TDEQ = Object
      Private
        PDEQ1, PDEQ2: PList2Record;
        PList2: ^TList2;
        DEQLength: Word;
      Public
        ErrorFlag: Boolean;
        Constructor Init (MaxSize: Word);
        Procedure Push1 (Element: Word);
        Procedure Push2 (Element: Word);
        Function Pop1: Word;
        Function Pop2: Word;
        Destructor Done;
    End;
    

3.4. Списки однонаправленные

Список однонаправленный — структура данных, состоящая из односторонней последовательности элементов. Использование таких списков очень естественно для представления данных, например, файл FAT-совместимой операционной системы (MS-DOS, Microsoft Windows 3.xx/95/NT, OS/2 и других) — это однонаправленный список кластеров. Списки часто используются как элементы других структур данных. Однонаправленный список можно представить в виде последовательности элементов данных с двумя указателями: на начальный и на текущий элементы, каждый непоследний элемент в такой последовательности должен содержать указатель на следующий элемент, а последний элемент должен содержать либо неопределенный указатель, либо указатель на первый элемент (в последнем случае получается циклический список). Элемент, на который указывает текущий указатель, называется текущим. Однонаправленный список должен реализовывать следующие операции:

    1. инициализация списка: присвоение текущему и начальному указателю неопределенного значения;
    2. помещение в список элемента: если текущий указатель определен, то указатель вставляемого (нового) элемента устанавливается равным указателю текущего элемента, указатель текущего элемента устанавливается на вставляемый элемент, после чего текущий указатель устанавливается на вставляемый элемент (см. рис. 1), в противном случае текущий и начальный указатели устанавливаются на новый элемент, указатель которого устанавливается неопределенным;
    3. получение значения текущего элемента;
    4. изменение значения текущего элемента;
    5. переход к следующему элементу;
    6. переход к начальному элементу;
    7. сортировка списка;
    8. уничтожение списка.

При попытке выполнить недопустимую операцию (перейти к следующему элементу, указатель на который неопределен и т.п.) должно генерироваться соответствующее сообщение об ошибке.

Для моделирования очереди реализация операций 3–7 не требуется.

Все перечисленные операции могут быть реализованы следующими методами, где PFirst — указатель на 1-й элемент, PCurrent — указатель на текущий элемент, Size — это длина списка, а ErrorFlag — переменная, сигнализирующая об ошибке:

    
    Constructor TList.Init;
      Begin
        ErrorFlag:=false; PCurrent:=nil; Size:=0
      End;
    Procedure TList.Insert (Element: Word);
      Var p1: PListRecord;
      Begin
        If PCurrent<>nil then begin
          New(p1); Inc(Size);
          p1^.Next:=PCurrent^.Next;
          PCurrent^.Next:=p1;
          PCurrent:=p1
        end else begin
          New(PCurrent); Size:=1;
          PFirst:=PCurrent;
          PCurrent^.Next:=nil
        end;
        PCurrent^.Data:=Element
      End;
    Function TList.Get: Word;
      Begin
        ErrorFlag:=(PCurrent=nil);
        If ErrorFlag then
          writeln('Список - пуст!')
        else Get:=PCurrent^.Data
      End;
    Procedure TList.Change (Element: Word);
      Begin
        ErrorFlag:=(PCurrent=nil);
        If ErrorFlag then
          writeln('Список - пуст!')
        else PCurrent^.Data:=Element
      End;
    Procedure TList.ToNext;
      Begin
        If PCurrent<>nil then
          If PCurrent^.Next<>nil then
            PCurrent:=PCurrent^.Next
          else writeln('Следующего элемента нет!')
        else writeln('Список - пуст!')
      End;
    Procedure TList.ToFirst;
      Begin
        If PCurrent<>nil then PCurrent:=PFirst
      End;
    Procedure TList.Sort; (* сортировка выбором *)
      Var
        p1, p2: PListRecord;
        MaxElem: Word;
      Begin
        If Size<2 then exit;
        p1:=PFirst;
        Repeat
          MaxElem:=p1^.Data;
          PCurrent:=p1^.Next;
          p2:=p1;
          While PCurrent<>nil do begin
            If PCurrent^.Data>MaxElem then begin
              MaxElem:=PCurrent^.Data;
              p2:=PCurrent
            end;
            PCurrent:=PCurrent^.Next
          end;
          if p1<>p2 then begin
            MaxElem:=p2^.Data;
            p2^.Data:=p1^.Data;
            p1^.Data:=MaxElem
          end;
          p1:=p1^.Next
        Until p1=nil;
        PCurrent:=PFirst
      End;
    Destructor TList.Done;
      Begin
        (* освобождение динамической памяти, выделенной
          для представления элементов списка *)
        While Size>0 do begin
          PCurrent:=PFirst^.Next;
          Dispose(PFirst);
          PFirst:=PCurrent;
          Dec(Size)
        end
      End;
    

Объект-список можно описать следующей последовательностью деклараций:

    
    PListRecord = ^TListRecord;
    TListRecord = record
      Data: Word;
      Next: PListRecord
    End;
    TList = Object
      Private
        PCurrent, PFirst: PListRecord;
        Size: Word;
      Public
        ErrorFlag: Boolean;
        Constructor Init;
        Procedure Insert (Element: Word);
        Function Get: Word;
        Procedure Change (Element: Word);
        Procedure ToNext;
        Procedure ToFirst;
        Procedure Sort;
        Destructor Done;
    End;
    

3.5. Списки двунаправленные

Список двунаправленный — структура данных, состоящая из двусторонней последовательности элементов. Двунаправленные списки часто используются как элементы других структур данных. Такой список можно представить в виде последовательности элементов данных с тремя указателями: на начальный, конечный и текущий элемент. Каждый непоследний элемент в такой последовательности должен содержать указатель на следующий элемент, а для последнего элемента списка этот указатель неопределен. Кроме того, каждый непервый элемент должен содержать указатель на предшествующий элемент, а для первого элемента списка этот указатель неопределен. Элемент, на который указывает текущий указатель, называется текущим. Двунаправленный список должен реализовывать следующие операции:

    1. инициализация списка: присвоение текущему, начальному и конечному указателю неопределенного значения;
    2. помещение в список элемента: если текущий указатель определен, то вставка в список нового элемента проходит согласно рисунку 2, в противном случае текущий, конечный и начальный указатели устанавливаются на новый элемент, оба указателя которого устанавливаются неопределенными;
    3. удаление элемента из списка: возможны четыре варианта, если удаляемый элемент: 1)неначальный и неконечный, то удаление элемента из списка проходит согласно рисунку 3; 2)неначальный и конечный, то удаление элемента из списка сначала проходит согласно рисунку 3, но затем указатель на последний элемент устанавливается равным текущему указателю; 3)начальный и конечный (т.е. единственный в списке), то удалить текущий элемент и установить в текущий указатель неопределенное значение; 4)начальный и неконечный, то присвоить начальному и текущему указателям значение указателя на следующий элемент текущего элемента, удалить текущий элемент и затем присвоить указателю на предыдущий элемент нового текущего элемента неопределенное значение;
    4. получение значения текущего элемента;
    5. изменение значения текущего элемента;
    6. переход к следующему элементу;
    7. переход к предыдущему элементу;
    8. переход к начальному элементу;
    9. переход к конечному элементу;
    10. уничтожение списка.

При попытке выполнить недопустимую операцию (удалить элемент из пустого списка и т.п.) должно генерироваться соответствующее сообщение об ошибке.

Для моделирования дека или стека реализация операций 4–9 не требуется.

Все перечисленные операции могут быть реализованы следующими методами, где PFirst — указатель на 1-й элемент, PLast — указатель на последний элемент, PCurrent — указатель на текущий элемент, Size — это длина списка, а ErrorFlag — это переменная, сигнализирующая об ошибке:

    
    Constructor TList2.Init;
      Begin
        ErrorFlag:=false; 
        PCurrent:=nil; 
        Size:=0
      End;
    Procedure TList2.Insert (Element: Word);
      Var p1: PList2Record;
      Begin
        If PCurrent<>nil then begin
          New(p1); 
          Inc(Size);
          p1^.Next:=PCurrent^.Next;
          PCurrent^.Next:=p1;
          p1^.Previous:=PCurrent;
          if p1^.Next<>nil then
            p1^.Next^.Previous:=p1
          else PLast:=p1;
          PCurrent:=p1
          end else begin
            New(PCurrent); Size:=1;
            PFirst:=PCurrent;
            PLast:=PCurrent;
            PCurrent^.Next:=nil;
            PCurrent^.Previous:=nil
        end;
        PCurrent^.Data:=Element
      End;
    Procedure TList2.Erase;
      Var p1: PList2Record;
      Begin
        If Size=0 then 
          exit 
        else dec(Size);
        If PCurrent<>PFirst then begin
        p1:=PCurrent;
        PCurrent:=PCurrent^.Previous;
        PCurrent^.Next:=p1^.Next;
        if p1=PLast then
          PLast:=PCurrent
        else p1^.Next^.Previous:=PCurrent;
        Dispose(p1)
        end else if PCurrent=PLast then begin
          Dispose(PCurrent);
          PCurrent:=nil
        end else begin
          PCurrent:=PFirst^.Next;
          PCurrent^.Previous:=nil;
          Dispose(PFirst);
          PFirst:=PCurrent
        end
      End;
    Function TList2.Get: Word;
      Begin
        ErrorFlag:=(PCurrent=nil);
        If ErrorFlag then
          writeln('Список - пуст!')
        else Get:=PCurrent^.Data
      End;
    Procedure TList2.Change (Element: Word);
      Begin
        ErrorFlag:=(PCurrent=nil);
        If ErrorFlag then
          writeln('Список - пуст!')
        else PCurrent^.Data:=Element
      End;
    Procedure TList2.ToNext;
      Begin
        If PCurrent<>nil then
          If PCurrent^.Next<>nil then
            PCurrent:=PCurrent^.Next
          else writeln('Следующего элемента нет!')
        else writeln('Список - пуст!')
      End;
    Procedure TList2.ToPrevious;
      Begin
        If PCurrent<>nil then
          If PCurrent^.Previous<>nil then
            PCurrent:=PCurrent^.Previous
          else writeln('Предыдущего элемента нет!')
        else writeln('Список - пуст!')
      End;
    Procedure TList2.ToFirst;
      Begin
        If PCurrent<>nil then 
          PCurrent:=PFirst
      End;
    Procedure TList2.ToLast;
      Begin
        If PCurrent<>nil then 
          PCurrent:=PLast
      End;
    Destructor TList2.Done;
      Begin
        While Size>0 do 
          Erase
      End;
    

Объект-список двунаправленный можно описать следующей последовательностью деклараций:

    
    PList2Record = ^TList2Record;
    TList2Record = record
      Data: Word;
      Next, Previous: PList2Record
    End;
    TList2 = Object
      Private
        PCurrent, PFirst, PLast: PList2Record;
        Size: Word;
      Public
        ErrorFlag: Boolean;
        Constructor Init;
        Procedure Insert (Element: Word);
        Procedure Erase;
        Function Get: Word;
        Procedure Change (Element: Word);
        Procedure ToNext;
        Procedure ToPrevious;
        Procedure ToFirst;
        Procedure ToLast;
        Destructor Done;
    End;
    

3.6. Бинарные деревья

Бинарное дерево — структура данных, в которой элементы образуют древовидную структуру, причем каждый узел дерева не может иметь более двух потомков, которые называются левым и правым преемниками. Левый преемник должен быть меньше, а правый — больше или равен предшественнику. Единственный элемент, не имеющий предшественника, называется корнем дерева. Бинарные деревья и их обобщения (B-деревья) необходимы для организации быстрого поиска в базах данных. Каждый узел бинарного дерева естественно реализуется через динамическую переменную-запись, содержащую четыре поля: два указателя на левый и правый преемники, указатель на предшественника и собственно данные. Необходимо также иметь постоянный указатель на корень, указатель на текущий узел и переменную, хранящую текущий размер дерева (кол-во узлов в нем). Бинарное дерево должно реализовывать следующие операции:

    1. инициализация бинарного дерева: текущий указатель устанавливается неопределенным, а количество узлов нулевым;
    2. помещение в бинарное дерево элемента: для нового элемента в бинарном дереве создается соответствующий узел, указатели на преемников которого пусты (поиск позиции для такого узла начинается с корня и проходит согласно правилам, определяющим структуру бинарного дерева);
    3. получение значения текущего элемента;
    4. переход к корню;
    5. переход к левому преемнику;
    6. переход к правому преемнику;
    7. переход к предшественнику;
    8. поиск заданного элемента: если искомый элемент находится в дереве, то текущий указатель устанавливается на него и возвращается сигнализирующее об успехе поиска значение, в противном случае только возвращается сигнализирующее о неуспехе поиска значение;
    9. уничтожение бинарного дерева.

При попытке выполнить недопустимую операцию (удалить элемент из пустого дерева и т.п.) должно генерироваться соответствующее сообщение об ошибке.

Все перечисленные операции могут быть реализованы следующими методами, где PRoot — указатель на корень, PCurrent — указатель на текущий элемент, а ErrorFlag — это переменная, сигнализирующая об ошибке:

    
    Constructor TBTree.Init;
      Begin
        PCurrent:=nil; Size:=0; ErrorFlag:=false
      End;
    Procedure TBTree.Insert (Element: Word);
      Var p1: PBTreeRecord;
      Begin
        If PCurrent<>nil then begin (*создание некорневого узла*)
          p1:=PRoot;
          repeat
            PCurrent:=p1;
            if Element<p1^.Data then
              p1:=p1^.Left
            else p1:=p1^.Right
          until p1=nil;
          New(p1);
          p1^.Data:=Element;
          p1^.Left:=nil; 
          p1^.Right:=nil;
          p1^.Pred:=PCurrent;
          if Element<PCurrent^.Data then
            PCurrent^.Left:=p1
          else PCurrent^.Right:=p1;
          PCurrent:=p1
        end else begin (* создание корня *)
          New(PRoot);
          With PRoot^ do begin
            Data:=Element;
            Pred:=nil; 
            Left:=nil; 
            Right:=nil
          end;
          PCurrent:=PRoot
        end;
        Inc(Size)
      End;
    Function TBTree.Get: Word;
      Begin
        ErrorFlag:=(PCurrent=nil);
        If ErrorFlag then
          writeln('Дерево - пусто!')
        else Get:=PCurrent^.Data
      End;
    Procedure TBTree.ToRoot;
      Begin
        If PCurrent<>nil then 
          PCurrent:=PRoot
      End;
    Procedure TBTree.ToLeft;
      Begin
        If PCurrent<>nil then
          If PCurrent^.Left<>nil then
            PCurrent:=PCurrent^.Left
          else writeln('Левый преемник отсутствует!')
        else writeln('Дерево - пусто!')
      End;
    Procedure TBTree.ToRight;
      Begin
        If PCurrent<>nil then
          If PCurrent^.Right<>nil then
            PCurrent:=PCurrent^.Right
          else writeln('Правый преемник отсутствует!')
        else writeln('Дерево - пусто!')
      End;
    Procedure TBTree.ToPredecessor;
      Begin
        If PCurrent<>nil then
          If PCurrent^.Pred<>nil then
            PCurrent:=PCurrent^.Pred
          else writeln('Предшественник неопределен!')
        else writeln('Дерево - пусто!')
      End;
    Function TBTree.FindNode(Element: Word): Boolean;
      (* поиск элемента в дереве: в случае успеха указатель на
        найденный элемент передается в текущий указатель *)
      Var p1: PBTreeRecord;
      Begin
        If PCurrent<>nil then begin
          p1:=PRoot;
          while p1<>nil do begin
            if Element<p1^.Data then
              p1:=p1^.Left
            else if Element=p1^.Data then
              break
            else p1:=p1^.Right
          end;
          FindNode:=(p1<>nil);
          if p1<>nil then 
            PCurrent:=p1
          end else FindNode:=false
        End;
    Destructor TBTree.Done;
      Var p1: PBTreeRecord;
      Begin
        While PCurrent<>nil do
          If PCurrent^.Left=nil then
            If PCurrent^.Right=nil then begin
              p1:=PCurrent;
              PCurrent:=PCurrent^.Pred;
              If PCurrent<>nil then
                If PCurrent^.Left=p1 then
                  PCurrent^.Left:=nil
              else PCurrent^.Right:=nil;
              Dispose(p1)
            end else PCurrent:=PCurrent^.Right
          else PCurrent:=PCurrent^.Left
      End;
    

Объект, бинарное дерево, можно описать следующей последовательностью деклараций:

    
    PBTreeRecord = ^TBTreeRecord;
    TBTreeRecord = record
      Data: Word;
      Left, Right, Pred: PBTreeRecord
    End;
    TBTree = Object
      Private
        PCurrent, PRoot: PBTreeRecord;
        Size: Word;
      Public
        ErrorFlag: Boolean;
        Constructor Init;
        Procedure Insert (Element: Word);
        Function Get: Word;
        Procedure ToRoot;
        Procedure ToLeft;
        Procedure ToRight;
        Procedure ToPredecessor;
        Function FindNode(Element: Word): Boolean;
        Destructor Done;
    End;
    

4. ОРГАНИЗАЦИЯ ИНТЕРАКТИВНОГО РЕЖИМА РАБОТЫ С МОДЕЛИРУЕМЫМИ СТРУКТУРАМИ

Диалоговое тестирования моделируемых структур данных лучше всего проводить при помощи специально созданного для этой цели объекта, который должен содержать следующие методы:

    1. инициализация: создание моделирующего объекта;
    2. показ меню: вывод на экран дисплея списка операций, применимых к моделируемой структуре данных;
    3. реакция на ввод данных пользователем: проверка корректности введенных данных и возврат значения, соответствующего пункту меню, выбранному этим вводом;
    4. организация вызова соответствующего метода моделируемой структуры данных;
    5. уничтожение моделирующего объекта.

Конструкция объекта, тестирующего моделируемую структуру в диалоговом режиме, очевидным образом зависит от самой структуры. Далее приводится описание объекта для тестирования бинарного дерева — объекты для тестирования других структур строятся аналогично.

    
    TTestStructure=Object
      Private
        PDataStructure:^TBTree;
      Public
        Constructor Init;
        Procedure ShowMenu;
        Function WaitKey: Byte;
        Function Dispatcher (Key: Byte): Boolean;
        Destructor Done;
    End;
    Constructor TTestStructure.Init;
      Begin
        New(PDataStructure, Init); ShowMenu
      End;
    Procedure TTestStructure.ShowMenu;
      Begin
        Writeln;
        Writeln(' 1. Добавить элемент');
        Writeln(' 2. Получить значение текущего элемента');
        Writeln(' 3. Перейти к корню');
        Writeln(' 4. Перейти к левому преемнику');
        Writeln(' 5. Перейти к правому преемнику');
        Writeln(' 6. Перейти к предшественнику');
        Writeln(' 7. Найти элемент');
        Writeln(' 8. Окончание работы')
      End;
    Function TTestStructure.WaitKey: Byte;
      Var
        s: string[31];
        n: word;
        m: integer;
      Begin
        Repeat
          Write('Введите номер операции: ');
          Readln(s); Val(s,n,m);
          If (m=0)and(n>0)and(n<=8) then break;
            (* 8 - это кол-во пунктов меню*)
          ShowMenu
        Until false;
        WaitKey:=n
      End;
    Function TTestStructure.Dispatcher(Key: Byte): Boolean;
      Var
        s: string[31];
        n: word;
        m: integer;
      Begin
        Dispatcher:=false;
        Case Key of
          1: begin
            write('Введите значение элемента: ');
            readln(s); 
            val(s,n,m);
            PDataStructure^.Insert(n)
          end;
          2: begin
            n:=PDataStructure^.Get;
            if PDataStructure^.ErrorFlag then
              PDataStructure^.ErrorFlag:=false
            else writeln('Текущий элемент - ', n)
          end;
          3: PDataStructure^.ToRoot;
          4: PDataStructure^.ToLeft;
          5: PDataStructure^.ToRight;
          6: PDataStructure^.ToPredecessor;
          7: begin
            write('Введите искомое значение: ');
            readln(s); 
            val(s,n,m);
            if PDataStructure^.FindNode(n) then
              writeln('Искомый элемент найден')
            else writeln('Элемент не обнаружен')
          end;
          8: Dispatcher:=true
        End
      End;
    Destructor TTestStructure.Done;
      Begin
        Dispose(PDataStructure, Done)
      End;
    

5. ПОРЯДОК ВЫПОЛНЕНИЯ И ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ

5.1. Порядок выполнения лабораторной работы

5.1.1. Требования к структуре программы

Программа должна содержать две основных части: 1)описание объектов; 2)раздел переменных и операторов, который должен иметь, с точностью до пользовательских идентификаторов, следующий вид:

    
    Var PTestStructure: ^TTestStructure;
    Begin
      New(PTestStructure, Init);
      Repeat
      Until PTestStructure^.Dispatcher(PTestStructure^.WaitKey);
      Dispose(PTestStructure, Done)
    End.
    

5.1.2 Порядок анализа результатов

Показать соответствие моделируемых структур данных существующим областям их применения. Сравнить использованный при выполнении лабораторной работы способ моделирования, использующий технологию ООП и динамическое распределение данных, с традиционным, использующим командные языки и массивы.

5.2. Отчет по лабораторной работе

Отчет по работе выполняется на отдельных бланках или листах и должен содержать:

    1. цель исследования; краткую характеристику моделируемой структуры данных; листинг исследовательской программы;
    2. описание исследовательской программы (назначение используемых идентификаторов и блок-схема);
    3. анализ результатов эксперимента;
    4. выводы.

6. ВАРИАНТЫ РАБОТ

Лабораторная работа по теме "Моделирование структур данных средствами объектно-ориентированного программирования с динамическим распределением памяти" имеет 6 вариантов заданий, отличающихся друг от друга моделируемыми структурами данных: 1)стек; 2)дек; 3)очередь; 4)список однонаправленный; 5)список двунаправленный; 6)бинарное дерево.

7. КОНТРОЛЬНЫЕ ВОПРОСЫ

    1. Назвать преимущества объектно-ориентированного подхода для создания программ, моделирующих некоторые сущности и отношения между ними.
    2. Описание стека.
    3. Описание дека.
    4. Описание очереди.
    5. Описание однонаправленного списка.
    6. Описание двунаправленного списка.
    7. Описание бинарного дерева.

ЛИТЕРАТУРА

  1. Бородин Ю.С., Вальвачев А.Н., Кузмич А.И. Паскаль для персональных компьютеров — Минск: Вышэйшая школа, БФ ГИТМП "НИКА", 1991.
  2. Зуев Е.А. Язык программирования Turbo Pascal 6.0 — М.: Унитех, 1992.
  3. Кнут Д. Искусство программирования для ЭВМ — М.: Мир, 1978.
  4. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков — М.: Наука, 1988



ОГЛАВЛЕНИЕ

Введение

1. Системные требования

2. Объектно-ориентированное программирование и задачи моделирования

3. Структуры данных

3.1. Стеки

3.2. Очереди

3.3. Деки

3.4. Списки однонаправленные

3.5. Списки двунаправленные

3.6. Бинарные деревья

4. Организация интерактивного режима работы с моделируемыми структурами

5. Порядок выполнения и отчет по лабораторной работе

5.1. Порядок выполнения лабораторной работы

5.2. Отчет по лабораторной работе

6. Варианты работ

7. Контрольные вопросы

Литература