E-book details

C++. Struktury danych i algorytmy

C++. Struktury danych i algorytmy

Wisnu Anggoro

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
  • Title: C++. Struktury danych i algorytmy
  • Author: Wisnu Anggoro
  • Original title: C++ Data Structures and Algorithms
  • Translation: Maksymilian Gutowski
  • ISBN: 978-83-283-5186-8, 9788328351868
  • Date of issue: 2019-04-09
  • Format: Ebook
  • Item ID: cppstr
  • Publisher: Helion