Projekt okładki Hubert Zacharski

Ilustracja na okładce shutterstock/polygraphus

Wydawca Łukasz Łopuszański

Redaktor prowadzący Iwona Lewandowska

Redaktor Irena Puchalska

Koordynator produkcji Anna Bączkowska

Skład wersji elektronicznej na zlecenie Wydawnictwa Naukowego PWN: Mobisfera

Zastrzeżonych nazw firm i produktów użyto w książce wyłącznie w celu identyfikacji.

Książka, którą nabyłeś, jest dziełem twórcy i wydawcy. Prosimy, abyś przestrzegał praw, jakie im przysługują. Jej zawartość możesz udostępnić nieodpłatnie osobom bliskim lub osobiście znanym. Ale nie publikuj jej w internecie. Jeśli cytujesz jej fragmenty, nie zmieniaj ich treści i koniecznie zaznacz, czyje to dzieło. A kopiując jej część, rób to jedynie na użytek osobisty.

Szanujmy cudzą własność i prawo
Więcej na www.legalnakultura.pl
Polska Izba Książki

Copyright © by Wydawnictwo Naukowe PWN SA
Warszawa 2016

eBook został przygotowany na podstawie wydania papierowego z 2016 r., (wyd. I)
Warszawa 2016

ISBN 978-83-01-19047-7

Wydawnictwo Naukowe PWN SA
02-460 Warszawa, ul. Gottlieba Daimlera 2
tel. 22 69 54 321, faks 22 69 54 288
infolinia 801 33 33 88
e-mail: pwn@pwn.com.pl
www.pwn.pl

Spis treści

1. Okładka

2. Strona tytułowa

3. Strona redakcyjna

4. Spis treści

5. Wstęp

1. Przygotowanie środowiska pracy

1. Instalacja systemu Linux

1. Pobranie OpenSUSE

2. Przygotowanie instalacji

3. Instalacja

2. Uruchamianie programów

1. Edycja kodu źródłowego

2. Przejście do trybu tekstowego

3. Skompilowanie programu

4. Uruchomienie programu

2. Polecane źródła w Internecie

6. Część I

1. Lekcja 1. Optymalizowanie funkcji

1. Elementy matematyki

2. Podstawy języka C

1. Program, instrukcja

2. Komentarze

3. Identyfikatory

4. Słowa kluczowe

5. Białe znaki

6. Podstawowe typy numeryczne

7. Zmienne i operator przypisania

8. Operatory

9. Instrukcja warunkowa

10. Instrukcje pętli

1. Pętla while

2. Pętla do while

3. Pętla for

11. Funkcje

1. Funkcje rekurencyjne

3. Rozwiązanie zadania

1. Krok 1. Pierwsze zadanie pomocnicze

2. Krok 2. Rachunki matematyczne

3. Krok 3. Drugie zadanie pomocnicze

4. Krok 4. Uogólnienie rachunków

5. Krok 5. Pierwsza wersja kodu funkcji rozwiązującej zadanie

6. Krok 6. Dodanie warunku zakończenia rekurencji

7. Krok 7. Optymalizacja liczby operacji

8. Krok 8. Optymalizacja liczby zmiennych

9. Krok 9. Usunięcie rekurencji

10. Krok 10. Sprawdzenie poprawności argumentów

4. Wnioski

5. Polecane źródła w Internecie

2. Lekcja 2. Działania na bitach

1. Sito Eratostenesa

2. Podstawy Języka C

1. Operacje na bitach

1. Operacja and

2. Operacja or

3. Operacja xor

4. Operacja not

5. Przesunięcie bitowe w lewo

6. Przesunięcie bitowe w prawo

2. Rzutowanie

3. Dyrektywy preprocesora

4. Tablice

5. Adresy zmiennych

6. Wskaźniki

7. Wskaźniki a tablice

8. Alokowanie pamięci dla tablicy

3. Rozwiązanie zadania

1. Krok 1. Podejście standardowe

2. Krok 2. Zmniejszenie liczby operacji

3. Krok 3. Oszczędność pamięci

4. Krok 4. Poprawa efektywności algorytmu

4. Wnioski

5. Polecane źródła w Internecie

