Táblázatok fontosabb műveletei 1

Táblázatok fontosabb műveletei - - Soros táblázat procedure BESZÚR1(TÁBLA, újelem) - - beszúrás soros táblázatba - - a táblázatot egy rekordokat tartalmazó dinamikus vektorral reprezentáljuk - - a rekordok kulcs és érték mezőkből állnak 1. i ← 1 2. while i ≤ méret(TÁBLA) és TÁBLA[i].kulcs 6= újelem.kulcs do i←i+1

3.

4. end while 5. if

i ≤ méret(TÁBLA) then KIVÉTEL "már van ilyen kulcsú elem"

6. 7. else 8.

TÁBLA[i] ← újelem

9.

méret(TÁBLA) ← méret(TÁBLA) + 1

10. end if end procedure procedure TÖRÖL1(TÁBLA, kulcs) - - törlés soros táblázatból - - a táblázatot egy rekordokat tartalmazó dinamikus vektorral reprezentáljuk - - a rekordok kulcs és érték mezőkből állnak 1. i ← 1 2. while i ≤ méret(TÁBLA) és TÁBLA[i].kulcs 6= kulcs do i←i+1

3.

4. end while 5. if

i > méret(TÁBLA) then

6.

KIVÉTEL "nincs ilyen kulcsú elem"

7. else 8.

TÁBLA[i] ← TÁBLA[méret(TÁBLA)]

9.

méret(TÁBLA) ← méret(TÁBLA) – 1

10. end if end procedure

1

Táblázatok fontosabb műveletei procedure BESZÚR1a(TÁBLA, újelem) - - beszúrás soros táblázatba "strázsa" technikával - - a táblázatot egy rekordokat tartalmazó dinamikus vektorral reprezentáljuk - - a rekordok kulcs és érték mezőkből állnak 1. méret(TÁBLA) ← méret(TÁBLA) + 1 2. TÁBLA[méret(TÁBLA)] ← újelem 3. i ← 1 4. while TÁBLA[i].kulcs 6= újelem.kulcs do i←i+1

5.

6. end while 7. if

i ≤ méret(TÁBLA) then

8.


9.

KIVÉTEL "már van ilyen kulcsú elem"

10. end if end procedure procedure TÖRÖL1a(TÁBLA, kulcs) - - törlés soros táblázatból "strázsa" technikával - - a táblázatot egy rekordokat tartalmazó dinamikus vektorral reprezentáljuk - - a rekordok kulcs és érték mezőkből állnak 1. méret(TÁBLA) ← méret(TÁBLA) + 1 2. TÁBLA[méret(TÁBLA)].kulcs ← kulcs 3. i ← 1 4. while TÁBLA[i].kulcs 6= kulcs do i←i+1

5.

6. end while 7. méret(TÁBLA) ← méret(TÁBLA) – 1 8. if

i > méret(TÁBLA) then

9.


10. else 11.

TÁBLA[i] ← TÁBLA[méret(TÁBLA)]

12.



2

Táblázatok fontosabb műveletei - - Önátrendező táblázat procedure ELÉR2(tábla, kulcs) - - adott kulcsú elem elérése önátrendező táblázatban - - a táblázatot egyirányban láncolt listával reprezentáljuk 1. x ← tábla 2. előző ← NIL 3. while x 6= NIL és x→kulcs 6= kulcs do 4.

előző ← x

5.

x ← x→következő

6. end while 7. if

x = NIL then

8.


9. else 10.

(x→érték) feldolgozása

11.

if

előző 6= NIL then

12.

előző→következő ← x→következő

13.

x→következő ← tábla

14.

tábla ← x

15.

end if


3

Táblázatok fontosabb műveletei - - Kulcstranszformációs táblázat – "nyílt címzés" szinonimakezelési technikával procedure BESZÚR3(TÁBLA, újelem) - - beszúrás kulcstranszformációs táblázatba "nyílt címzés" szinonimakezelési technikával - - a táblázatot egy rekordokat tartalmazó statikus vektorral reprezentáljuk - - a rekordok kulcs, érték és státusz (foglalt, üres, törölt) mezőkből állnak 1. poz ← HASH(újelem.kulcs) 2. if

