KREDIT
VADÁSZ

Adatszerkezetek, algoritmusok

Országok listájaHungaryNyíregyházi FőiskolaTermészettudományi Főiskolai KarProgramozó matematikusZáróvizsgaAdatszerkezetek, algoritmusok

06. Adatszerkezetek
(tömb /sor, verem, láncolt lista, fák és bejárásuk), sorozatok feldolgozása (programozási tételek), keresések, rendezések.
Tömb
A legalapvetQbb, leggyakrabban használt adatszerkezet.Olyan homogén adatszerkezet, melynek elemeit a sokaságon belül elfoglalt helyük azonosítja. Tehát:
elemei azonos típusúak,
az elemeket nem névvel, hanem a tömbön belüli helyükkel, az indexükkel azonosítjuk.
Deklaráláskor meg kell adnunk a tömb:
nevét
elemeinek típusát
indextartományát
dimenzióját.
Egy dimenziós tömb: vektor, sorozat.
Két dimenziós tömb: mátrix, táblázat.
Leírónyelv:
Változó (var) tömbnév: tömb[alsóhatár..felsQhatár] elemtípus
Változó (var) tömbnév: tömb[ah1..fh1, ah2..fh2] elemtípus

A töm elemeinek száma:
elemszám = felsQhatár  alsóhatár + 1
elemszám = (fh1  ah1 + 1) * (fh2  ah2 + 1)

A tömbök feldolgozása gyakran jelenti ugyanazon mqveletek ismétlését az egyes elemekre, ez pedig tipikusan valamilyen ciklus alkalmazásához vezet. Különösen a léptetQ (for) ciklus kötQdik szorosan a tömbökhöz, mert a ciklusváltozó jól használható a tömbelemek egymás utáni megcímzésére.
ciklus cv:=alsóhatár..felsQhatár ismétel
tömbnév[cv] ...
cvége

ciklus cv1:=alsóhatár1..felsQhatár1 ismétel
ciklus cv2:=alsóhatár2..felsQhatár2 ismétel
tömbnév[cv1,cv2] ...
cvége
cvége
Tömbök tárolása: sorfolytonosan (más néven lexikografikusan). Ez lehetQvé teszi, hogy bármely elem helyét az indexek ismeretében kiszámíthassuk, s így közvetlenül elérhessük Qket. A tömb méretétQl függetlenül bármelyik elemét ugyanannyi idQ alatt érhetjük el.
Sor
A sor (angolul: queue) homogén adatelemek olyan sorozata, amelyen két mqvelet értelmezett:
új elem elhelyezése a sor végére (put)
elem kivétele a sor elejérQl (get).
Mqködése FIFO (First In First Out) elvq. Mindazon feladatuk megoldására alkalmas, ahol sorban állást kell megvalósítanunk.

Objektum orientált módszertannal készítsünk egy sor osztályt, melynek adattagjai:
az elemek tárolására szolgáló tömb,
indexek, melyek a sor elsQ ill. utolsó elemére mutatnak,
a sor (tömb) mérete.
Metódusai:
konstruktor,
sorba (put), sorból (get): mqveletek,
tele, ures: állapot lekérdezések.
Ciklikus sort készítünk, tehát ha az utolsó mutató eléri a tömb végét, akkor ugrik a tömb elejére, feltéve, hogy még nincs tele a sor. Ha a sor kiürül, mindig alaphelyzetbe állítjuk, amikor az utolsó=-1, elsQ=0.
Verem
A verem (angolul: stack) homogén adatelemek olyan sorozata, amelyen két mqvelet értelmezett:
új elem elhelyezése a verem tetejére (push)
elem kivétele a verem tetejérQl (pop).
Mqködése LIFO (Last In First Out) elvq.

Objektum orientált módszertannal készítsünk egy verem osztályt, melynek adattagjai:
az elemek tárolására szolgáló tömb,
indexek, melyek a verem aljára ill. tetejére mutatnak,
a verem (tömb) mérete.
Metódusai:
konstruktor,
verembe (push), verembQl (pop): mqveletek,
tele, ures: állapot lekérdezések.
Láncolt lista
A láncolt lista egyike a számítógépprogramozásban használatos legegyszerqbb adatszerkezeteknek. Olyan csomópontok, cellák sorozatából épül fel, amelyek tetsztQleges számú és fajtájú  HYPERLINK "http://hu.wikipedia.org/w/index.php?title=Adatmez%C5%91&action;=edit&redlink;=1" \o "AdatmezQ (megíratlan szócikk)" adatmezQt, és egy vagy két  HYPERLINK "http://hu.wikipedia.org/w/index.php?title=Hivatkoz%C3%A1s&action;=edit&redlink;=1" \o "Hivatkozás (megíratlan szócikk)" hivatkozást tárolnak. A hivatkozás(ok) a lista következQ (és elQzQ) elemére mutat(nak). A láncolt szerkezet lehetQvé teszi listaelemek törlését és beszúrását a lista tetszQleges pontjára konstans (azaz a konkrét helytQl független) idQben, ugyanakkor egy véletlenszerqen kiválasztott elem elQkeresése a lista hosszával arányos idQt igényel.

Egy listaelem szerkezete:

