Okładka

Strona tytułowa

Strona redakcyjna

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

Okładka

Strona tytułowa

Strona redakcyjna

Spis treści

Wstęp

Przygotowanie środowiska pracy

Instalacja systemu Linux

Pobranie OpenSUSE

Przygotowanie instalacji

Instalacja

Uruchamianie programów

Edycja kodu źródłowego

Przejście do trybu tekstowego

Skompilowanie programu

Uruchomienie programu

Polecane źródła w Internecie

Część I

Lekcja 1. Optymalizowanie funkcji

Elementy matematyki

Podstawy języka C

Program, instrukcja

Komentarze

Identyfikatory

Słowa kluczowe

Białe znaki

Podstawowe typy numeryczne

Zmienne i operator przypisania

Operatory

Instrukcja warunkowa

Instrukcje pętli

Pętla while

Pętla do while

Pętla for

Funkcje

Funkcje rekurencyjne

Rozwiązanie zadania

Krok 1. Pierwsze zadanie pomocnicze

Krok 2. Rachunki matematyczne

Krok 3. Drugie zadanie pomocnicze

Krok 4. Uogólnienie rachunków

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

Krok 6. Dodanie warunku zakończenia rekurencji

Krok 7. Optymalizacja liczby operacji

Krok 8. Optymalizacja liczby zmiennych

Krok 9. Usunięcie rekurencji

Krok 10. Sprawdzenie poprawności argumentów

Wnioski

Polecane źródła w Internecie

Lekcja 2. Działania na bitach

Sito Eratostenesa

Podstawy Języka C

Operacje na bitach

Operacja and

Operacja or

Operacja xor

Operacja not

Przesunięcie bitowe w lewo

Przesunięcie bitowe w prawo

Rzutowanie

Dyrektywy preprocesora

Tablice

Adresy zmiennych

Wskaźniki

Wskaźniki a tablice

Alokowanie pamięci dla tablicy

Rozwiązanie zadania

Krok 1. Podejście standardowe

Krok 2. Zmniejszenie liczby operacji

Krok 3. Oszczędność pamięci

Krok 4. Poprawa efektywności algorytmu

Wnioski

Polecane źródła w Internecie

Lekcja 3. Alokowanie pamięci

Podstawy informatyki

Podstawy języka C

Funkcja malloc()

Funkcja calloc()

Funkcja realloc()

Funkcja free()

Przykład zarządzania pamięcią

Zmienne automatyczne i statyczne

Rozwiązanie zadania

Wnioski

Polecane źródła w Internecie

Część II

Lekcja 4. Program główny

Podstawy języka C

Funkcja main()

Funkcja exit ()

Standardowe strumienie wejścia i wyjścia

Napisy

Konwersja napisu do liczby

Rozwiązanie zadania

Krok 1. Zadanie pomocnicze

Krok 2. Unikanie prostych błędów

Krok 3. Zastosowanie nazwy programu

Krok 4. Obsługa opcji

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

Krok 6. Zastosowanie zmiennych środowiskowych

Wnioski

Polecane źródła w Internecie

Lekcja 5. Przetwarzanie opcji

Podstawy języka C

Przekazywanie argumentów funkcji

Instrukcja wielokrotnego wyboru: switch

Standardowe opcje programu

Rozwiązanie zadania

Wnioski

Polecane źródła w Internecie

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

Podstawy języka C

Odczyt i zapis do pliku

Trójargumentowy operator warunkowy

Sterowanie preprocesorem

Prototyp funkcji

Atrybut extern

Kompilacja programu

Rozwiązanie zadania

Krok 1. Rozdzielenie kompetencji między funkcje

Krok 2. Rozdzielenie kompetencji między pliki

Krok 3. Utworzenie plików nagłówkowych

Krok 4. Przetwarzanie danych wejściowych

Krok 5. Kompilacja

Aneks

Polecane źródła w Internecie

Część III

Lekcja 7. Debugowanie programu

Na czym polega debugowanie

Podstawy języka C

Buforowanie

Wyrażenie przecinkowe

Funkcja char()

Rozwiązanie zadania

Krok 1. Wydruki kontrolne w kodzie programu

Krok 2. Zastosowanie makra

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

Krok 4. Debugowanie wybierane dynamicznie

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

Wnioski

Aneks

Modyfikacje w funkcji set_opt()

Modyfikacje w funkcji main()

Modyfikacja wypisywania pomocy rozszerzonej

Polecane źródła w Internecie

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

Podstawy teoretyczne

Struktura pliku Makefile

Rozwiązanie zadania

Krok 1. Tworzenie pliku Makefile

Deklaracje zmiennych

Reguły kompilacji

Krok 2. Optymalizacja pliku Makefile

Krok 3. Realizowanie celów specjalnych

make clean

make distclean

make dist

make install

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

Wnioski

Polecane źródła w Internecie

Lekcja 9. Udostępnianie programu

Narzędzia do udostępniania programów

Krok 1. Skanowanie katalogu

Krok 2. Edytowanie pliku configure.ac

Krok 3. Edytowanie pliku config.h.in

Krok 4. Edytowanie pliku makefile.in

Krok 5. Wywołanie programu autoconf

Krok 6. Uruchomienie programu configure

Krok 7. Korzystanie z pliku config.h

Krok 8. Budowanie programu

Krok 9. Dystrybucja

Wnioski

Polecane źródła w Internecie

Część IV

Lekcja 10. Dynamiczne struktury danych

Funkcje rekurencyjne

Rekurencyjne struktury danych

Dynamiczne struktury danych

Listy

Drzewa binarne

Porównanie przetwarzania list i drzew

Realizacja dynamicznych struktur danych w języku C

Struktury

Rozwiązanie zadania

Reprezentacja węzła drzewa

Krok 1. Tworzenie drzewa

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

Krok 3. Zamiana drzewa na listę

Krok 4. Zamiana listy na drzewo

Krok 5. Wypisywanie zawartości drzewa

Krok 6. Wyszukiwanie informacji w drzewie

Krok 7. Optymalizacja wyszukiwania

Krok 8. Baza z wieloma kluczami

Wnioski

Polecane źródła w Internecie

Lekcja 11. Wyrażenia regularne

Automaty skończone

Wyrażenia regularne

Metaznaki

Rozpoznawanie wyrażeń regularnych

Rozwiązanie zadania

Krok 1. Sformułowanie zadania dla konkretnego zastosowania

Krok 2. Budowanie tablicy sterującej

Wnioski

Polecane źródła w Internecie

Lekcja 12. Interpreter poleceń

Gramatyki formalne

Narzędzia informatyczne

Generator parsera yacc

Deklaracje języka C

Deklaracje parsera

Reguły gramatyki

Kod dodatkowy

Generator leksera lex

Reguły leksykalne

Rozwiązanie zadania

Krok 1. Tworzenie pliku mag.y

Krok 2. Generowanie parsera

Krok 3. Tworzenie pliku mag.l

Krok 4. Generowanie analizatora leksykalnego

Krok 5. Tworzenie prostego programu głównego

Krok 6. Modyfikacja pliku Makefile

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

Krok 8. Sterowanie reakcjami systemu

Modyfikacja leksera

Modyfikacja funkcji main()

Modyfikacja parsera

Krok 9. Rozwijanie interpretera

Krok 10. Rozwiązywanie konfliktów

Wnioski

Polecane źródła w Internecie

Pliki towarzyszące książce

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) szybciej zwraca wyniki;

2) zużywa mniej pamięci;

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² · 3¹ · 5¹

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).