Tartalomjegyzék Köszönetnyilvánítás Bevezetés Kinek szól a könyv? Elvárt előismeretek A könyv témája A könyv használata A megközelítés alapelvei Törekedjünk az egyszerűségre! Ne optimalizáljunk előre! Felhasználói interfészek Tesztelni, tesztelni! Legyünk alaposak! Mire van szükség a könyv használatához? A könyvben használt jelölések Forráskód Hibajegyzék p2p.wrox.com
1.
Az alapok Az algoritmusok definíciója Az algoritmusok bonyolultsága A nagy O jelölés Konstans idő: O(1) Lineáris idő: O(N) Kvadratikus idő: O(N2) Logaritmikus idő: O(log N) és O(N log N) Faktoriális idő: O(N!) Egységtesztelés Mi az egységtesztelés? Miért fontos az egységtesztelés? JUnit-bevezető Tesztelésen alapuló programozás Összefoglalás
xi xiii xiii xiii xiv xiv xv xvi xvi xvii xvii xviii xix xx xxi xxi xxii
1 1 4 5 7 7 8 9 9 10 11 13 13 17 18
Tartalomjegyzék
2.
3.
4.
5.
Iteráció és rekurzió
19
Számítások végrehajtása Tömbök feldolgozása Iterátorok használata tömbalapú problémák megoldására Rekurzió Rekurzív könyvtárfa-nyomtatási példa A rekurzív algoritmus működése Összefoglalás Gyakorlatok
20 22 23 42 44 47 48 49
Listák
51
A listákról A listák tesztelése Listák megvalósítása A tömblista Láncolt lista Összefoglalás Gyakorlatok
51 55 68 69 77 87 87
Várakozási sorok
89
A sorok Sorműveletek A sorinterfész A FIFO-sor A FIFO-sor megvalósítása Blokkolósorok Példa: telefonos ügyfélszolgálat szimulátora Az alkalmazás futtatása Összefoglalás Gyakorlatok
89 90 91 92 96 97 102 112 114 114
Vermek Vermek A tesztek Megvalósítás Példa: az undo/redo parancs megvalósítása Az undo/redo parancs tesztelése Összefoglalás
vi
115 115 118 121 124 125 134
Tartalomjegyzék
6.
Alapvető rendezés A rendezés fontossága Rendezési alapismeretek Az összehasonlítókról Összehasonlító műveletek Az összehasonlító interfész Néhány szabványos összehasonlító A buborékrendezésről A ListSorter interfész Az AbstractListSorter tesztelése A kiválasztásos rendezés alkalmazása A beszúrásos rendezésről A stabilitásról Az alapvető rendezési algoritmusok összehasonlítása CallCountingListComparator ListSorterCallCountingTest Az algoritmus-összehasonlításról Összefoglalás Gyakorlatok
7.
Fejlettebb rendezés A Shell-rendezési algoritmus alapjai A gyorsrendezésről Az összetett összehasonlítóról és a stabilitásról Az összefésüléses rendezési algoritmusról Összefésülés Az összefésüléses rendezési algoritmus A fejlettebb rendezési algoritmusok összehasonlításáról Összefoglalás Gyakorlatok
8.
Prioritásos sorok A prioritásos sorok áttekintése Egyszerű példa prioritásos sorra Prioritásos sorok kezelése Rendezetlen listás prioritásos sor áttekintése Rendezetlen listás prioritásos sor megvalósítása Halmon alapuló prioritásos sorok működése Prioritásos sorok megvalósításainak összehasonlítása Összefoglalás Gyakorlatok
135 135 136 137 137 138 138 143 146 146 151 156 160 161 162 163 166 167 168
169 169 175 182 186 186 187 194 198 198
199 199 200 203 206 208 210 219 222 223
vii
Tartalomjegyzék
9.
Bináris keresés és beszúrás A bináris keresés működése A bináris keresés megközelítései Listabeli kereső Iteratív bináris kereső A listabeli kereső teljesítményének vizsgálata Bináris beszúrás működése Listabeszúró Teljesítmény vizsgálata Összefoglalás
10. Bináris keresőfák A bináris keresőfákról Minimum Maximum A következő csomópont A megelőző csomópont Keresés Beszúrás Törlés Inorder bejárás Preorder bejárás Posztorder bejárás Kiegyensúlyozás A bináris keresőfa tesztelése és megvalósítása A bináris keresőfa teljesítményének megállapítása Összefoglalás Gyakorlatok
11. Hasítás A hasítás megértése Munka a hasítással Lineáris vizsgálat Vödrös módszer A teljesítmény megállapítása Összefoglalás Gyakorlatok
12. Halmazok A halmazokról Halmazmegvalósítások tesztelése Listahalmaz
viii
225 225 228 228 236 238 245 246 250 254
257 257 258 259 259 260 260 262 264 266 267 267 268 270 295 299 299
301 301 309 312 319 324 331 331
333 333 337 344
Tartalomjegyzék
Hasítóhalmaz Fahalmaz Összefoglalás Gyakorlatok
13. Leképezések A leképezésekről Leképezésmegvalósítások vizsgálata Listaleképezés Hasítóleképezés Faleképezés Összefoglalás Gyakorlatok
14. Hármas keresőfák Hármas keresőfák Szó keresése Szó beszúrása Prefix keresés Mintaillesztés A hármas keresőfák gyakorlati alkalmazása Keresztrejtvény megoldását segítő példa Összefoglalás Gyakorlat
15. B-fák A B-fákról B-fák a gyakorlatban Összefoglalás Gyakorlatok
16. Sztringkeresés Általános sztringkereső interfész Általános tesztcsomag Letámadásos algoritmus A Boyer–Moore-algoritmus A tesztek létrehozása Az algoritmus megvalósítása Sztringillesztő iterátor A teljesítmény összehasonlítása A teljesítmény mérése Az összehasonlítás eredménye Összefoglalás
346 350 357 358
359 359 364 373 377 381 388 389
391 391 392 396 398 399 403 417 422 422
423 423 429 443 443
445 445 447 451 454 456 457 461 462 463 467 468 ix
Tartalomjegyzék
17. Sztringillesztés A Soundex algoritmus A Levenshtein-szótávolság Összefoglalás
18. Számítógépes geometria Rövid geometriai ismétlés Koordináták és pontok Egyenes szakaszok Háromszögek Két egyenes szakasz metszéspontjának meghatározása Meredekség Az y tengely metszése A metszéspont meghatározása A legközelebbi pontpár meghatározása Összefoglalás Gyakorlatok
19. Pragmatikus optimalizálás Az optimalizálás szerepe A profilírozásról A FileSortingHelper példaprogram Profilírozás a hprof modullal Profilírozás a Java Memory Profiler programmal Az optimalizálásról Optimalizálás a gyakorlatban Összefoglalás
471 471 483 494
495 495 495 497 497 498 499 500 501 517 529 529
531 531 533 534 538 541 543 544 552
„A” függelék: Ajánlott irodalom
553
„B” függelék: Internetes források
555
„C” függelék: Bibliográfia
557
„D” függelék: A gyakorlatok megoldásai
559
Tárgymutató
609
A szerzőkről
621
x