típus ListaElem: rekord(
Érték: ÉrtékTípus;
Köv: MutatóTípus //mely a ListaElem-re képes mutatni
)
Egyszeresen láncolt lista
A láncolt lista legegyszerqbb formája az egyszeresen láncolt lista, amelyben cellánként egy hivatkozás található. Ez a hivatkozás a lista következQ elemére mutat, speciálisan az utolsó elem esetén  HYPERLINK "http://hu.wikipedia.org/w/index.php?title=Null%C3%A9rt%C3%A9k&action;=edit&redlink;=1" \o "Nullérték (megíratlan szócikk)" nullértékq vagy egy kitüntetett üres listára hivatkozik.
 HYPERLINK "http://hu.wikipedia.org/wiki/F%C3%A1jl:Singly_linked_list.png" \o "Egy három egész elembQl álló egyszeresen láncolt lista"  INCLUDEPICTURE "http://upload.wikimedia.org/wikipedia/commons/3/37/Singly_linked_list.png" \* MERGEFORMATINET 
Egy három egész elembQl álló egyszeresen láncolt lista

Ha egy egyszeresen láncolt listára akarunk hivatkozni (például paraméterátadáskor), elegendQ megadnunk az elsQ elemének címét.
Kétszeresen láncolt lista
Valamivel elmésebb adatszerkezet a kétszeresen láncolt lista. Itt minden cellában két hivatkozást tárolunk, az egyik a lista elQzQ, a másik a következQ cellájára mutat.
 HYPERLINK "http://hu.wikipedia.org/wiki/F%C3%A1jl:K%C3%A9tszeresen_l%C3%A1ncolt_lista.png" \o "Kép:Kétszeresen láncolt lista.png"  INCLUDEPICTURE "http://upload.wikimedia.org/wikipedia/hu/5/51/K%C3%A9tszeresen_l%C3%A1ncolt_lista.png" \* MERGEFORMATINET 
Egy kétszeresen láncolt lista egyik vége
Körkörös lista
Egy körkörös listában az elsQ és az utolsó elem össze van kötve egymással. Ez a megoldás mqködik mind egyszeresen, mint kétszeresen láncolt szerkezeteknél. Egy körkörös lista bejárását természetesen tetszQleges eleménél elkezdhetjük, a körbeérés felismeréséhez csupán azt kell megjegyeznünk, hogy ezt pontosan melyik elemnél tesszük.
Prcellák (Strázsás (ütközQs) lista)
Láncolt listák esetén gyakori trükk a valódi adatot nem tároló, ún Qrcellák használata a lista elejének vagy végének jelzéséhez. Ennek célja bizonyos mqveletek megkönnyítése vagy felgyorsítása, ekkor ugyanis a programozó élhet azzal a feltételezéssel, hogy a lista minden (valós) elemének van rákövetkezQ (vagy megelQzQ) eleme, valamint hogy minden listának van legalább egy (hamis) legelsQ és egy legutolsó eleme.
Fa
A fa az adatok hierarchikus kapcsolatának ábrázolására alkalmas adatszerkezet (pl. háttértárolók könyvtárszerkezete).
Rendelkezik egy kitüntetett kezdQponttal, és e kezdQpontból kiindulva minden adatelemhez tetszQleges számú új elem kapcsolódhat. A kapcsolódó elemek a fa más részeihez nem kapcsolódhatnak.
Elnevezések:
gyökér: a kezdQelem;
csomópontok: adatelemek;
élek: egymással közvetlen kapcsolatban lévQ csomópontokat kötik össze, irányuk mindig a gyökértQl a távolabbi csomópont felé mutat;
levél: azon csomópontok, amelyekbQl nem vezet tovább él;
út: egy csomópontból egy másikba vezetQ élsorozat;
szülQ: ha A csomópontból él mutat B csomópontba, akkor A szülQje B-nek;
gyerek: ha A csomópontból él mutat B csomópontba, akkor B gyereke A-nak;
testvér: egy szülQhöz tartozó csomópontok.
A fa definíciójából következik, hogy a gyökérbQl bármely csomópont pontosan egy úton érhetQ el.
Bináris fa
Bináris fa: minden csomópontnak legfeljebb két gyereke van.
Szigorúan bináris fa: a levélelemek kivételével minden csomópontnak pontosan két gyereke van.

A bináris fa megvalósítása:
Tárbeli megvalósítása a láncolt listában alkalmazott adatszerkezet bQvítésével: minden elemnek két rákövetkezQje lehet, ezért két mutatót alkalmazunk a csomópontokban, az egyik a baloldali, a másik a jobboldali részfa gyökerére mutat. Ha valamely mutató értéke a VégJel (null), akkor ebben az irányban nincs folytatása a fának. A levélelemek mindkét mutatója VégJel.
Tehát egy csomópont szerkezete:

típus BinFaElem: rekord(
Érték: ÉrtékTípus;
Bal, Jobb: MutatóTípus //mely a BinFaElem-re képes mutatni
)

Minden fához tartozik egy változó: Gyökér, mely a fa kezdQpontjára, a gyökérelemre mutat. Ez a mutató fogja azonosítani a fát.
Bináris fa bejárása
Bejárásnak nevezzük azt a folyamatot, amikor a fa minden elemét pontosan egyszer érintve feldolgozzuk. Erre a gyakorlatban három, a rekurzív definíciókra támaszkodó módszer terjedt el:
preorder bejárás:
gyökérelem feldolgozása;
baloldali részfa preorder bejárása;
jobboldali részfa preorder bejárása;
inorder bejárás:
baloldali részfa inorder bejárása;
gyökérelem feldolgozása;
jobboldali részfa inorder bejárása;
postorder bejárás:
baloldali részfa postorder bejárása;
jobboldali részfa postorder bejárása;
gyökérelem feldolgozása;

Példa: Algebrai kifejezések (pl. a*b+c) ábrázolása, bejárása.

 SHAPE \* MERGEFORMAT 
Az ilyen típusú felírásban a fa levelei az operandusokat, a többi csomópont pedig az operátorokat tartalmazza. A háromféle bejárás szerint feldolgozva az elemeket, az algebrai kifejezések ismert formáit kapjuk:
preorder bejárással a prefix alakot: +*abc;
inorder bejárással az infix alakot: a*b+c;
postorder bejárással a postfix alakot: ab*c+;

