Körkörös listák ❄
✲
✲
✲
✻
✻
fej
❄
utolsó
✲
✲
✲
✻
✻
utolsó ✻
fej Példa. Kiszámolós játék. Körben áll n gyermek. k-asával kiszámoljuk őket. Minden k-adik kilép a körből. Az nyer, aki utolsónak marad. #include
using namespace std; typedef struct lista{ char nev[20]; lista *kov; } LISTA; int k,i,n; LISTA *p,*q, *fej, *utolso; 1
void init(){ fej= new LISTA; fej->kov=NULL; utolso=fej; } void olvas(){ FILE *f=fopen("jatek.txt","r"); fscanf(f,"%d", &n); // n: nevek száma for (i=1; i<=n; i++){ p=new LISTA; fscanf(f, "%s", &p->nev); // egy nevet olvasunk p->kov=NULL; utolso->kov=p; utolso=p; }; fclose(f); printf("k="); scanf("%d", &k); }
2
void kiszamol(){ for (i=1;i<=k-1;i++) p=p->kov; printf("%s kilep a korbol\n", p->nev); q=p->kov; *p=*q; delete q; } void main(){ init(); olvas(); utolso->kov=fej->kov; p=fej->kov; while (p!=p->kov) kiszamol(); printf("A gyoztes: %s", p->nev); }
3
Állományból olvasva az állomány végéig: void olvas(){ FILE *f=fopen("jatek2.txt","r"); while (!feof(f)){ // állomány vége? p=new LISTA; fscanf(f, "%s", &p->nev); p->kov=NULL; utolso->kov=p; utolso=p; }; fclose(f); printf("k="); scanf("%d", &k); }
4
Más változat: void olvas(){ FILE *f=fopen("jatek.txt","r"); p=new LISTA; while (fscanf(f, "%s", &p->nev)>0){ if (fej==fej->kov){ p->kov=p; fej->kov=p; } else{ p->kov=fej->kov->kov; fej->kov->kov=p; } p=new LISTA; }; delete(p); fclose(f); printf("k="); scanf("%d", &k); }
5
Ritka mátrixok láncolt ábrázolása 50 0 0 0 10 0 20 0 0 0 0 0 −30 0 −60 5
6
Fák Bináris fák Bináris fák ábrázolásai 1) tömbökkel index info
✎☞
a
✍✌ ✎☞
✎☞
c
b
✍✌ ✎☞
d
✍✌
✍✌ ✎☞
✎☞
e ✍✌
f
✍✌ ✎☞ ✎☞
g h
✍✌ ✍✌ ✎☞
i
✍✌
7
1 2 3 4 5 6 7 8 9
a b c d e f g h i
bal jobb utód utód 2 3 4 0 5 6 0 0 0 7 8 0 9 0 0 0 0 0
2) bináris füzérrel index info 1 2 3 4 5 6 7 8 9
A B C D E F G H I
bal jobb utód utód 2 3 4 0 5 6 0 0 0 7 8 0 9 0 0 0 0 0
kódolás Dyck-szóval: 00 01 11 00 10 01 11 01 ábrázolás A 00 B 01 D 11 C 00 E 10 G 01 I 11 F 01 H vagy 00 01 11 00 10 01 11 01 A B D C E G I F H
8
A 00 B 01 D 11 C 00 E 10 G 01 I 11 F 01 H ↑ 10 X eredmény: A 00 B 01 D 10 X 11 C 00 E 10 G 01 I 11 F 01 H
9
A 00 B 01 D 11 C 00 E 10 G 01 I 11 F 01 H ↑ 00 Y 11 eredmény: A 00 B 01 D 11 C 00 E 00 Y 11 G 01 I 11 F 01 H helyfoglalás szempontjából: eredeti: 3n javasolt: n +
n 8
10
3) dinamikusan typedef struct fa{ típus info; fa *bal, *jobb; } FA;
info✟✟
✟✟ ✙ ✟✟
info ✠
Tetszőleges fák ábrázolásai 1) Lefele mutató kapcsolattartás n c1 · · · cn info
11
❈
✟
❈
❈
info ❈ ❈❲
❈ ❲❈
✡ ✡ ✢
✡
❇
❇ ◆❇
2) Bináris fákkal való ábrázolás bal utód: legbalodalibb utód jobb utód: jobb szomszéd ✎☞
✎☞
A ✍✌ ✎☞
B ✍✌ ✎☞
E ✍✌
✎☞
C ✍✌
✎☞
F ✍✌
A ✍✌ ✎☞
✎☞
D ✍✌
B ✍✌ ✎☞
✎☞✎☞ ✎☞ ✎☞
G ✍✌ H ✍✌ I ✍✌ J ✍✌
E ✍✌
✎☞
C ✍✌
✎☞
✎☞ ✎☞
F ✍✌
K ✍✌ L ✍✌
✎☞
D ✍✌
✎☞
G ✍✌ ✎☞
H ✍✌ infó
bal utód jobb testvér
✎☞✎☞
K I ✍✌ ✍✌ ✎☞✎☞ L ✍✌ J ✍✌
3) Felfele mutató kapcsolattartás infó
szülő
12
Kimeneti ábrázolásmódok behúzással (indentálással)
A B
✎☞
E F
A ✍✌ ✎☞
B ✍✌ ✎☞
E ✍✌
✎☞
C ✍✌
✎☞
F ✍✌
✎☞
C D
D ✍✌
✎☞✎☞ ✎☞ ✎☞
G ✍✌ H ✍✌ I ✍✌ J ✍✌ ✎☞ ✎☞
G H K
K ✍✌ L ✍✌
I L J
zárójeles kifejezéssel A B E, F , C, D G, H(K), I(L), J
13
halmazokkal ✎☞
A ✍✌ ✎☞
B ✍✌ ✎☞
✎☞
C ✍✌
✎☞
E ✍✌
✎☞
D ✍✌
✎☞✎☞ ✎☞ ✎☞
F ✍✌
G ✍✌ H ✍✌ I ✍✌ J ✍✌ ✎☞ ✎☞
K ✍✌ L ✍✌ A
B
E
C
F
D
G
H K
I
J
L
Bemeneti ábrázolásmódok bináris fánál: pl. preorder bejárás szerint, jelezve a hiányzó utódokat tetszőleges fánál: mindig jelezni kell az utódok számát 14
Bináris fa bejárásai preorder – gyökérkezdő (gyökér, bal részfa, jobb részfa) inorder – gyökérközepű (bal részfa, gyökér, jobb részfa) postorder – gyökérvégző (bal részfa, jobb részfa, gyökér) ✎☞
A ✍✌ ✎☞
✎☞
B ✍✌
C ✍✌ ✎☞
✎☞
D ✍✌
preorder: A, B, C, D, F, H, E, G
E ✍✌ inorder: B, A, D, H, F, C, G, E ✎☞ ✎☞
F ✍✌ G ✍✌
postorder: B, H, F, D, G, E, C, A
✎☞
H ✍✌
#include using namespace std; struct Csucs{ char info; Csucs *bal, *jobb; }; Csucs *binfa, *x;
15
void Preorder(Csucs* AktualisCsucs){ if (AktualisCsucs){ printf("%c ", AktualisCsucs->info); Preorder(AktualisCsucs->bal); Preorder(AktualisCsucs->jobb); }; }
void Postorder(Csucs* AktualisCsucs){ if (AktualisCsucs){ Postorder(AktualisCsucs->bal); Postorder(AktualisCsucs->jobb); printf("%c ", AktualisCsucs->info); }; } void Inorder(Csucs* AktualisCsucs){ if (AktualisCsucs){ Inorder(AktualisCsucs->bal); printf("%c ", AktualisCsucs->info); Inorder(AktualisCsucs->jobb); }; }
16
Csucs* Keres(Csucs* AktualisCsucs, char c){ if (AktualisCsucs){ if (AktualisCsucs->info==c) return AktualisCsucs; else {x=Keres(AktualisCsucs->bal,c); if (x) return x; x=Keres(AktualisCsucs->jobb,c); if (x) return x; }; }; return NULL; } void Letrehoz(){ char a,b,c; Csucs *p,*q; FILE *f=fopen("binfa.txt","r"); fscanf(f, "%c%c%c%c", &a,&b,&c);// gyökér olvasása binfa=new Csucs; // gyökér létrehozása binfa->info=a; if (b!=’ ’){p=new Csucs; p->info=b; binfa->bal=p; p->bal=p->jobb=NULL; }; if (c!=’ ’){p=new Csucs; p->info=c; binfa->jobb=p; p->bal=p->jobb=NULL; }; 17
while (!feof(f)){ // következő csúcs olvasása fscanf(f, "%c%c%c%c", &a,&b,&c); q=Keres(binfa,a); if (q) { if (b!=’ ’){p=new Csucs; p->info=b; q->bal=p; p->bal=p->jobb=NULL; }; if (c!=’ ’){p=new Csucs; p->info=c; q->jobb=p; p->bal=p->jobb=NULL; }; }; }; fclose(f); }; void main(){ Letrehoz(); printf("\n Preorder: "); Preorder(binfa); printf("\n Inorder: "); Inorder(binfa); printf("\n Postorder: "); Postorder(binfa); }
18
Példa. A "binfa.txt" állomány tartalma: ABC CDE EF FGH A fa: ✎☞
A ✍✌ ✎☞ ✎☞
B C ✍✌ ✍✌ ✎☞ ✎☞ D ✍✌
E ✍✌
✎☞
F ✍✌
✎☞
G ✍✌
✎☞
H ✍✌
Bejárások: pre: ABCDEFGH in: BADCGFHE post: BDGHFECA
19
