Algorytmy.Struktury.danych.i.techniki.programowania.9788324623068.pdf

Podstawowy podręcznik do nauki algorytmiki

• Przystępne wprowadzenie do algorytmiki

•

Bez zbędnej teorii

Gotowe rozwiązania w

•

C++

A LGORYT MY

STRUKTURY DANYC H

------

---

TECHNIKI

PRO G RAMOWANIA

WYDANIE

PI OTR WRÓBLE WSKI

IR Helion

Podstawowy podręcznik do nauki algorytmiki

ALGORYTMY

� -- -

STRUKTURY

DANYCH

TECHNIKI

PROGRAMOWANIA

-- ---

-- - -

WYDANIE

\ \

\ \\

--- ��,

�

-- -�

PIOTR WRÓBLEWSKI .

�HeHon

Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszecnianie całości lub ragmentu niniejszej

publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograiczną,

fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym

powoduje naruszenie praw autorskich niniejszej publikacji.

Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymi

ich właścicieli.

Autor oraz Wydawnictwo HELION dołożyli wszelkich starań, by zawarte w tej książce informacje

były kompletne i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za ich wykorzystanie,

ani za związane z tym ewentualne naruszenie praw patentowych lub autorskich. Autor oraz

Wydawnictwo HELION nie ponoszą również żadnej odpowiedzialności za ewentualne szkody

wynikłe z wykorzystania informacji zawartych w ksiżce.

Redakcja: Michał Mrowiec

Projekt okładki: Maciej Pasek

Fotografia na okładce została wykorzystana za zgodą iStockPhoto Inc.

Wydawnictwo HELION

ul. Kościuszki

le,

44-100 GLIWICE

tel. 32 231 22 19, 32 230 98 63

e-mail: helion@helionpl

WW : http://helion.pl (księgania intenetowa, katalog książek)

Drogi Czytelniku!

Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres

http://helion.pl/user/opinie?algo4

Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję.

ISBN: 978-83-246-2306-8

Printed in Poland.

Spis treści

Pzedmowa ...... „ „ „ ••• „ „ „ ••••••• „ „. „ •• „ •••••••••••••••••••••••••••••••••••••••• „ „ .•• 9

Rozdział 1. Zanim wystatujemy ...... . ........... . .. . ......... . .......... ... ..................... ... . . 17

Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych

...................

Jak to się niedawno odbyło,

czyli o tym, kto „wymyślił" metodologię programowania ..... „„ .................... „„ .......... 21

Proces koncepcji programów ......................................................... „ .............. „ ............... 22

Poziomy abstrakcji opisu i wybór języka .........„ ........... „ ......„ ... „.„ ......„ ......„ „.„.......... 23

Poprawność algorytmów ............................................... „ .......... „ .. „ ............ ................... 24

Rozdział 2. Rekurencja . .......... . ... . .......... .. ........... ... ...... .. ....... . .. . . . .. . ...... .. .......... 27

Deinicja rekurencji .................................... „ .................................................................. 27

Ilustracja pojęcia rekurencji ............................................................................................ 28

Jak wykonują się programy rekurencyjne? ............„ .......•........... „ ..•....•..•....•..•.•..•.......... 30

Niebezpieczeństwa rekurencji ........................................................................................ 31

Ciąg Fibonacciego ................ .................................................................................... 31

Stack overflow! ........................................................................................................ 33

Pułapek ciąg dalszy ... ....... „ .......•............•....•..•............•.......•.......•............•..•... „ ............. 34

Stąd do wieczności ..................... „ .............. „ ................... „ .......•............................... 34

Definicja poprawna, ale ... ........................... „ ................... „ ........................ „.„ .......... 35

Typy programów rekurencyjnych ..... „ ......................................... „ „ ........ „ .. „ „. „ „ .......... 36

Myślenie rekurencyjne

Przykład 1.: Spirala „ ........................... „ .. „ ........... „.„ ...... „ .... „ ........ „ ....................... 38

Przykład 2.: Kwadraty „parzyste" ...... „ .................................„ .. „.„ ....... „ ................. 40

Uwagi praktyczne na temat teclmik rekurencyjnych ..................„.„ .........„ ... „ .... „„„„ ... 41

Zadania ............................................................... „ ....................... „ ........... „„ ......... „ ....... 42

Rozwiązania i wskazówki do zadań

........................... „.„„„ ............ „„ .............. „ .............. „ ...„ ..........

.............. „ ....... „ ...........................•.......•....•.............

