Занятие I тема. Основные понятия - vnekl.netnado.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Занятие I тема. Основные понятия - страница №1/1

Занятие I

Тема. Основные понятия.

Граф – это непустое множество точек (вершин) и множество отрезков (ребер), концы которых принадлежат заданному множеству точек.

Если на каждом ребре задать направление, то граф будет ориентированным.




Если, двигаясь по ребрам графа в заданном направлении, можно попасть из заданной вершины 1 в заданную вершину 2, то говорят, что эти вершины соединены путем.

Замкнутый путь, состоящий из различных ребер, называется циклом.

Граф называется связным, если любые две его вершины соединены путем.

Связный граф без циклов называется деревом.

С каждой вершиной дерева связывается конечное число отдельных деревьев, называемых поддеревьями.

Рассмотрите пример дерева, в узлах которого располагаются символы.



Для дальнейшей работы с деревьями необходимо определить ряд понятий.

• Вершина у, находящаяся непосредственно ниже вершины х, называется непосредственным потомком х, а вершина х называется предком у.

• Если вершина не имеет потомков, то она называется терминальной вершиной или листом, если имеет, то называется внутренней вершиной.

• Количество непосредственных потомков внутренней вершины называется ее степенью.

Степенью дерева называется максимальная степень всех вершин.

Например,

• вершины F, D, E являются непосредственными потомками вершины В;

• вершины F, D, E являются листьями;

• вершины C, G, H – внутренние;

• степень вершины В – 3, а вершины Н – 1;

• степень дерева равна 3.



Определение. Двоичное дерево – это дерево, в котором из каждой вершины исходит не более двух ребер.

Задание. Наберите текст программы на компьютере и рассмотрите ее действие. Данная программа демонстрирует создание произвольного двоичного дерева.

Program DemidenkoS;

Uses

Crt, Graph;



Const

Arr : array [1..6] of integer=(160,80,40,20,10,5);

Arr1 : array [1..6] of integer=(120,80,70,60,50,40);

Type


ss=^sp;

sp=record

elem:byte;

Next : array[1..2] of ss;

end;

Var


a, b, c, d : longint;

s : string;

grDriver : integer;

grMode : integer;

a1, b1 : real;

x, Some, Max, Min : ss;

Procedure Zap(y : ss; n : integer);

Var


aa,bb:integer;

Begin


y^.elem:=random(99)+1;

bb:=random(3);

if n<1

then


bb:=2;

if n


then

for aa : =1 to bb do

begin

new(y^.next[aa]);



y^.next[aa]^.next[1]:=nil;

y^.next[aa]^.next[2]:=nil;

zap(y^.next[aa],n+1);

end;


End;

Procedure Strel(x1, y1 : integer; k : Real);

Var

aa : Real;



Begin

aa:=arctan(k);

if k>0

then


begin

line(x1,y1,x1+round(10*cos(aa+pi/18)),y1-round(10*sin(aa+pi/18)));

line(x1,y1,x1+round(10*cos(aa-pi/18)),y1-round(10*sin(aa-pi/18)));

line(x1+round(10*cos(aa+pi/18)),y1-round(10*sin(aa+pi/18)),x1+round(10*cos(aa-pi/18)),y1-round(10*sin(aa-pi/18)));

end

else


begin

aa:=-aa;


line(x1,y1,x1-round(10*cos(aa+pi/18)),y1-round(10*sin(aa+pi/18)));

line(x1,y1,x1-round(10*cos(aa-pi/18)),y1-round(10*sin(aa-pi/18)));

line(x1-round(10*cos(aa+pi/18)),y1-round(10*sin(aa+pi/18)),x1-round(10*cos(aa-pi/18)),y1-round(10*sin(aa-pi/18)));

end


end;

Procedure Wiv(y : ss; n, x1, y1 : integer);

Var

spi : ss;



Begin

SetColor(n+1);

Circle(x1,y1,10);

Str(y^.elem, s);

if length(s)=2

then


OutTextXY(x1-6, y1-2, s)

