Podstawy programowania strukturalnego w języku C++

Książka "Podstawy programowania strukturalnego w języku C++" jest przeznaczona do początkowej nauki programowania w języku algorytmicznym wysokiego poziomu na przykładach pisanych w języku C++. Poszczególne rozdziały książki systematycznie omawiają elementy języka i programów oraz podstawowe algorytmy i metody algorytmiczne. Pokazano ich zastosowanie do budowy programów sekwencyjnych, rozgałęzionych, powtarzających obliczenia, z zadaniami programu rozdzielonymi między funkcjami, a także moduły. Książka omawia typy standardowe oraz definiowane przez programistę zmienne proste i wskaźniki oraz statyczne struktury danych, takie jak: tablice, rekordy, tablice rekordów, pliki binarne i pliki tekstowe. Przedstawia też dynamiczne struktury danych, tj. tablice dynamiczne, dynamiczne tablice wskaźników, listy jednokierunkowe, dwukierunkowe i cykliczne, struktury danych wykorzystujące listy, np.: stosy, kolejki, listy wskaźników, listy list, a także drzewa binarne i drzewa AVL. Wiele uwagi poświęca się algorytmom obsługi struktur danych, ilustrując je licznymi przykładami programów. Oprócz części teoretycznej, każdy rozdział zawiera ćwiczenie, prezentujące gotowe programy, na których przeprowadza się pewne eksperymenty, mające na celu lepsze poznanie i utrwalenie elementów języka i algorytmów omawianych w danym rozdziale. Przykłady programów stanowią też pewien wzór do naśladowania podczas opracowywania przez Czytelnika własnych programów do zadań przewidzianych do samodzielnego rozwiązywania. Wszystkie programy omawiane w książce są dostarczone na nośniku w różnych wersjach środowiskowych dla Borlanda Builder6.0, Visual C++6.0, Visual Studio.Net. W programach używa się strumieniowego wejścia - wyjścia oraz tych elementów języka C++, które ułatwiają programowanie, tj. stałych definiowanych, referencji, operatorów new i delete, typu wskaźnikowego, prototypów funkcji. Przestudiowanie książki wraz z opracowaniem zbioru własnych programów będzie stanowić dla Czytelnika dobrą podstawą do dalszej nauki programowania obiektowego w języku C++

Spis treści

Wstęp
Uwagi o wyróżnieniach w tekście

Rozdział 1. Program sekwencyjny
Pojęcia podstawowe
Cechy algorytmów
Cechy obiektów
Działania
Charakterystyka języka C++
Zasady kompilacji
Elementy języka C++
Typy standardowe
Struktura programu
Deklaracje i definicje stałych
Definicje i deklaracje zmiennych
Instrukcje
Podprogramy
Nadawanie wartości zmiennym
Wyrażenia
Nadawanie wartości zmiennym przez program, instrukcja przypisania
Nadawanie wartości zmiennym przez użytkownika
Wyprowadzanie informacji i danych z programu do użytkownika
Wyprowadzanie komunikatów
Wyprowadzanie wyników
Wyprowadzanie ostrzeżeń i komunikatów o błędach
Struktura programu sekwencyjnego
Uwagi o zasadach i stylu programowania
Pytania kontrolne
Ćwiczenie 1. Edycja, kompilacja i uruchomienie programu sekwencyjnego
Wprowadzanie i wyświetlanie liczb całkowitych - plik wewyint.cpp
Wprowadzanie i wyświetlanie liczb rzeczywistych - plik wewyreal.cpp
Wprowadzanie i wyświetlanie napisów i znaków - wewystr.cpp
Zadania
Zasady przeliczania miar

