[ЗМІСТ] [Далі] [Назад] [Початок розділу]
10.5.2 Сильно розгалужене
дерево
Сильно
розгалуженим називають дерево, в якому напівстепінь виходу вершин більше 2.
Реалізація сильно розгалужених дерев залежить від того, чи відома максимальна
напівстепінь виходу вершин. Ми будемо вважати, що максимальна напівстепінь
виходу не визначена. Тоді кожну вершину сильно розгалуженого дерева можна
представити навантаженням та списком синів. Відповідно, всі дії над деревом
можна розбити на дві групи: дії над вершинами дерева та дії над списком синів.
Виберемо у якості списку вже відомий нам список з поточним елементом. Тоді
операції, відношення та інструкції для сильно розгалужених дерев можна
визначити так:
1.
Почати
роботу.
2.
Чи
порожнє дерево?
3.
Створити
вершину.
4.
Корінь
дерева.
5.
Список
синів.
6.
Видалити
вершину.
7.
Почати
роботу із списком синів.
8.
Чи
порожній залишок списку синів?
9.
Встати
до початку списку синів.
10.
Перейти
до наступного елемента списку синів.
11.
Поточний
елемент списку синів.
12.
Вставити
елемент у список синів.
13.
Видалити
елемент списку синів.
Дії 1 –
6 – це дії над вершинами дерева, а дії 7 – 13 - вже знайомі нам дії із списком
з поточним елементом. Тому далі розглянемо лише дії безпосередньо над деревами
1 - 6.
Дії 1,
3, 6 – інструкції, 4, 5 – операції; 2 – відношення.
Інструкція
“Почати роботу” створити порожнє дерево.
“Створити
вершину” – за списком дерев l та даними n створити дерево з коренем з навантаженням
n, та списком синів l.
“Корінь дерева” повертає навантаження кореня дерева. Дерево при
цьому не змінюється. Для порожнього дерева ця операція повинна давати відмову.
“Список
синів” повертає список дерев, які є синами даної вершини. Для порожнього дерева
ця операція не визначена.
“Видалити
вершину” видалити поточну вершину дерева. Для порожнього дерева ця інструкція
повинна давати відмову.
Можлива
реалізація сильно розгалуженого дерева з використанням вказівників зображена на
Рис. 10.35. Вершини дерева – це записи з двох полів: поле даних та список синів
(який, в свою чергу, є записом з двох вказівників: на початок списку та на
поточний елемент списку). За допомогою вказівників вершини дерева з’єднані між
собою. На рисунку вказівники на вершини позначені грубими стрілками, а
вказівники у списку синів – тонкими. Саме дерево – це вказівник на корінь. Якщо
дерево порожнє, то вершин немає, а вказівник дорівнює nil.
Рис. 10.35 – Реалізація сильно розгалуженого дерева
Для
сильно розгалужених дерев докладно розглянемо реалізацію у мові Сі. Для Паскаля
обмежимось інтерфейсною частиною модуля.
unit IntTree;
interface
type tree
= ^node; {Дерево}
lref = ^lelem; {Вказівник на елемент списку}
lelem
= record {Елемент списку}
nd: tree;
next: lref
end;
list = record {Список дерев}
beg, cur: lref
end;
node = record {Вершина дерева}
d: integer;
sl: list
end;
procedure Init(var t: tree); { Почати роботу }
function Empty(t: tree): boolean; { Чи порожнє дерево? }
procedure MakeNode(var t: tree; n: integer;
l: list);{ Створити вершину }
function Root(t: tree): integer; { Корінь дерева }
procedure SonsList(t: tree; var l: list); { Список синів }
procedure DelNode(var t: tree); { Видалити вершину }
procedure SlInit(var l: list); { Почати роботу із списком }
function SlEmpEnd(l: list): boolean;
{ Чи порожній
залишок списку?}
procedure SlFirst(var l: list); { Встати до початку списку }
procedure SlNext(var l: list); {Перейти до наступного
елемента}
function SlCurrent(l: list): tree; { Поточний елемент списку}
procedure SlInsert(var l: list; t: tree); { Вставити елемент у список}
procedure SlDelete(var l: list); { Видалити елемент списку}
implementation
.................
end.
Модуль
реалізації сильно розгалужених дерев у Сі скаладється з двох файлів: tree.h та
tree.c. З файлу tree.c наведемо тільки реалізацію дій створення
вершини та видалення вершини. Інші дії над вершинами дуже прості, а дії над
списками з поточним елементом були розглянуті у п. 10.4.2. Тому всі ці підпрограми залишаються для самостійної роботи. Треба
зауважити, що функція del_node звільняє тільки пам’ять, раніше виділену для
вершини дерева. Ця функція не очищує список синів, тому очищення списку для
повного видалення вершини та всіх її синів треба виконувати вручну.
/* tree.h */
typedef struct node *tree; /* Дерево */
typedef struct lelem *lref; /* Вказівник на елемент списку */
struct lelem { /*
Елемент списку */
tree nd;
lref next;
};
typedef struct { /*
Список дерев */
lref beg, cur;
} list;
struct node { /*
Вершина дерева */
int d;
list sl;
};
extern void init(tree *pt); /* Почати роботу */
extern int empty(tree t); /* Чи порожнє дерево? */
extern void make_node(tree *pt, int n, list l);/* Створити вершину */
extern int root(tree t); /* Корінь дерева */
extern void sons_list(tree t, list *pl); /*
Список синів */
extern void del_node(tree *pt); /* Видалити вершину */
extern void sl_init(list *pl); /* Почати роботу із списком */
extern int sl_emp_end(list l); /* Чи порожній залишок списку?*/
extern void sl_first(list *pl); /* Встати до початку списку */
extern void sl_next(list *pl); /* Перейти до наступного елемента */
extern tree sl_current(list l); /* Поточний елемент списку */
extern void sl_insert(list *pl, tree t); /*
Вставити елемент у список */
extern void sl_delete(list *pl); /* Видалити елемент списку
*/
/* tree.c */
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
.................
extern void make_node(tree *pt, int n, list l)
{
tree p;
p =
(tree) malloc(sizeof(struct node));
p ->
d = n; p -> sl = l;
*pt =
p;
}
.................
extern void del_node(tree *pt)
{
if(*pt ==
NULL)
{
printf("del_node: empty tree\n");
exit(1);
}
free(*pt);
}
.................
Як
приклад використання сильно розгалужених дерев наведемо програму, яка порівнює два
дерева. Функція cmp_tree порівнює дерева t1 та t2. Функція input_tree вводить сильно розгалужене дерево. Обидві функції є
рекурсивними. Основна програма організовує введення двох дерев та показує
результат порівняння.
/* treetst.c */
#include <stdio.h>
#include "tree.h"
#define TRUE 1
int cmp_tree(tree t1, tree t2)
{
int b;
list l1, l2;
b = empty(t1) && empty(t2) ||
!empty(t1) && !empty(t2);
if (!empty(t1) && !empty(t2))
{
b = root(t1)==root(t2);
sons_list(t1, &l1); sons_list(t1, &l2);
sl_first(&l1); sl_first(&l2);
while(!sl_emp_end(l1) &&
!sl_emp_end(l2) && b)
{
b
= cmp_tree(sl_current(l1),sl_current(l2));
sl_next(&l1);
sl_next(&l2);
}
b = b && sl_emp_end(l1) &&
sl_emp_end(l2);
}
return
b ;
}
void input_tree(tree *pt)
{
unsigned m, n, i;
list l;
tree s;
int k;
init(pt);
printf("Вводити дерево? [0-Ні/1-Так]:
");
scanf("%u", &m);
if
(m==1)
{
printf("Введіть корінь: ");
scanf("%d", &k);
printf("Введіть кількість синів:
");
scanf("%u", &n);
sl_init(&l);
for(i=1; i<=n; i++)
{
printf("Син
%u\n", i);
input_tree(&s);
sl_insert(&l,
s);
}
make_node(pt,k,l);
}
}
main()
{
tree t1, t2;
printf("\nВведіть перше дерево\n");
input_tree(&t1);
printf("\nВведіть друге дерево\n");
input_tree(&t2);
printf("Дерева ");
if (!cmp_tree(t1,t2)) printf("не ");
printf("рівні\n");
}
Для
роботи з графами існують різні реалізації. Відома, наприклад, реалізація графа
у вигляді матриці суміжності (матриці з 0 та 1, де 1 стоїть у клітинці матриці,
яка відповідає вершинам графа vi, vj, пов’язаних дугою). Така реалізація досить
проста, але не економить пам’ять, особливо для розріджених графів. Ми
розглянемо більш загальну реалізацію графів, в якій для кожної вершини
складається список вершин, з яких входять дуги у дану вершину (попередників) та
список вершин, у які виходять дуги з даної вершини (наступників). Сам граф
також можна представити у вигляді списку вершин.
Визначимо
перелік операцій відношень та інструкцій для графів:
1.
Створити
вершину.
2.
Навантаження
вершини.
3.
Список
попередників.
4.
Список
наступників.
5.
Змінити
список попередників.
6.
Змінити
список наступників.
7.
Видалити
вершину.
8.
Почати
роботу із списком вершин.
9.
Чи порожній
залишок списку вершин?
10.
Встати
до початку списку вершин.
11.
Перейти
до наступного елемента списку вершин.
12.
Поточний
елемент списку вершин.
13.
Вставити
елемент у список вершин.
14.
Видалити
елемент списку вершин.
Дії 1 –
7 – це дії над вершинами графа, а дії 8 – 14 - знайомі нам дії із списком з
поточним елементом. Тому далі розглянемо лише дії безпосередньо над вершинами
графа 1 - 7.
Дії 1,
5, 6, 7 – інструкції, 2, 3, 4 – операції.
“Створити
вершину” – за списками вершин l1, l2 та даними n створити вершину
графа з навантаженням n,
списком попередників l1 та
списком наступників l2.
“Навантаження
вершини” повертає навантаження даної вершини. Вершина при цьому не змінюється.
“Список
попередників” повертає список вершин, які є попередниками даної вершини.
“Список
наступників” повертає список вершин, які є наступниками даної вершини.
“Змінити
список попередників” замінює список попередників даної вершини даним списком
вершин.
“Змінити
список наступників” замінює список наступників даної вершини даним списком
вершин.
“Видалити
вершину” видалити дану вершину графа.
Наведений
набір дій над графами є скоріше набором так званих “мікрооперацій”, на базі
яких можна реалізовувати “великі”
операції над графами. Наприклад, додавання вершини графа повинно включати
створення списку попередників, списку наступників, створення вершини та
безпосередньо вставку вершини у граф. До того ж, під час додавання вершини
треба модифікувати списки наступників всіх вершиин, які є попередниками нової,
та списки попередників всіх вершин, які є наступниками нової, включивши у ці
списки дану вершину.
Можлива
реалізація графа з використанням вказівників зображена на Рис. 10.36. Вершини
графа – це записи з трьох полів: поле даних, список наступників та список
попередників (які, в свою чергу, є записами з двох вказівників: на початок
списку та на поточний елемент списку). За допомогою вказівників вершини графа
з’єднані між собою. На рисунку вказівники на вершини позначені грубими
стрілками, а вказівники у списках вершин – тонкими. Сам граф, список
попередників вершини, список наступників вершини – це списки вершин.
Рис. 10.36 – Реалізація графа
Розглянемо
модуль реалізації графів у мові Паскаль. З файлу IntGraph наведемо тільки
реалізацію дій створення вершини, отримання та зміни списку попередників. Інші
дії над вершинами дуже прості або схожі на розглянуті, а дії над списками з
поточним елементом були розглянуті у п. 10.4.2. Тому всі ці підпрограми залишаються для самостійної роботи.
unit IntGraph;
interface
type
noderef =
^node; {Вказівник
на вершину графа}
lref =
^lelem; {Вказівник
на елемент списку вершин}
lelem =
record {Елемент
списку вершин}
nd: noderef;
next: lref
end;
graph =
record {Список
вершин (граф)}
beg, cur: lref
end;
node =
record {Вершина
графа}
d: integer;
pl, sl: graph
end;
procedure MakeNode(var nod: noderef; n: integer; l1, l2: graph);{Створити вершину}
function Weight(nod: noderef): integer; { Навантаження вершини }
procedure GetPredList(nod: noderef; var l: graph);
{ Список попередників }
procedure GetSuccList(nod: noderef; var l: graph);
{ Список наступників }
procedure SetPredList(nod: noderef; l: graph); { Змінити список попередників }
procedure SetSuccList(nod: noderef; l: graph); { Змінити список наступників }
procedure DelNode(var nod: noderef); { Видалити вершину }
procedure Init(var g: graph); { Почати роботу із списком вершин }
function EmpEnd(g: graph): boolean; { Чи порожній залишок списку вершин?}
procedure First(var g: graph); { Встати до початку списку вершин }
procedure Next(var g: graph); { Перейти до наступного елемента }
function Current(g: graph): noderef; { Поточний елемент списку вершин }
procedure Insert(var g: graph; nod: noderef); { Вставити елемент }
procedure Delete(var g: graph); { Видалити елемент списку вершин }
implementation
.................
procedure MakeNode(var nod: noderef; n: integer;
l1, l2: graph);
begin
new(nod);
nod^.d:=n; nod^.pl:=l1; nod^.sl:=l2
end;
.................
procedure GetPredList(nod: noderef; var l: graph);
begin
l:=nod^.pl
end;
.................
procedure SetPredList(nod: noderef; l: graph);
begin
nod^.pl:=l
end;
.................
end.
Як
приклад використання графів наведемо програму, яка перевіряє, чи є граф
деревом. Функція Len обчислює довжину списка вершин. Функція FindRoot обчислює
номер вершини, яка є коренем дерева, тобто має напівстепінь входу 0. Якщо така
вершина є і вона у графі єдина, FindRoot повертає її номер у списку, інакше
FindRoot повертає 0. Процедура TestTree(nod, b, k) перевіряє, чи є частина
графа, яка починається з nod деревом (тоді значення b - істина) та повертає у змінній k кількість вершин цього дерева. Процедура
InsLink(nod, g, n) зв’язує дугою вершину nod графа g з вершиною цього графа з номером n, модифікуючи список попередників вершини nod та список наступників вершини з номером n. Ця процедура використовується у процедурі
введення графа InputGraph. Остання процедура спочатку вводить навантаження всіх
вершин графа, формує граф з порожніми списками попередників та наступників.
Потім вводяться всі дуги графа. Основна програма організовує введення графа,
перевіряє, чи є він деревом та показує результат.
Program GraphTst;
uses IntGraph;
function Len(g: graph): word;
var l:
word;
begin
l:=0;
First(g);
while
not EmpEnd(g) do begin
l:=l+1;
Next(g)
end;
Len:=l
end;
function FindRoot(g: graph): word;
var k, n,
i: word;
b, c:
boolean;
nod:
noderef;
l:
graph;
begin
k:=0;
c:=true; b:=false;
First(g); i:=0;
while
not EmpEnd(g) and c do begin
nod:=Current(g); i:=i+1;
GetPredList(nod, l);
if Len(l)=0
then begin
n:=i;
b:=true; k:=k+1;
c:=k<=1
end;
Next(g)
end;
if b and
c then FindRoot:=n
else
FindRoot:=0
end;
procedure TestTree(nod: noderef; var b: boolean;
var k: word);
var nod1:
noderef;
sl, pl: graph;
begin
k:=k+1;
GetSuccList(nod,sl);
First(sl); b:=true;
while
not EmpEnd(sl) and b do begin
nod1:=Current(sl);
GetPredList(nod1,pl);
TestTree(nod1, b, k);
b:=b
and (Len(pl)=1);
Next(sl)
end;
end;
procedure InsLink(nod: noderef; g: graph; n:
word);
var nod1:
noderef;
pl,sl:
graph;
i:
word;
begin
First(g);
for i:=1
to n-1 do
Next(g);
nod1:=Current(g);
GetSuccList(nod,sl); GetPredList(nod1,pl);
Insert(sl,nod1);
Insert(pl,nod);
SetSuccList(nod,sl); SetPredList(nod1,pl);
end;
procedure InputGraph(var g: graph);
var n, i,
m, j, n1: word;
k:
integer;
l1,
l2: graph;
nod:
noderef;
begin
Init(g);
write('Кількість вершин: '); readln(n);
Init(l1); Init(l2);
for i:=1
to n do begin
write('Навантаження вершини ',i,': ');
readln(k);
MakeNode(nod,k,l1,l2);
Insert(g,nod)
end;
First(g);
for i:=1
to n do begin
nod:=Current(g);
write('Кількість наступників для вершини
',i,': ');
readln(m);
for
j:=1 to m do begin
repeat
write('Номер ',j,' наступника[1-',n,']: ');
readln(n1);
until (n1>=1) and (n1<=n);
InsLink(nod,g,n1);
end;
Next(g)
end;
end;
var g: graph;
n,k,m,i:
word;
b:
boolean;
nod:
noderef;
begin
InputGraph(g); {введення
графа}
n:=Len(g);
{обчислення кількості
вершин}
m:=FindRoot(g); {пошук
номера вершини - кореня дерева}
b:=m<>0; {якщо
m<>0, то вершина з номером m - корінь}
if b then
begin
First(g);
for i:=1
to m-1 do Next(g);
nod:=Current(g); {nod -
вказівник на вершину - корінь дерева}
k:=0;
TestTree(nod,b,k); {перевірка,
чи є частина графа, починаючи з nod, деревом}
b:=b and
(k=n); {граф є деревом, якщо
кількість вершин k дорівнює n}
end;
if b then
writeln('Граф - дерево з коренем ',m,' з навантаженням ',Weight(nod))
else
writeln('Граф не є деревом')
end.
Нарешті, наведемо файл заголовку модуля
реалізації графів у мові Сі, graph.h.
/* graph.h */
typedef struct node *noderef; /*
Вказівник на вершину графа */
typedef struct lelem *lref; /*Вказівник на елемент списку
вершин*/
struct lelem { /*
Елемент списку вершин */
noderef nd;
lref next;
};
typedef struct { /*
Список вершин (граф) */
lref beg, cur;
} graph;
struct node { /*
Вершина графа */
int d;
graph pl, sl;
};
extern void make_node(noderef *pnod, int n, graph l1, graph l2); /*Створити вершину*/
extern int root(noderef nod); /* Навантаження вершини */
extern void get_pred_list(noderef nod, graph *pl); /* Список попередників */
extern void get_succ_list(noderef nod, graph *pl); /* Список наступників */
extern void set_pred_list(noderef nod, graph l); /*Змінити список
попередників*/
extern void set_pred_list(noderef nod, graph l); /*Змінити список
наступників*/
extern void del_node(noderef *pnod); /* Видалити вершину */
extern void init(graph *pl); /* Почати роботу із списком */
extern int emp_end(graph l); /* Чи порожній залишок списку?*/
extern void first(graph *pl); /*
Встати до початку списку */
extern void next(graph *pl); /* Перейти до наступного
елемента */
extern noderef current(graph l); /* Поточний
елемент списку */
extern void insert(graph *pl, noderef nod); /* Вставити елемент у список */
extern void delete(graph *pl); /* Видалити елемент списку */
Задачі та вправи
Вправа
10.1. Скласти програму, яка впорядковує введену послідовність символів за
зростанням з використанням стеку символів.
Підказка: використати два стеки.
Вправа
10.2. Доповнити модуль для реалізації черг у мові Паскаль підпрограмами Init та Empty.
Вправа
10.3. Скласти модуль для реалізації черг у мові Сі. Розв’язати у мові Сі задачу присвоєння для черг
з використанням модуля.
Вправа
10.4. Доповнити модуль для реалізації деків у мові Сі підпрограмами init, empty, put_en, get_en.
Вправа
10.5. Скласти модуль для реалізації деків у мові Паскаль. Розв’язати у мові Паскаль задачу
впорядкування послідовності чисел з використанням деку.
Вправа
10.6. Доповнити модуль для реалізації класичних списків у мові Паскаль
підпрограмами Init, Empty, Head.
Вправа
10.7. Скласти модуль для реалізації класичних списків у мові Сі. Розв’язати у мові Сі задачу
порівняння двох списків.
Вправа
10.8. Доповнити модуль для реалізації списків з поточним елементом у мові
Сі підпрограмами init, emp_end, first, next, current.
Вправа
10.9. Скласти модуль для реалізації списків з поточним елементом у мові Паскаль. Розв’язати у мові
Паскаль задачу порівняння двох списків з поточним елементом.
Вправа
10.10. Доповнити модуль для реалізації кільцевих списків у мові Паскаль
підпрограмами Init, Next, Current.
Вправа
10.11. Скласти модуль для реалізації кільцевих списків у мові Сі. Розв’язати у мові Сі задачу
впорядкування послідовності чисел з використанням кільцевого списку.
Вправа
10.12. Доповнити модуль для реалізації двозв’язних списків у мові Сі
підпрограмами init, emp_beg, emp_end, first, last, next, previous, current, ins_after.
Вправа
10.13. Скласти модуль для реалізації двозв’язних списків у мові Паскаль. Розв’язати у мові Паскаль
задачу перевірки двозв’язного списку на симетричність.
Вправа
10.14. Доповнити модуль для реалізації бінарних дерев у мові Паскаль
підпрограмами Init, Empty, Root, LeftSon.
Вправа
10.15. Скласти модуль для реалізації бінарних дерев у мові Сі. Розв’язати у мові Сі задачу підрахунку
кількості вузлів бінарного дерева.
Вправа
10.16. Доповнити модуль для реалізації сильно розгалужених дерев у мові Сі
підпрограмами виконання всіх дій окрім створення вершини та видалення вершини.
Вправа
10.17. Скласти модуль для реалізації сильно розгалужених дерев у мові Паскаль. Розв’язати у мові
Паскаль задачу порівняння двох сильно розгалужених дерев.
Вправа
10.18. Доповнити модуль для реалізації графів у мові Паскаль підпрограмами виконання
всіх дій окрім створення вершини, отримання та зміни списку попередників.
Вправа
10.19. Скласти модуль для реалізації графів у мові Сі. Розв’язати у мові Сі задачу перевірки, чи є
граф деревом.
[ЗМІСТ] [Далі] [Назад] [Початок розділу]