C++ to dojrzały język programowania o wielu różnych zastosowaniach. Inżynier oprogramowania, który chce w pełni skorzystać z jego zalet, powinien płynnie posługiwać się dostępnymi w tym języku strukturami danych i algorytmami. W ten sposób łatwiej można rozwiązywać konkretne problemy. Zastosowanie odpowiedniej struktury danych oraz algorytmu jest również ważne z punktu widzenia wydajności działania kodu, co bezpośrednio przekłada się na szybkość pracy aplikacji. Bez dogłębnego zrozumienia tych zagadnień bardzo trudno nauczyć się biegle programować w C++.
Dzięki tej książce dowiesz się, na czym polega implementacja klasycznych struktur danych i algorytmów w C++. Znajdziesz tu również przystępne wprowadzenie do podstawowych konstrukcji językowych oraz do korzystania z zintegrowanego środowiska programistycznego (IDE). Ponadto dowiesz się, w jaki sposób przechowywać dane za pomocą list wiązanych, tablic, stosów i kolejek, a także jak zaimplementować algorytmy sortowania, takie jak sortowanie szybkie i sortowanie przez kopcowanie, oraz algorytmy wyszukiwania, takie jak wyszukiwanie liniowe czy binarne. Kolejnym ważnym zagadnieniem ujętym w książce jest wysoka wydajność algorytmów operujących na ciągach znakowych i strukturach mieszających, jak również analiza algorytmów siłowych, zachłannych i wielu innych.
Najciekawsze zagadnienia ujęte w książce:
- podstawy C++, w tym kontrola przepływu kodu i abstrakcyjne typy danych
- listy, listy wiązane, stosy i kolejki
- algorytmy sortowania, w tym bąbelkowe, przez selekcję, wstawianie, scalanie
- tworzenie hierarchicznej struktury drzewa
- praktyczne aspekty implementacji algorytmów
C++. O jakości kodu decyduje algorytm i odpowiednia struktura danych!
Rozdziały:
- O autorze
- O recenzencie
- Wstęp
- Dla kogo jest ta książka?
- Zakres tematyczny książki
- Jak korzystać z tej książki?
- Przykłady kodu do pobrania
- Kolorowe wersje rysunków
- Konwencje
- 1. Struktury danych i algorytmy w C++
- Wymagania techniczne
- Podstawy C++
- Pierwszy kod w C++
- Usprawnianie pracy nad kodem przy użyciu IDE
- Definiowanie zmiennych przy użyciu podstawowych typów danych
- Sterowanie przepływem kodu
- Instrukcja warunkowa
- Pętle
- Wykorzystanie zmiennych za pośrednictwem zaawansowanych typów danych
- Tworzenie abstrakcyjnych typów danych
- Wykorzystanie klas C++ przy tworzeniu ADT zdefiniowanych przez użytkownika
- Posługiwanie się szablonami
- Szablony funkcji
- Szablony klas
- Biblioteka standardowych szablonów
- Analiza algorytmów
- Analiza asymptotyczna
- Najgorsze, średnie i najlepsze przypadki
- Notacja , O i
- Metoda rekurencyjna
- Analiza kosztu zamortyzowanego
- Podsumowanie
- Pytania
- Dodatkowe materiały
- 2. Przechowywanie danych w listach i listach wiązanych
- Wymagania techniczne
- Tablice
- Tworzenie ADT listy
- Zwracanie elementu z listy
- Wstawianie elementu do listy
- Wyszukiwanie indeksu wybranego elementu w liście
- Usuwanie elementu z listy
- Implementacja listy
- Wprowadzenie do węzłów
- Tworzenie ADT listy jednokierunkowej
- Zwracanie elementu z listy wiązanej
- Wstawianie elementu do listy wiązanej
- Wyszukiwanie indeksu wybranego elementu w liście wiązanej
- Usuwanie elementu z listy wiązanej
- Implementacja listy wiązanej
- Tworzenie ADT listy dwukierunkowej
- Refaktoryzacja typu danych Node
- Refaktoryzacja kilku operacji LinkedList
- Usuwanie elementu
- Wstawianie elementu
- Implementacja ADT listy dwukierunkowej
- Wykorzystanie typów List i LinkedList przy użyciu STL
- Podsumowanie
- Pytania
- Dodatkowe materiały
- 3. Tworzenie stosów i kolejek
- Wymagania techniczne
- Tworzenie ADT stosu
- Pobieranie wartości elementu z ADT stosu
- Umieszczanie elementów na ADT stosu
- Usuwanie elementów z ADT stosu
- Implementacja ADT stosu
- Inny przykład implementacji ADT stosu
- Tworzenie ADT kolejki jednokierunkowej
- Pobieranie wartości elementu z ADT kolejki
- Wstawianie elementu do ADT kolejki
- Usuwanie elementu z ADT kolejki
- Implementacja ADT kolejki
- Tworzenie ADT kolejki dwukierunkowej
- Pobieranie wartości elementu z ADT kolejki dwukierunkowej
- Dodawanie elementu do ADT kolejki dwukierunkowej
- Usuwanie elementu z ADT kolejki dwukierunkowej
- Implementacja ADT kolejki dwukierunkowej
- Podsumowanie
- Pytania
- Dodatkowe materiały
- 4. Porządkowanie elementów przy użyciu algorytmów sortowania
- Wymagania techniczne
- Sortowanie bąbelkowe
- Sortowanie przez wybieranie
- Sortowanie przez wstawianie
- Sortowanie przez scalanie
- Sortowanie szybkie
- Sortowanie przez zliczanie
- Sortowanie pozycyjne
- Podsumowanie
- Pytania
- Dodatkowe materiały
- 5. Wyszukiwanie elementów przy użyciu algorytmów wyszukiwania
- Wymagania techniczne
- Wyszukiwanie liniowe
- Opracowanie algorytmu wyszukiwania liniowego
- Implementacja algorytmu wyszukiwania liniowego
- Wyszukiwanie binarne
- Opracowanie algorytmu wyszukiwania binarnego
- Implementacja algorytmu wyszukiwania binarnego
- Wyszukiwanie ternarne
- Opracowanie algorytmu wyszukiwania ternarnego
- Zastosowanie algorytmu wyszukiwania ternarnego
- Wyszukiwanie interpolacyjne
- Opracowanie algorytmu wyszukiwania interpolacyjnego
- Zastosowanie algorytmu wyszukiwania interpolacyjnego
- Wyszukiwanie skokowe
- Opracowanie algorytmu wyszukiwania skokowego
- Zastosowanie algorytmu wyszukiwania skokowego
- Wyszukiwanie wykładnicze
- Opracowanie algorytmu wyszukiwania wykładniczego
- Wywołanie funkcji ExponentialSearch()
- Wyszukiwanie podlisty
- Opracowanie algorytmu wyszukiwania podlisty
- Wykorzystanie algorytmu wyszukiwania podlisty
- Podsumowanie
- Pytania
- Dodatkowe materiały
- 6
- Używanie znakowego typu danych
- Wymagania techniczne
- Ciąg znakowy C++
- Tworzenie ciągu znaków przy użyciu tablicy znaków
- Dodatkowe funkcje std::string
- Zabawa słowami
- Tworzenie anagramów
- Wykrywanie palindromów
- Tworzenie ciągu z cyfr binarnych
- Konwertowanie liczb dziesiętnych na binarne
- Konwertowanie ciągu binarnego na dziesiętny
- Ciąg podsekwencji
- Generowanie podsekwencji z ciągu
- Sprawdzanie, czy ciąg jest podsekwencją innego ciągu
- Wyszukiwanie wzorca
- Podsumowanie
- Pytania
- Dodatkowe materiały
- 7. Tworzenie hierarchicznej struktury drzewa
- Wymagania techniczne
- Tworzenie ADT drzewa binarnego
- Tworzenie ADT binarnego drzewa poszukiwań
- Wstawianie nowego klucza do BST
- Przechodzenie po BST po kolei
- Sprawdzanie obecności klucza w BST
- Zwracanie minimalnych i maksymalnych wartości kluczy
- Wyszukiwanie następnika klucza w BST
- Wyszukiwanie poprzednika klucza w BST
- Usuwanie węzła według podanego klucza
- Implementacja ADT BST
- Tworzenie ADT zrównoważonego BST (AVL)
- Rotacja węzłów
- Wstawianie nowego klucza
- Usuwanie wskazanego klucza
- Implementacja ADT AVL
- Tworzenie ADT kopca binarnego
- Sprawdzanie, czy kopiec jest pusty
- Wstawianie nowego elementu do kopca
- Pobieranie elementu o największej wartości
- Usuwanie elementu o największej wartości
- Implementacja stosu binarnego jako kolejki priorytetowej
- Podsumowanie
- Pytania
- Dodatkowe materiały
- 8. Zestawianie wartości z kluczem w tablicy mieszającej
- Wymagania techniczne
- Wprowadzenie do tablic mieszających
- Dużo danych w małych komórkach
- Przechowywanie danych w tablicy mieszającej
- Obsługa kolizji
- Implementacja metody łańcuchowej
- Generowanie klucza mieszającego
- Opracowanie operacji Insert()
- Opracowanie operacji Search()
- Opracowanie operacji Remove()
- Opracowanie operacji IsEmpty()
- Zastosowanie ADT HashTable wykorzystującego metodę łańcuchową
- Implementacja techniki adresowania otwartego
- Opracowanie operacji Insert()
- Opracowanie operacji Search()
- Opracowanie operacji Remove()
- Opracowanie operacji IsEmpty()
- Opracowanie operacji PrintHashTable()
- Wdrożenie ADT HashTable wykorzystującego technikę szukania liniowego
- Podsumowanie
- Pytania
- Dodatkowe materiały
- 9. Implementacja algorytmów w praktyce
- Wymagania techniczne
- Algorytmy zachłanne
- Rozwiązanie problemu wydawania reszty
- Zastosowanie kodowania Huffmana
- Algorytmy dziel i zwyciężaj
- Rozwiązywanie problemów selekcyjnych
- Mnożenie macierzy
- Programowanie dynamiczne
- Ciąg Fibonacciego
- Programowanie dynamiczne i problem wydawania reszty
- Algorytmy siłowe
- Wyszukiwanie i sortowanie siłowe
- Wady i zalety algorytmów siłowych
- Algorytmy zrandomizowane
- Klasyfikacja algorytmów zrandomizowanych
- Generatory liczb losowych
- Zastosowania algorytmów zrandomizowanych
- Algorytmy z nawrotami
- Meblowanie nowego mieszkania
- Kółko i krzyżyk
- Podsumowanie
- Pytania
- Dodatkowe materiały
