adatszerkezetek - mezogazd

Report
3. LOGIKAI ADATSZERKEZETEK
1. Lineáris
2. Tömb
3. Lista
4. Verem (LIFO)
5. Sor (FIFO)
6. Táblázatok
Forrás: Simon Gyula
Összeállította:
Sashalmi Tibor
Számítástechnika középiskolásoknak
A programok különböző típusú adatokat dolgoznak
fel.
Az adattípus a következőktől függ:
1. Belső ábrázolás, - amely az adott adattípusra jellemző
2. Értékkészlet – az adott adattípusú változó milyen értékeket
vehet fel.
3. Műveletek – Milyen műveleteket lehet végezni az adott típusú
változón?
A probléma megoldás során több adattal is dolgozunk.
Ezek az adatok általában egymástól nem függetlenek,
logikailag összefüggnek.
Ezek az összefüggések az adatszerkezetek.
3.1 Lineáris adatszerkezet
Ez egy általános jellegű adatszerkezet.
A lineáris adatszerkezet az alábbiakkal jellemezhető:
1. Van egy első és egy utolsó eleme
2. Az ezeken kívüli elemeknek létezik megelőzője,
és rákövetkezője.
3. Az első elemnek csak rákövetkezője van, az
utolsónak csak megelőzője.
3.2 Tömb
A tömb azonos típusú adatok sorozata. A
tömbök-nél a logikai szerkezetet az adatelemek
egymás-hoz viszonyított elhelyezkedése adja. Így
nyilván az első elem kitüntetett helyzetű, hiszen a
többi elem helyét az elsőhöz viszonyíthatjuk.
– Egydimenziós tömb (vektor)
– Kétdimenziós tömb
Léteznek még három-, négy-, stb. dimenziós tömbök is,
de ezek ritkábban fordulnak elő.
3.3 Lista
A tömbelemek tárolási módja a memóriában fix
méretű és szekvenciális. A program futása közben
nem változtatható. A törlés és beszúrás műveletet
nehéz elvégezni.
A lista adatszerkezetben az elemek sorrendje
szintén jól meghatározott, de az egyes elemek a
memóriában nem biztos, hogy ugyanilyen
sorrendben helyezkednek el.
–Egyirányú láncolt lista
–Kétirányú láncolt lista
3.4 Verem (LIFO) (1 dia)
A verem egy olyan lineáris adatszerkezet, amelynek mindig
csak az utolsó elemével lehet műveletet végezni.
– Új adat beírása utolsó elemként
– Az utolsó elem kiolvasása, egyúttal az elem törlődik
Szemléletesen az utolsó elem a verem tetejére kerül. Ezt
vesszük ki elöször. És ha kivesszük az utolsó elemet ( az
elsőként berakott) is, akkor kiürül a verem. Ezt a
feldolgozási módot hívják LIFO –nak ( Last-In-First-Out :
utoljára be- először ki.
3.4 Verem (LIFO)
A verem legfontosabb alkalmazási területe az eljáráshívás:
Program
1
2
3
4
5
6
A rútin
„A” eljárás
7
8
9
10 B rútin
11
12
„B” eljárás
13
14
15
16
17
18
Cím 11
Cím 4
3.5 Sor (FIFO)
Olyan lineáris adatszerkezet, amelynek mindig a
legelső elemével lehet műveletet végezni.
1. Új elem beírása utolsó elemnek.
2. A legelső elem kiolvasása, egyúttal ez az elem
tölődik.
Az adatokat sorba kell állítani. Ezt a feldolgozási
módot FIFO - nak nevezik (First – In – First -Out:
elsőként be - először ki).
Tipikus alkalmazási terület a nyomtatási sor.
3.6 Bináris fa
A fagráf egy olyan összefüggő gráf, amelyben nincsen kör. A fa adatszerkezetben az egyes szögpontokat összekötő élek irányítottak lesznek.
Kiválasztunk egy szögpontot,
ez lesz a a fa gyökéreleme.
Ezután a gyökérelemtől
éleket húzunk a szomszédos
szögpotokhoz, ezekből újra a
velük szomszédos
szögpontokhoz, stb.
Azokat a fa adatszerkezeteket
3.7 Táblázatok
A táblázat tulajdonképpen egy függvénykapcsolat összetartozó értékek között. Adatelem a következőképpen néz
ki:
Argomentum
érték
Az argomentum és az érték is állhat több mezőből. A
táblaelemeket általában az argumentumuk alapján szokták
keresni, nevezhetjük ezt tartalom szerinti keresésnek
VÉGE
Logikai adatszerkezetek
3.2.1 Egydimenziós tömb (vektor)
A legegyszerűbb tömb típus. Az egyes elemekre
egy számmal, az index segítségével hivatkozhatunk. Az index az mutatja hogy az elem hányadik
a tömb elemek között.
Például turbó Pascal esetén a deklaráció formája:
Var tomb : array [1…100] of integer
A tömb neve
Az indexek lehetséges értékei
Ennek a tömbnek a 6.eleme: tomb[6]
elemtípus
vissza
3.2.2 Kétdimenziós tömb (1.dia)
Itt az elemek egy táblázatban helyezkednek el. Pl:
A11
A12
A13
A14
A21
A31
A22
A32
A23
A33
A24
A34
A42
A43
A44
A52
A53
A54
A41
A51
A32
második index
első index
A kétdimenziós tömb logikailagoszlopindex
sorokból, és oszlopokból
sorindex
áll. Az első index a sor sorszámát jelenti, a második
szám az oszlop sorszáma.
vissza
3.2.2 Kétdimenziós tömb (2.dia)
Például a Turbo Pascal – ban a deklaráció formája:
var A: array [1..5, 1..4] of char;
Az a A32 – re való hivatkozás: A[3,2].
A memóriában az elemek általában sorfolytonosan helyezkednek el. Az elemek sorrendje az előző példákon szemléltetve:
A11 A12 A13 A14 A21 A22 A23 A24 A31 A32 A33 ... stb.
vissza
3.3.1 Egyirányú láncolt lista (1.dia)
A listaelemei a következő szerkezetűek:
adat
mutató
A mutató a következő elem címét tartalmazza. Az elemek
összeláncolása ezeknek a mutatóknak a segítségével
történik.
listafej
1.elem Cím 2
2.elem Cím 3
3.elem 000
A lista tartalmaz két speciális elemet. - Listafej
- Végelem
vissza
3.3.1 Egyirányú láncolt lista (2.dia)
Két fontos művelet a kővetkezőképpen végezhető el:
– Beszúrás : Egy elem beszúrásához elegendő az előző elem
mutatójának megváltoztatása.
listafej
Cím új
1.elem Cím
2
2.elem Cím 3
3.elem 000
újelem
- Törlés: Egy elem törléséhez is az előző elem mutatóját kell
megváltoztatni.
listafej
1.elem Cím
Cím 32
2.elem Cím 3
3.elem 000
vissza
3.3.2 Kétirányú láncolt lista
listafej
1.elem
Cím lf Cím 2
2.elem
Cím 1 Cím 3
3.elem
Cím 2 Cím 4
4.elem
Cím 3
Ha az egyes lista elemeket
még egy résszel kiegészítjük, akkor kétirányú láncolt listát kapunk. A lista
elemek három részből állnak: - információs rész
- előző elem címe
- következő elem címe
000
vissza

similar documents