Rozdział 2. Typy danych. Program z rozgałęzieniami
Typy standardowe i wyrażenie
Operatory i wyrażenia
Operatory arytmetyczne
Operatory przypisania
Operatory relacji
Typy całkowite
Typy rzeczywiste
Typ znakowy
Wprowadzanie znaków
Wyświetlanie znaków
Napisy
Wprowadzanie napisów
Wyświetlanie napisów
Schematy blokowe
Organizacja rozgałęzień w programach
Instrukcja złożona
Instrukcje warunkowe
Przykład programu rozgałęzionego
Konstrukcja if else if
Instrukcja wyboru
Instrukcja skoku goto
Typy definiowane
Typ wyliczeniowy
Uwagi o zasadach i stylu programowania
Pytania kontrolne
Ćwiczenie 2. Programy z rozgałęzieniami
Użycie instrukcji warunkowych z warunkami prostymi - plik jezyki.cpp
Program z zagnieżdżonymi instrukcjami warunkowymi z wyrażeniami relacyjnymi - plik jezyki1.cpp
Program z zagnieżdżonymi instrukcjami warunkowymi badającymi wartość zmiennej - plik jezyki2.cpp
Program z warunkami złożonymi - plik jezyki3.cpp
Program z warunkami prostymi i złożonymi - plik warunki.cpp
Program z rozgałęzieniem na większą liczbę dróg - plik wybor.cpp
Zadania

Rozdział 3. Program z powtórzeniami
Podstawowe operacje wykonywane w pętli
Typy pętli
Pętle o znanej liczbie powtórzeń - instrukcja for
Składnia instrukcji for
Ustalanie liczby powtórzeń
Użycie stałej jawnej
Użycie stałej zdefiniowanej
Pętla z badaniem warunku na początku - instrukcja while
Pętla z badaniem warunku na końcu - instrukcja do while
Pętle z określoną liczbą powtórzeń i warunkiem wcześniejszego zakończenia
Pętle nieskończone
Przykład programu stosującego algorytm obliczania sumy
Pętle w pętli
Uwagi o zasadach i stylu programowania
Pytania kontrolne
Ćwiczenie 3. Organizacja pętli - instrukcje iteracyjne
Pętle o określonej liczbie powtórzeń
Pętle o nieokreślonej liczbie powtórzeń - badanie warunku powtarzania na początku pętli - plik petlawhi.cpp
Pętle o nieokreślonej liczbie powtórzeń - badanie warunku powtarzania na końcu pętli - plik petlarep.cpp
Zadania

Rozdział 4. Proces wytwarzania programu
Cykl życia programu
Projektowanie programu
Rodzaje konstrukcji programowych wykorzystywanych przy konstrukcji algorytmów i ich implementacja*
Algorytm strukturalny*
Testowanie i uruchamianie programu
Zasady testowania
Udogodnienia programu uruchamiającego systemów BC, BB i VC
Dokumentowanie programów
Rodzaje dokumentacji
Zawartość dokumentacji programów studenckich
Znaczenie i rodzaje komentarzy w programie
Uwagi o zasadach i stylu programowania
Pytania kontrolne
Ćwiczenie 4. Instrukcje warunkowe i instrukcje iteracyjne
Pętle zagnieżdżone - pętla for w pętli for
Pętle zagnieżdżone - pętla while w pętli for - plik kwesta.cpp
Pętle zagnieżdżone - pętla do while w pętli for - plik daty.cpp
Zadania

Rozdział 5. Podprogramy - funkcje
Przeznaczenie i efekty stosowania
Definicja podprogramu
Definicja funkcji
Rodzaje komunikacji funkcji z programem
Funkcje bezparametrowe, niezwracające wartości
Funkcje z parametrami wejściowymi, niezwracające wartości
Funkcje z parametrami wejściowymi, zwracające wartość
Funkcje z parametrami wejściowymi i wyjściowymi, niezwracające wartości
Funkcje bez parametrów wejściowych zwracające kilka wyników
Funkcje z parametrami wejściowymi i wyjściowymi, zwracające wartość
Przekazywanie parametrów do podprogramu
Przekazywanie parametru przez wartość
Przekazywanie parametru przez stałą
Przekazywanie parametru przez referencję
Treść podprogramu
Wywoływanie funkcji
Struktura programu z funkcjami
Zakres widzialności zmiennych programu
Funkcje inline*
Przeciążanie funkcji i parametry domyślne*
Przeciążanie operatorów *
Logiczny podział programu na podprogramy - metody projektowania programów
Diagramy do przedstawiania struktur danych i struktury programu*
Przeznaczenie i charakterystyka ogólna*
Formy diagramów struktury programu*
Przykłady diagramów struktury i przepływu sterowania*
Funkcje rekurencyjne*
Rekurencja pośrednia*
Rekurencja właściwa*
Przykłady funkcji rekurencyjnych*
Zastosowania rekurencji**
Uwagi o zasadach i stylu programowania
Pytania kontrolne
Ćwiczenie 5. Funkcje
Funkcja bez parametrów zwracająca wartość - plik klawisz.cpp
Funkcja z parametrem przekazywanym przez wartość, zwracająca obliczonąwartość - obliczanie wzorów iteracyjnych - plik pierwkw.cpp
Funkcja z parametrem przekazywanym przez wartość, zwracająca obliczony wynik - obliczanie sum szeregów - plik funkcje.cpp
Funkcja z parametrami przekazywanymi przez referencje - plik data.cpp
Zadania