else


OutTextXY(x1-3, y1-2, s);

if n


then

begin


if y^.next[1]<>nil

then


begin

SetColor(n+1);

Line(x1,y1+10,x1-(arr[n] div 2),y1+((arr1[n]-20) div 2)+10);

SetColor(n+2);

Line(x1-(arr[n] div 2),y1+((arr1[n]-20) div 2)+10,x1-arr[n],y1+arr1[n]-10);

Strel(x1-arr[n],y1+arr1[n]-10,(arr1[n]-20)/arr[n]);

Wiv(y^.next[1],n+1,x1-arr[n],y1+arr1[n]);

end;


if y^.next[2] <> nil

then


begin

SetColor(n+1);

Line(x1,y1+10,x1+arr[n],y1+arr1[n]-10);

SetColor(n+2);

Line(x1+(arr[n] div 2),y1+((arr1[n]-20) div 2)+10,x1+arr[n],y1+arr1[n]-10);

Strel(x1+arr[n],y1+arr1[n]-10,-(arr1[n]-20)/arr[n]);

Wiv(y^.next[2],n+1,x1+arr[n],y1+arr1[n]);

end;


end;

end;


Begin

ClrScr;


Randomize;

Repeat


new(x);

a:=6;


x^.next[1]:=Nil;

x^.next[2]:=Nil;

Zap(x,0);

Max:=x;


Min:=x;

writeln;


grDriver := Detect;

