[̲] [] [] [ ]

 

10.5.2

 

, 2. , . , . . ³, 䳿 : 䳿 䳿 . . , :

1.         .

2.         ?

3.         .

4.         .

5.         .

6.         .

7.         .

8.         ?

9.         .

10.     .

11.     .

12.     .

13.     .

 

ij 1 6 䳿 , 䳿 7 13 - 䳿 . 䳿 1 - 6.

ij 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");

}

 

10.5.3

 

. ³, , ( 0 1, 1 , vi, vj, ). , , . , , () , (). .

:

1.             .

2.             .

3.             .

4.             .

5.             .

6.             .

7.             .

8.             .

9.             ?

10.         .

11.         .

12.         .

13.         .

14.         .

 

ij 1 7 䳿 , 䳿 8 14 - 䳿 . 䳿 1 - 7.

ij 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. ѳ. ѳ , .

 

[̲] [] [] [ ]