KeresQfa
Gyors keresési módszerekben illetve az adattömörítésben alkalmazzák.
A keresQfa egy olyan bináris fa, amelynek minden csomópontjára igaz, hogy a benne tárolt érték:
nagyobb, mint a baloldali részfájában tárolt bármely érték;
kisebb, mint a jobboldali részfájában tárolt bármely érték.
Ha az adatok ismétlQdését is megengedjük, akkor a feltételek enyhíthetQk kisebb vagy egyenlQre illetve nagyobb vagy egyenlQre.
Az ábrán megfigyelhetQ, hogy inorder bejárás szerint az eredmény egy rendezett számsorozat lesz.

Keresés a keresQfában
A keresés során a keresQfa definícióját (rendezettség) használjuk ki.
Általános fák megvalósítása
Egy elemnek tetszQleges számú gyereke (vagyis tetszQleges számú testvére lehet).

Alkalmazhatunk láncolt listát: fqzzük listába a testvér csomópontokat, így a szülQtQl csak egyetlen mutatónak kell megcímeznie ezt a listát. Természetesen a szülQ maga is része egy hasonló listának, ami a testvéreivel kapcsolja össze.
Minden csomópontban két mutatóra lesz szükség: az egyik mutat a legelsQ gyerekre, a másik a következQ testvérre. Így az általános fák kezelését visszavezettük a bináris fákéra.
Az elsQ ábrán látható könyvtárszerkezete ily módon ábrázoljuk a memóriában:



Programozási tételek
A következQ sorozat feldolgozó algoritmusokat programozási tételeknek is nevezik. A sorozatokat a példáinkban tömbök tárolják, bár az algoritmusok általánosak.
Másolás
Egy bemenQ sorozatból egy kimenQ sorozatot készítünk, mégpedig úgy, hogy az eredménysorozat ugyanolyan elemszámú, mint a bemeneti sorozat, és az eredménysorozat I. tagját a bemenQ sorozat I. tagjából lehet meghatározni. A bemenQ sorozatot tehát átmásoljuk úgy, hogy közben az elemeken esetleges átalakításokat végzünk.
Az általános algoritmus:
Kiválogatás
Egy bemenQ sorozatból egy kimenQ sorozatot készítünk, úgy, hogy a bemenQ sorozat elemei közt válogatunk. Az eredménysorozat rövidebb vagy ugyanakkora lesz, mint a bemenQ sorozat. Ide tartozó feladat például:
Töröljünk ki egy karakterláncból minden szóközt!
Válogassuk ki a fizetések közül azokat, amelyek kisebbek, mint 150000!
Szétválogatás
Egy bemenQ sorozatból több kimenQ sorozatot készítünk. Azok a feladatok tartoznak ide, amelyeknél a bejövQ adatok mindegyikére szükségünk van ugyan, de azokat valamilyen szempontból el kell különíteni, szét kell válogatni. A kimenQ sorozatok elemszámainak összege megegyezik a bemenQ sorozat elemszámával. A szétválogatást fel lehet fogni több egymás utáni kiválogatásként is, ahol egyszer minden elemre sor kerül. Mindegyik eredménysorozatban ugyanannyi elemszámra kell felkészülni, mint a bemenQ sorozat elemszáma, hiszen szélsQséges esetben elképzelhetQ, hogy minden elem egyetlen kimenQ sorozatba kerül át. Ide tartozó feladat például:
A bejövQ személyi számokat bontsuk ketté: férfiak, nQk!
Dolgozók bejövQ adatrekordjait válogassuk szét foglalkozás szerint!
Közös rész meghatározása
Az ilyen típusú feladatoknál két vagy több sorozatból készítünk egy sorozatot úgy, hogy az eredménysorozatban csak olyan elemek szerepelnek, melyek mindegyik sorozatban benne vannak. A sorozatok nem rendezettek, de feltételezzük, hogy egy elem csak egyszer szerepel a sorozatban. A sorozatok tulajdonképpen halmazok, ahol a bejövQ sorozatok közös részét (metszetét) képezzük. Az eredménysorozat elemszáma kisebb vagy egyenlQ, mint a legrövidebb bemenQ sorozat elemszáma. Ilyen feladat például:
Szilveszteri bulit szervezünk. Mindenki felsorolja, milyen márkájú söröket szeret. Milyen söröket vegyünk, ha mindenkinek kedvezni akarunk?
Az egyes tanórákon írt katalógusokból megállapítjuk, hogy mely hallgató voltak jelen minden alkalommal.
Megoldás: végigmegyünk az elsQ sorozaton, és minden elemhez végignézzük a második sorozatot, van-e benne ugyanolyan elem. Ha több bemenQ sorozat van, akkor a többit is végignézzük. Csak akkor vesszük fel az elemet a kimenQ sorozatba, ha az elemet mindegyik sorozatban megtaláltuk.
Példa: Egy csoportban valaki összeírja a szép embereket, aztán az okosakat. E két névsor alapján határozzuk meg a csoport szép és okos embereit! (A névsorok nem rendezettek.)
Egyesítés
Ebben a feladatcsoportban is több bemenQ sorozatból készítünk egy kimenQ sorozatot. Itt azonban azokat az elemeket tesszük be az eredménysorozatba, melyek legalább az egyik bemenQ sorozatban benne vannak. A sorozatok itt is felfoghatók halmazként, a bemenQ sorozatok unióját képezzük. Az eredménysorozat elemeinek száma legfeljebb a bemenQ sorozatok elemszámainak az összege. Ilyen feladat például:
Csapatunk egy hetes túrára indul. Minden tag felsorolja, hogy milyen ételeket tud elkészíteni. Állapítsuk meg, hogy a csapatunk mire képes
Az egyes tanórákon írt katalógusokból megállapítjuk, hogy mely hallgató voltak jelen valamelyik alkalommal.
Megoldás: Az elsQ sorozatot átmásoljuk az eredménysorozatba. Ezután végignézzük a második sorozatot, és minden egyes elemre megállapítjuk, hogy már bent van-e az eredménysorozatban. Ha nincs, akkor betesszük. Ezt elvégezzük az összes bemenQ sorozatra.
Példa:
Apa és anya felsorolják, hogy a következQ hónapban mely estéjük szabad. Gyqjtsük össze azokat a napokat, amikor legalább az egyikük ráér, és így nem kell babysitter-t fogadni.
Összeválogatás
( & ( @
J
K
L
Y
Z
a
h
q


ç먌p]J:J51,1,1 hÈyš6hÈyš hÈyš5h¾~ZOJPJQJaJnH tH $h¾~ZhÈyšOJPJQJaJnH tH $hè*¨hÈyšOJPJQJaJnH tH 7hè*¨hÈyš6B*CJOJQJ]^JaJnH phO½tH 7h˜'“hÈyš6B*CJOJQJ]^JaJnH phO½tH $hè*¨h‡,•OJPJQJaJnH tH $hè*¨h˜'“OJPJQJaJnH tH 0h˜'“h‡,•B*KHOJQJ\aJnH ph6_‘tH 0h˜'“h˜'“B*KHOJQJ\aJnH ph6_‘tH ( ( -
E
™
¿
Å
×
è
õ