InitGraph(grDriver, grMode,'c:\tp7\bgi\');

SetFillStyle(solidfill,15);

SetColor(15);

Wiv(x,1,320,50);

Delay(5000);

until KeyPressed;

End.


Задание. Поэкспериментируйте над предложенной программой, внося свои изменения. Результат покажите учителю.

Занятие II

Тема. Представление деревьев. Основные операции над деревом.

Дерево – это сложная динамическая структура данных, применяющаяся для эффективного хранения информации.

Очевидно, что для описания требуются ссылки. Опишем, как переменные с фиксированной структурой – сами вершины, тогда степень дерева будет определять число ссылочных компонент, указывающих на вершины поддеревьев. В бинарном дереве их два: левое и правое.

Type


TreeLink = ^Tree;

Tree = Record

Data : <тип данных>;

Left, Right : TreeLink;

End;

Корень дерева опишем в разделе описания переменных:



Var

kd : TreeLink;

К основным операциям над деревьями относятся:

• занесение элемента в дерево;

• обход дерева;

• удаление элемента из дерева.

Рассмотрим вставку и обход дерева на примере следующей задачи.

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

Опишем процедуру вставки в дерево новой вершины. При вставке в дерево вершина вставляется либо как поддерево уже существующей вершины или как единственная вершина дерева. Поэтому и левая и правая связи новой вершины должны быть Nil. Когда дерево пусто, значение передаваемое в виде параметра ссылки равно Nil. В этом случае нужно изменить ее так, чтобы она указывала на новую вершину, которая была вставлена как корневая. При вставке второго элемента переданный из основной программы параметр t уже не будет равен Nil, и надо принимать решение о том, в какое поддерево необходимо вставить новую вершину.

Procedure InsTree(n : integer; Var t : TreeLink);

Begin


if t=nil

then


begin

new(t);


with t^ do

begin


Left := nil;

Right := nil;

Data := n;

end;


end;

else


if n<=t^.data

then


InsTree(n, t^.Left)

else


InsTree(n, t^.Right)

End;


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

• вывод числа, хранящегося в узле;

• обход левого поддерева;

• обход правого поддерева.

Порядок выполнения этих действий определяет способ обхода дерева. Способы вывода:

• прямой вывод (сверху вниз);

• обратный вывод (слева направо);

• концевой вывод (снизу вверх).

Процедура обратного вывода дерева имеет следующий вид:

Procedure PrintTree(t : TreeLink);

Begin

if t<>Nil



then

begin


PrintTree(t^.Left);

Write(t^.Data:3);

PrintTree(t^.Right);

end;


End;

Задание. Написать процедуры прямого и концевого вывода значений элементов дерева.

Основная программа осуществляет ввод чисел с клавиатуры. Используются: переменная nd типа TreeLink – значение указателя на корень дерева; переменная Digit типа integer для хранения очередного введенного числа.

Begin

writeln('Вводите вершины дерева. Окончание ввода – 0');



kd := nil;

read(Digit);

while Digit <> 0 do

begin


InsTree(Digit, kd);

writeln(' Введите очередное число ');

read(Digit);

end;


PrintTree(kd);

End.


Задание. Напишите программу создания и вывода на экран двоичного дерева, используя свою процедуру вывода. Протестируйте программу и представьте учителю файл и листинг для оценки.

Занятие III

Тема. Самостоятельное решение задач.

Выберите с учителем одну из предложенных задач.

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

2. Создайте программой числовое двоичное дерево. Опишите рекурсивную числовую функцию, подсчитывающую сумму элементов дерева. В программе используйте подпрограммы.

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

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

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

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

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

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

9. Создайте двоичное дерево записей. Проверьте выбранное поле записей на равенство. В программе используйте подпрограммы.

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



Занятие IV

Тема. Идеально сбалансированное дерево.

В дереве поиска можно найти место каждого элемента, двигаясь от корня и переходя на левое или правое поддерево в зависимости от значений встречающихся данных.

Использование деревьев поиска значительно сокращает время решения задачи.

Правильно организованным деревом считается идеально сбалансированное дерево, то есть для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 1.

Сформируем идеально сбалансированное дерево, элементами которого являются N чисел, вводимых с клавиатуры.

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

• Взять один узел в качестве корня.

• Построить левое поддерево с числом узлов n1=N div 2 тем же способом.

• Построить правое поддерево с числом узлов n2=N-n1-1 тем же способом.

Program BalansTree;

Uses

Crt;


Type

Pt = ^Node;

Node = record

Data : integer;

Left, Right : Pt;

end;


Var

n : integer;

kd : Pt;

f : text;

Function Tree(n : integer) : Pt;

Var


NewNode : Pt;

x, n1, n2 : integer;

Begin

if n=0


then

Tree := Nil

else

begin


n1 := n Div 2;

n2 := n–n1–1;

read(f,x);

new(NewNode);

with NewNode^ do

begin


Data := x;

Left := Tree(n1);

Right := Tree(n1);

end;


Tree := NewNode;

end;


End;

Procedure PrintTree(t : Pt; h : integer);

Var

i : integer;



Begin

if t<>nil

then

with t^ do



begin

PrintTree(Left, h+1);

for i := 1 to h do

write(' ');

writeln(Data:6);

PrintTree(Right, h+1);

end;

End;


Begin

ClrScr;


assign(f, 'c:\f.pas');

reset(f);

write('n=');

readln(n);

kd := Tree(n);

PrintTree(kd, 0);

readln;

End.


Задание. Наберите программу, протестируйте ее, вставьте комментарий, приготовьтесь объяснить учителю принцип построения идеально сбалансированного дерева.

Поиск и включение элемента в дерево.

Задача. Задана последовательность слов. Определить частоту вхождения каждого из слов в последовательности.

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

Program Poisk;

Uses


Crt;

Type


Words = ^WordTree;

WordTree = record

Data : string;

k : integer;

Left, Right : Words;

end;


Var

n : integer;

kd : Words;

x : string;

f : text;

Procedure Tree(x : string; Var p : Words);

Begin

if p=nil


then

begin


new(p);

with p^ do

begin

k := 1;


Data := x;

Left := Nil;

Right := Nil;

end;


end;

else


if x>p^.Data

then


Tree(x. p^.Left)

else


if x

then


Tree(x. p^.Right)

else


Inc(p^.k);

End;


Procedure PrintTree(t : Words; h : integer);

Var


i : integer;

Begin


if t <> Nil

then


with t^ do

begin


PrintTree(Left, h+1);

for i := 1 to h do

write(' ');

writeln(Data, ',(', k, ')');

PrintTree(Right, h+1);

end;


End;

Begin


ClrScr;

assign(f, 'c:\f.dan');

reset(f);

write('n=');

readln(n);

kd := Nil;

while n>0 do

begin


readln(f,x);

Tree(x, kd);

Dec(n);

end;


close(f);

PrintTree(kd, 0);

readln;

End.


Эта задача называется задачей поиска по дереву с включением.

Задание. Наберите программу, протестируйте ее, вставьте комментарий, приготовьтесь объяснить учителю принцип поиска по дереву с включением. По желанию можете усложнить текст задачи, усовершенствовать ее решение или внести еще какие-либо изменения.

Удаление из дерева.

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

Если же из удаляемой вершины выходит две ветви, то нужно найти подходящую вершину дерева, которую можно было бы вставить на место удаляемой вершины.
frame4

Из вышесказанного следует, что процедура удаления элемента из дерева должна различать три случая.

1. Удаляемая вершина имеет два поддерева. В этом случае удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева. При этом они должны иметь не больше одного потомка.

2. Удаляемая вершина имеет не более одного поддерева (0 или 1).

3. Удаляемой вершины в дереве нет.

Просмотрите рекурсивную процедуру DelTree, которая отыскивает элемент с заданным ключом и удаляет его. В процедуре DelTree описана процедура d1, которая работает только в первом из трех перечисленных случаев.

Вспомогательная процедура d1 "движется" по правой ветви левого поддерева исключаемого элемента q^ и заменяет значение ключа в q^ на соответствующее значение из самого правого элемента r^ левого поддерева.

Type


Pt = ^Node;

Node = Record

Data : integer;

Left, Right : Pt;

End;

Procedure DelTree(x : integer; Var p : Pt);



Var

q : Pt;


Procedure D1(Var r : Pt);

Begin


if r^.Right <> Nil

then


d1(r^.Right)

else


begin

q^.Data := r^.Data;

q := r;

r := r^.Left;



Dispose(q);

end;


End;

Begin


if p=nil

then


writeln('Элемента с ключом ', x, 'в дереве нет.')

else


if x

then


DelTree(x, p^.Left)

else


if x>p^.Data

then


DelTree(x, p^.Right)

else


begin

q := p;


if q^.Right = Nil

then


begin

p := q^.Left;

dispose(q);

end;


else

if q^.Left = Nil

then

begin


p := q^.Right;

dispose(q);

end;

else


D1(q^.Left)

end;


End;

Задание. Наберите программу, протестируйте ее, вставьте комментарий, приготовьтесь объяснить учителю принцип удаления элемента из дерева.

Выберите задачу для решения из предложенных ниже.

1. Удалите из дерева все равные между собой элементы. В программе используйте подпрограммы.

2. Удалите из дерева все повторяющиеся элементы. В программе используйте подпрограммы.

3. Постройте два дерева. Проверьте, является ли одно из них поддеревом другого. Если "да", то удалите это поддерево. В программе используйте подпрограммы.

4. Постройте два дерева. Проверьте, является ли одно из них поддеревом другого. Если "нет", то включите это поддерево. В программе используйте подпрограммы.

5. Используя очередь или стек, вычислите среднее арифметическое всех элементов непустого дерева Т и удалите все элементы меньшие этого числа. В программе используйте подпрограммы.

6. Используя очередь или стек, поменяйте местами максимальный и минимальный элементы непустого дерева Т, все элементы которого различны. В программе используйте подпрограммы.

7. Используя очередь или стек, напечатайте все элементы дерева Т по уровням: сначала – из корня дерева, затем (слева направо) – из вершин, дочерних по отношению к корню, затем (также слева направо) – из вершин, дочерних по отношению к этим вершинам, и т.д. В программе используйте подпрограммы.

8. Используя очередь или стек, найдите в непустом дереве Т длину (число ветвей) пути от корня до ближайшей вершины с элементом Е. Если такого элемента не обнаружено, то выдайте на экран соответствующее сообщение. В программе используйте подпрограммы.

9. Используя очередь или стек, подсчитайте число вершин на n-ом уровне непустого дерева Т (корень считайте вершиной 0-го уровня). В программе используйте подпрограммы.

10. Объедините два дерева в одно идеально сбалансированное. В программе используйте подпрограммы.



Задачи для самостоятельного решения (на усмотрение учителя)

1. Напишите программу, содержащую процедуру или функцию, которая присваивает параметру Е элемент из самого левого листа непустого дерева (лист – вершина, из которой не выходит ни одной ветви), используя очередь или стек. В программе используйте подпрограммы.

2. Напишите программу, содержащую процедуру или функцию, которая находит в непустом дереве длины (число ветвей) путей от корня до всех вершин, используя очередь или стек. В программе используйте подпрограммы.

3. Напишите программу, содержащую процедуру или функцию, которая подсчитывает число вершин на каждом уровне непустого дерева (корень считать вершиной 0-го уровня). В программе используйте подпрограммы.

4. Напишите программу, содержащую процедуру или функцию, которая определяет максимальную глубину непустого дерева Т, т.е. число ветвей в самом длинном из путей от еорня дерева до листьев. В программе используйте подпрограммы.

5. Напишите программу, содержащую процедуру, которая строит Т1 – копию дерева Т. В программе используйте подпрограммы.

6. Напишите программу, содержащую процедуру Create(T,n), где n – положительное целое число, которая строит Т – дерево, изображенное на рисунке. В программе используйте подпрограммы.

7. Напишите программу, содержащую процедуру Create(T,n), где n – положительное целое число, которая строит Т – дерево, изображенное на рисунке. В программе используйте подпрограммы.



8. Формулу вида



<формула>::=<терминал>|(<формула><знак><формула>)

<знак>::=+|-|*

<терминал>::=0|1|2|3|4|5|6|7|8|9

можно представить в виде двоичного дерева ("дерева-формулы") с элементами типа char согласно следующим правилам: формула из одного терминала (цифры) представляется деревом из одной вершины с этим терминалом, а формула вида (f1sf2) – деревом, в котором корень – это знак s, а левое и правое поддеревья – это соответствующие представления формул f1 и f2. Для примера посмотрите как будет выглядеть дерево, соответствующее формуле (5*(3+8)).

Опишите рекурсивную функцию или процедуру, которая:

а) вычисляет (как целое число) значение дерева-формулы Т);