TÁBLA[poz].státusz = ÜRES then

3.

TÁBLA[poz].státusz ← FOGLALT

4.

TÁBLA[poz].kulcs ← újelem.kulcs

5.

TÁBLA[poz].érték ← újelem.érték TÁBLA[poz].státusz = FOGLALT és TÁBLA[poz].kulcs = újelem.kulcs then

6. else if


7. 8. else

i ← (poz mod méret(TÁBLA)) + 1

9. 10. ...

while i 6= poz és (TÁBLA[i].státusz = TÖRÖLT vagy TÁBLA[i].státusz = FOGLALT és TÁBLA[i].kulcs 6= újelem.kulcs) do i ← (i mod méret(TÁBLA)) + 1

11. 12.

end while

13.

if

i 6= poz és TÁBLA[i].státusz = FOGLALT then KIVÉTEL "már van ilyen kulcsú elem"

14. 15.

else if

TÁBLA[poz].státusz = FOGLALT then

16.

i ← poz mod méret(TÁBLA) + 1

17.

while i 6= poz és TÁBLA[i].státusz = FOGLALT do i ← i mod méret(TÁBLA) + 1

18. 19.

end while

20.

if

KIVÉTEL "betelt a táblázat"

21.

end if

22. 23.

i = poz then

else i ← poz

24. 25.

end if

26.

TÁBLA[i].státusz ← FOGLALT

27.

TÁBLA[i].kulcs ← újelem.kulcs

28.

TÁBLA[i].érték ← újelem.érték


4

Táblázatok fontosabb műveletei procedure TÖRÖL3(TÁBLA, kulcs) - - törlés kulcstranszformációs táblázatból "nyílt címzés" szinonimakezelési technikával - - a táblázatot egy rekordokat tartalmazó statikus vektorral reprezentáljuk - - a rekordok kulcs, érték és státusz (foglalt, üres, törölt) mezőkből állnak 1. poz ← HASH(kulcs) 2. if

TÁBLA[poz].státusz = ÜRES then KIVÉTEL "nincs ilyen kulcsú elem"

3.

TÁBLA[poz].státusz = FOGLALT és TÁBLA[poz].kulcs = kulcs then

4. else if

TÁBLA[poz].státusz ← TÖRÖLT

5. 6. else 7.

i ← poz mod méret(TÁBLA) + 1

8.

while i 6= poz és (TÁBLA[i].státusz = TÖRÖLT vagy TÁBLA[i].státusz = FOGLALT és TÁBLA[i].kulcs 6= kulcs) do

...

i ← i mod méret(TÁBLA) + 1

9. 10.

end while

11.

if

i = poz vagy TÁBLA[i].státusz = ÜRES then KIVÉTEL "nincs ilyen kulcsú elem"

12. 13.

else TÁBLA[i].státusz ← TÖRÖLT

14. 15.

end if


5

Táblázatok fontosabb műveletei - - Kulcstranszformációs táblázat – "láncolás" szinonimakezelési technikával procedure BESZÚR4(TÁBLA, újelem) - - beszúrás kulcstranszformációs táblázatba "láncolás" szinonimakezelési technikával - - a táblázatot egy rekordokat tartalmazó statikus vektorral reprezentáljuk - - a rekordok kulcs, érték, státusz (foglalt, üres, törölt) és mutató mezőkből állnak 1. poz ← HASH(újelem.kulcs) 2. if

TÁBLA[poz].státusz 6= FOGLALT then

3.


4.


5.

TÁBLA[poz].érték ← újelem.érték

6.

TÁBLA[poz].mutató ← 0

7. else if 8.

TÁBLA[poz].kulcs = újelem.kulcs then


9. else 10.

i ← TÁBLA[poz].mutató

11.

előző ← poz

12.

while i 6= 0 és TÁBLA[i].kulcs 6= újelem.kulcs do

