II. Поиск узла с заданным значением ключевого поля.
При осуществлении этой операции необходимо совершить обход дерева. Необходимо учитывать различные формы записи дерева: префиксную, инфиксную и постфиксную.
Возникает вопрос: каким образом представить узлы дерева, чтобы было наиболее удобно работать с ними? Можно представлять дерево с помощью массива, где каждый узел описывается величиной комбинированного типа, у которой информационное поле символьного типа и два поля ссылочного типа. Но это не совсем удобно, так как деревья имеют большое количество узлов, заранее не определенное. Поэтому лучше всего при описании дерева использовать динамические переменные. Тогда каждый узел представляется величиной одного типа, которая содержит описание заданного количества информационных полей, а количество соответствующих полей должно быть равно степени дерева. Логично отсутствие потомков определять ссылкой nil. Тогда на языке Pascal описание бинарного дерева может выглядеть следующим образом:
TYPE TreeLink = ^Tree;
Tree = record;
Inf: <тип данных>;
Left, Right: TreeLink;
End.
22. Примеры реализации операций
1. Построить дерево из з узлов минимальной высоты, или идеально сбалансированное дерево (количество узлов левого и правого поддеревьев такого дерева должны отличаться не более чем на единицу).
Рекурсивный алгоритм построения:
1) первый узел берется в качестве корня дерева;
2) тем же способом строится левое поддерево из nl узлов;
3) тем же способом строится правое поддерево из nr узлов;
nr = n – nl – 1
В качестве информационного поля будем брать номера узлов, вводимые с клавиатуры. Рекурсивная функция, реализующая данное построение, будет выглядеть следующим образом:
Function Tree(n: Byte): TreeLink;
Var t: TreeLink; nl,nr,x: Byte;
Begin
If n = 0 then Tree:= nil
Else
Begin
nl:= n div 2;
nr = n – nl – 1;
writeln('Введите номер вершины );
readln(x);
new(t);
t^.inf:= x;
t^.left:= Tree(nl);
t^.right:= Tree(nr);
Tree:= t;
End;
{Tree}
End.
2. В бинарном упорядоченном дереве найти узел с заданным значением ключевого поля. Если такого элемента в дереве нет, то добавить его в дерево.
Procedure Search(x: Byte; var t: TreeLink);
Begin
If t = nil then
Begin
New(t);
t^inf:= x;
t^.left:= nil;
t^.right:= nil;
End
Else if x < t^.inf then
Search(x, t^.left)
Else if x > t^.inf then
Search(x, t^.right)
Else
Begin
{обработка найденного элемента}
…
End;
End.
23. Понятие графа. Способы представления графа
Граф – пара G = (V,E), где V – множество объектов произвольной природы, называемых вершинами, а E – семейство пар ei = (vil, vi2), vijOV, называемых ребрами. В общем случае множество V и (или) семейство E могут содержать бесконечное число эле-ментов, но мы будем рассматривать только конечные графы, т. е. графы, у которых как V, так и E конечны. Если порядок элементов, входящих в ei, имеет значение, то граф называется ориентированным, сокращенно – орграф, иначе – неориентированным. Ребра орграфа называются дугами.
Если e =
Степень вершины графа – это число ребер, инцидентных данной вершине, причем петли учитываются дважды.
Вес вершины – число (действительное, целое или рациональное), поставленное в соответствие данной вершине (интерпретируется как стоимость, пропускная способность и т. д.).
Путем в графе (или маршрутом в орграфе) называется чередующаяся последовательность вершин и ребер (или дуг – в орграфе) вида v0, (v0,v1), v1, …, (vn –1,vn), vn. Число n называется длиной пути. Путь без повторяющихся ребер называется цепью, без повторяющихся вершин – простой цепью. Замкнутый путь без повторяющихся ребер называется циклом (или
контуром в орграфе); без повторяющихся вершин (кроме первой и последней) – простым циклом.
Граф называется связным, если существует путь между любыми двумя его вершинами, и несвязным – в противном случае.
Существуют различные способы представления графов.
1. Матрица инцидентности.
Это прямоугольная матрица размерности n ч m, где n – количество вершин, а m – количество ребер.
2. Матрица смежности.
Это квадратная матрица размерности n ч n, где n – количество вершин.
3. Список смежности (инцидентности). Представляет собой структуру данных, которая
для каждой вершины графа хранит список смежных с ней вершин. Список представляет собой массив указателей, i-ый элемент которого содержит указатель на список вершин, смежных с i-ой вершиной.
4. Список списков.
Представляет собой древовидную структуру данных, в которой одна ветвь содержит списки вершин, смежных для каждой.
24. Различные представления графа
Для реализации графа в виде списка инцидентности можно использовать следующий тип:
Type List = ^S;
S = record;
inf: Byte;
next: List;
end;
Тогда граф задается следующим образом:
Var Gr: array[1..n] of List;
Теперь обратимся к процедуре обхода графа. Это вспомогательный алгоритм, который позволяет просмотреть все вершины графа, проанализировать все информационные поля. Если рассматривать обход графа в глубину, то существуют два типа алгоритмов: рекурсивный и нерекурсивный.
На языке Pascal процедура обхода в глубину будет выглядеть следующим образом:
Procedure Obhod(gr: Graph; k: Byte);
Var g: Graph; l: List;
Begin
nov[k]:= false;
g:= gr;
While g^.inf <> k do
g:= g^.next;
l:= g^.smeg;
While l <> nil do begin
If nov[l^.inf] then Obhod(gr, l^.inf);
l:= l^.next;
End;
End;
Представление графа списком списков
Граф можно определить с помощью списка списков следующим образом:
Type List = ^Tlist;
Tlist = record
inf: Byte;
next: List;
end;
Graph = ^TGpaph;
TGpaph = record
inf: Byte;
smeg: List;
next: Graph;
end;
При обходе графа в ширину мы выбираем произвольную вершину и просматриваем сразу все вершины, смежные с ней.
Приведем процедуру обхода графа в ширину на псевдокоде:
Procedure Obhod2(v);
Begin
queue = O;
queue <= v;
nov[v] = False;
While queue <> O do
Begin
p <= queue;
For u in spisok(p) do
If nov[u] then
Begin
nov[u]:= False;
queue <= u;
End;
End;
End;
25. Объектный тип в PascalПонятие объекта, его описание и использование
Объектно-ориентированный язык программирования характеризуется тремя основными свойствами:
1) инкапсуляцией. Комбинирование записей с процедурами и функциями, манипулирующими полями этих записей, формирует новый тип данных – объект;
2) наследованием. Определение объекта и его дальнейшее использование для построения иерархии порожденных объектов с возможностью для каждого порожденного объекта, относящегося к иерархии, доступа к коду и данным всех порождающих объектов;
3) полиморфизмом. Присваивание действию одного имени, которое затем совместно используется вниз и вверх по иерархии объектов, причем каждый объект иерархии выполняет это действие способом, именно ему подходящим.
Говоря об объекте, мы вводим в рассмотрение новый тип данных – объектный. Объектный тип является структурой, состоящей из фиксированного числа компонентов. Каждый компонент является либо полем, содержащим данные строго определенного типа, либо методом, выполняющим операции над объектом.
Объектный тип может наследовать компоненты другого объектного типа. Если тип T2 наследует от типа T1, то тип T2 является потомком типа Г, а сам тип Г, является родителем типа Г2.
Следующий исходный код приводит пример описания объектного типа.
type
Point = object
X, Y: integer;
end;
Rect = object
A, B: TPoint;
procedure Init(XA, YA, XB, YB: Integer);
procedure Copy(var R: TRectangle);
procedure Move(DX, DY: Integer);
procedure Grow(DX, DY: Integer);
procedure Intersect(var R: TRectangle);
procedure Union(var R: TRectangle);
function Contains(P: Point): Boolean;
end;
В отличие от других типов объектные типы могут описываться только в разделе описаний типов, находящемся на самом внешнем уровне области действия программы или модуля. Таким образом, объектные типы не могут описываться в разделе описаний переменных или внутри блока процедуры, функции или метода.
Тип компоненты файлового типа не может иметь объектный тип или любой структурный тип, содержащий компоненты объектного типа.
26. Наследование
Наследование – это процесс порождения новых типов-потомков от существующих типов-родителей, при этом потомок получает (наследует) от родителя все его поля и методы.
Тип-потомок, при этом, называется наследником или порожденным (дочерним) типом. А тип, которому наследует дочерний тип, называется порождающим (родительским) типом.
Наследуемые поля и методы можно использовать в неизменном виде или переопределять (модифицировать).
Н. Вирт в своем языке Паскаль стремился к максимальной простоте, поэтому он не стал его усложнять введением отношения наследования. Поэтому типы в Паскале не могут наследовать.
Однако Turbo Pascal 7.0 расширяет этот язык для поддержки наследования. Одним из таких расширений является новая категория структуры данных, связанная с записями, но значительно более мощная. Типы данных в этой новой категории определяются с помощью нового зарезервированного слова Object. Синтаксис при этом очень похож на синтаксис определения записей: