Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
.Билет 18. Использование указателей для обработки деревьев.
Указатели можно использовать не только для работы со списками, но и с динамическими структурами данных более общего вида, в частности графами - системой взаимосвязанных вершин и дуг.
Частным случаем графов являются деревья - структуры, представляющие иерархические связи. Дерево имеет единственную вершину - корень дерева, с которым связаны все остальные вершины (непосредственно или посредством связей через другие вершины), а также висячие вершины, называемые листьями дерева.
Дерево также как список является рекурсивной структурой, однако, в отличие от однонаправленного списка содержит несколько указателей на следующие элементы. В простейшем случае дерево имеет два указателя на следующие элементы. Такое дерево называется бинарным деревом. Оно является простейшим типом деревьев, имеющим, однако, широкие приложения.
Для бинарного дерева характерно наличие двух поддеревьев для каждой вершины - левого и правого поддеревьев (отростков). Просмотр бинарного дерева удобно выполнять рекурсивно, например тремя следующими операциями: исследовать вершину, просмотреть левое поддерево, просмотреть правое поддерево.
В соответствии с этим для обработки деревьев обычно используют рекурсивные процедуры (или функции). Кроме просмотра деревьев, добавления или удаления вершин, при обработке также используют процедуры быстрого поиска информации. Двоичное дерево представляет эффективную структуру для хранения и поиска данных, поступающих в случайном порядке (значительно более удобную, чем массив).
В качестве примера программы работы с двоичным деревом приведем программу построения частотного словаря букв, встречающихся в анализируемом тексте. Бинарное дерево представляется в этой программе как указатель на вершину-запись, содержащую два информационных поля (размещаемый символ и число его повторений) и два указателя (на левое и правое поддерево):
type link =^node; node = record c:char;count:word;left,right:link end;
Программа имеет следующий вид:
program frequency_letters; {Частота вхождения латинских букв в строку}
type link=^node; {тип - Указатель на запись}
node=record c:char;count:word;left,right:link end;
var root:link; {Корень дерева поиска} symb:char;j:word;
L:set of char; {множество символов}
s:string; { вводимая строка }
procedure insert_tree(var r:link;ch:char);{Вставка ch в дерево}
begin if r=nil then
begin new(r);with r^ do begin c:=ch;count:=1;left:=nil;right:=nil end end
else with r^ do
if ch<c then insert_tree(left,ch) else
if ch>c then insert_tree(right,ch) else count:=count+1;
end{insert_tree};
procedure print_tree(r:link); {Печать количества вхождений букв }
begin if r<>nil then with r^ do
begin print_tree(left);writeln(c,':',count); print_tree(right) end
end{print_tree};
procedure search_tree(r:link;ch:char); {Поиск ch и печать}
begin if r=nil then writeln(ch,':0') else with r^ do
begin if ch<c then search_tree(left,ch) else
if ch>c then search_tree(right,ch) else writeln(ch,':',count)
end
end{search_tree};
BEGIN L:=['A'..'Z']; root:=nil;writeln(' Введите текст:');while not eof do
begin readln(s);for j:=1 to length(s) do
begin if upcase(s[j]) in L then insert_tree(root,s[j]) end;
end; writeln('СПРАВКА ПО ЧАСТОТАМ ЛАТИНСКИХ БУКВ:');
while not eof do begin readln(symb);search_tree(root,symb) end;
write('Печатать по всем буквам?(Y/N)');readln(symb);
if symb<>'N' then print_tree(root);
END{frequency_letters}.
Program Z_433_18;
Определить по экзаменациооной ведомости попадает ли группа на конкурс лучших групп. Условие конкурса: средний балл группы выше четырех, отсутствие неуспевающих, число студентов не имеющих тройки больше половины всех студентов группы
program Z433_18;
uses Z433_18;
Var A: matr;
sum, sr_bal: real;
T: vector;
k, i, j, kol: integer;
Begin {осн. программы}
For i:=1 to n do
For j:=1 to m do
readln(A[i,j]);
Bal(A,sum, sr_bal);
USPEVAEMOST(A, k);
TROIKI(A, T, kol);
If (sr_bal>4) and (k=0) and
(kol>(m/2)) then writeln('Gruppa_popadaet')
else writeln('ne_popadaet');
end.
Unit Z433_18;
interface
Const n=3; m=4;
Type matr=array[1..n,1..m] of real;
vector=array [1..m] of integer;
Var A: matr;
sum, sr_bal: real;
T: vector;
k, i, j, kol: integer;
Procedure BAL(A: matr; Var sum, sr_bal: real);
Procedure USPEVAEMOST(A: matr; Var k: integer);
Procedure TROIKI(A:matr; Var T:vector; Var kol: integer);
implementation
Procedure BAL(A: matr; Var sum, sr_bal: real);
Var i, j: integer;
Begin
sum:=0;
sr_bal:=0;
For i:=1 to n do
For j:=1 to m do
sum:=sum+A[i,j];
sr_bal:=sum/(n*m);
end;
Procedure USPEVAEMOST(A: matr; Var k: integer);
Var i, j: integer;
Begin
k:=0;
For i:=1 to n do
For j:=1 to m do
If A[i, j]<3 then k:=k+1
end;
Procedure TROIKI(A:matr; Var T:vector; Var kol: integer);
Var i, j: integer;
Begin
kol:=0;
For i:=1 to n do
For j:=1 to m do
If A[i,j]>3 then T[j]:=1 else T[j]:=0;
For j:=1 to m do
If T[j]=1 then kol:=kol+1
end;
end.