close

Вход

Забыли?

вход по аккаунту

?

ТП лаб №1

код для вставкиСкачать
Лабораторная работа №1
(расчетное время выполнения работы - 3 занятия)
Цель: изучение основ объектно-ориентированного программирования на примере реализации динамических структур данных.
Задание: разработать объектно-ориентированное программное обеспечение, реализующее динамическую структуру данных.
Варианты заданий.
Структура данныхМаксимальная оценка в баллах*Реализация на базе вектора (массива)Динамическая реализацияСтек2565Очередь4065Последовательность4565Дек5080Список Л1 (однонаправленный)6080Список Л2 (двунаправленный)6580Дерево, граф75100
* - максимальная оценка выставляется при успешной защите отчета (при отсутствии правильных ответов на дополнительные вопросы оценка может быть снижена на 75%)
Порядок выполнения:
Теория ООП
Объектно-ориентированное программирование (ООП) - это методика разработки программ, в основе которой лежит понятие объекта, как некоторой структуры, описывающей объект реального мира, его поведение. Задача, решаемая с помощью методики ООП, описывается в терминах объектов и операций над ними, а программа при таком подходе представляет собой набор объектов и связей между ними.
Расширяя рамки сложного типа данных - записи (record), концепция объектно-ориентированного программирования позволяет программисту определять классы. Тип данных класс - сложная структура, включающая в себя помимо описания данных описание процедур и функций, которые могут быть выполнены над представителем класса - объектом. Пример описания простого класса:
type TPerson = class
private
fname: string[15];
faddress: string[40];
public
procedure Show;
end;
Данные класса называются полями, процедуры и функции - методами. В приведенном примере TPerson - это имя класса, fname и faddress - имена полей, а Show - имя метода. Свойства - виртуальные характеристики объектов, базирующиеся на значениях конкретных полей. Оспределение значения свойства и изменение его значения выполняются в рамках соответствующих методов.
Объекты - экземпляры класса описываются в разделе var:
var
Student : TPerson;
Professor: TPerson;
Переменная типа объект является ссылочной. Она хранит адрес динамической структуры в памяти, содержащей ссылку на класс объекта и значения его полей. В отличие от полей, которые у каждого объекта свои, методы у разных объектов одного класса общие (поэтому нет необходимости каждому объекту хранить адреса его методов - достаточно ссылки на класс). От обычных процедур и функций методы отличаются тем, что при вызове им передается указатель на тот объект, который вызвал метод. Внутри метода этот объект доступен под зарезервированным именем Self.
Создание и удаление объектов.
Так как экземпляры объектов являются динамическими, то для работы с ними предварительно требуется произвести необходимые действия по их созданию в куче. Эти действия выполняют специальные методы - конструкторы объектов. Любой конструктор перед выполнением записанных в его теле операторов вначале резервирует в куче место, необходимое для размещения объекта, и заполняет поля созданного объекта нулевыми значениями. После выполнения содержащихся в его теле операторов, конструктор, являясь функцией, возвращает адрес нового объекта. По умолчанию в каждом классе доступен стандартный конструктор Create, не содержащий внутренних операторов.
Созданный экземпляр объекта уничтожается другим методом - деструктором. Для разрушения объектов можно использовать деструктор Destroy, доступный любому объекту по умолчанию. Однако чаще всего применяют стандартный метод Free. Пользователь вправе написать свои конструктор или деструктор, указав их в описании класса.
Жизненный цикл объекта, состоящий из трех этапов (создание, использование и разрушение), может выглядеть примерно так:
Student:=TPerson.Create; // создание объекта
...
Writeln(Student.fname) // использование объекта
...
Student.Free; // разрушение объекта
Обратите внимание, имена вызываемых методов и полей объекта записываются через точку после имени объекта. Однако для метода Create сделано исключение: его применение к объекту напрямую невозможно, т.к. самого объекта еще не существует (т.н. ошибка доступа). Поэтому функция Create вызывается как метод класса (в данном случае TPerson) и возвращаемый ею адрес объекта присваивается ссылке Student.
Ниже представленный класс описывает точку на плоскости с координатами (x,y). Переменная данного класса содержит два поля (x и y), три метода (Ro, Move, GetSection) конструктор CreateLine и свойство Section (только для чтения).
type TPoint = class
x,y: Real;
constructor CreateLine;
function Ro : real;
proceure Move(Dx,Dy : real);
function GetSection : byte; property Section: byte read GetSection;
end;
constructor TPoint.CreateLine; // создает точку с координатами (1,1)
begin
x:=1;
y:=1
end;
function TPoint.Ro; // вычисляет расстояние до начала координат
begin
result:=Sqrt(Sqr(x)+Sqr(y));
end;
procedure TPoint.Move; // перемещает точку на вектор (Dx,Dy)
begin
x:=x+Dx;
y:=y+Dy;
end;
function TPoint.GetSection;
begin
if x*y=0 then Result:=0
else if x >0
then if y>0 then result:=1
else result:=4
else if y>0 then result:=2
else result:=3
end;
Жизненный цикл объекта данного класса может выглядеть примерно так:
var a : Tpoint;
begin
a:=TPoint.Create;
...
a.Move(5,-1.6);
...
a.Free;
end
Классическое правило объектно-ориентированного программирования утверждает, что для обеспечения надежности нежелателен прямой доступ к полям объекта: чтение и обновление их содержимого должно производиться посредством вызова соответствующих методов. Это правило называется инкапсуляцией.. В языке Object Pascal принцип инкапсуляции реализуется посредством свойств - виртуальных характеристик объектов, базирующихся на значениях конкретных полей.
Поля объекта хранят данные (т.е. занимают место в памяти), а свойства посредством вызова соответствующих методов позволяют определять и узнавать различные характеристики объектов, которые, в общем случае, могут и не храниться в памяти, а, например, вычислться по формулам. Обычно свойство определяется полем соответствующего типа и двумя методами доступа - для чтения значения поля (функция) и изменения значения (процедура): type TMyClass = class
fValue : TSomeType; function GetValue: TSomeType; procedure SetValue(NewValue: TSomeType);
property pValue: TSomeType read GetValue write SetValue;
end;
В этом примере fValue -поле для хранения значения свойства,
GetValue - метод для чтения значения свойства,
SetValue - метод для изменения значения свойства,
pValue -само свойство,
TSomeType -тип данного свойства.
В тексте программы использование свойства не отличается от использования обычного поля, но при компиляции вызов свойства для чтения или для записи заменяется вызовом соответствующих методов, например (var MyObject : TMyClass):
исходный текст интерпретируется как MyObject.pValue:=AValue; MyObject.SetValue(AValue); AVariable:= MyObject.pValue; AVariable:= MyObject.GetValue; В рамках методов Get и Set прописываются дополнительные операции, которые необходимо выполнить для реализации чтения или изменения свойства. Например, при изменении ширины формы надо не просто занести в соответствующую ячейку новое значение, но и выполнить операции по перерисовке на мониторе как самой формы, так и окружающей ее области.
Если же дополнительные операции не требуются, то при описании свойства ссылку на метод можно заменить ссылкой на поле. Рассмотрим следующее описание:
type TMyClass = class
fValue : TSomeType; procedure SetValue(NewValue: TSomeType);
property pValue: TSomeType read fValue write SetValue;
function Correct(Value: TSomeType):boolean; procedure DoSomeThing;
end;
...
procedure TmyClass.SetValue(NewValue: TSomeType);
begin
if Correct(NewValue) then fValue:=NewValue;
DoSomeThing;
end;
Здесь чтение свойства pValue означает просто чтение поля fValue. Зато при присвоении ему значения внутри SetValue будут вызваны сразу два метода.
Если свойство только читается или записывается, то в его описании присутствует только один, соответствующий, метод: property pValue: TSomeType read GetValue;
В этом примере попытка изменить значение свойства pValue вызовет ошибку компиляции.
Часто количество свойств, основанных на группе полей может значительно превышать число самих полей. Например, описывая как объект точку на плоскости можно на основе двух полей - координат точки X и Y можно построить достаточно много свойств - характеристик точки: X и Y - декартовые координаты (для чтения и записи),  и  - полярные координаты (для чтения и записи), K- номер координатной четверти (от 1 до 4, только для чтения) и т.п.
Теория "структуры данных"
Структурой данных называют совокупность правил и ограничений, которые отражают связи, существующие между отдельными частями (элементами) данных.
Определение каждой структуры данных включает в себя: * список действий, которые можно выполнять над этой структурой (функциональная спецификация); * формально-логическое определение как объекта, которое задает разбиение объекта на более элементарные объекты и определенные над ними операции; * описание физического представления структуры, которое определяет расположение данных в памяти компьютера, а также способы кодирования операций в конкретном языке программирования. Массив
Массив - упорядоченная структура однотипных данных. Упорядоченность определяется тем, что отдельные элементы массива обозначаются упорядоченной совокупностью n значений, называемых индексами. Число n называется размерностью массива. Одномерный массив (линейная таблица) - массив, элементами которого являются атомарные переменные, например, одномерный массив вещественных чисел. Массив, элементами которого являются одномерные массивы, называется двумерным массивом. В данном случае размерностью массива будет количество строк - например, n, количество столбцов - количество элементов в строке - например, m. Массив, элементами которого являются двумерные массивы, называется трехмерным массивом и т.д. Массив - статический тип данных, поэтому изменить размерность в ходе работы программы невозможно. К компонентам массива можно обращаться в произвольном порядке, вычисляя значения индекса (индексов). Действия над элементами массива определяются типом этих элементов. Массив - один из самых общеупотребительных способов структурирования данных. С помощью массива можно представить такую структуру данных как граф. При обработке одномерного массива следует уделить внимание следующим алгоритмам: * перебор всех элементов массива - нахождение суммы элементов, среднего арифметического элементов, количества четных по значению элементов и т.д.; * поиск элемента массива с заданными свойствами - поиск значения и местоположения минимального (максимального) элемента массива, поиск первого положительного, последнего отрицательного и т.д.; * сортировка одномерного массива одним из способов. Множество
Множество (в паскале) - это произвольная совокупность значений перечисляемого типа. Максимальное количество элементов во множестве - 256 элементов. Над множествами определены бинарные операции: объединение, пересечение, разность, сравнение на равенство и неравенство, проверка на включение, проверка на принадлежность. В бытовом смысле множество можно воспринимать как витрину, куда можно складывать образцы неких вещей (например, перчаток): одна красная перчатка, одна синяя, одна зеленая и т.д. В отличие от массива, где элементами могут быть одни и те же значения, то во множестве каждое значение представлено только один раз. Линейные списки
Целесообразно определить несколько терминов и понятий, которыми будем пользоваться в дальнейшем. Информация в списках представлена множество узлов (элементов). Каждый узел состоит из одного или нескольких последовательных ячеек памяти компьютера, разделенных на именуемые части, называемые полями. Адрес узла является адресом первого слова в узле. Адрес узла называют связью, указателем, стрелкой, ссылкой на этот узел. Линейный список - это множество, состоящее из n(большее или равное 0) узлов X[1], X[2], ..., X[n], структурные свойства которого, по сути, ограничиваются лишь линейным (одномерным) относительным положением узлов, то есть теми условиями, что если n>0, то X[1] является первым узлом; если 1<k<n, то k-му узлу X[k] предшествует X[k-1] и за ним следует X[k+1]; X[n] является последним узлом. Операции, которые мы имеем право выполнять с линейными списками, включают следующие: 1. Получить доступ к k-му узлу списка, чтобы проанализировать и/или изменить содержимое его полей. 2. Включить новый узел непосредственно перед k-м узлом. 3. Исключить k-й узел. 4. Объединить два (или более) линейных списка в один список. 5. Разбить линейный список на два (или более) списка. 6. Сделать копию линейного списка. 7. Определить количество узлов в списке. 8. Выполнить сортировку узлов списка в возрастающем порядке по некоторым полям в узлах. 9. Найти в списке узел с заданным значением в некотором поле. Специальные случаи k=1 и k=n в операциях 1), 2) и 3) особо выделяются, поскольку в линейном списке проще получить доступ к первому и последнему элементу, чем к произвольному элементу. Очень часто встречаются линейные списки, в которых включение, исключение или доступ к значением почти всегда производятся в первом или последнем узлах, им даны специальные названия: Стек - линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются в одном конце списка. Очередь - линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) делаются на другом его конце. Дек (очередь с двумя концами) - линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются на обоих концах списка. Следовательно, дек обладает большей общностью, чем стек или очередь. Иногда аналогия с переключением железнодорожных путей, предложенная Э. Дейкстрой, помогает понять механизм стека. Из стека мы всегда исключаем младший элемент из имеющихся в списке, то есть тот, который был включен позже других. Для очереди справедливо в точности противоположное правило: исключается всегда самый старший элемент; узлы покидают список в том порядке, в котором они вошли. Многие люди независимо поняли важность стеков и очередей и дали другие названия этим структурам. Стек называли push-down списком, реверсивной памятью, гнездовой памятью, магазином, списком LIFO (last-in-firs-down - последний вошел - первый вышел) и даже употребляется такой термин, как список йо-йо! Очередь иногда называют циклической памятью или списком типа FIFO (first-in-first-out - первый вошел - первый вышел). При описании алгоритмов, использующих такие структуры, принята специальная технология. Так, мы помещаем элемент на верх стека или снимаем верхний элемент. Внизу стека находится наименее доступный элемент, и он не удаляется до тех пор, пока не будут исключены все другие элементы. Часто говорят, что элемент опускается (push-down) в стек или что стек поднимается (pop-up), если исключается верхний элемент. В применении к очередям мы говорим о начале и конце очереди. Объекты встают в конец очереди и удаляются в момент, когда, наконец, достигают ее начала. Говоря о деках, мы указываем левый и правый концы. Понятие верха и низа, начала и конца применимо иногда и к декам, если они используются как стеки или очереди. Кольцо
Циклически связанный список (кольцо или циклический список) обладает той особенностью, что связь его последнего узла не равна пустоте, а идет назад к первому узлу списка. В этом случае можно получить доступ к любому элементу, находящемуся в списке, отправляясь от любой заданной точки; одновременно мы достигаем полной симметрии, и теперь нам уже не приходится различать в списке последний или первый узел. Граф
Термин граф впервые появился в работах венгерского математика Д.Кенинга в 1936 году, хотя ряд задач по теории графов решался еще Л.Эйлером в XVIII веке. Пусть V - непустое конечное множество, V(2) - множество всех его двухэлементных подмножеств. Пара G=(V,E), где E - произвольное подмножество множества V(2), называется графом (неориентированным графом). Элементы множества V называются вершинами графа, а элементы множества E - ребрами. Говорят, что две вершины u и v графа смежные, если (u,v) является ребром, то есть принадлежит множеству E. Изучению алгоритмов на графах будет посвящено воторе заседание виртуального методического объединения. Дерево
Одним из частных случаев графа является дерево. Определим формально дерево как конечное множество Т, состоящее из одного или более узлов, таких, что: * имеется один специально обозначенный узел, называемый корнем данного дерева; * остальные узлы (исключая корень) содержаться в m (большее или равное 0) попарно не пересекающихся множествах Т1, ..., Тm, каждое из которых в свою очередь является деревом. Деревья Т1, ..., Тm называются поддеревьями данного корня. Из определения следует, что каждый узел дерева является корнем некоторого поддерева, которое содержится в дереве. Число поддеревьев данного узла называется степенью этого узла. Узел с нулевой степенью называется концевым узлом; иногда его называют листом. Неконцевые узлы часто называют узлами разветвления. Уровень узла по отношению к дереву T определяется следующим образом: говорят, что корень имеет уровень 1, а другие узлы имеют уровень на единицу выше их уровня относительно содержащего их поддерева Tj этого корня. На рисунке 11 показано дерево с семью узлами. Проиллюстрируем на нем введенные понятия. Корнем дерева является A; дерево имеет два поддерева: {B} и {C, D, E, F, G}. Конем дерева {C, D, E, F, G} является узел C. Узел C имеет уровень 2 относительно всего дерева; он имеет три поддерева: {D}, {E} и {F, G}, и, следовательно, его степень равна 3. Узлы B, D, E и G являются концевыми узлами; F - единственный узел степени 1, а G - единственный узел уровня 4. В разговоре о деревьях удобно пользоваться генеалогической терминологией. Говорят, что корень является отцом корней своих поддеревьев и что последние являются братьями между собой и сыновьями своего отца. Практика (примеры подобных программ)
Пример реализации стека на базе вектора.
unit main;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Edit1: TEdit;
Button2: TButton;
Label1: TLabel;
Button3: TButton;
procedure Button3Click(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
Tsteck = class
st : array [1..10] of integer;
head: integer;
procedure add (a:integer);
function get:integer;
end;
var
Form1: TForm1;
steck : tsteck;
implementation
{$R *.dfm}
procedure Tsteck.add (a:integer);
begin
inc (head);
St[head]:=a;
end;
function Tsteck.get:integer;
var d: integer;
begin
d:=St[head];
dec(head);
Result := d;
end;
procedure TForm1.Button3Click(Sender: TObject);
begin
steck := Tsteck.Create;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
steck.add(StrToInt(Edit1.Text));
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
label1.Caption:= IntToStr(steck.get);
end;
end.
Пример динамической реализации очереди (приведенная реализация не единственная, приветствуются оригинальные идеи).
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Button2: TButton;
Edit1: TEdit;
Button3: TButton;
Label1: TLabel;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
TElement = class
data: integer;
next: tElement;
end;
TOcher = class
beg,head:Telement;
end;
var
Form1: TForm1;
Ocher : TOcher;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
begin
Ocher:= TOcher.Create;
end;
procedure TForm1.Button2Click(Sender: TObject);
Var element: TElement;
begin
element:=TElement.Create;
element.data:=StrToInt(Edit1.Text);
if Ocher.beg=nil then Ocher.beg:=element
else Ocher.head.next:= element;
Ocher.head:=element;
end;
procedure TForm1.Button3Click(Sender: TObject);
Var element: TElement;
begin
Label1.Caption:=IntToStr(Ocher.beg.data);
element:=Ocher.beg;
Ocher.beg:=Ocher.beg.next;
end;
end.
Документ
Категория
Рефераты
Просмотров
49
Размер файла
112 Кб
Теги
лаб
1/--страниц
Пожаловаться на содержимое документа