13.

előző ← i

14.

i ← TÁBLA[i].mutató

15.

end while

16.

if

i 6= 0 then KIVÉTEL "már van ilyen kulcsú elem"

17. 18.

end if

19.

i ← előző mod méret(TÁBLA) + 1

20.

while i 6= előző és TÁBLA[i].státusz = FOGLALT do i ← i mod méret(TÁBLA) + 1

21. 22.

end while

23.

if

i = előző then KIVÉTEL "betelt a táblázat"

24. 25.

end if

26.

TÁBLA[i].státusz ← FOGLALT

27.

TÁBLA[i].kulcs ← újelem.kulcs

28.

TÁBLA[i].érték ← újelem.érték

29.

TÁBLA[i].mutató ← 0

30.

TÁBLA[előző].mutató ← i


6

Táblázatok fontosabb műveletei procedure TÖRÖL4(TÁBLA, kulcs) - - törlés kulcstranszformációs táblázatból "láncolás" szinonimakezelési technikával - - a táblázatot egy rekordokat tartalmazó statikus vektorral reprezentáljuk - - a rekordok kulcs, érték, státusz (FOGLALT, ÜRES, TÖRÖLT) és mutató mezőkből állnak 1. poz ← HASH(kulcs) 2. if


3.

KIVÉTEL "nincs ilyen kulcsú elem" TÁBLA[poz].kulcs = kulcs then

4. else if 5.

if

TÁBLA[poz].mutató = 0 then TÁBLA[poz].státusz ← TÖRÖLT

6. 7.

else TÖRÖL_KÖV(TÁBLA, poz)

8. 9.

end if

10. else 11.

i ← TÁBLA[poz].mutató

12.

előző ← poz

13.

while i 6= 0 és TÁBLA[i].kulcs 6= kulcs do

14.

előző ← i

15.

i ← TÁBLA[i].mutató

16.

end while

17.

if

i = 0 then KIVÉTEL "nincs ilyen kulcsú elem"

18. 19.

else if

TÁBLA[i].mutató = 0 then

20.

TÁBLA[i].státusz ← TÖRÖLT

21.

TÁBLA[előző].mutató ← 0

22.

else TÖRÖL_KÖV(TÁBLA, i)

23. 24.

end if


7

Táblázatok fontosabb műveletei procedure TÖRÖL_KÖV(TÁBLA, poz) - - egy adott pozícióban lévő elem törlése láncból 1. köv ← TÁBLA[poz].mutató 2. i ← TÁBLA[köv].mutató 3. while i 6= 0 és HASH(TÁBLA[i].kulcs) 6= köv do i ← TÁBLA[i].mutató

4.

5. end while 6. if

i = 0 then

7.

TÁBLA[poz] ← TÁBLA[köv]

8.

TÁBLA[köv].státusz ← TÖRÖLT

9. else 10.

elem ← TÁBLA[i]

11.

TÖRÖL(TÁBLA, elem.kulcs)

12.

TÁBLA[poz] ← TÁBLA[köv]

13.

TÁBLA[köv].státusz ← TÖRÖLT

14.

BESZÚR(TÁBLA, elem)


8

Táblázatok fontosabb műveletei procedure BESZÚR_4a(TÁBLA, újelem) - - beszúrás kulcstranszformációs táblázatba "láncolás" szinonimakezelési technikával - - Minden lánc csak szinonim elemeket tartalmaz. - - a táblázatot egy rekordokat tartalmazó statikus vektorral reprezentáljuk - - a rekordok kulcs, érték, státusz (FOGLALT, ÜRES, TÖRÖLT) és mutató mezőkből állnak 1. poz ← HASH(újelem.kulcs) 2. if

TÁBLA[poz].státusz = FOGLALT then

3.

i ← első ← HASH(TÁBLA[poz].kulcs)

4.

if

poz = első then repeat

5.

if

6.

TÁBLA[i].kulcs = újelem.kulcs then KIVÉTEL "Már van ilyen kulcsú elem."

7. 8.