3. Lekcja 3. Alokowanie pamięci

1. Podstawy informatyki

2. Podstawy języka C

1. Funkcja malloc()

2. Funkcja calloc()

3. Funkcja realloc()

4. Funkcja free()

5. Przykład zarządzania pamięcią

6. Zmienne automatyczne i statyczne

3. Rozwiązanie zadania

4. Wnioski

5. Polecane źródła w Internecie

7. Część II

1. Lekcja 4. Program główny

1. Podstawy języka C

1. Funkcja main()

2. Funkcja exit ()

3. Standardowe strumienie wejścia i wyjścia

4. Napisy

5. Konwersja napisu do liczby

2. Rozwiązanie zadania

1. Krok 1. Zadanie pomocnicze

2. Krok 2. Unikanie prostych błędów

3. Krok 3. Zastosowanie nazwy programu

4. Krok 4. Obsługa opcji

5. Krok 5. Wyświetlenie komunikatu o błędzie

6. Krok 6. Zastosowanie zmiennych środowiskowych

3. Wnioski

4. Polecane źródła w Internecie

2. Lekcja 5. Przetwarzanie opcji

1. Podstawy języka C

1. Przekazywanie argumentów funkcji

2. Instrukcja wielokrotnego wyboru: switch

2. Standardowe opcje programu

3. Rozwiązanie zadania

4. Wnioski

5. Polecane źródła w Internecie

3. Lekcja 6. Przetwarzanie parametrów wejściowych – plików

1. Podstawy języka C

1. Odczyt i zapis do pliku

2. Trójargumentowy operator warunkowy

3. Sterowanie preprocesorem

4. Prototyp funkcji

5. Atrybut extern

6. Kompilacja programu

2. Rozwiązanie zadania

1. Krok 1. Rozdzielenie kompetencji między funkcje

2. Krok 2. Rozdzielenie kompetencji między pliki

3. Krok 3. Utworzenie plików nagłówkowych

4. Krok 4. Przetwarzanie danych wejściowych

5. Krok 5. Kompilacja

3. Aneks

4. Polecane źródła w Internecie

8. Część III

1. Lekcja 7. Debugowanie programu

1. Na czym polega debugowanie

2. Podstawy języka C

1. Buforowanie

2. Wyrażenie przecinkowe

3. Funkcja char()

3. Rozwiązanie zadania

1. Krok 1. Wydruki kontrolne w kodzie programu

2. Krok 2. Zastosowanie makra

3. Krok 3. Makro ze zmienną liczbą parametrów

4. Krok 4. Debugowanie wybierane dynamicznie

5. Krok 5. Obsługa parametru wywołania +d

4. Wnioski

5. Aneks

1. Modyfikacje w funkcji set_opt()

2. Modyfikacje w funkcji main()

3. Modyfikacja wypisywania pomocy rozszerzonej

6. Polecane źródła w Internecie

2. Lekcja 8. Budowanie złożonych programów

1. Podstawy teoretyczne

1. Struktura pliku Makefile

2. Rozwiązanie zadania

1. Krok 1. Tworzenie pliku Makefile

1. Deklaracje zmiennych

2. Reguły kompilacji

2. Krok 2. Optymalizacja pliku Makefile

3. Krok 3. Realizowanie celów specjalnych

1. make clean

2. make distclean

3. make dist

4. make install

4. Krok 4. Sprawdzenie poprawności listy zależności

3. Wnioski

4. Polecane źródła w Internecie

3. Lekcja 9. Udostępnianie programu

1. Narzędzia do udostępniania programów

1. Krok 1. Skanowanie katalogu

2. Krok 2. Edytowanie pliku configure.ac

3. Krok 3. Edytowanie pliku config.h.in

4. Krok 4. Edytowanie pliku makefile.in

5. Krok 5. Wywołanie programu autoconf

6. Krok 6. Uruchomienie programu configure

7. Krok 7. Korzystanie z pliku config.h

8. Krok 8. Budowanie programu

9. Krok 9. Dystrybucja

2. Wnioski

3. Polecane źródła w Internecie

9. Część IV

1. Lekcja 10. Dynamiczne struktury danych

1. Funkcje rekurencyjne

2. Rekurencyjne struktury danych

