PHP 7. Algorytmy i struktury danych - ebook

Algorytmy i struktury danych leżą u podstaw programowania. Zrozumienie zasad rządzących tymi zagadnieniami jest koniecznym warunkiem opracowania prawidłowej i efektywnej aplikacji. Niestety, wielu programistów uznaje tę tematykę za zbyt złożoną czy zbyt banalną i nie poświęca jej wystarczającej uwagi. Takie podejście często się mści: modne narzędzia, frameworki czy technologie deweloperskie nie zapewnią sukcesu, jeśli projektant nie przemyśli zastosowanych algorytmów i struktur danych. Z tego obowiązku nie zwalniają nawet narzędzia wbudowane w język PHP!

Jeśli chcesz biegle posługiwać się algorytmami, wziąłeś do ręki właściwą książkę! Przedstawiono tu podstawy implementacji algorytmów i struktur danych w PHP, dzięki czemu poznasz rodzaje struktur i powody, dla których warto je wybierać, a także dowiesz się, gdzie i kiedy należy stosować poszczególne algorytmy. Znajdziesz tu dużo praktycznych przykładów, które uzupełniono rysunkami i wyczerpującym komentarzem. Przystępne i zrozumiałe wyjaśnienia ułatwią Ci szybkie przyswojenie prezentowanych koncepcji, nawet tak złożonych, jak programowanie dynamiczne, algorytmy zachłanne, algorytmy z nawrotami czy funkcyjne struktury danych.

Najważniejsze zagadnienia:

• podstawy analizy algorytmów i struktur danych,
• tablice, listy i drzewa,
• stosy, kolejki i algorytmy rekurencyjne,
• sortowanie, wyszukiwanie, sterty i kopce,
• wsparcie ze strony PHP, w tym biblioteki PECL i Tarsana.

Algorytmy: poznaj, zrozum, stosuj!

Mizanur Rahman od 14 lat rozwija aplikacje w PHP. Jest znawcą Laravela, CodeIgnitera, Symfony, JavaScriptu, C, C++, Javy, Node.js, Socket.io i React.js. Jest właścicielem dwóch startupów technologicznych. Jest osobą niezwykle zaangażowaną w życie kilku społeczności programistycznych, takich jak PHPXperts, Agile Bangladesh czy Project Euler. Regularnie wygłasza referaty na różnych konferencjach i seminariach technologicznych. Wraz z żoną Nishą i dwoma synami, Adiyanem i Mikhaelem, mieszka w Dhace w Bangladeszu. Jego pasją są podróże po świecie.

Wstęp (15)

Rozdział 1. Wprowadzenie do algorytmów i struktur danych (19)

• Znaczenie algorytmów i struktur danych (20)
• Znaczenie abstrakcyjnych typów danych (ADT) (23)
• Różne struktury danych (24)
  
  • Struktura (25)
  • Tablica (25)
  • Lista jednokierunkowa (26)
  • Lista dwukierunkowa (26)
  • Stos (27)
  • Kolejka (27)
  • Zbiór (28)
  • Mapa (tablica asocjacyjna) (28)
  • Drzewo (28)
  • Graf (29)
  • Sterta (kopiec) (29)
• Rozwiązywanie problemu - podejście algorytmiczne (30)
• Pisanie pseudokodu (31)
  
  • Przekształcanie pseudokodu w prawdziwy kod (32)
• Analiza algorytmu (33)
  
  • Obliczanie złożoności (34)
• Zrozumienie notacji dużego O (35)
• Standardowa biblioteka PHP (SPL) i struktury danych (37)
• Podsumowanie (38)

Rozdział 2. Zrozumienie tablic PHP (39)

• Zrozumienie tablic PHP w lepszy sposób (39)
  
  • Tablica liczbowa (41)
  • Tablica asocjacyjna (42)
  • Tablica wielowymiarowa (43)
• Używanie tablicy jako elastycznego sposobu przechowywania danych (44)
• Używanie wielowymiarowych tablic do reprezentowania struktur danych (45)
  
  • Tworzenie tablic o stałym rozmiarze za pomocą klasy SplFixedArray (47)
