``МАТИ'' — РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ им. К.Э. ЦИОЛКОВСКОГО
Кафедра ``Моделирование систем и информационные технологии''
МОДЕЛИРОВАНИЕ СТРУКТУР ДАННЫХ СРЕДСТВАМИ
ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАММИРОВАНИЯ
С ДИНАМИЧЕСКИМ РАСПРЕДЕЛЕНИЕМ ПАМЯТИ
Методические указания к лабораторной работе по курсу
``Алгоритмические языки и технология программирования''
Москва 1998
Владимир Викторович Лидовский
МОДЕЛИРОВАНИЕ СТРУКТУР ДАННЫХ СРЕДСТВАМИ
ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАММИРОВАНИЯ
С ДИНАМИЧЕСКИМ РАСПРЕДЕЛЕНИЕМ ПАМЯТИ
Методические указания к лабораторной работе по курсу
"Алгоритмические языки и технология программирования"
Редактор Соколова М.А.
Под. в печ. Объем 1,75 п.л. Тираж 50 экз. Зак.
Ротапринт РГАТУ, Берниковская наб. 14
Настоящие методические указания предназначены для обеспечения учебного процесса студентов второго курса дневной формы обучения специальности 220200 "АСОИиУ" при выполнении лабораторной работы по курсу "Алгоритмические языки и технология программирования".
Цель лабораторной работы: изучить возможности средств объектно-ориентированного программирования для моделирования структур данных, используя динамическое управление распределением памяти.
Для выполнения лабораторной работы необходимы следующие системные компоненты: а)IBM PC совместимый компьютер, работающий под управлением операционной системы Linux; б)система программирования Free Pascal версии 0.95 или выше.
Объектно-ориентированный подход является идеальным для задач моделирования: каждая моделируемая сущность отображается в моделирующей программе отдельным объектом. Кроме того, объектно-ориентированный подход позволяет скрыть внутрипрограммный способ реализации моделируемой сущности от пользователя, предоставив ему только интересующие его в данной сущности компоненты: свойства сущности и методы воздействия на нее. При традиционном подходе к программированию моделей каждая такая сущность представляла собой совокупность часто очень большого числа разнообразных чисто программных, трудных для восприятия пользователем компонент (процедур, функций, массивов, указателей и т.п.), связь между которыми явно не обозначивалась.
При программировании наиболее часто используются следующие структуры данных: стеки, очереди, одно- и двунаправленные списки, деки и бинарные деревья. Каждая такая структура должна представляться в программе одной переменной объектного типа. Закрытая для доступа пользователя часть (private) такого объекта должна содержать переменные и подпрограммы, реализующие в совокупности машинное представление моделируемой структуры. Открытая для доступа пользователя часть (public) такого объекта должна содержать методы типичные для моделируемой структуры и, возможно, некоторые свойства. Важно чтобы использование как методов, так и свойств не приводило к нарушению целостности моделируемой структуры. Машинное представление структур должно использовать динамические переменные, т.к. моделироваться будут идеальные структуры, которые могут содержать неограниченное число элементов. Таким образом, в закрытой части объекта, представляющего моделируемую структуру, должны быть только несколько полей типа указателей и полей-счетчиков целого типа. В качестве данных моделируемые структуры должны хранить целые числа в диапазоне от 0 до 65535 (тип Word): каждый элемент структуры должен хранить одно такое число. Память под собственно объект нужно также выделить динамически (стандартной процедурой New).
Стек — структура данных, доступ к элементам которой организуется по правилу "первый пришел — последним ушел" (алгоритм LIFO/FILO). Использование стека является непременным атрибутом любой вычислительной машины, т.к. стек необходим для организации вызовов подпрограмм и обработки прерываний. Стек можно представить как комбинацию циклического двунаправленного списка и указателя на элементы этого списка, который называется указателем стека. Стек должен реализовывать следующие операции:
Все перечисленные операции могут быть реализованы следующими методами, где 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;
Очередь — структура данных, доступ к элементам которой организуется по правилу: "первый пришел — первый ушел" (алгоритм FIFO/LILO). Использование очередей является почти непременным атрибутом любой вычислительной системы, т.к. очереди необходимы для организации взаимодействия асинхронных устройств. Очередь можно представить в виде кольцевой ограниченной последовательности элементов данных с двумя указателями: на текущие начальную и конечную позиции в последовательности (начальный и конечный указатели), ее длины и количеством занесенных в нее элементов. Начальный и конечный указатели могут сдвигаться только в одном направлении, например, против часовой стрелки. Очередь должна реализовывать следующие операции:
При попытке выполнить недопустимую операцию (извлечь элемент из пустой очереди или поместить элемент в заполненную очередь) должно генерироваться соответствующее сообщение об ошибке.
Все перечисленные операции могут быть реализованы следующими методами, где 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;
Дек — структура данных, состоящая из двух соединенных стеков. Дек позволяет реализовать либо двунаправленную очередь, либо два стека. Дек можно представить как циклическую последовательность элементов данных с двумя указателями: на 1-й элемент ("1-я вершина" дека) и на последний элемент ("2-я вершина" дека). Дек должен реализовывать следующие операции:
При попытке выполнить недопустимую операцию (извлечь элемент из пустого дека или поместить элемент в заполненный дек) должно генерироваться соответствующее сообщение.
Все перечисленные операции могут быть реализованы следующими методами, где 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;
Список однонаправленный — структура данных, состоящая из односторонней последовательности элементов. Использование таких списков очень естественно для представления данных, например, файл FAT-совместимой операционной системы (MS-DOS, Microsoft Windows 3.xx/95/NT, OS/2 и других) — это однонаправленный список кластеров. Списки часто используются как элементы других структур данных. Однонаправленный список можно представить в виде последовательности элементов данных с двумя указателями: на начальный и на текущий элементы, каждый непоследний элемент в такой последовательности должен содержать указатель на следующий элемент, а последний элемент должен содержать либо неопределенный указатель, либо указатель на первый элемент (в последнем случае получается циклический список). Элемент, на который указывает текущий указатель, называется текущим. Однонаправленный список должен реализовывать следующие операции:
При попытке выполнить недопустимую операцию (перейти к следующему элементу, указатель на который неопределен и т.п.) должно генерироваться соответствующее сообщение об ошибке.
Для моделирования очереди реализация операций 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;
Список двунаправленный — структура данных, состоящая из двусторонней последовательности элементов. Двунаправленные списки часто используются как элементы других структур данных. Такой список можно представить в виде последовательности элементов данных с тремя указателями: на начальный, конечный и текущий элемент. Каждый непоследний элемент в такой последовательности должен содержать указатель на следующий элемент, а для последнего элемента списка этот указатель неопределен. Кроме того, каждый непервый элемент должен содержать указатель на предшествующий элемент, а для первого элемента списка этот указатель неопределен. Элемент, на который указывает текущий указатель, называется текущим. Двунаправленный список должен реализовывать следующие операции:
При попытке выполнить недопустимую операцию (удалить элемент из пустого списка и т.п.) должно генерироваться соответствующее сообщение об ошибке.
Для моделирования дека или стека реализация операций 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;
Бинарное дерево — структура данных, в которой элементы образуют древовидную структуру, причем каждый узел дерева не может иметь более двух потомков, которые называются левым и правым преемниками. Левый преемник должен быть меньше, а правый — больше или равен предшественнику. Единственный элемент, не имеющий предшественника, называется корнем дерева. Бинарные деревья и их обобщения (B-деревья) необходимы для организации быстрого поиска в базах данных. Каждый узел бинарного дерева естественно реализуется через динамическую переменную-запись, содержащую четыре поля: два указателя на левый и правый преемники, указатель на предшественника и собственно данные. Необходимо также иметь постоянный указатель на корень, указатель на текущий узел и переменную, хранящую текущий размер дерева (кол-во узлов в нем). Бинарное дерево должно реализовывать следующие операции:
При попытке выполнить недопустимую операцию (удалить элемент из пустого дерева и т.п.) должно генерироваться соответствующее сообщение об ошибке.
Все перечисленные операции могут быть реализованы следующими методами, где 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;
Диалоговое тестирования моделируемых структур данных лучше всего проводить при помощи специально созданного для этой цели объекта, который должен содержать следующие методы:
Конструкция объекта, тестирующего моделируемую структуру в диалоговом режиме, очевидным образом зависит от самой структуры. Далее приводится описание объекта для тестирования бинарного дерева — объекты для тестирования других структур строятся аналогично.
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.1.1. Требования к структуре программы
Программа должна содержать две основных части: 1)описание объектов; 2)раздел переменных и операторов, который должен иметь, с точностью до пользовательских идентификаторов, следующий вид:
Var PTestStructure: ^TTestStructure;
Begin
New(PTestStructure, Init);
Repeat
Until PTestStructure^.Dispatcher(PTestStructure^.WaitKey);
Dispose(PTestStructure, Done)
End.
5.1.2 Порядок анализа результатов
Показать соответствие моделируемых структур данных существующим областям их применения. Сравнить использованный при выполнении лабораторной работы способ моделирования, использующий технологию ООП и динамическое распределение данных, с традиционным, использующим командные языки и массивы.
Отчет по работе выполняется на отдельных бланках или листах и должен содержать:
Лабораторная работа по теме "Моделирование структур данных средствами объектно-ориентированного программирования с динамическим распределением памяти" имеет 6 вариантов заданий, отличающихся друг от друга моделируемыми структурами данных: 1)стек; 2)дек; 3)очередь; 4)список однонаправленный; 5)список двунаправленный; 6)бинарное дерево.
2. Объектно-ориентированное программирование и задачи моделирования
4. Организация интерактивного режима работы с моделируемыми структурами
5. Порядок выполнения и отчет по лабораторной работе
5.1. Порядок выполнения лабораторной работы