@
L
,



ñç×뮣£ç΋‹gdÈyš
&
F„Ê„›þd ^„Ê`„›þgd¾~Z
d ¤Ègd¾~Zm$

&
Fd ¤Ègdè*¨
&
F„Ê„›þd ^„Ê`„›þgdè*¨ d gd¾~Zm$$$d ¤È ¤a$gd˜'“ d ¤Ègdè*¨ $$d ¤a$gd˜'“





*

,

F

H

V

d

j

n

~

‚

ˆ

Œ

ž

¢

Ò

x
z
¸ÄÎàäøú .8FN’‚úöúöñöúöúöúöúöúöÞÊöÞñöúöúöñöúöñöñöúöúöñöúöúöñöúöñöñöÞ®›—›h6/â$h¾~Zh6/âOJPJQJaJnH tH 7h˜'“h6/â6B*CJOJQJ]^JaJnH phO½tH 'h¾~ZhÈyš6OJPJQJaJnH tH $h¾~ZhÈyšOJPJQJaJnH tH hÈyš5hÈyš hÈyš69

¢

Ò


x
z
¸
.:<”ð"2>FN R š úñññúæáááúáááááÖƽ®®
&
Fd ¤xgd¾~Zm$ d gdP”m$$$d ¤È ¤a$gd˜'“
d ¤xgd¾~Zm$gdÈyš
d ¤xgd¾~Zm$ d gd¾~Zm$gdÈyš š ’6~ð0J–Ú‚ŽH î@BêôïôàààôÑÑÑôÁ¸««¸¥¸gd¾~Zm$


&
Fd gd¾~Zm$ d gd¾~Zm$$$d ¤È ¤a$gd˜'“
&
Fd ¤xgd¾~Zm$
&
Fd ¤xgd¾~Zm$gd6/â
d ¤xgd¾~Zm$‚Ž@B˜´ -"- 2 4 X Z ^!`!v!x!$@$B$L$Ì$ð$ò$%%ãÐÌа††††††soho]U]oh6/âB*ph3™fhëüh6/âB*ph3™f

h6/â5\h6/â$h¾~Zh6/âOJPJQJaJnH tH -jhM®hM®OJPJQJUaJnH tH $hM®hM®OJPJQJaJnH tH 7h˜'“h6/â6B*CJOJQJ]^JaJnH phO½tH h˜'“$h¾~Zh˜'“OJPJQJaJnH tH 7h˜'“h˜'“6B*CJOJQJ]^JaJnH phO½tH ê2 ÎäþT˜´
$

$@$B$t$¢$ %%R%òòòéÔÇÇ·²²²²­­­­$$d ¤È ¤a$gdM®gd6/âgd6/â$$d ¤È ¤a$gd˜'“


