Adatszerkezetek

 

A következőkben röviden ismertetésre kerülnek a verem, sor és rekord fogalmak.

 

1. Verem (stack):

 

N elem tárolására képes.

Last In First Out adatszerkezet (amit utolsónak be, azt elsőnek ki)

 

Üres: Empty

Tele: Full

Inicializálás: Init

Berak: Push

Kiszed: Pop

 

VM: egész – veremmutató (az elemek számát mutatja)

 

1. Verem üres, ha VM=0

 

2. Verem teli, ha VM=N

 

3. Verem üresre állítása (inicializálása): VM:=0

 

4. Elem elhelyezése a verembe:

HA VM<>N AKKOR (vagyis VM<N)

  VM:=VM+1

  Tomb[VM]:=Elem

KÜLÖNBEN

  HIBA! (Fel kell dolgozni!)

 

5. Elem kiszedése a veremből:

HA VM<>0 AKKOR (vagyis VM>0)

  Elem:=Tomb[VM]

  VM:=VM-1

KÜLÖNBEN

  HIBA! (Fel kell dolgozni!)

 

A verem létrehozása után üresre kell állítani (inicializálni kell) a vermet! A verem egy butított tömb.

 

Pl. Egy numerikus kifejezésnél ellenőrizni kell, hogy jól van-e zárójelezve. (12*(14-(-12)+8)-4)

(Elég egy változó értékét növelni és csökkenteni, nem kell verem.)

Menet közben betelhet a verem. Az elején meg kell adni, hogy hány nyitó (vagy záró) zárójelet tartalmazhat.

 

CIKLUS a végéig

  HA ’(’ AKKOR

    Elem elhelyezése a verembe

  HAVÉGE

  HA ’)’ AKKOR

    Elem kiszedése a veremből – Hiba esetén több záró zárójel van, mint nyitó!

  HAVÉGE

CVÉGE

HA VM=0 AKKOR

  Jó!

KÜLÖNBEN

  Több nyitó zárójel van, mint záró zárójel!

 

Eljárás- és függvényhívások esetén a proci használ verem adatszerkezetet.

 

2. Sor (queue):

 

N elem tárolására képes.

First In First Out adatszerkezet (amit elsőnek be, azt elsőnek ki)

 

1. Egyszerű sorok:

a) Egyszer használatos sor,

b) léptetős (többször használatos) sor.

2. Ciklikus sorok.

 

1/a. Egyszer használatos sor:

 

Ha végig beraktuk, azután kiszedtük, akkor már nem tudjuk használni.

Két változó van: első és utolsó.

 

Init:

ELSO:=1

UTOLSO:=0

 

Üres:

ELSO>UTOLSO

 

Tele:

UTOLSO=N

 

Betesz:

HA UTOLSO<>N AKKOR

  UTOLSO:=UTOLSO+1

  Sor[UTOLSO]:=Elem

KÜLÖNBEN

  HIBA!

 

Kivesz:

HA ELSO<=UTOLSO AKKOR

  Elem:=Sor[ELSO]

  ELSO:=ELSO+1

KÜLÖNBEN

  HIBA!

 

1/b. Léptetős sor:

 

A sor elemeit visszahúzza (balra lépteti). Hasonlít az egyszer használatoshoz, csak a kiszedés módosul.

 

Kivesz:

HA ELSO<=UTOLSO AKKOR

  Elem:=Sor[ELSO]

  CIKLUS I:=2-től UTOLSO-ig

      Sor[I-1]:=SOR[I]

    CVÉGE

KÜLÖNBEN

  HIBA!

 

2. Ciklikus sor:

 

Felhasználja a már kiolvasott elemek helyeit, ha már feltöltődött a sor. Amikor összeér a 2 változó, akkor inicializál.

 

Init:

ELSO:=1

UTOLSO:=0

 

Üres:

UTOLSO=0

 

Teli:

ELSO=1 AND UTOLSO=N

(Mert mindig úgy teszünk bele elemet, hogy az utolsót növeljük először.)

VAGY

UTOLSO>0 AND UTOLSO= ELSO-1

 

Betesz:

HA NOT ((ELSO=1 AND UTOLSO=N) OR (UTOLSO>0 AND UTOLSO= ELSO-1)) AKKOR

  HA UTOLSO<N AKKOR

  UTOLSO:=UTOLSO+1

  KÜLÖNBEN (vagyis UTOLSO=N)

    UTOLSO:=1 (Átfordul a sor első indexére)

  HAVÉGE

  Sor[UTOLSO]:=Elem

KÜLÖNBEN

  HIBA!

 

Kivesz:

HA UTOLSO<>0 AKKOR

  Elem:=Sor[Elem]

  HA ELSO=UTOLSO AKKOR

    Init

  KÜLÖNBEN

    HA ELSO<N AKKOR

      ELSO:=ELSO+1

    KÜLÖNBEN (vagyis ELSO=N)

      ELSO:=1

    HAVÉGE

  HAVÉGE

KÜLÖNBEN

  HIBA!

HAVÉGE

 

3. Rekord:

 

Példa:

 

típus     RTanulo=rekord

            Nev:Szöveg;

            Szulido:Szöveg;

            Lakcim:Szöveg;

            Osztondij:Szöveg;

tvége

 

Egyik:   RTanulo

Oszes:  Egész

 

A rekord részadatai mezők (Nev, Szulido, Lakcim, Osztondij). Egyesével lehet a rekord mezőit kezelni.

 

Szintaktika:

 

Rekordnév.Mezőnév:=érték

 

Egyik.Nev:=’Kiss István’

 

Be: Egyik.Nev

Osszes:=Osszes+Egyik.Osztondij

 

Masik:Rtanulo

 

Az egyik rekord értékeit átadhatjuk a másik rekordnak, ha azonos típusú a két rekord.

Masik:=Egyik

 

Példa:

 

A futók helyezésére vagyunk kíváncsiak. Ehhez rekord a megoldás.

 

típus     RTanulo=rekord

            Nev:Szöveg;

            Iskola:Szöveg;

            Evfolyam:Szöveg;

            Ido:Szöveg;

tvége

 

T:tomb[1..n]RTanuloból

C:RTanulo

Ciklus I:=1-től N-1-ig

  Ciklus J:=I+1-től N-ig

    Ha T[I].Ido>T[J].Ido akkor

      C:=T[I]

      T[I]:=T[J]

      T[J]:=C

    Havége

  Cvége

Cvége

 

Ciklus I:=1-től 3-ig

  Ki: T[I].Nev, T[I].Iskola, T[I].Evfolyam

Cvége

 

Szűcs Tamás - szucs_t@freestart.hu