Rozdział 6. Tablice - dostęp indeksowy
Ogólna charakterystyka
Definicje i deklaracje tablic
Odwołanie do elementu tablicy
Inicjowanie tablicy
Nadawanie wartości elementom tablicy
Nadawanie wartości początkowej elementom tablicy przez przypisanie
Nadanie wartości elementom tablicy przez wczytanie danych wprowadzanych z klawiatury
Wyprowadzanie elementów tablicy
Wyprowadzenie elementów tablicy jednowymiarowej
Wyprowadzenie elementów tablicy dwuwymiarowej
Wyszukiwanie w tablicy elementu spełniającego określony warunek
Wyszukiwanie liniowe z pętlą do while
Wyszukiwanie z wartownikiem z pętlą do while
Wyszukiwanie liniowe z pętlą while - algorytm klasyczny
Wyszukiwanie z wartownikiem z pętlą while
Wyszukiwanie liniowe z pętlą for
Wyszukiwanie w tablicach wielowymiarowych
Wybór elementów tablicy spełniających określony warunek
Wyznaczanie wartości maksymalnej w tablicy
Operacje na wierszach i kolumnach tablicy dwuwymiarowej
Sumy w wierszach
Zliczanie w kolumnach tablicy dwuwymiarowej
Inne algorytmy wykonujące operacje na tablicach lub wykorzystujące tablice
Sortowanie tablicy jednowymiarowej przez wybieranie
Sortowanie bąbelkowe
Sortowanie szybkie Quick Sort*
Scalanie tablic
Sito Eratostenesa*
Generator liczb pseudolosowych o rozkładzie nierównomiernym z przedziału 1-m
Uwagi o zasadach i stylu programowania
Pytania kontrolne
Ćwiczenie 6. Tablice jedno- i dwuwymiarowe
Operacje na tablicy jednowymiarowej - plik tablind.cpp
Algorytm szybkiego wyszukiwania wartości minimalnej i maksymalnej w tablicy - plik minmaks.cpp Rekurencyjny algorytm szybkiego wyszukiwania wartości minimalnej i maksymalnej w tablicy* - plik minmaksr.cpp
Operacje na tablicy dwuwymiarowej - plik tab2ind.cpp
Zadania

Rozdział 7. Wskaźniki
Charakterystyka ogólna
Wskaźnik do wskaźnika
Przekazywanie parametru funkcji przez wskaźnik
Przekazywanie wskaźników
Operacje na wskaźnikach i zmiennych wskazywanych
Przypisanie wskaźnikowi adresu innej zmiennej
Przypisanie wskaźników
Przypisanie zmiennych wskazywanych
Przesuwanie wskaźnika
Porównanie wskaźników
Wskaźniki do stałych i wskaźniki stałe*
Wskaźnik nieokreślonego typu
Dostęp wskaźnikowy do elementów tablic. Arytmetyka wskaźników
Tablice jednowymiarowe
Tablice dwuwymiarowe
Uwagi o zasadach i stylu programowania
Pytania kontrolne
Ćwiczenie 7. Wskaźniki
Operacje na wskaźnikach - plik wskliczb.cpp
Wskaźnikowy dostęp do elementów tablic jednowymiarowych - plik tablwsk.cpp
Wskaźnikowy dostęp do elementów tablic dwuwymiarowych - plik tab2wsk.cpp
Zadania