3. Dynamiczne struktury danych

1. Listy

2. Drzewa binarne

3. Porównanie przetwarzania list i drzew

4. Realizacja dynamicznych struktur danych w języku C

1. Struktury

5. Rozwiązanie zadania

1. Reprezentacja węzła drzewa

2. Krok 1. Tworzenie drzewa

3. Krok 2. Wstawianie elementu na początek i na koniec listy

4. Krok 3. Zamiana drzewa na listę

5. Krok 4. Zamiana listy na drzewo

6. Krok 5. Wypisywanie zawartości drzewa

7. Krok 6. Wyszukiwanie informacji w drzewie

8. Krok 7. Optymalizacja wyszukiwania

9. Krok 8. Baza z wieloma kluczami

6. Wnioski

7. Polecane źródła w Internecie

2. Lekcja 11. Wyrażenia regularne

1. Automaty skończone

2. Wyrażenia regularne

1. Metaznaki

2. Rozpoznawanie wyrażeń regularnych

3. Rozwiązanie zadania

1. Krok 1. Sformułowanie zadania dla konkretnego zastosowania

2. Krok 2. Budowanie tablicy sterującej

4. Wnioski

5. Polecane źródła w Internecie

3. Lekcja 12. Interpreter poleceń

1. Gramatyki formalne

2. Narzędzia informatyczne

1. Generator parsera yacc

1. Deklaracje języka C

2. Deklaracje parsera

3. Reguły gramatyki

4. Kod dodatkowy

2. Generator leksera lex

1. Reguły leksykalne

3. Rozwiązanie zadania

1. Krok 1. Tworzenie pliku mag.y

2. Krok 2. Generowanie parsera

3. Krok 3. Tworzenie pliku mag.l

4. Krok 4. Generowanie analizatora leksykalnego

5. Krok 5. Tworzenie prostego programu głównego

6. Krok 6. Modyfikacja pliku Makefile

7. Krok 7. Wywołanie funkcji yyparse() w pętli

8. Krok 8. Sterowanie reakcjami systemu

1. Modyfikacja leksera

2. Modyfikacja funkcji main()

3. Modyfikacja parsera

9. Krok 9. Rozwijanie interpretera

10. Krok 10. Rozwiązywanie konfliktów

4. Wnioski

5. Polecane źródła w Internecie

10. Pliki towarzyszące książce

11. Skorowidz

Wstęp

Pierwsze prawo „programisty” brzmi: „U mnie działa”. Niezły programista nieco je przeformułuje: „Mój program działa wszędzie”. Dobry programista doda: „Mój program działa wszędzie i dobrze”.

Dobremu programiście nie wystarczy fakt, że program „chodzi”. Dobrze napisany program jest jak dzieło sztuki: piękny i elegancki. Podświadomość programisty zapala czerwone światełko, gdy widzi rozwiązanie nieeleganckie. Zazwyczaj później okazuje się, że w programie jest jakaś „rysa na szkle” – mały defekt, który ujawni się kiedyś zupełnie niespodziewanie.

Dobry program można łatwo odróżnić od „działającego”:

1. 1) szybciej zwraca wyniki;

2. 2) zużywa mniej pamięci;

3. 3) działa dla szerszego zakresu danych.

W tej książce chcemy nauczyć tworzenia dobrych programów. Na kilkunastu przykładach pokażemy krok po kroku, jak optymalizować programy – czynić je bardziej efektywnymi.

Język C, wynaleziony w roku 1972, do dziś nie znalazł sobie równych – wraz z językami pochodnymi, takimi jak C++, C# lub Objective-C, tworzy najbardziej popularną rodzinę języków programowania na świecie. Przykłady zawarte w tej książce są przedstawione w „czystym” języku C, ponieważ wszystko, co można w nim zapisać, bez trudu można wyrazić w językach pochodnych, co nie musi zachodzić w przeciwnym kierunku.

