Struktury danych z przymrużeniem oka. Zabawna przygoda z przykładami pachnącymi kawą - ebook

O strukturach danych można myśleć jako o konstruktach do organizowania i zapisywania danych. Zrozumienie, czym są, jak je tworzyć i do czego się przydają, jest jednym z fundamentów programowania. Bez tego nie można pisać efektywnego i skalowalnego kodu. Jednak dla wielu osób opanowanie struktur danych stanowi poważne wyzwanie.

Dzięki tej książce ta trudna sztuka musi Ci się udać! Znajdziesz tu gruntowne, a przy tym zabawne wprowadzenie do tworzenia i używania struktur danych. Naukę oprzesz na przejrzystych schematach i dowcipnych porównaniach, aby już wkrótce móc tworzyć wydajniejszy i elastyczny kod. Nieistotne, jakim językiem programowania się posługujesz - podczas lektury zaimplementujesz za pomocą pseudokodu kilkanaście głównych struktur danych, w tym stosy, filtry Blooma, drzewa czwórkowe i grafy. Fantazyjne przykłady ułatwią Ci intuicyjne posługiwanie się tymi strukturami danych. Dowiesz się, jak indeksować przedmioty kolekcjonerskie, optymalizować wyszukiwanie za pomocą latającej wiewiórki, a nawet jak znaleźć najbliższy kubek kawy!

Z tą książką nauczysz się:

• znajdować równowagę między szybkością, elastycznością i zużyciem pamięci
• projektować struktury danych, które dynamicznie rosną lub maleją
• łączyć proste struktury danych, by przeprowadzać zaawansowane operacje
• znajdować i uzyskiwać dane w tabelach z haszowaniem
• przyspieszać wyszukiwanie za pomocą binarnych drzew poszukiwań
• poprawiać wydajność poszukiwań przy użyciu B-drzew

Nalej sobie kawy i wyjdź poza standardowe podejścia!

O autorze

Podziękowania

Wstęp

• Dla kogo jest ta książka?
• Bez konkretnego języka programowania
• Analogie i parzenie kawy
• Jak korzystać z tej książki?

1. Informacje w pamięci

• Zmienne
• Złożone struktury danych
• Tablice
  • Sortowanie przez wstawianie
• Łańcuchy znaków
• Dlaczego to takie ważne?

2. Wyszukiwanie binarne

• Problem
• Przeszukiwanie liniowe
• Algorytm wyszukiwania binarnego
  • Nieobecne wartości
  • Implementacja wyszukiwania binarnego
• Przystosowanie wyszukiwania binarnego
• Czas wykonywania się algorytmu
• Dlaczego to takie ważne?

3. Dynamiczne struktury danych

• Ograniczenia tablic
• Wskaźniki i referencje
• Listy
• Działania na listach
  • Wstawianie do listy
  • Usuwanie z listy
• Listy dwukierunkowe
• Tablice i listy
• Dlaczego to takie ważne?

4. Stosy i kolejki

• Stosy
  • Stosy jako tablice
  • Stosy jako listy
• Kolejki
  • Kolejki jako tablice
  • Kolejki jako listy
• Znaczenie kolejności
  • Przeszukiwanie w głąb
  • Przeszukiwanie wszerz
• Dlaczego to takie ważne?

5. Binarne drzewa poszukiwań

• Budowa binarnego drzewa poszukiwań
• Wyszukiwanie w binarnych drzewach poszukiwań
  • Wyszukiwania iteracyjne i rekurencyjne
  • Wyszukiwanie w drzewach a wyszukiwanie w posortowanych tablicach
• Wprowadzanie zmian w binarnych drzewach poszukiwań
  • Dodawanie węzłów
  • Usuwanie węzłów
• Zagrożenia związane z niewyważonymi drzewami
• Rozbudowana struktura binarnego drzewa poszukiwań
• Dlaczego to takie ważne?

6. Drzewa trie oraz przystosowywanie struktury danych

• Binarne drzewa poszukiwań z łańcuchami znaków
  • Łańcuchy znaków w drzewach
  • Koszt porównywania łańcuchów znaków
• Drzewa trie
  • Wyszukiwanie w drzewach trie
  • Dodawanie i usuwanie węzłów
• Dlaczego to takie ważne?