Rozdział 8. Napisy - łańcuchy znaków
Deklaracje, wprowadzanie, wypełnianie i wyświetlanie napisów
Deklarowanie i inicjowanie stałych i zmiennych napisowych oraz wskaźników na napisy
Wprowadzanie i wyprowadzanie napisów
Funkcje działające na napisach - moduł string
Odczytanie długości napisu - funkcja strlen
Kopiowanie napisów - funkcje: strcpy, strncpy, strdup
Łączenie (konkatenacja) napisów - funkcje: strcat, strncat
Porównywanie napisów - funkcje: strcmp, stricmp, strncmp
Przeszukiwanie napisów - funkcje: strstr, strchr, strrchr
Wypełnianie napisów
Konwersje napisów
Przykłady użycia standardowych funkcji działających na napisach
Funkcje działające na znakach
Przykłady funkcji i programów działających na napisach
Usuwanie spacji początkowych
Funkcje wstawiania, usuwania i zamiany
Zamiana daty w postaci trzech liczb na napis w formacie odpowiednim do porównywania dat
Wieże Hanoi*
Tablice napisów
Uwagi o zasadach i stylu programowania
Pytania kontrolne
Ćwiczenie 8. Napisy
Operacje na wskaźnikach - plik wsknapis.cpp
Sprawdzanie poprawności napisu - plik sprawdz.cpp
Operacje na nieuporządkowanej tablicy napisów - plik tabnapis.cpp
Zadania

Rozdział 9. Rekordy i tablice rekordów
Przeznaczenie
Diagramy do przedstawiania struktur danych*
Deklaracje zmiennych
Operacje na składowych struktury i strukturach
Inicjowanie struktury
Selektor pola - selektor składowej struktury
Przypisywanie wartości polom i odczyt pól
Przypisywanie całych struktur
Przekazywanie struktury do i z funkcji: wczytywanie, wyświetlanie i aktualizacja struktury
Przekazanie struktury do funkcji przez referencję
Przekazanie struktury do funkcji przez wskaźnik
Przekazanie struktury do funkcji przez wartość
Przekazanie struktury do programu przez wartość zwracaną
Odwołania do pól struktury przekazanej przez wskaźnik
Operacje dotyczące pojedynczego rekordu
Importowanie modułów i deklaracje globalne
Zdefiniowane funkcje
Program główny
Pola bitowe*
Unie*
Gromadzenie rekordów w tablicach
Deklaracje
Odwołania do elementów tablicy i ich pól
Operacje wykonywane na tablicy rekordów
Organizacja kartoteki danych
Przetwarzanie kartoteki zorganizowanej w tablicy rekordów
Uwagi o zasadach i stylu programowania
Pytania kontrolne
Ćwiczenie 9. Rekordy i tablice rekordów
Operacje wykonywane na jednym rekordzie - plik rekord.cpp
Zakładanie kartoteki w tablicy rekordów i wyświetlanie jej zawartości - plik tabreka.cpp
Przetwarzanie tablicy rekordów - plik tabrekb.cpp
Przykłady obiektów rzeczywistych i ich cech

Rozdział 10. Komunikacja użytkownika z programem. Podział programu na moduły
Komunikacja użytkownika z programem
Tryby pracy programu
Rodzaje programów
Sterowanie pracą programów
Konstruowanie i prezentacja oferty programu*
Sterowanie wprowadzaniem danych przez użytkownika
Sterowanie wyprowadzaniem danych przez program
Podział programu na moduły
Przeznaczenie modułu
Budowa i użycie modułu
Przykład programu wykorzystującego funkcje z modułu własnego
Zasady modularyzacji
Biblioteka własnych funkcji użytkownika
Uwagi o zasadach i stylu programowania
Pytania kontrolne
Ćwiczenie 10. Fizyczny podział programu na moduły
Moduły programu

