[ Pobierz całość w formacie PDF ]
IDZ DO
PRZYK£ADOW
Algorytmy w C
SPIS TRECI
KATALOG KSI¥¯EK
Autor: Kyle Loudon
T³umaczenie: Tomasz ¯mijewski
ISBN: 83-7197-912-6
Tytu³ orygina³
Format: B5, stron: 492
Przyk³ady na ftp: 272 kB
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
TWÓJ KOSZYK
DODAJ DO KOSZYKA
Ksi¹¿ka „Algorytmy w C” jest doskona³¹ pomoc¹ dla programistów, którym
w codziennej pracy potrzebne s¹ sprawdzone rozwi¹zania. Nie ma tu teoretycznych
dywagacji tak charakterystycznych dla wiêkszoci ksi¹¿ek o strukturach danych
i algorytmach. Znajdziesz w niej za to przystêpnie podane informacje i praktyczne
techniki programowania.
Wyj¹tkowo elegancki styl programowania i pisania autora, Kyle’a Loudona, u³atwia
poznanie najwa¿niejszych struktur danych, takich jak listy, stosy, kolejki, zbiory, sterty,
kolejki priorytetowe i grafy. Autor prezentuje u¿ycie algorytmów sortuj¹cych,
wyszukiwania, analiz numerycznych, kompresji danych, szyfrowania danych, typowych
algorytmów obs³ugi grafów oraz geometrii analitycznej. W rozdzia³ach powiêconych
kompresji i szyfrowaniu czytelnik znajdzie nie tylko gotowy, szybki w dzia³aniu kod, ale
te¿ informacje przydatne dla osób, które nigdy nie mia³y czasu ani chêci zag³êbiaæ siê
w omawiane zagadnienia.
W tekcie umieszczono tak¿e kody wraz z przyk³adami zastosowania poszczególnych
struktur danych i algorytmów. Komplet kodów ród³owych znajduje siê na p³ycie
CD-ROM. Kod ten zosta³ napisany w taki sposób, by ³atwo móg³ go wykorzystaæ
we w³asnych aplikacjach.
W ksi¹¿ce omówiono:
• Wskaniki
• Rekurencjê
• Analizê algorytmów
• Struktury danych (listy, stosy, kolejki, zbiory, tablice asocjacyjne, drzewa, sterty,
kolejki priorytetowe i grafy)
• Sortowanie i wyszukiwanie
• Metody numeryczne
• Kompresjê danych
• Szyfrowanie danych
• Algorytmy operuj¹ce na grafach
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
O NOWOCIACH
ZAMÓW CENNIK
CZYTELNIA
FRAGMENTY KSI¥¯EK ONLINE
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
Spis treci
Wstp ..........................................................................................................................................9
Cz I Zagadnienia podstawowe........................................................................ 15
Rozdział 1. Wprowadzenie.......................................................................................................17
Wprowadzenie do struktur danych ............................................................................................... 18
Wprowadzenie do algorytmów ......................................................................................................19
Odrobina inynierii oprogramowania ........................................................................................... 22
Jak tej ksi"ki uywa# ....................................................................................................................... 23
Rozdział 2. Uycie wskaników...............................................................................................25
Podstawowe informacje o wska'nikach ........................................................................................ 26
Alokacja pami*ci................................................................................................................................ 27
Agregaty i arytmetyka wska'ników .............................................................................................. 29
Wska'niki jako parametry funkcji .................................................................................................. 31
Wska'niki ogólne i rzutowanie....................................................................................................... 34
Wska'niki do funkcji ........................................................................................................................ 37
Pytania i odpowiedzi ........................................................................................................................ 38
Tematy pokrewne.............................................................................................................................. 39
Rozdział 3. Rekurencja.............................................................................................................41
Podstawy rekurencji.......................................................................................................................... 42
Rekurencja prawostronna ................................................................................................................ 46
Pytania i odpowiedzi ........................................................................................................................ 48
Tematy pokrewne.............................................................................................................................. 50
Rozdział 4. Analiza algorytmów..............................................................................................51
Analiza najgorszego przypadku ..................................................................................................... 52
O-notacja ............................................................................................................................................. 53
Złoono4# obliczeniowa ................................................................................................................... 55
 4