7. Kolejki priorytetowe i kopce

• Kolejki priorytetowe
• Kopce typu max
  • Dodawanie elementów do kopca
  • Usuwanie z kopca elementów o najwyższym priorytecie
  • Zapisywanie dodatkowych informacji
• Aktualizowanie priorytetów
• Kopce typu min
• Sortowanie przez kopcowanie
• Dlaczego to takie ważne?

8. Siatki

• Wprowadzenie do wyszukiwania najbliższego sąsiada
  • Wyszukiwanie najbliższego sąsiada za pomocą przeszukiwania liniowego
  • Wyszukiwanie danych przestrzennych
• Siatki
  • Struktura siatki
  • Budowanie siatek i wstawianie punktów
  • Usuwanie punktów
• Przeszukiwanie siatek
  • Odrzucanie pojemników
  • Przeszukiwanie liniowe pojemników
  • Wyszukiwanie zwiększające zasięg
  • Uproszczone wyszukiwanie zwiększające zasięg
• Istota rozmiaru siatki
• Więcej niż dwa wymiary
• Poza danymi przestrzennymi
• Dlaczego to takie ważne?

9. Drzewa przestrzenne

• Drzewa czwórkowe
  • Budowa jednolitych drzew czwórkowych
  • Dodawanie punktów
  • Usuwanie punktów
  • Przeszukiwanie jednolitych drzew czwórkowych
  • Kod wyszukiwania najbliższego sąsiada
• Drzewa kd
  • Struktura drzewa kd
  • Węższe ograniczenia przestrzenne
  • Tworzenie drzew kd
  • Działania na drzewach kd
• Dlaczego to takie ważne?

10. Tablice z haszowaniem

• Przechowywanie i wyszukiwanie z użyciem kluczy
• Tablice haszujące
  • Kolizje
  • Metoda łańcuchowa
  • Próbkowanie liniowe
• Funkcje skrótu
  • Obsługa kluczy nieliczbowych
  • Przykładowy przypadek użycia
• Dlaczego to takie ważne?

11. Pamięć podręczna

• Wprowadzenie do pamięci podręcznej
• Eksmisja LRU a pamięć podręczna
  • Tworzenie pamięci podręcznej typu LRU
  • Aktualizowanie znacznika ostatniego użycia
• Inne strategie eksmitowania
• Dlaczego to takie ważne?

12. B-drzewa

• Struktura B-drzewa
• Przeszukiwanie B-drzew
• Dodawanie kluczy
  • Algorytm wstawiający
  • Przykłady dodawania kluczy
• Usuwanie klucza
  • Naprawa niedostatecznie wypełnionych węzłów
  • Szukanie klucza o najmniejszej wartości
  • Algorytm usuwania
  • Przykłady usuwania kluczy
• Dlaczego to takie ważne?

13. Filtry Blooma

• Wprowadzenie do filtrów Blooma
  • Tablice haszujące ze wskaźnikami
  • Filtr Blooma
  • Kod dla filtru Blooma
• Dobieranie parametrów filtru Blooma
• Filtry Blooma a tabele z haszowaniem
• Dlaczego to takie ważne?

14. Listy z przeskokami

• Deterministyczne a losowe struktury danych
• Wprowadzenie do listy z przeskokami
  • Przeszukiwanie list z przeskokami
  • Dodawanie węzłów
  • Usuwanie węzłów
• Czas działania
• Dlaczego to takie ważne?

15. Grafy

• Wprowadzenie do grafów
  • Reprezentacja grafów
  • Przeszukiwanie grafów
• Szukanie najkrótszej ścieżki za pomocą algorytmu Dijkstry
• Szukanie minimalnych drzew rozpinających za pomocą algorytmu Prima
• Sortowanie topologiczne za pomocą algorytmu Kahna
• Dlaczego to takie ważne?

Zakończenie

• Jaki wpływ ma struktura danych?
• Czy potrzebujemy dynamicznych struktur danych?
• Jaki jest koszt amortyzacji?
• Jak możemy przystosować strukturę danych do określonego problemu?
• Jaki jest związek między pamięcią a czasem działania?
• Jak możemy ulepszyć naszą strukturę danych?
• Jak losowość wpływa na spodziewane działanie?
• Dlaczego to takie ważne?