Programować można w językach różnego poziomu. Najniższy poziom to język „asemblerowy”, w którym kodujemy bezpośrednio rozkazy maszynowe (a nie instrukcje będące złożeniami rozkazów). C jest językiem średniego poziomu. Zawiera niektóre konstrukcje wysokiego poziomu (unie, tablice, struktury), ale jest jeszcze na tyle „blisko maszyny”, że można w nim np. zdefiniować fragmenty będące wstawkami w assemblerze. Ponadto, język C umożliwia działania na strukturach dynamicznych, których nie można definiować w tych językach wyższego poziomu, które nie zawierają zmiennych wskaźnikowych.

Z niniejszej książki dowiesz się, jak napisać funkcję, za pomocą której można wyznaczyć liczby pierwsze 56 razy większe niż przykłady podawane w standardowych kursach programowania, i to 7 razy szybciej. Nauczysz się, jak tworzyć programy, którego działanie zależy od argumentów wywołania. Dowiesz się, jak efektywnie napisać interpreter poleceń podanych w języku naturalnym oraz zrozumiesz, jak działa analizator wyrażeń regularnych.

Treść książki ułożono w ciąg lekcji, podzielonych na cztery części. Część I (lekcje 1–3) to nauka pisania funkcji, które oszczędnie i efektywnie gospodarują pamięcią operacyjną. Część II (lekcje 4–6) jest poświęcona strukturze programu głównego. W części III (lekcje 7–9) omówiono proces tworzenia programów złożonych, składających się z kilku modułów, np. napisanych przez różnych autorów. Ostatnia część (lekcje 10–12) zawiera przykłady zastosowania pozyskanych umiejętności. Pokazujemy w niej, jak w sposób przejrzysty i krótki można napisać programy wykonujące niebanalne zadania.

Każda lekcja ma na celu wyrobienie określonej umiejętności programistycznej. Cel ten realizowany jest poprzez rozwiązywanie, krok po kroku, zadania podanego na początku lekcji. Lekcję kończy podsumowanie – lista porad przydatnych każdemu programiście.

Jeśli dopiero zaczynasz przygodę z programowaniem, to ten podręcznik jest dla Ciebie – znajdziesz w nim wyjaśnienia poszczególnych elementów języka C, a już od początku swojej programistycznej edukacji nauczysz się dążyć do perfekcji.

Jeśli programujesz od wielu lat, to zajrzyj do tej książki – zapewne utwierdzisz się w przekonaniu, że potrafisz programować całkiem nieźle, ale być może przekonamy cię, że możesz jeszcze coś udoskonalić w swoim warsztacie.

Przygotowanie środowiska pracy

Aby móc wypróbować, jak działają funkcje i programy opisane w tej książce, musisz, drogi Czytelniku, przygotować odpowiednie środowisko pracy. W tym celu trzeba zainstalować jedną z wersji systemu Linux.

Istnieją dziesiątki tzw. dystrybucji (odmian) systemu Linux, a jej wybór jest sprawą w dużej mierze osobistą. Największą popularnością cieszy się obecnie dystrybucja Ubuntu oraz oparta na niej wersja Linux Mint. Dla osób rozpoczynających swoją przygodę z Linuksem rekomendujemy stosowanie dystrybucji OpenSuse. Jest ona rozwijana przez SUSE – najstarszą, wciąż działającą, organizację linuksową. Jest to według nas wersja najłatwiejsza do przyjęcia dla użytkowników systemu Windows.

Instalacja systemu Linux

Podamy tutaj kilka wskazówek, jak zainstalować dystrybucję OpenSUSE.

Pobranie OpenSUSE

Pakiet można pobrać pod adresem: //software.opensuse.org/421/en. Przed pobraniem warto przeczytać instrukcje podane na tej stronie internetowej.

Przygotowanie instalacji

Najlepszym rozwiązaniem jest nagranie („wypalenie”) płyty DVD z pobranym pakietem instalacyjnym. Alternatywnie, pakiet ten można umieścić na dysku USB (wtedy do poprawnej instalacji potrzebny jest program pomocniczy, np. ImageWriter). Użytkownikom systemu Windows polecamy dokonanie defragmentacji dysku bezpośrednio przed instalacją (w nowszych wersjach Windows defragmentacja odbywa się samoczynnie co pewien czas). Chodzi o to, aby wszystkie pliki windowsowe zgromadzić na początku dysku, zostawiając jego resztę wolną do użytku przez Linux.

Instalacja