Algorytmy w C
Przykład analizy: sortowanie przez wstawianie .......................................................................... 57
Pytania i odpowiedzi ........................................................................................................................ 59
Tematy pokrewne.............................................................................................................................. 60
Cz II Struktury danych .................................................................................. 61
Rozdział 5. Listy powi(zane.....................................................................................................63
Opis list powi"zanych....................................................................................................................... 64
Interfejs list powi"zanych................................................................................................................. 65
Implementacja list powi"zanych i analiza kodu .......................................................................... 68
Przykład uycia list powi"zanych: zarz"dzanie ramkami ......................................................... 75
Opis list podwójnie powi"zanych .................................................................................................. 78
Interfejs list podwójnie powi"zanych............................................................................................. 79
Implementacja list podwójnie powi"zanych i analiza kodu ...................................................... 81
Opis list cyklicznych ......................................................................................................................... 90
Interfejs list cyklicznych ................................................................................................................... 91
Implementacja list cyklicznych i analiza kodu ............................................................................. 93
Przykład uycia list cyklicznych: zamiana stron.......................................................................... 98
Pytania i odpowiedzi ...................................................................................................................... 101
Tematy pokrewne............................................................................................................................ 103
Rozdział 6. Stosy i kolejki ......................................................................................................105
Opis stosów ...................................................................................................................................... 106
Interfejs stosu ................................................................................................................................... 107
Implementacja stosu i analiza kodu ............................................................................................. 108
Opis kolejek ...................................................................................................................................... 111
Interfejs kolejek ................................................................................................................................ 111
Implementacja kolejki i analiza kodu........................................................................................... 113
Przykład uycia kolejek: obsługa zdarze7 .................................................................................. 116
Pytania i odpowiedzi ...................................................................................................................... 118
Tematy pokrewne............................................................................................................................ 119
Rozdział 7. Zbiory..................................................................................................................121
Opis zbiorów .................................................................................................................................... 122
Interfejs zbiorów .............................................................................................................................. 124
Implementacja zbioru i analiza kodu ........................................................................................... 127
Przykład uycia zbiorów: pokrycie .............................................................................................. 137
Pytania i odpowiedzi ...................................................................................................................... 141
Tematy pokrewne............................................................................................................................ 143
Rozdział 8. Tablice asocjacyjne ..............................................................................................145
Opis ła7cuchowych tablic asocjacyjnych ..................................................................................... 147
Interfejs ła7cuchowych tablic asocjacyjnych ............................................................................... 150
Implementacja ła7cuchowej tablicy asocjacyjnej i analiza kodu.............................................. 152
Przykład uycia ła7cuchowych tablic asocjacyjnych: tablice symboli.................................... 159
Tablice asocjacyjne z otwartym adresowaniem.......................................................................... 162
Interfejs tablic asocjacyjnych z otwartym adresowaniem......................................................... 166
Spis treci
5
Implementacja tablicy asocjacyjnej z otwartym adresowaniem i analiza kodu .................... 167
Pytania i odpowiedzi ...................................................................................................................... 175
Tematy pokrewne............................................................................................................................ 177
Rozdział 9. Drzewa ................................................................................................................179
Drzewa binarne................................................................................................................................ 181
Interfejs drzew binarnych .............................................................................................................. 184
Implementacja drzew binarnych i analiza kodu ........................................................................ 187
Przykład uycia drzewa binarnego: przetwarzanie wyrae7.................................................. 198
Binarne drzewa wyszukiwania ..................................................................................................... 201
Interfejs binarnych drzew wyszukiwania ................................................................................... 203
Implementacja binarnych drzew wyszukiwania i analiza kodu ............................................. 205
Pytania i odpowiedzi ...................................................................................................................... 227
Tematy pokrewne............................................................................................................................ 228
Rozdział 10. Sterty i kolejki priorytetowe..............................................................................231
Sterty.................................................................................................................................................. 232
Interfejs stert..................................................................................................................................... 233
Implementacja stert i analiza kodu............................................................................................... 235
Kolejki priorytetowe ....................................................................................................................... 245
Interfejs kolejek priorytetowych.................................................................................................... 245
Implementacja kolejek priorytetowych i analiza kodu ............................................................. 247
Przykład zastosowania kolejek priorytetowych: sortowanie paczek...................................... 248
Pytania i odpowiedzi ...................................................................................................................... 250
Tematy pokrewne............................................................................................................................ 251
Rozdział 11. Grafy..................................................................................................................253
Grafy .................................................................................................................................................. 254
Interfejs grafów ................................................................................................................................ 260
Implementacja grafów i analiza kodu.......................................................................................... 264
Przykład uycia grafów: zliczanie kroków w ruchu po sieci................................................... 275
Przykład uycia grafów: sortowanie topologiczne.................................................................... 281
Pytania i odpowiedzi ...................................................................................................................... 285
Tematy pokrewne............................................................................................................................ 287
Cz III Algorytmy .......................................................................................... 289
Rozdział 12. Sortowanie i przeszukiwanie ............................................................................291
Sortowanie przez wstawianie........................................................................................................ 293
Interfejs sortowania przez wstawianie......................................................................................... 293
Implementacja sortowania przez wstawianie i analiza kodu .................................................. 294
Quicksort........................................................................................................................................... 296
Interfejs quicksort ............................................................................................................................ 297
Implementacja quicksort i analiza kodu...................................................................................... 298
Przykład uycia quicksort: zawarto4# katalogu ......................................................................... 303
Sortowanie przez zł"czanie............................................................................................................ 306
Interfejs sortowania przez zł"czanie ............................................................................................ 307
Implementacja sortowania przez zł"czanie i analiza kodu ...................................................... 307
6
Algorytmy w C
Sortowanie ze zliczaniem............................................................................................................... 312
Interfejs sortowania ze zliczaniem................................................................................................ 313
Implementacja sortowania ze zliczaniem i analiza kodu.......................................................... 313
Sortowanie na bazie ........................................................................................................................ 317
Interfejs sortowania na bazie ......................................................................................................... 317
Implementacja sortowania na bazie i analiza kodu................................................................... 318
Wyszukiwanie binarne ................................................................................................................... 321
Interfejs wyszukiwania binarnego................................................................................................ 321
Implementacja wyszukiwania binarnego i analiza kodu.......................................................... 322
Przykład uycia przeszukiwania binarnego: kontrola pisowni............................................... 324
Pytania i odpowiedzi ...................................................................................................................... 326
Tematy pokrewne............................................................................................................................ 328
Rozdział 13. Metody numeryczne..........................................................................................329
Przyblianie wielomianami ........................................................................................................... 330
Interfejs interpolacji wielomianowej............................................................................................. 334
Implementacja interpolacji wielomianowej i analiza kodu ...................................................... 334
Oszacowanie najmniejszymi kwadratami ................................................................................... 337
Interfejs oszacowania najmniejszymi kwadratami..................................................................... 339
Implementacja szacowania najmniejszymi kwadratami i analiza kodu ................................ 339
Rozwi"zywanie równa7 ................................................................................................................. 340
Interfejs rozwi"zywania równa7................................................................................................... 345
Implementacja rozwi"zywania równa7 i analiza kodu ............................................................ 345
Pytania i odpowiedzi ...................................................................................................................... 347
Tematy pokrewne............................................................................................................................ 348
Rozdział 14. Kompresja danych.............................................................................................349
Operatory bitowe............................................................................................................................. 352
Interfejs operacji bitowych ............................................................................................................. 353
Implementacja operacji bitowych i analiza kodu....................................................................... 354
Kodowanie Huffmana .................................................................................................................... 358
Interfejs kodowania Huffmana ..................................................................................................... 362
Implementacja kodowania Huffmana i analiza kodu ............................................................... 362
Przykład uycia kodowania Huffmana: optymalizacja przesyłania przez sie# .................... 376
Algorytm LZ77................................................................................................................................. 378
Interfejs LZ77.................................................................................................................................... 382
Implementacja LZ77 i analiza kodu ............................................................................................. 382
Pytania i odpowiedzi ...................................................................................................................... 395
Tematy pokrewne............................................................................................................................ 397
Rozdział 15. Szyfrowanie danych ..........................................................................................399
DES..................................................................................................................................................... 402
Interfejs DES ..................................................................................................................................... 409
Implementacja DES i analiza kodu............................................................................................... 410
Przykład uycia DES: blokowe tryby szyfrowania.................................................................... 420
Algorytm RSA.................................................................................................................................. 423
Interfejs RSA..................................................................................................................................... 426
[ Pobierz całość w formacie PDF ]