• Porównanie wydajności zwykłych tablic PHP oraz tablic SplFixedArray (48)
  
  • Więcej przykładów zastosowania tablicy SplFixedArray (51)
• Zrozumienie tablic mieszających (53)
• Implementacja struktury przy użyciu tablicy PHP (54)
• Implementacja zbioru przy użyciu tablicy PHP (55)
• Najlepsze zastosowanie tablicy PHP (57)
• Czy tablica PHP jest zabójcą wydajności? (57)
• Podsumowanie (58)

Rozdział 3. Używanie list (59)

• Czym jest lista? (59)
• Różne typy list (63)
  
  • Lista dwukierunkowa (63)
  • Lista cykliczna (63)
  • Lista wielokierunkowa (64)
• Wstawianie, usuwanie i wyszukiwanie elementu (64)
  
  • Wstawianie węzła na pierwszej pozycji (65)
  • Wyszukiwanie węzła (65)
  • Wstawianie przed określonym węzłem (66)
  • Wstawianie po określonym węźle (67)
  • Usuwanie pierwszego węzła (67)
  • Usuwanie ostatniego węzła (68)
  • Wyszukiwanie i usuwanie jednego węzła (69)
  • Odwracanie listy (69)
  • Pobieranie elementu z n-tej pozycji (70)
• Zrozumienie złożoności list (71)
• Sprawianie, aby lista była iterowalna (72)
• Budowanie listy cyklicznej (73)
• Implementacja listy dwukierunkowej w PHP (75)
• Operacje na liście dwukierunkowej (75)
  
  • Wstawianie węzła na pierwszej pozycji (76)
  • Wstawianie węzła na ostatniej pozycji (76)
  • Wstawianie przed określonym węzłem (77)
  • Wstawianie po określonym węźle (78)
  • Usuwanie pierwszego węzła (78)
  • Usuwanie ostatniego węzła (79)
  • Wyszukiwanie i usuwanie jednego węzła (79)
  • Wyświetlanie listy od początku do końca (80)
  • Wyświetlanie listy od końca do początku (80)
• Złożoność list dwukierunkowych (80)
• Używanie obiektów klasy PHP SplDoublyLinkedList (81)
• Podsumowanie (82)

Rozdział 4. Konstruowanie stosów i kolejek (83)

• Zrozumienie stosu (83)
• Implementacja stosu za pomocą tablicy PHP (84)
• Zrozumienie złożoności operacji na stosie (87)
• Implementacja stosu za pomocą listy (88)
• Używanie klasy SplStack należącej do SPL (90)
• Rzeczywiste zastosowanie stosu (90)
  
  • Dopasowywanie zagnieżdżonych nawiasów (91)
• Zrozumienie kolejki (93)
• Implementacja kolejki za pomocą tablicy PHP (94)
• Implementacja kolejki za pomocą listy (95)
• Używanie klasy SplQueue należącej do SPL (96)
• Zrozumienie kolejki priorytetowej (96)
  
  • Sekwencja uporządkowana (97)
  • Sekwencja nieuporządkowana (97)
• Implementacja kolejki priorytetowej za pomocą listy (97)
• Implementacja kolejki priorytetowej za pomocą klasy SplPriorityQueue (99)
• Implementacja kolejki cyklicznej (100)
• Tworzenie kolejki dwustronnej (102)
• Podsumowanie (105)

Rozdział 5. Stosowanie algorytmów rekurencyjnych (107)

• Zrozumienie rekurencji (108)
  
  • Właściwości algorytmów rekurencyjnych (109)
  • Algorytmy rekurencyjne kontra algorytmy iteracyjne (110)
  • Implementacja ciągu Fibonacciego za pomocą rekurencji (111)
  • Implementacja obliczania NWD za pomocą rekurencji (111)
• Różne rodzaje rekurencji (112)
  
  • Rekurencja liniowa (112)
  • Rekurencja binarna (112)
  • Rekurencja ogonowa (112)
  • Rekurencja wzajemna (113)
  • Rekurencja zagnieżdżona (113)
