STRUKTURY DANYCH Z PRZYMRUŻENIEM OKA

Spis treści

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?