&
Fd gd¾~Zm$
&
F„Ê„›þd ^„Ê`„›þgd¾~Zm$ d gd¾~Zm$


&
Fd gd¾~Zm$%R%Ü&Þ&è'ê'þ'(^(`(n)p)r)P*V*X*Z*Æ*È*È+ü+N-P-V.X.Z.P/R/T/V/X/Z/ª/¬/Ê/f2v2ãйййб­± ˜ ±­ÐˆÐãб­± ˜ { ±­r­ãÐãhM®6CJ ]j" hM®B*UphÿhM®OJPJQJaJnH tH hM®B*phÿjhM®B*UphÿhM®jhM®U-jhM®hM®OJPJQJUaJnH tH $hM®hM®OJPJQJaJnH tH 7hM®hM®6B*CJOJQJ]^JaJnH phO½tH $R%^(Z*È*Ê*È+ü+N-¬/Ê/f2®2ì5ò5Þ6X8r8œ8Î8Ö9H:®:>;øóóóóãøÛãóãóËÆÆƾ¾¾¾¾¾
&
F-gdM®gd6/â$$d ¤È ¤a$gd˜'“ $a$gdM®$$d ¤È ¤a$gdM®gdM® ¤xgdM®v2z2ª2¬2®2ì5ò5r8~8œ8²8Î8Ö8Ö9à9H:L:®:¸:>;J;Ð;Þ;&<è<þ<2>4>h>æÊæÊ·›ˆtˆtˆtˆtˆtˆtˆtˆtˆa›a]I'hóo€h6/â>*OJPJQJaJnH tH h6/â$hóo€h6/âOJPJQJaJnH tH 'hóo€h6/â6OJPJQJaJnH tH $hM®h6/âOJPJQJaJnH tH 7h˜'“h6/â6B*CJOJQJ]^JaJnH phO½tH $hM®hM®OJPJQJaJnH tH 7hM®hM®6B*CJOJQJ]^JaJnH phO½tH 1hM®6B*CJOJQJ]^JaJnH phO½tH >;Ð;&<è<þ4>l>¦@Æ@Ç@à@÷@6A;A &
F gd¶²
&
F gd6/âgd6/â$$d ¤È ¤a$gd˜'“gd6/â
&
F-gdM®h>j>l>Æ@Ç@Ì@AA-A$A%A5A
hÒEh6/â$h¶²h6/âOJPJQJaJnH tH 7h˜'“h6/â6B*CJOJQJ]^JaJnH phO½tH hÀV…h6/â0Jh6/âB*ph3™fhëüh6/âB*ph3™f

h6/â5\h6/â$hóo€h6/âOJPJQJaJnH tH 'hóo€h6/â>*OJPJQJaJnH tH !hóo€>*OJPJQJaJnH tH &˜D©DÌDåD EEAEgE€EE¿EÀEÝE°FÜF G5G6GHžH^IÖINJ÷ïïï÷ïïïêêêêêâââêÒêêÊÊ
&
F!gd¶²$$d ¤È ¤a$gd˜'“
&
F
gd6/âgd6/â
&
F gd¶²
&
F gd6/âÀEÁEØEÙEÚEÛEÜEÝE¯F°F5GHHþHI

L LLL>LÈLÌLMxQzQ|Q~Q‚Q¬QìR÷ó÷åÝ÷óÊóÊó®ÊóÊó¦óÊó®Êóˆ€ófS$h¶²hè*¨OJPJQJaJnH tH 3h¶²h¶²5B*CJOJQJ\aJnH phO½tH jéh6/âUjMFh6/âU*h¶²h6/â5>*OJPJQJaJnH tH j9.h6/âU7h˜'“h6/â6B*CJOJQJ]^JaJnH phO½tH $h¶²h6/âOJPJQJaJnH tH j©-h6/âUjh6/âUmHnHuh6/âjh6/âUNJLK LL>LÌLM¦M¨M~OàPxQzQ€Q‚Q¬QìRüRzU¬UÄUdWÆWúúòííÝííííííííØØÈØØÈØÀ
&
F"gdøuâ$$d ¤È ¤a$gdè*¨gdè*¨$$d ¤È ¤a$gd˜'“gd6/â $a$gd6/âgd¶²ìRüR¬UÄUTXpXh^š^fšfžfîghooovp”p”À™š šXšfšþš›

›¾›À›à›nœŒœ:žDžHžŽžž˜žœžÂžÆžÈžÊžÌžÐžãÐã½ã½ã½¸´½ã¡¸´¡ãŸ¡´¸´¸´¸´¡´‹¡‹¡¸´x´r´x´r´x´
hè*¨0J$hÄ|hè*¨OJPJQJaJnH tH 'h8ƒhè*¨5OJPJQJaJnH tH U$h8ƒhè*¨OJPJQJaJnH tH hè*¨ hè*¨5$høuâhè*¨OJPJQJaJnH tH $h¶²hè*¨OJPJQJaJnH tH 7hè*¨hè*¨6B*CJOJQJ]^JaJnH phO½tH ,ÆWTXpXp]à]h^š^vbŽc^dfîgh k6l moovp”pv™À™Â™÷çâÚÚçâÒÒââçâÊÂâââçâââ
&
F gdè*¨
&
Fgdè*¨
&
F$gdøuâ
&
F#gdøuâgdè*¨$$d ¤È ¤a$gdè*¨
&
F"gdøuâEnnél a feladattípusnál több bemenQ sorozatból egy kimenQ sorozatot készítünk. A bemenQ sorozatok itt rendezettek, melyeket egyszerre dolgozzuk meg úgy, hogy közben a benne lévQ elemeket összeválogatjuk. ElQször hozzáférhetQvé tesszük az összes sorozatból az elsQ elemet. Amelyik a legkisebb azt feldolgozzuk (pl. áttesszük az új sorozatba). A feldolgozott elem helyére mindig teszünk egy újat ugyanabból a sorozatból. A rendezettség miatt a csoportok egyenlQ elemei egyszerre lesznek elérhetQek. Egyes feladatoknál ezt figyelhetjük, és az egyforma elemeket tesszük át az új sorozatba. Minden sorozatot egyszerre olvasunk végig párhuzamosan, és a feldolgozás végére készen lesz az eredménysorozat.
Az összeválogatás durva algoritmusa:

Ráállás a bemenQ sorozatok elsQ elemeire
amíg van elem minden sorozatban ismétel
Elemek összehasonlítása
Amelyik elem kell, azt feldolgozzuk, pótoljuk
avége

Az összeválogatásnak azt az esetét, amikor minden elemet beteszünk egy eredménysorozatba, összefuttatásnak is szokás nevezni. Ha a bemenQ sorozatoknak nincs közös elemük, akkor összefésülésrQl beszélünk.
A legnagyobb problémát az egyes sorozatok végeinek feldolgozása jelenti:
Hogyan állapítjuk meg azt, hogy van-e még valamelyik sorozatban elem?
Hogyan pótoljuk azt a sorozatot, amelyikben már nincs elem?
Példa: Állítsuk elQ két rendezett sorozat (A, B) rendezett unióját (C)!