Rozdział 11. Pliki
Ogólna charakterystyka i przeznaczenie
Cechy plików
Sposoby obsługi plików w języku C++
Sposoby przechowywania danych
Sposoby dostępu do danych pliku
Rodzaje operacji
Dobór cech pliku do przeznaczenia pliku
Zmienne plikowe
Operacje na plikach logicznych
Operacje niskopoziomowe*
Operacje na strumieniach
Otwarcie pliku
Zamknięcie pliku
Zapis do pliku
Odczyt z pliku
Obsługa błędów*
Operacje dotyczące wskaźnika pliku
Obsługa buforów strumienia*
Operacje na plikach fizycznych
Utrwalanie danych ź tablic
Składowanie tablicy rekordów w pliku binarnym
Odtwarzanie struktury danych typu tablica rekordów na podstawie pliku
Algorytmy przetwarzania plików
Zapis elementów do pliku
Algorytm przetwarzania danych z pliku
Algorytm wybierania elementów pliku o nieunikatowej wartości pola
Algorytm wyszukiwania elementu pliku według unikatowego pola
Algorytm aktualizacji elementu w pliku
Algorytm usunięcia elementu z pliku nieuporządkowanego
Usunięcie elementu z pliku uporządkowanego
Algorytm aktualizacji grupowej - przetwarzanie pliku źródłowego w plik wynikowy o tej samej nazwie
Funkcje dotyczące katalogów i plików dyskowych
Funkcje zarządzania katalogami*
Funkcje dotyczące plików dyskowych*
Zaawansowane operacje na wskaźnikach
Zastosowanie przekazywania do funkcji wskaźnika na wskaźnik
Wskaźnik na funkcję
Przekazywanie wskaźnika na funkcję przez parametr
Uwagi o zasadach i stylu programowania
Pytania kontrolne
Ćwiczenie 11. Pliki binarne
Składowanie i odtwarzanie tablicy
Zakładania kartoteki w pliku i wyświetlanie danych z kartoteki
Przetwarzanie pliku rekordów
Wyszukiwanie w pliku rekordów rekordu o unikatowej wartości pola
Usuwanie znalezionego rekordu z pliku
Zadania

Rozdział 12. Pliki tekstowe
Ogólna charakterystyka i przeznaczenie
Operacje wykonywane na plikach tekstowych
Schematy przetwarzania pliku tekstowego
Zapisywanie pojedynczych znaków
Zapisywanie wierszy
Odczytywanie pojedynczych znaków
Odczytywanie wierszy
Czytanie danych z pliku według formatu
Zapis danych do pliku według formatu
Tworzenie wykazu w postaci tabeli
Tworzenie raportu w postaci tabeli
Generowanie dokumentu korespondencji seryjnej
Komunikacja programu z drukarką*
Wysyłanie pliku źródłowego do drukarki blokami znaków*
Kopiowanie pliku tekstowego na drukarkę blokami*
Inne uwagi*
Bezpośredni dostęp do znaków pliku tekstowego*
Uwagi dotyczące zasad i stylu programowania
Pytania kontrolne
Ćwiczenie 12. Pliki binarne i tekstowe
Kopiowanie plików binarnych
Tworzenie wykazu z danymi z pliku rekordów w pliku tekstowym
Wpisywanie raportu do pliku tekstowego
Generowanie dokumentu korespondencji seryjnej w pliku tekstowym
Zadania