Rozdział 3. Analiza zożoności algorytmów ... . ............. . ...... „. „ ••••••••••• „ •• „ .......... 49

Definicje i przykłady ........................................... „ ................................ „„„ ....... „ .. „„„ .. 50

Jeszcze raz unkcja silnia ........... „ ....„......„„ ...... „ ...„„„........ „„„ ............ „„.„ .......... 53

Zerowanie ragmentu tablicy „„.„ .......... „„ ...... „ .. „ .. „ ...........„„„„........„ .................. 57

Wpadamy w pułapkę ................................................................................................ 58

Różne typy złożoności obliczeniowej

............„ .... „. „ ... „ ....... „ „ ... „ ......... „ ...............

Nowe zadanie: uprościć obliczenia!

.......... 61

.„„„„ ....... „.„„.„„„„.„„.„ ... „.„„ .. „ ...... „„„.„

Algorytmy, struktury danych i techniki programowania

Analiza programów rekurencyjnych ............................................................................... 62

Terminologia i deinicje ........................................................................................... 62

Ilustracja metody na przykładzie .............................................................................. 63

Rozkład logarytmiczny ............................................................................................. 64

Zamiana dziedziny równania rekurencyjnego .......................................................... 66

Funkcja Ackermanna, czyli coś dla smakoszy

Złożoność obliczeniowa to nie religia! ........................................................................... 68

Techniki optymalizacji programów ................................................................................ 68

Zadania ........................................................................................................................... 69

Rozwiązania i wskazówki do zadań ............................................................................... 70

Rozdział 4. Algorytmy sotowania .... . . ... ........... ............................... . . .. ... . ... . . ..... 73

Sortowanie przez wstawianie, algorytm klasy O(N 2 ) •...•...............•.•........•..........•.......... 74

Sortowanie bąbelkowe, algorytm klasy O(N 2 )

.........................................................

Quicksort, algorytm klasy O(N log N) ........................................................................... 77

Heap Sort - sortowanie przez kopcowanie ................................................................... 80

Scalanie zbiorów posortowanych ................................................................................... 82

Sortowanie przez scalanie ............................................................................................... 83

Sortowanie zewnętrzne ................................................................................................... 84

Uwagi praktyczne .................. ......................................................................................... 87

..........•...••.•.•..•....•..•.•.....•....•...........•.......

Rozdział 5. Typy i struktury danych .. .......... . . . . . . ...................... . .. . .............. ........ 89

Typy podstawowe i złożone ........................................................................................... 89

Ciągi znaków i napisy w C+ ......................................................................................... 90

Abstrakcyjne sury danych ....................................................................................... 92

Listy jednokierunkowe ............................................................................................. 93

Tablicowa implementacja list ................................................................................. 115

Stos ......................................................................................................................... 119

Kolejki FIFO

123

Sterty i kolejki priorytetowe ................................................................................... 125

Drzewa i ich reprezentacje ..................................................................................... 131

Zbiory ..................................................................................................................... 143

Zadania ................................................................................................................... 145

Rozwiązania zadań ................................................................................................. 146

Rozdział 6. Derekursywacja i optymalizacja algorytmów ....... . . ... .......... . ... ...... . . 14 7

Jak pracuje kompilator? ................................................................................................ 148

Odrobina ormalizmu nie zaszkodzi! ............................................................................ 150

Kilka przykładów derekursywacji algorytmów ............................................................ 151

Derekursywacja z wykorzystaniem stosu ..................................................................... 154

Eliminacja zmiennych lokalnych ............................................................................ 154

Metoda unkcji przeciwnych ........................................................................................ 156

Klasyczne schematy derekursywacji ............................................................................ 158

Schemat typu while ................................................................................................ 159

Schemat typu if-else ............................................................................................... 160

Schemat z podwójnym wywołaniem rekurencyjnym ............................................. 162

Podsumowanie .............................................................................................................. 163

..........................................................................................................

Rozdział 7. Algorytmy przeszukiwania ....... . . . ..... . ...... . . .... .. .. .. .... .. ..... . . .............. 165

Przeszukiwanie liniowe ................................................................................................ 165

Przeszukiwanie binane ..... „ ......................................................................................... 166

Transformacja kluczowa (hashing) ............................................................................... 167

W poszukiwaniu unkcji H ..................................................................................... 169

Najbardziej znane unkcje H .................................................................................. 169

Obsuga konfliktów dostępu ................................................................................... 171

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: