Tartalmi kivonat
Pusztai Pál ALGORITMUSOK ÉS ADATSTRUKTÚRÁK Készült a HEFOP 3.31-P-2004-09-0102/10 pályázat támogatásával Szerző: Pusztai Pál egyetemi adjunktus Lektor: Pukler Antal egyetemi adjunktus Varjasi Norbert egyetemi adjunktus Pusztai Pál, 2006 Marton László emlékére Algoritmusok és adatstruktúrák A dokumentum használata | Tartalomjegyzék | Függelék A dokumentum használata Vissza ◄ 4 ► A dokumentum használata Mozgás a dokumentumban A dokumentumban való mozgáshoz a Windows és az Adobe Reader megszokott elemeit és módszereit használhatjuk. Minden lap tetején és alján egy navigációs sor található, itt a megfelelő hivatkozásra kattintva ugorhatunk a használati útmutatóra, a tartalomjegyzékre, valamint a tárgymutatóra. A ◄ és a ► nyilakkal az előző és a következő oldalra léphetünk át, míg a Vissza mező az utoljára megnézett oldalra visz vissza bennünket. Pozícionálás a könyvjelzőablak segítségével
A bal oldali könyvjelző ablakban tartalomjegyzékfa található, amelynek bejegyzéseire kattintva az adott fejezet/alfejezet első oldalára jutunk. Az aktuális pozíciónkat a tartalomjegyzékfában kiemelt bejegyzés mutatja. A tartalomjegyzék és a tárgymutató használata Ugrás megadott helyre a tartalomjegyzék segítségével Kattintsunk a tartalomjegyzék megfelelő pontjára, ezzel az adott fejezet első oldalára jutunk. Keresés a szövegben A dokumentumban való kereséshez használjuk megszokott módon a Szerkesztés menü Keresés parancsát. Az Adobe Reader az adott pozíciótól kezdve keres a szövegben A dokumentum használata | Tartalomjegyzék | Függelék Vissza ◄ 4 ► Algoritmusok és adatstruktúrák A dokumentum használata | Tartalomjegyzék | Függelék Tartalomjegyzék Vissza ◄ 5 ► Tartalomjegyzék 1. Előszó 8 2. Bevezetés 10 3. Egyszerű adattípusok 16 3.1 Egész típus16 3.2 Karakter típus 16 3.3 Logikai típus 17 3.4
Valós típus 17 4. Adatok tárolása 19 4.1 Változó 19 4.2 Kifejezés19 4.3 Függvények 20 4.4 Az értékadó utasítás 21 4.5 Beolvasó utasítás 22 4.6 Kiíró utasítás23 5. Adatszerkezeti táblázat 24 6. Algoritmusok megadása 26 7. Strukturált algoritmusok tervezése 32 7.1 Szekvencia32 7.2 Szelekció33 7.3 Iteráció37 8. Elemi feladatok 44 8.1 Prímfelbontás 44 8.2 Monoton növő sorozat 45 8.3 Pozitív adatok maximuma, átlaga 46 8.4 ex hatványsora 47 8.5 Gyökkeresés intervallumfelezéssel 49 8.6 Integrálérték meghatározása közelítéssel 50 8.7 Feladatok52 A dokumentum használata | Tartalomjegyzék | Függelék Vissza ◄ 5 ► Algoritmusok és adatstruktúrák A dokumentum használata | Tartalomjegyzék | Függelék Tartalomjegyzék Vissza ◄ 6 ► 9. Összetett adattípusok 55 9.1 Tömbök55 9.2 Sztringek70 9.3 Halmazok 79 9.4 Rekordok89 10. Szubrutinok 94 11. Algoritmusok 99 11.1 Algoritmusok hatékonysága 99 11.2 Elemi
statisztikák 99 11.3 Rendezés és keresés105 11.4 Ellenőrzött input116 11.5 Rekurzív algoritmusok 124 11.6 Visszalépéses algoritmusok 130 11.7 Feladatok138 12. Verem 143 12.1 Általános jellemzés 143 12.2 Gyorsrendezés saját veremmel 144 12.3 Feladatok148 13. Dinamikus adatstruktúrák149 13.1 Dinamikus tömbök149 13.2 Mutatók és dinamikus változók 149 13.3 Kollekciók153 13.4 Láncolt listák 159 13.5 Összetett listák 166 13.6 Feladatok170 14. Fájlok 174 14.1 Fájlok kezelése175 14.2 Szekvenciális fájlok 178 14.3 Véletlen elérésű fájlok 179 14.4 Feladatok193 A dokumentum használata | Tartalomjegyzék | Függelék Vissza ◄ 6 ► Algoritmusok és adatstruktúrák A dokumentum használata | Tartalomjegyzék | Függelék Tartalomjegyzék Vissza ◄ 7 ► 15. Gráfok194 15.1 Alapfogalmak194 15.2 Tárolás 196 15.3 Fák 201 15.4 Útkeresés214 15.5 Feladatok227 16. Irodalomjegyzék 228 17. Függelék 229 17.1 C programok 232 17.2 Pascal
programok296 A dokumentum használata | Tartalomjegyzék | Függelék Vissza ◄ 7 ► Algoritmusok és adatstruktúrák A dokumentum használata | Tartalomjegyzék | Függelék Előszó Vissza ◄ 8 ► 1. Előszó Az algoritmusokat az emberiség már jóval azelőtt ismerte és használta, mielőtt az őket végrehajtani tudó számítógépeket megépítette. Noha az algoritmus szó eredete egy IX. századi perzsa matematikus (Al-Hvárizmi) nevéhez kötődik [Knu 87] [Sai 86], az algoritmusokat – mint egy feladat megoldásához vezető lépések sorozatát – már időszámításunk előtt is használták. Sokáig csak papíron, „kézzel” volt lehetőség az algoritmusok „végrehajtására”, ma már számítógépek végzik ezt helyettünk. Az univerzális, magasszintű programozási nyelvek [Nyé 03] megjelenése óta olyan eszközrendszert használhatunk algoritmusaink leírására, a feladatunkat megoldó program megírására, amelyek közel állnak az
emberi gondolkodás-, és jelölésmódhoz. Természetesen ezeket a programokat közvetlenül nem értik meg a számítógépek, le kell őket „fordítani” az adott számítógép utasításkészletére, és csak ezután hajthatók végre, futtathatók le. Könyvünkben bevezetett adatstruktúrák és algoritmus megadási módszerek nem egy konkrét programozási nyelvhez kötődnek, több nyelvből (C, Pascal, Basic) lettek „összegyúrva”, kiemelve a közös, általános részeket, így lehetőségünk van az algoritmusok „nyelv-független” lényegére koncentrálni. Algoritmusainkat strukturált módon készítjük, azaz csak a szekvencia, szelekció, iteráció vezérlőelemekből építkezünk, ugró utasítások nélkül, így megoldásaink áttekinthetők és könnyen programozhatók lesznek. Amellett, hogy bemutatjuk és elemezzük a kiválasztott algoritmusokat, elsődleges célunk az algoritmikus feladatmegoldó készség kialakítása, fejlesztése, a logikus
gondolkodásra való „nevelés”. Ha egy algoritmushoz olyan adatszerkezetet használunk, amelyet a programírásra szánt nyelv nem támogat (pl. a C nyelvben nincsenek halmazok), akkor kitérünk a megvalósítás lehetőségeire A megoldások, noha nem úgy terveztük őket, akár objektumorientáltan is programozhatók, kihasználva ezzel az egységbezárás előnyeit. Feladataink azonban többnyire kevés közös részt tartalmaznak, ezért az objektumorientált programozás igazi erejét adó öröklés, így annak előnyei nem érvényesíthetők. A dokumentum használata | Tartalomjegyzék | Függelék Vissza ◄ 8 ► Algoritmusok és adatstruktúrák A dokumentum használata | Tartalomjegyzék | Függelék Előszó Vissza ◄ 9 ► Egy univerzális programozási nyelv ismeretében algoritmusaink programmá írhatók, kipróbálhatók, hiszen a „visszacsatolás”, a megoldás helyességének számítógéppel történő ellenőrzése a tanulási folyamat
szerves része. Ezt a tantárgyunktól független, önálló programozást megkönnyítendő, a jegyzetben szereplő megoldásokat C és Pascal nyelven programoztuk, amelyekhez a Borland cég Turbo C és Turbo Pascal fejlesztőrendszerét használtuk A forrásprogramok a függelékben megtalálhatók Ismerve az egyedül elvégzett, önálló munka hasznosságát és maradandóságát, fejezeteink végén egy csokor, az adott témához kapcsolódó feladatot tűzünk ki, amelyből kedvére válogathat a gyakorlásra vágyó, tudását lemérni kívánó hallgató, olvasó. Jegyzetünk a BSc képzésű, műszaki informatika szakos hallgatók Algoritmusok és adatstruktúrák című tantárgyához készült, amelyet a második félévben, heti két órában tanulnak a nappali tagozaton. Példáinkat ennek megfelelően válogattuk, szem előtt tartva az összeállított tananyag 30 órában történő taníthatóságát. Hallgatóink az első félévtől kezdődően három féléven
keresztül (heti 3-5 órában) tanulják a Programozás című tantárgyat, amely két félév C és egy félév objektumorientált Java programozást tartalmaz. Tantárgyunk átfed tehát a C programozás második félévével, így • Könnyebb a bevezető fejezetek tanítása. • Megoldásainkat a hallgatók C nyelven programozni tudják, így nemcsak kipróbálhatják, ellenőrizhetik azokat, hanem egyben „anyagot” is kapnak a C nyelvű programozás gyakorlásához. • A nehezebb részeket (pl. mutatók, dinamikus adatstruktúrák) közel egy időben tárgyalja a két tantárgy, megkönnyítve ezzel a megértésüket. Tudjuk, hogy a rendelkezésre álló időkeret nem engedi meg az összes feladat részletes tárgyalását, de bízunk benne, hogy a jegyzet anyaga tanári segédlet nélkül, önállóan is feldolgozható, megérthető és elsajátítható. Győr, 2006. május A dokumentum használata | Tartalomjegyzék | Függelék A szerző Vissza ◄ 9 ►
Algoritmusok és adatstruktúrák A dokumentum használata | Tartalomjegyzék | Függelék Bevezetés Vissza ◄ 10 ► 2. Bevezetés Ha egy feladat megoldására számítógépes programot készítünk, akkor általában az alábbi lépéseket, tevékenységeket kell elvégeznünk: 1. A feladat megfogalmazása, pontosítás, általánosítás 2. Matematikai (vagy egyéb) modell kiválasztása, megadása (ha szükséges, ill. lehetséges) 3. Az adatszerkezet definiálása, az input-output specifikálása 4. A megoldást megvalósító algoritmus megtervezése, elkészítése 5. Programírás, kódolás (az adatszerkezet és az algoritmus alapján) 6. Tesztelés, hibakeresés 7. Dokumentálás (felhasználóknak, fejlesztőknek) Természetesen az adott munka, ill. feladat jellegéből adódóan bizonyos lépések el is maradhatnak (pl. 2, 7), ill javítás, módosítás esetén szükség lehet egy korábbi szintre való visszalépésre is. Jegyzetünkben elsősorban a megoldások
érdemi részét jelentő 3. és 4 lépésekre fókuszálunk az Algoritmusok + Adatstruktúrák = Programok „képlet” alapján [Wir 82], de mint ahogy a puding próbája az evés, itt az 5., 6 lépések igazolják vissza megoldásunk helyességét, helytelenségét Az 1-5. megoldási lépéseket az alábbi feladat megoldásán keresztül szemléltetjük, de az alkalmazott adattípusokat, az adatszerkezeti táblázatot, az algoritmus megadási módszereket, azaz a megoldás eszközeit a későbbi fejezetekben részletesen tárgyaljuk. Feladat: Alakítsunk át egy pozitív egész számot egy adott (2-16) számrendszerbe! 1. Általánosítás: A megoldást nem két konkrét adatra, hanem megadható, input adatokra készítjük el, így „tetszőlegesen” konvertálhatunk 2. Matematikai modell: Ez maga az algoritmus, miszerint először a megadott számot, utána a keletkező hányadosokat mindaddig osszuk el az adott számrendszer alapszámával, amíg a hányados nulla nem lesz.
Minden osztásnál jegyezzük fel az osztás maradékát Ezekből, mint számjegyekből, a feljegyzésük fordított sorrendjében számot képezve, a megoldást kapjuk. A dokumentum használata | Tartalomjegyzék | Függelék Vissza ◄ 10 ► Algoritmusok és adatstruktúrák Bevezetés A dokumentum használata | Tartalomjegyzék | Függelék Pl: 40-et 2-s számrendszerbe 40 20 10 5 2 1 0 Vissza ◄ 11 ► Pl: 40-et 16-s számrendszerbe 0 0 0 1 0 1 Eredmény: 101000 Eredmény: 28 3. Adatszerkezet: Tekintettel a hexadecimális számrendszer betűvel jelölt számjegyeire, ill. a nagy egész számok (4 bájt) esetén a kettes számrendszerbeli, esetlegesen 32 számjegyes eredményre, az eredmény típusa csak sztring lehet. Funkció Azonosító Típus Jelleg Az átalakítandó szám A számrendszer alapszáma Az eredmény „szám” A B ER Egész Egész Sztring I I M, O Az ER változó munka jellegű is, mert értéke az algoritmus során alakul, változik,
ahogyan a maradékokat egy sztringgé fűzzük. 4. Algoritmus: A lehetséges számjegyeket egy sztringkonstansban deklaráljuk: Konstans SZAMJEGYEK ”0123456789ABCDEF” A megoldás pszeudokódja: /* Számrendszer konverzió / KONVERTAL(A,B) ER ← ”” repeat ER ← SZAMJEGYEK[A MOD B+1]+ER A ← A DIV B until A=0 return ER A dokumentum használata | Tartalomjegyzék | Függelék Vissza ◄ 11 ► Algoritmusok és adatstruktúrák A dokumentum használata | Tartalomjegyzék | Függelék Bevezetés Vissza ◄ 12 ► 5. Programírás: Az alábbiakban, az összehasonlítás végett három magasszintű és egy gépközeli nyelven is programmá írtuk a megoldásunkat. C program /* SZRKONV.C : Számrendszer konverzió */ #include <stdio.h> #include <conio.h> #define MaxHossz 32+1 /* +1: a végjelnek / #define SzamJegyek "0123456789ABCDEF" void Konvertal(int a, int b, char *er) { int i,j; char cs; /* Osztogatás / i=0; do { er[i++]=SzamJegyek[a%b]; a=a/b;
} while (a>0); /* Végjel / er[i]='