1. algoritmus: A két sorozatot párhuzamosan dolgozzuk fel, amíg van elem mindkét sorozatban.

2. algoritmus: A bemenQ sorozatok végére fizikailag egy-egy ütközQt helyezünk. Az ütközQ egy olyan elem, amely értéke bármely, a feldolgozásban résztvevQ elemnél nagyobb. A feldolgozás végét kétféleképpen figyelhetjük: van-e még elem valamelyik sorozatban, ütközQn állunk-e mindegyik sorozatban. Amelyik adatsorban az ütközQn állunk, az természetesen már nem ad elemet a kimenQ sorozatba.

Ha több sorozatunk van, célszerqbb az ütközQt, mint végjelet figyelnünk.

3. algoritmus: A bemenQ sorozatok végére logikai ütközQket helyezünk. Ez azt jelenti, hogy minden pótláskor figyeljük, hogy elfogyott-e a sorozat, és ha igen, akkor az utolsó elem értékét végtelenre állítjuk. A feldolgozásnak akkor van vége, ha mindegyik elem értéke végtelen.
Sorozatok feldolgozása
Adatok feldolgozása végjelig
Nem ismerjük az iterációk számát, ciklus végrehajtása attól függ, hogy van-e még feldolgozandó adat. Az adatfolyam végét egy végjel jelzi. A megoldás általános algoritmusa:

be: Adat
amíg Adat<>Végjel ismétel
Az adat feldolgozása
be: Adat
avége

Mivel a végjelet nem kell feldolgoznunk, ezért célszerq az adat beolvasását a ciklusmag végén elvégeznünk, így a vezérlQ feltétel következQ kiértékelésekor befejezQdik a ciklus. Ez elsQ adatot a ciklus elQtt olvassuk be, ezt elQolvasásnak nevezzük. Mivel kezdQfeltételes ciklussal oldottuk meg a problémát, az algoritmus akkor is jól mqködik, ha nincs adat, azaz már elsQre a végjelet olvassa be a program.
Példa: Olvassuk be körök sugarait nulla végjelig (addig, amíg nullát nem ütünk), majd írjuk ki a kerületét és a területét!
Megszámlálás
Egy sorozat, adatfolyam valamilyen adott tulajdonságú elemeinek a számát akarjuk meghatározni. Felveszünk egy számláló változót, melynek az értékét növeljük, ha az elem kívánt tulajdonságú. A számlálót természetesen le kell nulláznunk. Ha elQre ismerjük az elemek számát, akkor for ciklust használhatunk, ha nem akkor az elQzQ pontban megismert végjelig történQ feldolgozást alkalmazzuk.
Példa:
Olvassunk be 10 számot, és írjuk ki, hogy mennyi hárommal osztható volt közöttük!
Olvassunk be számokat nulla végjelig, és írjuk ki, hogy mennyi hárommal osztható volt közöttük!
Összegzés
Egy sorozat elemeit valamilyen módon gyqjteni kell, összegezni, esetleg a szorzatukat képezni.
Ismert elemszám esetén az algoritmus:
Összeg:=0
ciklus I:=1..N ismétel
Hozzáférés az I. elemhez
Összeg:=Összeg+I. elem
cvége

Ismeretlen elemszám esetén az algoritmus:
Összeg:=0
Hozzáférés az elsQ elemhez
amíg Elem <> Végjel ismétel
Összeg:=Összeg+ Elem
Hozzáférés a következQ elemhez
avége

Példa: 0 végjelig olvassunk be számokat, és számoljuk ki a párosak összegét! Itt egy picit bonyolítottuk az algoritmus, hiszen nem minden adatot kell összegeznünk.
Átlagszámítás
Az átlagszámítás során egy megszámlálást és egy összegzést kell párhuzamosan végeznünk.
Példa: 0 végjelig olvassunk be számokat, és számoljuk ki az átlagukat!
Minimum és maximum kiválasztás
Egy sorozat legkisebb, illetve legnagyobb elemét kell kiválasztanunk. Az algoritmus lényege, hogy használunk egy Min, illetve Max változót, amely a már beolvasott elemek minimumát, illetve maximumát tartalmazza. Ha az éppen vizsgált adat kisebb, mint a minimum, akkor ez lesz a minimum új értéke. Hasonlóan járunk el a maximumnál. A Min és Max kezdQértékének az elsQ adatot választjuk.
Példa: 0 végjelig olvassunk be számokat, és írjuk ki a legkisebbet és a legnagyobbat!
Keresések
A probléma általános megfogalmazása: adott egy N elemq sorozat, keressük meg azt az elemet (határozzuk meg a helyét a sorozatban), mely megfelel egy megadott tulajdonságnak. Ha több ilyen van, akkor a keresQalgoritmusok általában az elsQ ilyen elemet találják meg. A konkrét megvalósításoknál mi egy adott értéket keresünk.
Lineáris keresés
Más néven: szekvenciális keresés. ElölrQl kezdve sorra vizsgáljuk a sorozatelemeit. A keresés sikertelenségét jelzi, hogy a sorozat végére érve nem találtuk meg a keresett adatot.

a, Rendezetlen sorozatban
N elemq sorozat esetén minimum 1, maximum N, átlagosan (N+1)/2 ciklusvégrehajtás után találja meg a keresett elemet; vagy N összehasonlítás után derül ki, hogy nincs meg a keresett elem.

b, Rendezett sorozatban
Az elQzQhöz képest növeli a hatékonyságot, hogy akkor is leáll a keresés, ha nagyobb elemre lépünk, mint a keresett érték. Viszont hátrány, hogy elQfeltétel a rendezettség.