end if

9.

utolsó ← i i ← TÁBLA[i].mutató

10.

until i = 0

11. 12.

else repeat

13.

if

14.

i = poz then előző ← utolsó

15. 16.

end if

17.

utolsó ← i

18.

i ← TÁBLA[i].mutató until i = 0

19. 20.

end if

21.

i ← (utolsó mod méret(TÁBLA)) + 1

22.

while i 6= utolsó és TÁBLA[i].státusz = FOGLALT do i ← (i mod méret(TÁBLA)) + 1

23. 24.

end while

25.

if

i = utolsó then KIVÉTEL "Betelt a táblázat."

26. 27.

else if

TÁBLA[utolsó].mutató ← poz ← i

28. 29.

poz = első then

else

30.

TÁBLA[i] ← TÁBLA[poz]

31.

TÁBLA[előző].mutató ← i

32.

end if

33. end if 34. TÁBLA[poz].kulcs ← újelem.kulcs 35. TÁBLA[poz].érték ← újelem.érték 36. TÁBLA[poz].státusz ← FOGLALT 37. TÁBLA[poz].mutató ← 0 end procedure

9

Táblázatok fontosabb műveletei procedure TÖRÖL_4a(TÁBLA, kulcs) - - törlés kulcstranszformációs táblázatból "láncolás" szinonimakezelési technikával - - Minden lánc csak szinonim elemeket tartalmaz. - - a táblázatot egy rekordokat tartalmazó statikus vektorral reprezentáljuk - - a rekordok kulcs, érték, státusz (FOGLALT, ÜRES, TÖRÖLT) és mutató mezőkből állnak 1. poz ← HASH(kulcs) 2. if 3.

TÁBLA[poz].státusz 6= FOGLALT vagy HASH(TÁBLA[poz].kulcs) 6= poz then KIVÉTEL "nincs ilyen kulcsú elem"

4. end if 5. előző ← 0 6. while poz 6= 0 és TÁBLA[poz].kulcs 6= kulcs do 7.

előző ← poz

8.

poz ← TÁBLA[poz].mutató

9. end while 10. if 11.

poz = 0 then KIVÉTEL "nincs ilyen kulcsú elem"

12. else if 13.

előző 6= 0 then

TÁBLA[előző].mutató ← TÁBLA[poz].mutató

14. else if

TÁBLA[poz].mutató 6= 0 then

15.

előző ← poz

16.

poz ← TÁBLA[poz].mutató

17.

TÁBLA[előző] ← TÁBLA[poz]

18. end if 19. TÁBLA[pos].státusz ← TÖRÖLT end procedure

10

Táblázatok fontosabb műveletei - - Kulcstranszformációs táblázat – "független túlcsordulási lista" szinonimakezelési technikával procedure BESZÚR5(TÁBLA, újelem) - - beszúrás kulcstranszformációs táblázatba - - "független túlcsordulási lista" szinonimakezelési technikával - - a táblázatot egy rekordokat tartalmazó statikus vektorral reprezentáljuk - - a rekordok kulcs, érték, státusz (FOGLALT, ÜRES, TÖRÖLT) és mutató mezőkből állnak 1. poz ← HASH(újelem.kulcs) 2. if


3.


4.


5.


6.

TÁBLA[poz].mutató ← NIL

7. else if 8.



9. else if

TÁBLA[poz].mutató = NIL then

10.

új ← lefoglal

11.

új→kulcs ← újelem.kulcs

12.

új→érték ← újelem.érték

13.

új→következő ← NIL

14.

TÁBLA[poz].mutató ← új

15. else 16.

x ← TÁBLA[poz].mutató

17.

while x 6= NIL és x→kulcs 6= újelem.kulcs do

18.

előző ← x

19.


20.

end while

21.

if

x 6= NIL then KIVÉTEL "már van ilyen kulcsú elem"

22. 23.

end if

24.

új ← lefoglal

25.


26.


27.

új→következő ← NIL

28.

előző→következő ← új


11

