C++. Struktury danych i algorytmy - ebook

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!

• 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