c, RendezhetQ a sorozat keresési gyakoriság szerint is (konyhapolc elv). Ekkor az a, algoritmus átlagosan kevesebb, mint (N+1)/2 ciklusvégrehajtás után találja meg a keresett elemet.
Gyakoriság szerint rendezhetünk:
Létrehozunk egy párhuzamos számlálótömböt, és idQnként ez alapján csökkenQ sorrendbe rendezzük az adattömböt.
ÖnszervezQdQ struktúra: valahányszor sikeresen megtaláltunk egy elemet, az eredetileg elQtte lévQket eggyel hátrébb léptetjük, majd azt a sorozat legelejére helyezzük.

d, ÜtközQs (strázsás) keresés
A keresQ ciklus összetett feltételét egyszerqsítjük le. A sorozat végére felvesszük a keresett adatot, így felesleges vizsgálni, hogy túlhaladtunk-e a sorozaton (I<=N), hiszen mindenképpen megtaláljuk a keresett elemet. FQképp nagy elemszámú sorozatoknál hatékonyabb az egyszerq lineáris keresésnél, mivel a ciklusfeltétel kiértékelése lényegesen rövidebb lesz.
Bináris keresés
Más néven: felezéses keresés. Csak rendezett sorozaton valósítható meg. Meghatározzuk a középsQ elemet, majd megvizsgáljuk ez-e a keresett. Ha nem, akkor ha a keresett kisebb a középsQnél, akkor a sorozat alsó, egyébként a felsQ részébe folytatjuk a keresést.
A keresés két esetben fejezQdhet be:
megtaláltuk a keresett adatot;
a részsorozat alsó indexe (E) nagyobb a felsQ (U), nincs benne a sorozatban a keresett adat.

Szokásos logaritmikus keresésnek is nevezni, mivel 2k elemq sorozatot k lépésben vizsgálhatunk végig. Tehát egy n elemq sorozatnál minimum n, maximum log2(n)+1, átlagosan log2n hasonlítás után találja meg az elemet, vagy derül ki, hogy nincs ilyen.
Ez egymillió elem esetén kb. 20 lépést jelent, tehát igen látványos a különbség a lineáris módszerhez képest.
Probléma lehet a rendezettség fenntartása mellett az, hogy nem minden adatszerkezetnél címezhetQ meg a középsQ elem (pl. láncolt lista).
Rendezések
A rendezési feladatok általános problémája: adott egy n elemq sorozat, készítsük el ezeknek az elemeknek egy olyan permutációját, amelyre igaz, hogy a sorozat i. eleme kisebb (egyenlQ) az i+1-ediktQl. Ez a növekvQ rendezés. Az ilyen algoritmusok értelemszerqen átalakíthatók csökkenQ sorrendqvé.

A különbözQ rendezések leginkább a következQ két mqvelet alkalmazásában térnek el egymástól:
összehasonlítás  két sorozatelem viszonyának meghatározása,
mozgatás  az elemek sorrendjének változtatása a rendezettségnek megfelelQen.
A hatékonyság vizsgálatakor is ez a két mqvelet, valamint az igényelt tárterület érdekes számunkra.
Minimumkiválasztásos rendezés
ElQször megkeressük az egész tömb legkisebb elemét, és ezt kicseréljük az elsQ elemmel.
Most már csak a maradék: 2..N részt kell rendeznünk. Megkeressük itt is a legkisebb elemet, majd ezt kicseréljük a másodikkal.
Folytassuk ezt a procedúrát. Utolsó lépésként az utolsó elQtti helyre kell kiválasztanunk a legkisebb elemet, hiszen ezzel az utolsó is a helyére kerül.

Hatékonyság:
Helyfoglalás: n+1 (n elemq tömb és a cserékhez szükséges segédváltozó)
Összehasonlítások száma: n*(n-1)/2
Értékadások száma: 0..3*(n-1)

A ha Min<>I akkor elágazást kihagyhatjuk az algoritmusból. Ezt akkor célszerq megtenni, ha az elemek kevesebb, mint a negyede van eleve a helyén.

A minimumkiválasztásos rendezés már egy javításának tekinthetQ az egyszerq cserés rendezésnek, mely az egyik legkevésbé hatékony rendezés, túl sok felesleges cserét tartalmaz:
Buborékrendezés
Az elQzQhöz képest a különbség az összehasonlításokban van. Ennél mindig két szomszédos elemet hasonlítunk össze, és ha nem megfelelQ a sorrendjük, megcseréljük Qket.

Hatékonyság:
Helyfoglalás: n+1 (n elemq tömb és a cserékhez szükséges segédváltozó)
Összehasonlítások száma: n*(n-1)/2
Értékadások száma: 0..3*n*(n-1)/2
Szerencsétlen esetben tehát ez a módszer rosszabb a minimumkiválasztásosnál.
Javított buborékrendezés I.
Ötlet: ha egy teljes belsQ ciklus lefutása alatt egyetlen csere sem volt, akkor az ez utáni menetekben sem lehet, tehát a sorozat már rendezetté vált. Ezzel kiküszöböltük a már feleslegessé vált összehasonlításokat.

Hatékonyság:
Helyfoglalás: n+1 (n elemq tömb és a cserékhez szükséges segédváltozó)
Összehasonlítások száma: n-1..n*(n-1)/2
Értékadások száma: 0..3*n*(n-1)/2
Javított buborékrendezés II.
Ötlet: ha a belsQ ciklusban volt csere, de a legutolsó valahol a sorozat belsejében volt, akkor azon túl már rendezett a sorozat. Jegyezzük meg az utolsó csere helyét, és legközelebb csak addig rendezzünk. Ez a megoldás tartalmazza az elQzQ javítást is, ha nem volt csere, akkor befejezQdik.