Táblázatok fontosabb műveletei procedure TÖRÖL5(TÁBLA, kulcs) - - törlés kulcstranszformációs táblázatból - - "független túlcsordulási lista" szinonimakezelési technikával - - a táblázatot egy rekordokat tartalmazó statikus vektorral reprezentáljuk - - a rekordok kulcs, érték, státusz (FOGLALT, ÜRES, TÖRÖLT) és mutató mezőkből állnak 1. poz ← HASH(kulcs) 2. if


3.

KIVÉTEL "nincs ilyen kulcsú elem" TÁBLA[poz].kulcs = kulcs then

4. else if 5.

if

TÁBLA[poz].mutató = NIL then TÁBLA[poz].státusz ← TÖRÖLT

6. 7.

else

8.

köv ← TÁBLA[poz].mutató

9.

TÁBLA[poz].kulcs ← köv→kulcs

10.

TÁBLA[poz].érték ← köv→érték

11.

TÁBLA[poz].mutató ← köv→következő

12.

end if

13. else 14.


15.

előző ← NIL

16.

while x 6= NIL és x→kulcs 6= kulcs do

17.

előző ← x

18.


19.

end while

20.

if

x = NIL then KIVÉTEL "nincs ilyen kulcsú elem"

21. 22.

else if

TÁBLA[poz].mutató ← x→következő

23. 24.

else előző→következő ← x→következő

25. 26.

előző = NIL then

end if


12

Táblázatok fontosabb műveletei procedure BESZÚR5a(TÁBLA, újelem) - - beszúrás kulcstranszformációs táblázatba - - "független túlcsordulási lista" szinonimakezelési technikával - - a táblázatot egy rekordokat tartalmazó statikus vektorral reprezentáljuk - - a rekordok kulcs, érték, státusz (FOGLALT, ÜRES, TÖRÖLT) és mutató mezőkből állnak 1. poz ← HASH(újelem.kulcs) 2. if


3.


4.


5.


6.

TÁBLA[poz].mutató ← NIL

7. else if 8.



9. else 10.


11.

while x 6= NIL és x→kulcs 6= újelem.kulcs do x ← x→következő

12. 13.

end while

14.

if

x 6= NIL then KIVÉTEL "már van ilyen kulcsú elem"

15. 16.

end if

17.

új ← lefoglal

18.


19.


20.

új→következő ← TÁBLA[poz].mutató

21.

TÁBLA[poz].mutató ← új


13

Táblázatok fontosabb műveletei procedure TÖRÖL5a(TÁBLA, kulcs) - - törlés kulcstranszformációs táblázatból - - "független túlcsordulási lista" szinonimakezelési technikával - - a táblázatot egy rekordokat tartalmazó statikus vektorral reprezentáljuk - - a rekordok kulcs, érték, státusz (FOGLALT, ÜRES, TÖRÖLT) és mutató mezőkből állnak 1. poz ← HASH(kulcs) 2. if

TÁBLA[poz].státusz 6= FOGLALT then KIVÉTEL "nincs ilyen kulcsú elem"

3.

TÁBLA[poz].kulcs = kulcs then

4. else if if

5.

TÁBLA[poz].mutató = NIL then TÁBLA[poz].státusz ← TÖRÖLT

6. else

7. 8.

köv ← TÁBLA[poz].mutató

9.

TÁBLA[poz].kulcs ← köv→kulcs

10.

TÁBLA[poz].érték ← köv→érték

11.

TÁBLA[poz].mutató ← köv→következő end if

12. 13. else

TÖRÖL_LÁNCBÓL(TÁBLA[poz].mutató,kulcs)

14.

15. end if end procedure procedure TÖRÖL_LÁNCBÓL(fej, kulcs) - - törlés a független túlcsordulási listából 1. if

fej = NIL then

2.


3. else if 4.

fej→kulcs = kulcs then

fej ← fej→mutató

5. else 6.

TÖRÖL_LÁNCBÓL(fej→mutató, kulcs)


14

Táblázatok fontosabb műveletei 1

Recommend Documents