Należy uruchomić komputer z nośnika, na którym nagrany jest program instalacyjny i wybrać opcję Install. Procedura instalacyjna zadaje szereg pytań (np. o strefę czasową i język, w jakim ma być zainstalowany system). Na ogół nietrudno na nie odpowiedzieć.

Następnie procedura instalacyjna przystępuje do partycjonowania dysku. Polega to na tym, że w wolnej przestrzeni na dysku system wydziela nowe części (partycje) dla systemu Linux. Cała procedura instalacji w niczym nie zagraża danym przechowywanym w partycji Windows.

Ostatnią czynnością wykonywaną przez procedurę instalacyjną jest instalacja nowego programu rozruchowego. Działa on w trybie dualnym, co oznacza, że po uruchomieniu komputera możemy wybrać system Windows lub Linux.

W ramach instalacji utworzone zostają konta dwóch użytkowników: konto administratora o nazwie root oraz konto (zwykłego) użytkownika. Szczególnie istotne jest zapamiętanie hasła administratora.

Uruchamianie programów

W pierwszej części książki omawiamy funkcję, a dopiero w drugiej uczymy, jak napisać działający program. Niecierpliwy czytelnik może jednak chcieć sprawdzić, jak działają funkcje już od pierwszej lekcji. Podajemy teraz krótką instrukcję, jak to zrobić.

Edycja kodu źródłowego

Kod źródłowy programu można utworzyć jest w dowolnym edytorze tekstowym. Polecamy korzystanie z edytorów: Vim, Gvim lub Emacs. Aby sprawdzić działanie funkcji, trzeba napisać choćby najprostszy program z wykorzystaniem tej funkcji. W przypadku funkcji opisanej w lekcji 1 kod źródłowy całego programu może mieć następującą postać:

uint

wykladnik(uint n, uint k)

{

uint w = 0;

while (n/=k) w += n;

return (w);

}

void

main()