A konkrét számokat tekintve a hatékonysági mutatók ugyanazok, mint az elQzQnél, azonban az elQzQ javításhoz képest az átlagos végrehajtási idQ tovább csökkenhet.
Beszúró rendezés
Más néven beillesztQ vagy kártyás rendezés. A mqködést leginkább a kártyalapok egyenként való kézbe vételéhez és a helyükre igazításához hasonlíthatjuk. Vesszük a soron következQ elemet, és megkeressük a helyét a tQle balra lévQ, már rendezett részben. A kereséssel párhuzamosan a nagyobb elemeket rendre eggyel jobbra mozgatjuk. Az aktuális elemet egy segédváltozóban tároljuk, mert a mozgatások során értéke felülíródhat egy nagyobb elemmel.

Hatékonyság:
Helyfoglalás: n+1 (n elemq tömb és a cserékhez szükséges segédváltozó)
Összehasonlítások száma: n-1..n*(n-1)/2
Értékadások száma: 2*(n-1).. 2*(n-1)+n*(n-1)/2
Shell rendezés
Nem önálló módszer, hanem több, már megismert módszerhez illeszthetQ. Elve: sokat javíthat a rendezésen, ha elQször az egymástól nagy távolságra lévQ elemeket hasonlítjuk, cseréljük, mert így az egyes elemek gyorsabban közel kerülhetnek a végleges helyükhöz. Így az eredeti módszer hatékonyabbá válhat. Különösen igaz ez a beszúró rendezésnél.
Az elemek közötti távolságot jelöljük D-vel. ElsQ értéke: N/3+1, majd D:=D/3+1.
Pl. 10 elemq sorozatnál az alábbi részsorozatokat rendezzük:

D=4 1,5,9 2,6,10 3,7 4,8
D=2 1,3,5,7,9 2,4,6,8,10
D=1 1,2,3,4,5,6,7,8,9,10

Úgy tqnhet, mintha D=1 esetén lezajlana az egész beszúró rendezés, ekkor azonban már a korábbi menetek miatt minimális számú összehasonlítás és mozgatás történik.
Indexvektoros rendezés
A rendezendQ tömb elemeit nem mozgatjuk, hanem a tömbhöz egy indexvektort rendelünk, melyben a tömb elemeire mutató indexek a tömb rendezettségének megfelelQen követik egymást. Az eljárás során az indextömb elemeit az indexelt adatok rendezettségének függvényében sorba rakjuk. A hasonlítást tehát mindig az indexelt adatokra végezzük el, de csere esetén csak az indexeket cseréljük. Így az eredeti tömbünk változatlan maradhat. Közvetett módon így egyszerre több szempont szerint is módunkban áll adatainkat rendezni.
Gyorsrendezés (Quicksort)
Elve rekurzív:
osszuk két részre a rendezendQ sorozatot úgy, hogy az egyik rész minden eleme kisebb legyen a másik rész összes eleménél;
a két részre külön-külön ismételjük meg az elQbbi lépést, míg mindkét rész 0 vagy 1 elemq lesz.
A feldolgozási mqvelet egy szétválogatás, melynek során egy megadott értékhez viszonyítva a tQle kisebb elemeket elé, a nagyobbakat mögé helyezzük. Viszonyítási értéknek a gyakorlatban a sorozat középsQ vagy elsQ elemét választják ki.








 PAGE \* MERGEFORMAT 2



+

a

*

b

c

Hasonló témájú dokumentumok

5. Előadás

- 2007-11-25 22:27:21

ZH 2001.10.30

- 2008-03-10 20:56:24

A mások által feltöltött dokumentumokat értékelheted. Ha úgy ítéled meg, hogy a vizsgára való felkészülés szempontjából hasznos volt egy dokumentum, akkor adj rá sokcsillagos értékelést.
Ha hibákat tartalmaz, vagy egyéb probléma van vele, akkor keveset.
A dokumentumok sorrendje az értékelések alapján adódik. Ami fentebb van a listában, azt hasznosabbnak ítélték társaid. Az új dokumentumok pedig (értékelések hiányában) szintén a lista tetején kezdenek.

Hozzászólások

Ha észrevételed van egy dokumentummal kapcsolatban (például hibát találtál benne), akkor a Hozzászólások részben jelezheted. Az olyan jellegű kérdéseket mint pl.: A 2. feladat 4. sorából milyen átalakítással jutottunk az 5. sorban szereplő képlethez? - szintén ide érdemes írni

Egy tipp az oldalhoz! - Szavazz a feltöltött dokumentumokra az alapján, hogy mennyire volt számodra használható vagy épp használhatatlan (mondjuk azért, mert tele van hibával). A dokumentumok a szavazataitok alapján sorrendeződnek így hosszútávon a legjobb pontokat kapó dokumentumok lesznek a lista elején. Csak a saját szakod dokumentumaira szavazhatsz.

13 2004 2005 2008_12_17 4. óra ábris aggregált kereslet athén atombomba babits citrátkör de-avk definíciók dhm dolgozat elosztás előadás eu agrárpolitikája eupol évszámok fémek fogaskerék hajtás glikoneogenezis gyökerek katalízis képek közigazgatástörténet különleges épületszerkezetek labor lengéstan máté eörs mindennapok kémiája mpiac oktatási törvény oscar niemeyer oxidáció pedagógia példák platón reklámelmélet és gyakorlat sorozat stat stat1 szigetelés szöveg tanulás és kutatásmódszertan társ.st. tektonika vezetői vizsgához