Rozdział 13. Zmienne dynamiczne - tablice dynamiczne i listy
Przydzielanie i zwalnianie pamięci dla zmiennych dynamicznych
Tablice w języku C++
Tablice liczb
Tablice napisów
Inne funkcje operujące na blokach pamięci*
Grupowanie zmiennych dynamicznych w listach - organizacja list
Charakterystyka ogólna
Zasady organizacji struktur listowych
Tworzenie dynamicznych struktur danych
Operacje na liście jednokierunkowej
Deklaracje dla listy
Moduł listy jednokierunkowej
Dołączenie elementu na początku listy
Dołączenie elementu na końcu listy
Dołączenie elementu po elemencie o znanym adresie
Dołączenie elementu przy zachowaniu uporządkowania listy
Przeglądanie listy
Wyszukiwanie w liście
Wybieranie elementów spełniających określony warunek
Zliczanie liczby elementów listy
Usuwanie elementów z listy
Odwracanie kolejności elementów w liście*
Zwolnienie elementów listy
Odtworzenie listy na podstawie pliku
Operacje na liście dwukierunkowej
Struktura elementu listy
Moduł listy dwukierunkowej
Dołączenie elementu na początku listy
Dołączenie elementu na końcu listy*
Dołączenie elementu po elemencie o znanym adresie
Dołączenie elementu przed elementem o znanym adresie
Dołączenie elementu do listy uporządkowanej
Przeglądanie listy
Wyszukiwanie w liście
Usuwanie elementów z listy dwukierunkowej
Zwolnienie elementów listy
Odtworzenie listy według pliku
Listy z głową i listy cykliczne
Zasady organizacji jednokierunkowej listy z głową
Zasady organizacji jednokierunkowej listy cyklicznej z głową
Zasady organizacji dwukierunkowej listy cyklicznej z głową
Moduł programu, moduł uniwersalny
Moduł standardowy z funkcjami do obsługi listy
Moduł uniwersalny*
Moduł listy szablonowej
Rekurencyjne funkcje na liście jednokierunkowej*
Dołączenie elementu na końcu listy
Dołączenie do listy uporządkowanej*
Wyświetlanie listy w odwrotnym porządku*
Długość listy*
Sortowanie listy**
Uwagi o zasadach i stylu programowania
Pytania kontrolne
Ćwiczenie 13.Listy
Program wykorzystujący moduł listy jednokierunkowej -1ab13\listalk
Program wykorzystujący moduł listy dwukierunkowej 1ab13\listalk
Program wykorzystujący moduł listy dwukierunkowej, cyklicznej z głową 1ab13/listac
Utworzenie listy wybranych rekordów z pliku*
Zadania
Przykłady aplikacji

Rozdział 14. Dynamiczne struktury danych - listy i tablice
Abstrakcyjny typ danych
Stos
Charakterystyka ogólna
Implementacja stosu przez strukturę statyczną
Implementacja stosu przez strukturę dynamiczną
Kolejka
Charakterystyka ogólna
Kolejka zwykła
Kolejka priorytetowa
Implementacja kolejki w postaci listy odsyłaczy
Grupa uporządkowana
Deklaracje dla grupy uporządkowanej
Funkcje obsługi grupy uporządkowanej
Złożone struktury dynamiczne bazujące na listach
Listy łączone i listy niezależne*
Lista list
Kolekcja*
Deklaracje
Funkcje obsługujące kolekcję
Wektor rzadki i macierz rzadka**
Deklaracje dla wektora i macierzy rzadkich
Funkcje obsługi struktury danych typu Macierz Rzadka
Inne struktury danych organizowane na podstawie list
Listy samoorganizujące się**
Listy topologiczne**
Lista indeksów do pliku
Uwagi o zasadach i stylu programowania
Pytania kontrolne
Ćwiczenie 14. Struktury danych wykorzystujące dynamiczny przydział pamięci
Dynamiczna tablica danych - kolekcja.cpp
Dynamiczna tablica wskaźników
Tablica wskaźników do rekordów
Program wykorzystujący moduł jednokierunkowej listy odsyłaczy
Implementacja kolejki dwustronnej
Zadania

Rozdział 15. Drzewa
Cechy drzew
Implementacja drzewa w postaci struktur: statycznej i dynamicznej
Drzewo dokładnie wyważone
Binarne drzewa poszukiwań - drzewa BST
Dołączanie węzła do drzewa
Wyszukiwanie w drzewie binarnym
Przeglądanie drzewa
Usuwanie węzła z drzewa
Drzewa wyważone AVL*
Drzewo wielokierunkowe*
Uwagi dotyczące zasad i stylu programowania
Pytania kontrolne
Ćwiczenie 15. Drzewa binarne
Program wykorzystujący moduł drzewa binarnego
Drzewo wyważone AVL*
Zadania

Dodatek A. Instrukcje wejścia-wyjścia języka C

Dodatek B. Obiektowe wejście-wyjście

Dodatek C. Przykład dokumentacji programu
Opis przeznaczenia i operacji programu
Dane techniczne programu
Struktury danych programu
Struktura programu
Opis funkcji programu
Zasady współpracy z użytkownikiem
Opis możliwości rozbudowy lub optymalizacji programu

Literatura

Indeks