{

printf("Liczba 5 występuje w rozkładzie liczby 2000!

z wykładnikiem %u\n", wykladnik(2000,5));

}

Tak utworzony kod źródłowy zapisz pod wybraną przed siebie nazwą (np. wykladnik.c) w wybranym przed siebie katalogu.

Przejście do trybu tekstowego

Jeśli system OpenSUSE uruchomił się w trybie graficznym, to należy otworzyć okno, w którym polecenia wydaje się w trybie tekstowym (tzw. emulator konsoli). W tym celu wystarczy uruchomić program o nazwie Konsole. Inną metodą jest zastosowanie skrótu klawiaturowego Ctrl+Alt+Fn, gdzie n jest liczbą od 1 do 6, ale powoduje to opuszczenie trybu graficznego, więc ta metoda powinna być stosowana tylko jako środek ratunkowy, gdy w trybie graficznym coś się zepsuje.

Skompilowanie programu

Przejdź do katalogu (służy do tego polecenie cd), w którym został zapisany kod źródłowy programu i skompiluj go za pomocą programu gcc. W tym celu wydaj polecenie:

$ gcc -o wykladnik wykladnik.c

wykladnik to wybrana przez ciebie docelowa nazwa programu. Jeśli w kodzie programu są błędy, zostaniesz o nich poinformowany.

Uruchomienie programu

Jeśli kompilacja przebiegnie bez zakłóceń, to w tym samym katalogu powstanie nowy plik o nazwie wykladnik, który możesz uruchomić poprzez podanie polecenia:

$ ./wykladnik

Polecane źródła w Internecie

The Top 11 Best Linux Distros for 2015
https://www.linux.com/news/top-11-best-linux-distros-2015

The Best Linux Distros of 2016
https://www.linux.com/news/best-linux-distros-2016

openSUSE
https://pl.opensuse.org/

Compiling C and C++ Programs
http://pages.cs.wisc.edu/~beechung/ref/gcc-intro.html

Część I

Lekcja 1

Optymalizowanie funkcji

Zadanie: napisać funkcję, która, dla danego czynnika pierwszego k i liczby naturalnej n, obliczy potęgę, w jakiej czynnik k występuje w rozkładzie liczby n! na czynniki pierwsze.

Elementy matematyki

Rozkład liczby na czynniki pierwsze oznacza zapisanie jej jako iloczynu liczb pierwszych.

Przykładowo, rozkład liczby 60 na czynniki pierwsze zapisujemy w następujący sposób:

60 = 2 · 2 · 3 · 5

Kolejność czynników w rozkładzie można zmienić, np.:

60 = 2 · 3 · 2 · 5

Powyższe dwa rozkłady liczby 60 będziemy uważać za równoznaczne. Przy założeniu, że kolejność czynników rozkładu jest nieistotna, prawdziwe jest twierdzenie:

Każdą liczbę naturalną można rozłożyć na czynniki pierwsze tylko w jeden sposób.

W dalszym ciągu stosować będziemy tylko taki zapis, w którym czynniki pierwsze podane są w kolejności od najmniejszego do największego. Możemy wtedy rozkład liczby zapisać za pomocą potęg czynników pierwszych, np.

60 = 2^2 · 3^1 · 5^1

Powiemy wtedy, że w rozkładzie liczby 60 czynnik pierwszy 2 występuję w potędze drugiej (ma wykładnik 2), a czynniki pierwsze 3 oraz 5 występują w potędze pierwszej (mają wykładnik 1).

Silnia liczby naturalnej n, oznaczana jako n!, to iloczyn wszystkich liczb naturalnych nie większych niż n.

Przykładowo:

6! = 1 · 2 · 3 · 4 · 5 · 6 = 720

Silnię liczby naturalnej n można zdefiniować również rekurencyjnie, czyli za pomocą definicji, która odwołuje się do samej siebie:

n! = {

1 dla n = 1
n · (n – 1)! dla n > 1

Aby obliczyć wartość 6! korzystając z definicji rekurencyjnej, dokonujemy następujących wyliczeń cząstkowych:

6! =
= 6 · 5! =
= 6 · 5 · 4! =
= 6 · 5 · 4 · 3! =
= 6 · 5 · 4 · 3 · 2! =
= 6 · 5 · 4 · 3 · 2 · 1! =
= 6 · 5 · 4 · 3 · 2 · 1 = 720

Podstawy języka C

W tej części przybliżymy podstawowe elementy języka programowania C.

Program, instrukcja

Program to ciąg instrukcji wykonywanych zgodnie z kolejnością ich zapisania. W języku C każdą instrukcję kończy znak średnika. Instrukcja w języku C ma zatem postać:

nazwa_instrukcji (lista parametrów);

Przykładem instrukcji w języku C jest instrukcja printf, która wypisuje komunikat na urządzenie domyślne (np. monitor komputera). Komunikat kończony jest zwykle komendą przejścia do nowego wiersza \n, np.

printf("Witaj\n");
// wypisanie na ekran napisu 'Witaj'

Składnia języka C dopuszcza zastąpienie jednej instrukcji blokiem instrukcji. Instrukcje łączymy w bloki za pomocą nawiasów klamrowych { }, np.:

{

printf("Witaj\n");

printf("Jak się nazywasz?");

}

Komentarze

Komentarze to teksty pomocnicze, które nie są wykonywane przez program. Zaczynają się znakami /* i kończą znakami */.

Komentarz mieszczący się w jednym wierszu można również zapisać za znakami //.

/* To moj pierwszy program */
printf("Witaj");
// Wypisanie komunikatu powitalnego

Identyfikatory

Identyfikator to nazwa stworzona przez programistę. Identyfikator musi zaczynać się od małej lub dużej litery alfabetu łacińskiego albo znaku podkreślenia; może zawierać ponadto litery, znaki podkreślenia lub cyfry.

Przykładowe identyfikatory: wykladnik, _silnia, n, k1.

Słowa kluczowe

Słowa kluczowe to wyrazy zarezerwowane, których nie można stosować jako identyfikatorów, np. char, switch, return.

Białe znaki

Białe znaki oznaczają spacje, tabulatory, znaki przejścia do następnego wiersza, a także komentarze. Służą one do oddzielania poszczególnych elementów języka, np.

m = n/*ujemna*/ - k/*ujemnik*/;

W powyższym przykładzie spacje oraz komentarze oddzielają identyfikatory oraz operatory (przypisania i odejmowania).