б) по формуле из текстового файла f строит соответствующее дерево-формулу Т;

в) печатает дерево-формулу Т в виде соответствующей формулы;

г) проверяет, является ли двоичное дерево Т деревом-формулой.

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

а) упрощает дерево-формулу Т, заменяя в нем все поддеревья, соответствующие формулам (f+0), (0+f), (f-0), (f*1), (1*f) на поддеревья, соответствующие формуле f, а поддеревья, соответствующие формулам (f*0) и (0*f), на вершину с 0;

б) преобразует дерево-формулу Т, заменяя в нем все поддеревья соответствующие формулам ((f1+f2)*f3, (f1-f2)*f3) и (f1*(f2+f3), f1*(f2-f3)) на поддеревья, соответствующие формулам ((f1*f3)+(f2*f3), (f1*f3)-(f2*f3)) и ((f1*f2)+(f1*f3), (f1*f2)-(f1*f3)).



10. Во внешнем текстовом файле записана (без ошибок) некоторая программа на языке Паскаль. Известно, что в этой программе каждый идентификатор (служебное слово или имя) содержит не более 9 латинских букв и/или цифр. Напечатайте в алфавитном порядке все различные идентификаторы этой программы, указав для каждого из них число его вхождений в текст программы. Необходимо учесть, что в идентификаторах одноименные прописные и строчные буквы отождествляются, что внутри литерных значений, строк-констант и комментариев последовательности из букв и цифр не являются идентификаторами и что в записи вещественных чисел может встретиться буква Е или е.