C++. Struktury danych i algorytmy - Helion

Autor: Wisnu Anggoro
Tytuł oryginału: C++ Data Structures and Algorithms
Tłumaczenie: Maksymilian Gutowski
ISBN: 978-83-283-5185-1
stron: 303, Format: 168x237, okładka: miękka
Data wydania: 2019-01-01
Księgarnia: Helion

Cena książki: 34,20 zł (poprzednio: 57,00 zł)
Oszczędzasz: 40% (-22,80 zł)

Tagi: C++ - Programowanie

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!

Spis treści

C++. Struktury danych i algorytmy -- spis treści

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
  - std::vector
  - std::list
- 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