Listák • félstatikus adatszerkezetek: verem, várakozási sor, hasítótábla • dinamikus adatszerkezetek: lineáris lista, fa, hálózat A verem — LIFO lista (Last In First Out) angolul stack, románul stivă bevitel a verembe
kivitel a veremből
-
-
6 ?
6
verem ?
statikus megoldás V — verem (egydimenziós tömb) t — a verem teteje (csúcsa) Üres verem létrehozása: t := 0. 1
IsEmpty(V ) 1. if t=0 2. then return igaz else return hamis 3. IsFull(V ) 1. if t = M axElem 2. then return igaz 3. else return hamis Push(V, a) 1. t := t + 1 2. Vt := a Pop(V ) 1. a := Vt 2. t := t − 1 3. return a Top(V ) 1. a := Vt 2. return a 2
dinamikus megoldás – nagyon egyszerűsített! typedef int ItemType; struct NodeType{ ItemType info; NodeType* next; } NodeType* topPtr; bool IsEmpty(){ return (topPtr==NULL); } void Push(ItemType newItem){ NodeType* location; location= new NodeType; location->info = newItem; location->next = topPtr; topPtr=location; }
ItemType Top(){ return topPtr->info; } 3
ItemType Pop(){ ItemType a; a= topPtr->info; NodeType* tempPtr; tempPtr=topPtr; topPtr=topPtr->next; delete tempPtr; return a; }
A főprogramban: topPtr=NULL; Alkalmazás Bináris fák kódolása A gyökérből kiindulva, előbb a bal, majd a jobb oldali részfát kódoljuk. Ha egy csúcsból kiindulva mindkét leszármazott létezik, akkor a bal oldali él kódja 00, a jobb élé pedig 11; egy bal oldali él kódja 01, és egy jobb oldali él kódja 10, amennyiben hiányzik az él párja. Az alábbi 3-csúcsú bináris fa kódja: u
u
u
u
u
u
u
u u
01 01
u
01 10
u
u
10 01
10 10
u u
00 01 11 00 10 11 u
u
u
u
Egy bonyolultabb példa: u
u
u u
4
00 11
Bináris fa kódolási algoritmusa Bináris-Fa-Kódolás(B) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
Legyen B-ben BL a bal, BR pedig a jobb oldali részfa if BL 6= ∅ és BR = ∅ then kiír 01 Bináris-Fa-Kódolás(BL) if BL = ∅ és BR 6= ∅ then kiír 10 Bináris-Fa-Kódolás(BR ) if BL 6= ∅ és BR 6= ∅ then kiír 00 Bináris-Fa-Kódolás(BL) kiír 11 Bináris-Fa-Kódolás(BR )
Az eljárás hívása Bináris-Fa-Kódolás(B)
5
Visszakódolás Ha egy aktuális csúcsból élt húzunk egy másik csúcsba, akkor ez utóbbi aktuális csúccsá válik. Visszakódolás-Bináris-Fává(c) 1. if c nem üres then olvasd ab 2. 3. töröld ab-t c-ből 4. if ab = 01 5. then rajzolj egy bal élt az aktuális csúcsból 6. Visszakódolás-Bináris-Fává(c) if ab = 10 7. 8. then rajzolj egy jobb élt az aktuális csúcsból 9. Visszakódolás-Bináris-Fává(c) 10. if ab = 00 12. then írd be a verembe az aktuális csúcs helyét 13. rajzolj egy bal élt az aktuális csúcsból 14. Visszakódolás-Bináris-Fává(c) if ab = 11 15. 16. then olvasd ki a verem tetejét, ez lesz az aktuális csúcs 17. rajzolj egy jobb élt az aktuális csúcsból 18. Visszakódolás-Bináris-Fává(c)
Az eljárás hívása: Visszakódolás-Bináris-Fává(c) 6
Várakozási sor – FIFO (First In First Out) angolul queue, románul şir de aşteptare -
be
-
ki
e
h
egyik végén hozzáadunk egy elemet, a másikon olvassuk és töröljük Várakozási sor AAT, műveletek: üres, televan, beszúr, olvas és töröl
N N=NULL
6
6
hatso
elso
void Bevisz (ItemType newItem){ NodeType* newNode newNode = new NodeType; newNode->info = newItem; newNode->next = NULL; if (hatso==NULL) elso = newNode; else hatso->next=newNode; hatso=newNode; } 7
void Kivesz (ItemType& Item){ NodeType* tempPtr; tempPtr=elso; Item = elso->info; elso = elso->next; if (elso == NULL) hatso = NULL; delete tempPtr; } Priorítási sor — valamilyen kulcs szerint rendezett egyik végén veszünk ki, a kulcs szerinti helyre szúrunk be
8
Tetszőleges lista p → info kov beszúrás p után 6
6
p
s1
J
SS(1) J(2) o S JJ ^ S
6
s2
6
q
(1) q->kov = p->kov (2) p->kov = q törlés p utáni törlése 6
-
6
6
p
s1
s2 ? -
6
s1
6
p
-
6
q
q = p->kov p->kov = q->kov delete q
6
s2
p törlése q = p->kov *p = *q delete q
9
Két irányban láncolt lista #include
using namespace std; struct elem{ char szo[10]; elem *elore, *hatra; }; class DLista{ elem *str1, *str2; public: DLista(); ~DLista(){MindentTorol();}; void MindentTorol(); void BeszurEle(elem* p, char ujszo[10]); void BeszurUtana(elem* p, char ujszo[10]); void BeszurListaElejere(char ujszo[10]); void BeszurListaVegere(char ujszo[10]); void TorlesElotte(elem* p); void TorlesUtana(elem* p); void Torles(elem* p); void BejarElejerol(); void BejarVegerol(); }; 10
DLista::DLista(){ str1 = new elem; str2 = new elem; str1->hatra = NULL; str1->elore = str2; str2->hatra = str1; str2->elore = NULL; } void DLista::BeszurEle(elem *p, char ujszo[10]){ elem *q = new elem; strcpy(q->szo, ujszo); p->hatra->elore = q; q->hatra = p->hatra; q->elore = p; p->hatra = q; } void DLista::BeszurUtana(elem *p, char ujszo[10]){ elem *q = new elem; strcpy(q->szo, ujszo); q->elore = p->elore; q->hatra = p; p->elore->hatra = q; 11
p->elore = q; }; void DLista::BeszurListaElejere(char ujszo[10]){ BeszurUtana(str1,ujszo); }; void DLista::BeszurListaVegere(char ujszo[10]){ BeszurEle(str2,ujszo); }; void DLista::TorlesElotte(elem* p){ elem *r = p->hatra; p->hatra->hatra->elore = p; p->hatra = p->hatra->hatra; delete r; }; void DLista::TorlesUtana(elem* p){ elem *r = p->hatra; p->elore = p->elore->elore; p->elore->hatra = p; delete r; };
12
void DLista::Torles(elem* p){ elem *r = p; p->hatra->elore = p->elore; p->elore->hatra = p->hatra; delete r; }; void DLista::BejarElejerol(){ elem *p = str1->elore; while (p!=str2){ printf("%s ", p->szo); p = p->elore; } printf("\n"); }; void DLista::BejarVegerol(){ elem *p = str2->hatra; while (p!=str1){ printf("%s ", p->szo); p = p->hatra; } printf("\n"); };
13
void DLista::MindentTorol(){ elem* tempPtr; while (str1!=NULL){ tempPtr = str1; str1 = str1->elore; delete tempPtr; }; }; void main(){ DLista dlista; char uj[10]; printf("A szo: "); scanf("%s", &uj); while (strcmp(uj,"*")!=0){ dlista.BeszurListaVegere(uj); printf("A szo: "); scanf("%s", &uj); }; dlista.BejarElejerol(); printf("\n"); dlista.BejarVegerol(); };
14