• Budowanie N-poziomowego drzewa kategorii za pomocą rekurencji (114)
  
  • Budowanie systemu zagnieżdżonych odpowiedzi na komentarze (116)
• Wyszukiwanie plików i katalogów za pomocą rekurencji (120)
• Analizowanie algorytmów rekurencyjnych (122)
• Maksymalna głębokość rekurencji w PHP (123)
• Używanie rekurencyjnych iteratorów SPL (124)
• Używanie wbudowanej funkcji PHP array_walk_recursive (125)
• Podsumowanie (126)

Rozdział 6. Zrozumienie i implementacja drzew (127)

• Definicja i właściwości drzewa (128)
• Implementacja drzewa przy użyciu języka PHP (130)
• Różne typy struktur drzewiastych (132)
  
  • Drzewo binarne (132)
  • Drzewo binarne poszukiwań (133)
  • Samorównoważące się drzewo binarne poszukiwań (133)
  • B-drzewo (135)
  • Drzewo N-arne (135)
• Zrozumienie drzewa binarnego (135)
• Implementacja drzewa binarnego (136)
• Tworzenie drzewa binarnego za pomocą tablicy PHP (138)
• Zrozumienie binarnego drzewa poszukiwań (140)
  
  • Wstawianie nowego węzła (141)
  • Wyszukiwanie węzła (141)
  • Wyszukiwanie wartości minimalnej (142)
  • Wyszukiwanie wartości maksymalnej (142)
  • Usuwanie węzła (142)
• Konstruowanie binarnego drzewa poszukiwań (143)
• Przechodzenie przez drzewo (151)
  
  • Przechodzenie bezpośrednie (151)
  • Przechodzenie z wyprzedzeniem (152)
  • Przechodzenie z opóźnieniem (153)
• Złożoność różnych drzewiastych struktur danych (154)
• Podsumowanie (155)

Rozdział 7. Używanie algorytmów sortowania (157)

• Zrozumienie sortowania i jego rodzajów (157)
• Zrozumienie sortowania bąbelkowego (158)
  
  • Implementacja sortowania bąbelkowego za pomocą języka PHP (159)
  • Złożoność sortowania bąbelkowego (161)
  • Poprawianie algorytmu sortowania bąbelkowego (161)
• Zrozumienie sortowania przez wybieranie (165)
  
  • Implementacja sortowania przez wybieranie (167)
  • Złożoność sortowania przez wybieranie (167)
• Zrozumienie sortowania przez wstawianie (168)
  
  • Implementacja sortowania przez wstawianie (170)
  • Złożoność sortowania przez wstawianie (171)
• Zrozumienie technik sortowania wykorzystujących metodę dziel i zwyciężaj (171)
• Zrozumienie sortowania przez scalanie (171)
  
  • Implementacja sortowania przez scalanie (173)
  • Złożoność sortowania przez scalanie (174)
• Zrozumienie sortowania szybkiego (175)
  
  • Implementacja sortowania szybkiego (176)
  • Złożoność sortowania szybkiego (178)
• Zrozumienie sortowania kubełkowego (178)
• Używanie wbudowanych funkcji sortujących PHP (179)
• Podsumowanie (180)

Rozdział 8. Poznawanie technik wyszukiwania (181)

• Wyszukiwanie liniowe (181)
• Wyszukiwanie binarne (183)
  
  • Analiza algorytmu wyszukiwania binarnego (187)
  • Algorytm powtarzalnego wyszukiwania binarnego (187)
  • Przeszukiwanie nieposortowanej tablicy - czy należy ją najpierw posortować? (190)
• Wyszukiwanie interpolacyjne (191)
• Wyszukiwanie wykładnicze (192)
• Wyszukiwanie przy użyciu tablicy mieszającej (193)
• Wyszukiwanie w drzewach (194)
  
  • Przeszukiwanie wszerz (194)
  • Przeszukiwanie w głąb (198)
• Podsumowanie (203)

Rozdział 9. Włączanie grafów do akcji (205)

