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

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

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






















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

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

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




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

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













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













Москва 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. Контрольные вопросы

Литература