• Zrozumienie właściwości grafów (205)
  
  • Wierzchołek (206)
  • Krawędź (206)
  • Sąsiedztwo (207)
  • Incydencja (208)
  • Stopień wchodzący i stopień wychodzący (208)
  • Ścieżka (208)
• Typy grafów (209)
  
  • Grafy skierowane (209)
  • Grafy nieskierowane (209)
  • Grafy ważone (210)
  • Skierowane grafy acykliczne (210)
  • Reprezentowanie grafów w PHP (211)
• Algorytmy BFS i DFS dla grafów (212)
  
  • Przeszukiwanie wszerz (212)
  • Przeszukiwanie w głąb (214)
• Sortowanie topologiczne przy użyciu algorytmu Kahna (216)
• Wyznaczanie najkrótszej ścieżki za pomocą algorytmu Floyda-Warshalla (218)
• Wyznaczanie najkrótszej ścieżki z pojedynczego źródła za pomocą algorytmu Dijkstry (221)
• Wyznaczanie najkrótszej ścieżki za pomocą algorytmu Bellmana-Forda (224)
• Zrozumienie minimalnego drzewa rozpinającego (227)
• Wyznaczanie minimalnego drzewa rozpinającego za pomocą algorytmu Prima (228)
• Wyznaczanie minimalnego drzewa rozpinającego za pomocą algorytmu Kruskala (231)
• Podsumowanie (233)

Rozdział 10. Zrozumienie i używanie stert (235)

• Czym jest sterta? (235)
• Operacje na stercie (236)
• Implementacja kopca binarnego w języku PHP (237)
• Analiza złożoności operacji na stercie (241)
• Używanie sterty jako kolejki priorytetowej (242)
• Używanie sortowania przez kopcowanie (245)
• Używanie klas SplHeap, SplMaxHeap oraz SplMinHeap (248)
• Podsumowanie (248)

Rozdział 11. Rozwiązywanie problemów za pomocą technik zaawansowanych (249)

• Memoizacja (250)
• Algorytmy dopasowania do wzorca (252)
• Implementacja algorytmu Knutha-Morrisa-Pratta (253)
• Algorytmy zachłanne (255)
• Implementacja algorytmu kodowania Huffmana (256)
• Zrozumienie programowania dynamicznego (260)
• Dyskretny problem plecakowy (261)
• Znajdowanie długości najdłuższego wspólnego podciągu (262)
• Sekwencjonowanie DNA przy użyciu programowania dynamicznego (264)
• Używanie algorytmu z nawrotami do rozwiązywania zagadek (267)
• System rekomendacji używający wspólnego filtrowania (271)
• Używanie filtrów Blooma i macierzy rzadkich (274)
• Podsumowanie (277)

Rozdział 12. Obsługa algorytmów i struktur danych przez język PHP (279)

• Wbudowane w język PHP możliwości związane ze strukturami danych (279)
  
  • Używanie tablicy PHP (280)
• Klasy SPL (283)
• Algorytmy wbudowane (284)
• Mieszanie (287)
• Wbudowane możliwości dostępne dzięki PECL (288)
  
  • Instalacja (289)
  • Interfejsy (290)
  • Wektor (290)
  • Mapa (291)
  • Zbiór (291)
  • Stos i kolejka (293)
  • Kolejka dwustronna (294)
  • Kolejka priorytetowa (294)
• Podsumowanie (295)

Rozdział 13. Funkcyjne struktury danych w języku PHP (297)

• Zrozumienie programowania funkcyjnego w języku PHP (298)
  
  • Funkcje pierwszej klasy (299)
  • Funkcje wyższego rzędu (299)
  • Funkcje czyste (299)
  • Funkcje lambda (300)
  • Domknięcia (300)
  • Rozwijanie funkcji (300)
  • Wykonania częściowe (301)
• Rozpoczęcie pracy z biblioteką Tarsana (302)
• Implementacja stosu (303)
• Implementacja kolejki (304)
• Implementacja drzewa (305)
• Podsumowanie (306)

Skorowidz (307)