Umożliwia abstrakcję danych oraz stosowanie kilku paradygmatów programowania: proceduralnego, obiektowego i generycznego. Charakteryzuje się wysoką wydajnością kodu wynikowego, bezpośrednim dostępem do zasobów sprzętowych i funkcji systemowych, łatwością tworzenia i korzystania z bibliotek (napisanych w C++, C lub innych językach), niezależnością od konkretnej platformy sprzętowej lub systemowej (co gwarantuje wysoką przenośność kodów źródłowych) oraz niewielkim środowiskiem uruchomieniowym. Podstawowym obszarem jego zastosowań są aplikacje i systemy operacyjne.
C++ został zaprojektowany przez Bjarne'a Stroustrupa jako rozszerzenie języka C o obiektowe mechanizmy abstrakcji danych i silną statyczną kontrolę typów. Zachowanie zgodności z językiem C na poziomie kodu źródłowego pozostaje jednym z podstawowych celów projektowych kolejnych standardów języka.
Od 1998 obowiązuje standard ISO/IEC 14882:1998 (Standard for the C++ Programming Language) z drobnymi poprawkami zatwierdzonymi w 2003 r. (ISO/IEC 14882:2003). W 2009 roku ogłoszono, że nowy standard (tzw. C++0x) zacznie obowiązywać nie wcześniej niż w 2010 roku.
Cechy standardów
Projekt języka C++ usiłuje zachować możliwie jak największą zgodność (na poziomie kodu źródłowego) z językiem C. Zgodność pomiędzy obydwoma językami nie zawsze była całkowita, ale jak dotąd ewentualne różnice były w praktyce nieistotne. Większym problemem związanym ze zgodnością była niekompatybilność kompilatorów języka C++ w zakresie obsługiwanej składni - przez wiele lat programy napisane pod jednym nie działały pod innym. Biblioteki C++ związane z interfejsami systemów nie są przenośne poza ich obręb, co wynika z faktu, że takie interfejsy są specyficzne dla danego systemu i nie dotyczy to wyłącznie C++.
Większość użytecznych programów w C++ wymaga stosowania bibliotek niestandardowych. Są one łatwo dostępne w Sieci zarówno jako produkty własnościowe, jak i jako FLOSS. Programy napisane w C++ mogą korzystać również z zasobów bibliotek języka C.
Język C++ jest językiem wieloparadygmatowym. Oznacza to, ze można w nim stosować jednocześnie różne style programowania, w tym programowanie proceduralne, obiektowe, generyczne, jak również programować na poziomie asemblera.
Język C++ zakłada statyczną kontrolę typów; posiada też elementy dynamicznej kontroli typów. Język C++ umożliwia bezpośrednie zarządzanie wolną pamięcią.
Odzwierciedla ona fakt, że język ten jest rozszerzeniem języka C. Wcześniej używano nazwy "C z klasami". Nazwa języka C++ nawiązuje do faktu bycia "następcą języka C", przez użycie w niej operatora inkrementacji "++". Inkrementacja to zwiększenie liczby o 1, w języku C++ do jej wykonania wykorzystywany jest w/w operator;
dla przykładu:
zapis:
i=i+1; // zmiennej "i" przypisujemy jej aktualną wartość, powiększoną o 1
... jest równoważny:
i++; // również powiększamy wartość zmiennej "i" o 1.
Nazwa C++ jest więc symbolicznym stwierdzeniem, iż jest to język C, unowocześniony, o znacznie większych możliwościach.
Pierwsze kompilatory języka C++, podobnie jak Cfront, były wyłącznie translatorami na język C. Kompilatory takie dostępne są i dziś. Jednym z nich jest Comeau C++ - jeden z niewielu kompilatorów oferujących pełne wsparcie dla standardu języka. Pierwszym kompilatorem natywnym (produkującym od razu kod asemblerowy) dla języka C++ był g++ z pakietu GCC, którego pierwszym autorem był Michael Tiemann, założyciel Cygnus Solutions.
Przykładowy program
Poniższy program wyprowadza na standardowe urządzenie wyjścia napis "Hello world":
#include <iostream>
using namespace std;
int main()
{
cout << "Hello world\n";
}
Nowe cechy języka C++ względem języka ANSI C z 1989 roku
Pisząc program, zarówno w C++, jak i każdym innym języku możemy go w zasadzie pisać w dowolnym edytorze tekstowym, chociażby notatniku. Ten kod programu, który my piszemy jest nazywanym kodem źródłowym. Jednak posiadając sam kod źródłowy nie możemy z całą pewnością stwierdzić, że program dobrze działa, albo nawet, że robi to co miał robić - do tego jest właśnie potrzebny kompilator.
Kompilator umożliwia przekształcenie kodu źródłowego do kodu wynikowego, który możemy już bezpośrednio uruchomić na komputerze. W momencie kompilacji (czyli przetwarzania kodu źródłowego do kodu wynikowego), następuje prawdziwy test poprawności składni napisanego przez nas kodu. To tutaj, jeśli zrobiliśmy jakiś błąd, np. zapomnieliśmy średnika, zostaniemy poinformowani o błędzie.
Oprócz błędu, kompilator podczas kompilacji może wyświetlić ostrzeżenie. Ostrzeżenie, jest zazwyczaj odróżniane od błędu poprzez dodanie przed właściwym komunikatem słowa Warning, co po polsku znaczy właśnie ostrzeżenie.
Kryptografia jest nauką zajmującą się szyfrowaniem danych. Celem kryptografii jest wymyślanie różnych szyfrów, tak aby dane zaszyfrowane były jak najbardziej bezpieczne. Z mojego punktu widzenia kryptografia jest częścią algorytmiki, dlatego też zagadnienia kryptograficzne umieściłem w dziale dotyczącym algorytmiki.
Szyfrowanie jest bardzo ważną operacją w dzisiejszym świecie. Nawet nie zdajesz sobie sprawy, jak ciężkie byłoby życie, gdyby kryptografia się nie rozwinęła i nie rozwijała nadal.
Szyfrowanie polega na takim zapisaniu posiadanej informacji, aby odczytanie informacji przez osobę nieznającą sposobu odszyfrowania informacji było niemożliwe. W dzisiejszych czasach, w dobie banków internetowych i transakcji przez internet, szyfrowanie ma szczególnie duże znaczenie.
Szyfrowanie jest też niezbędne w nabierającej coraz większego znaczenia w dzisiejszych czasach transmisji bezprzewodowej Szyfrowanie ma również duże znaczenie podczas użytkowania systemu operacyjnego. Podawane hasła muszą być zapisywane tak, aby ktoś po znalezieniu i otwarciu pliku, nie poznał cudzych haseł. Ponadto w nowoczesnych systemach plików (np. NTFS) dane na dysku można szyfrować tak, aby nikt poza osobą, która dokonała szyfrowania, nie mógł odczytać zaszyfrowanych informacji.
Instrukcje warunkowe
Jak sama nazwa wskazuję są to instrukcje, które wykonują się tylko wtedy gdy spełniony jest podany warunek. Dzięki instrukcjom warunkowych program może "zachowywać" się zależnie od spełnienia pewnych warunków.
Intstrukcja if - else
Podstawowa instrukcja warunkowa wygląda następująco:
if( <warunek> )
{//blok1
...
}
else
{//blok2
...
}
Jeżeli spełniony jest warunek to wykonane zostaną instrukcje zawarte w bloku1,
a gdy warunek nie jest spełniony to wykonane zostaną instrukcje z bloku2.
Wartość zwracana przez warunek w instrukcjach warunkowych nie musi być typu
bool ale może być także wartością liczbową i w takim przypadku warunek nie jest spełniony wtedy i tylko wtedy gdy wartość ta wynosi 0
Gdy wartość jest różna od zera (również mniejsza od zera) to warunek jest spełniony.
Przykład:
#include <iostream>
using namespace std;
int main()
{
int x;
cout << "Podaj liczbę całkowitą:" << endl;
cin >> x;
if(x & 1) cout << "Liczba nieparzysta.";
else cout << "Liczba parzysta.";
return 0;
}
Po instrukcji warunkowej if nie musi występować słowo kluczowe else (oczywiście nie ma wtedy bloku2
).
Jeżeli w jednym z bloków znajduję się tylko jedna instrukcja to nie musi być ona zawarta w klamrach {} (czyli nie musimy tworzyć bloku).
Operator warunkowy
Operator warunkowy bardzo przypomina konstrukcje if - else:
( <warunek> ) ? <wyrażenie1> : <wyrażenie2>;
Jeżeli spełniony jest <warunek> to operator zwróci wartość
<wyrażenia1>, w przeciwnym wypadku wartość <wyrażenia2>.
<wyrażenie1> nie jest zakończone średnikiem natomiast
<wyrażenie2> może (a nawet musi) być zakończone średnikiem gdy wartość zwracana przez operator nie jest przekazywana jako argument.
operator warunkowy pozwala w wielu sytuacjach skrócić zapis kodu i zwiększać
przejrzystość kodu.
Teraz powyższy przykład zapiszmy z wykorzystaniem operatora warunkowego:
#include <iostream>
using namespace std;
int main()
{
int x;
cout << "Podaj liczbę całkowitą:" << endl;
cin >> x;
cout << ( (x & 1) ? "Liczba nieparzysta." : "Liczba parzysta.") << endl;
return 0;
}
Instrukcja switch - case
Ostatnią instrukcją warunkową jest konstrukcja switch - case, która pozwala nam na wybór więcej niż jednej opcji:
switch( <wyrażenie> )
{
case <wartość1>:
instrukcja1;
instrukcja2;
//...
break;
case <wartość2>:
instrukcja1;
instrukcja2;
//...
break;
//...
default:
instrukcja1;
instrukcja2;
//...
}
Instrukcja switch oblicza wartość <wyrażenia> i dopasowywuje go do jednej z podanych opcji.
Wszystkie opcje muszą być zawarte w bloku. Po słowie kluczowym case podajemy
<wartość>, a następnie dwukropek. Po dwukropku podajemy instrukcje, które z kolei nie muszą być już zawarte w nowym bloku.
Jeżeli wartość <wyrażenia> będzie odpowiadała jednej z <wartości> to wykonywane są wszystkie instrukcje występujące po niej aż do napotkania słowa kluczowego break
Jeżeli żadna z <wartości> nie będzie pasowała do wartości <wyrażenia> to wykonane zostaną instrukcje znajdujące się po słowie kluczowym default.
Jeżeli nie występuje opcja default i inne możliwości także nie pasują to nie zostanie
wykonana żadna instrukcja.
Przyład:
#include <iostream>
using namespace std;
int main()
{
short x;
cout << "Podaj cyfrę od 0 do 5" << endl;
cin >> x;
switch(x)
{
case 0: cout << "Wybrano 0" << endl;
break;
case 1: cout << "Wybrano 1" << endl;
break;
case 2: cout << "Wybrano 2" << endl;
break;
case 3:
case 4:
case 5: cout << "Wybrano 3, 4 lub 5" << endl;
break;
default: cout << "Wybrana liczba nie zawiera się w [0,5]" << endl;
}
return 0;
}
Mam nadzieję że ten program nie wymaga już komentarza. Chciałbym tylko zwrócić uwagę na brak słowa kluczowego break po 2 instrukcjach case co pozwala nam na wykonanie tego samego kodu jeśli zostanie spełniona jedna z tych opcji.
Instrukcja goto
Instrukcja goto jest instrukcją skoku bezwarunkowego. Powoduje ona "przeskoczenie"
programu do innego miejsca w tym samym bloku wskazanego etykietą:
goto <etykieta>;
//...
<etykieta>:
//...
Instrukcja skoku bezwarunkowego goto może być najczęściej zastąpiona przez pozostałe
instrukcje warunkowe, może być także używana w połączeniu z nimi. Powinna być używana w sposób rozsądny i tylko tam gdzie rzeczywiście powoduje ona przyspieszenie programu bądź zwiększa jego czytelność (np. przerywanie zagnieżdżonych pętli).
Pętle służą do wykonywania wielokrotnie tego samego bloku instrukcji.
Pętla while
Składnia:
while( <warunek> )
{
instrukcja1;
instrukcja2;
//...
}
Po słowie kluczowym while w nawiasach podajemy warunek a następnie instrukcje zawarte w bloku.
Na początku sprawdzany jest warunek. Jeżeli jest on spełniony to wykonywane są instrukcje zawarte w bloku. Następnie ponownie jeśli warunek jest spełniony wykonywanie są te same instrukcje z bloku.
Warunek nie jest spełniony wtedy i tylko wtedy gdy jego wartość logiczna wynosi
false co liczbowo odpowiada 0 (zeru). W przeciwnym wypadku warunek jest spełniony.
Pętla kończy się jeżeli warunek nie zostanie jest spełniony (możliwe jest, że instrukcje nie zostaną wykonane ani raz jeżeli warunek nie zostanie spełniony już przy pierwszym sprawdzaniu).
Istnieją jeszcze inne możliwości przerwania pętli:
Jeżeli wewnątrz bloku pętli wystąpi słowo kluczowe break to kolejne instrukcje zawarte w tym bloku nie zostaną już wykonane i pętla kończy swoje działanie.
Instrukcja goto zawarta w bloku może spowodować skok to etykiety znajdującej się poza blokiem pętli tym samym powodując jej przerwanie.
Wewnątrz bloku pętli może znajdować się także instrukcja continue, która co prawda nie powoduje natychmiastowego przerwania pętli ale sprawia, że kolejne instrukcje zawarte w bloku nie zostaną już wykonane i nastąpi ponowne sprawdzenie warunku pętli.
Pomijam słowo kluczowe return, które oczywiście przerywa wykonywanie pętlii całej funckji ;D.
przykłady:
int i = 5;
while(i < 10) i++; //po wykonaniu pętli i = 10
while(i++) if(i==15) break; //jeśli i wynosi 15 to przerywamy wykonywanie pętli
while(true) goto etykieta1; //skok do etykiety
etykieta1:
while(i <= 20) //wyswietla liczby 15, 16, 17, 19 i 20
{
if(i==18) { i++; continue; }
cout << i++ << endl;
}
Pętla do - while
Składania:
do {
instrukcja1;
instrukcja2;
//...
}while( <warunek> );
Zwracam uwagę, że po nawiasach w których zawarty jest warunek musimy postawić średnik!
Pętla do-while bardzo przypomina pętlę while. Działa ona niemal tak samo z tą różnicą, że instrukcje zawarte w bloku są wykonane minimum jeden raz. Dopiero po ich wykonaniu sprawdzany jest warunek i zależnie od jego spełnienia pętla ponownie wykonuje dane instrukcje bądź jest przerywana. Pętlę tą możemy przerywać tymi samymi sposobami co pętlę while.
Pętla for
Tradycyjnie zacznę od przedstawienia składni:
for(intrukcja1 ; <warunek> ; instrukcja2)
{
//instrukcje
}
Na początku wykonywana jest instruckcja1 (może być to kilka instrukcji oddzielonych przecinkami). Następnie sprawdzany jest warunek. Jeżeli jest spełniony to wykonywane są instrukcje zawarte w bloku a jeśli nie to pętla kończy swoje działanie. Po wykonaniu tych instrukcji (oczywiście jeżeli pętla nie została zakończona wykonywana jest instruckcja2
(znowu może to być kilka instrukcji oddzielonych przecinkami) po której ponownie sprawdzany jest warunek.
Podsumowując:
Instruckcja1
wykonywana jest zawsze tylko raz na samym początku. Następnie sprawdzany jest warunek i wykonywane są instrukcje zawarte w bloku (war. spełniony).
Instruckcja2 wykonywana jest zawsze po wykonaniu instrukcji z bloku (przed sprawdzeniem warunku) - wykonuje się zatem tyle razy ile wykonane zostały instrukcje z bloku chyba, że pętla została przerwana wewnątrz bloku (break, goto czy return).
Jeśli wewnątrz bloku wystąpi instrukcja continue to instrukcje w tym Bloku występujące dalej zostaną pominięte i wykonana zostanie instruckcja2 po której sprawdzony zostanie ponownie warunek.
przykład:
for(int i=1; i<=10 ;i++) cout << i << endl;
//pętla wypisze liczby od 1 do 10 włącznie
Wskaźniki
Wskaźnik na zmienną danego typu jest to zmienna, która przechowuje adres zmiennej danego typu. Może brzmi to nieco niezrozumiale jest to bardzo proste. Wszystkie zmienne jakie deklarujemy są niczym innym jak tylko komórkami pamięci operacyjnej RAM (może być inaczej ale nie jest to teraz istotne). Zatem odwołując się do zmiennej poprzez jej nazwę odwołujemy się do przydzielonej jej (zmiennej) pamięci. Wartością wskaźnika jest natomiast adres pamięci RAM, gdzie znajduje się taka zmienna. Żeby wytłumaczyć jak dokładnie to działa posłużymy się prostym przykładem:
int x=1; //deklaracja zmiennej int
int *wskaznik; //deklaracja wskaźnika na typ int
wskaznik = &x; //przypisanie adresu zmiennej wskaźnikowi
*wskaźnik = 99; //zapis równoważny z "x=99;"
Pierwsza linia przedstawionego kodu jest oczywista więc nie będziemy jej spejcajlnie analizować.
W drugiej lini zadeklarowaliśmy wskaźnik na typ int. Zatem jak można się domyślać
deklaracja wskaźnika wygląda następująco:
<modyfikator> <typ> *nazwa;
Zatem sama deklaracja wskaźnika na zmienną danego typu różni się od deklaracji zmiennej jedynie dodatkowym znakiem '*' poprzedzającym nazwę zmiennej.
Modyfikator const przy deklaracji wskaźnków podobnie jak przy deklaracji zwykłych zmiennych
powoduje, że obiekt jest stały. Oznacza to, że nie możemy zmieniać wartości takiego obiektu.
Przy wskaźnikach możemy użyć słowa kluczowego const na dwa sposoby. Możemy deklarować bowiem wskaźnik na stały obiekt (wskaźnik na stałą) lub stały wskaźnik na obiekt (stały wskaźnik na zmienną). Już wyjaśniam o co chodzi w tym całym zamieszaniu.
Wskaźnik na stałą deklarujemy w następujący sposób:
const <typ> *nazwa;
Operator wyłuskania
Jeśli już wspomniałem o obiektach to od razu wspomnę na temat operatora wyłuskania '->'. Operator ten pozwala nam na "wyłuskiwanie" pól obiektów na który wskazuje wskaźnik. Co prawda jego użycie możnaby zastąpić znanym nam już opratorem wyłuskania '*' ale byłoby to niewygodne - także sam kod z użyciem '->' wygląda nieco lepiej:
struct A { //deklaracja struktury A
int x;
int getx() { return x; }
} a, *ptr; //deklarujemy obiekt typu A oraz wskaźnik na struturę A
ptr = &a; //przypisujemy adres struktury do wskaźnika
(*ptr).x = 5; //przypisujemy wartość 5 polu x
ptr->x = 10; //przypisujemy polu wartość 10
Użycie nawiasu podczas dereferencji z użyciem operatora '*' jest konieczne ponieważ operator '.' ma wyższy priorytet niż
operator '*'. Jeśli zatem wyrażenia '*ptr' nie otoczylibyśmy nawiasami to byłoby to równoznaczne zapisowi:
*(ptr.x) = 5; //to samo co: *ptr.x=5;
Wskaźnik uniwersalny
Wskaźnik uniwersalny deklarujemy w następujący sposób:
void *nazwa;
Czym różni się on od zwykłego wskaźnika. Otóż jak widać w deklaracji nie podajemy na jaki typ będzie wskazywał dany wskaźnik. Pozwala nam to na przypisanie każdego typu wskaźnika.Ttracimy możliwości użycia operatorów dereferencji (wyłuskania) -
'*' oraz '->'. Jest tak ponieważ, wskaźnik typu void wskazuje tylko sam adres w pamięci operacyjnej ale nie mówi kompilatorowi nic o typie wartości przechowywanej pod tym adresem. Zatem kompilator nie posiada żadnej informacji
o typie, tym samym nie może wykonać operacji wyłuskania.
Tutaj z pomocą przychodzi nam operator rzutowania reinterpret_cast.
Dzięki niemu możemy zamienić zmienną na wskaźnik dowolnego typu. W tym momencie to
my jesteśmy odpowiedzialni za kontrolę typów. Kompilator nie może w czasie kompilacji
stwierdzić czy rzutowanie takie jest poprawne i musi nam zaufać. Proszę zatem o czujność w czasie wszelkiego rodzaju rzutowania wskaźników bowiem są one przyczyną wielu błędów, które niestety często trudno jest wykryć.
unsigned x = 0x12345678;
void *p = &x;
unsigned short y = *reinterpret_cast<unsigned short*>(p);
W przykładzie tym deklarujemy wskaźnik typu void i przypisujemy mu adres zmiennej
x (która jest typu unsigned int i zajmuje 4 bajty). W następnej lini deklarujemy zmienną
typu unsigned short i przypisujemy jej wartość wyłuskaną ze wskaźnika zwróconego
przez operator reinterpret_cast, który "przerobił" zmienną 'p' na wskaźnik do typu
unsigned short. Wartość 'y' wynosić będzie 0x5678. Na maszynach z rodziny x86,
gdzie stosowany jest wspomniany już system Little-Endian takie przypisane będzie poprawne
mimo tego, że rozmiar zmiennej 'y' (2 bajty) jest mniejszy niż rozmiar zmiennej 'x'.
Wskaźniki do funkcji
W języku C++ mamy możliwość deklarowania wskaźników nie tylko na zmienne ale także na funkcje. Znajdują one zastosowanie na przykład w czasie korzystania z bibliotek dynamicznych.
Sama idea wskaźnika jest taka sama jak w przypadku zwykłego wskaźnika z tym wyjątkiem, że adres wskaźnika
oznacza miejsce w pamięci w którym rozpoczyna się kod funkcji.
Deklaracja wygląda następująco:
<typ> (*nazwa)( <parametry_funkcji> );
Jak widać w czasie deklaracji podajemy zarówno typ zwracanej wartości jak i wszystkie parametry jakie pobiera wskazywana funkcja. Można się zatem domyślać, że nie ma uniwersalnego wskaźnika na funkcję - wynika to między innymi z kontroli typów w C++.
Struktury danych pozwalają nam "zebrać" różne dane. Pozwala to na wygodniejsze operowanie danymi. Deklaracja struktury wygląda następująco:
struct <nazwa> {
... //deklaracja pól i metod strutury
};
Polami struktury nazywamy wszystkie zmienne zawarte w strukturze danych, a metodami wszystkie funkcje, jakie posiada dana struktura.
Proszę zwrócić uwagę na średnik na końcu deklaracji struktury (po klamrze '}')
przykład
#include <string>
#include <iostream>
using namespace std;
struct Osoba {
string imie, nazwisko;
unsigned char wiek;
void wyswietl();
};
void Osoba::wyswietl()
{
cout << imie << " " << nazwisko << " ma " << wiek << " lat." << endl;
}
int main()
{
struct Osoba osoba;
cout << "Podaj imię, nazwisko i wiek" << endl;
cin >> osoba.imie >> osoba.nazwisko >> osoba.wiek;
osoba.wyswietl();
return 0;
}
Konstuktor to metoda (funkcja) w strukturze danych posiadająca taką samą nazwę jak typ naszej struktury. Jeżeli obiekt nie ma jawnie zadeklarowanego konstruktora (np. w naszym poprzednim przykładzie) to jest on tworzony automatycznie w czasie kompilacji (podobnie sytacja wygląda z operatorem kopiującym tzn. metodą "operator =()").
Konstutor jest wywoływany tylko w czasie tworzenia obiektu. Jeżeli przeciążyliśmy konstruktor (zadeklarowaliśmy kilka funkcji o różnych argumentach) to o wywołaniu konkretnego konstruktora decydują argumenty podane przy definicji naszego obiektu. Kompilator tak jak w przypadku zwykłego przeciążania funkcji postara się o wywołanie
konstruktora do którego najlepiej pasują podane argumenty. Jeśli ich nie ma wtedy wywoływany jest konstruktor nie posiadający argumentów.
Jeśli zadeklarowaliśmy choć jeden konstruktor to kompilator nie doda już za nas konstruktora, który nie posiada żadnych argumentów. W takim przypadku musimy już jawnie zadeklarować i zdefiniować taki konstruktor. Oczywiście nie jest on konieczny, ale bez niego nie możemy tworzyć obiektów bez podawania żadnych argumentów.
Jeżeli jawnie nie zadeklarujemy konstruktora kopiującego to jest on zawsze automatycznie dodany.
Destruktor to funkcja o nazwie identycznej z nazwą typu struktury poprzedzona znakiem tyldy "~". Destruktor nie zwraca żadnego typu ani nie posiada, żadnego argumentu. Jego deklarację (i definicję) również nie poprzedzamy żadną nazwą nazwą typu.
Jak można się domyślać destruktor wywoływany jest automatycznie gdy niszczony jest obiekt. Dzieje się tak gdy program wychodzi z bloku kodu w którym zadeklarowy był nasz obiekt. Jeżeli był on tworzony dynamicznie to destuktor wywoływany jest gdy użytkownik jawnie usuwa zmienną z pamięci. Destruktor możemy także wywołać jawnie - nie oznacza to jednak automatycznego zwolnienia miejca po obiekcie na rzecz którego został on wywołany.
prosty program, na przykładzie którego omówiona zostanie budowa programu w c++.
#include <iostream> /* plik nagłówkowy */
using namespace std;
int main() //główny program
{
cout << "Hello world!"; //wypisanie na standardowe wyjście
return 0; //koniec programu - zwracam 0
}
Przeanalizujmy zatem kod programu. Pierwsza linia
1
#include <iostream> /* plik nagłówkowy */
rozpoczyna się od dyrektywy preprocesora. Są to polecenia dla preprocesora, które wykonywane są przed kompilacją kodu programu. Dyrektywa #include nakazuje
preprocesorowi dołączenie w tym miejscu kodu pliku podanego po dyrektywie.
W tym przypadku dołączony zostanie plik nagłówkowy "iostream" ponieważ będziemy używać strumieni do wypisania tekstu.
Komentarze to tekst w kodzie źródłowym, który nie podlega kompilacji a jedynie pozwala programiście komentować kod. Komentarze znacznie ułatwiają późniejsze utrzymywanie kodu, pomagają także zrozumieć działanie programu innym.
W c++ istnieją 2 sposoby wstawiania komentarzy:
...
/*pierwszy sposób komentowania kodu
kolejna linia komentarza a to już ostatnia */
...
//to jest drugi sposób wstawiana komentarza
...
Jak widać pierwszy sposób polega na wstawieniu komentarza pomiędzy
/*(otwarcie komentarza) i */ (zamknięcie komentarza).
Wszystko, co jest zawarte pomiędzy tymi znakami jest traktowane jako komentarz.
Drugi rodzaj komentarza pozwala na podanie komentarza, który rozpoczyna się
od sekwencji znaków //, a kończy się wraz ze
znakiem nowej linii.
Nie powinno się zagnieżdżać komentarzy pierwszego rodzaju.
Należy pamiętać, że komentarz zaczyna się od sekwencji znaków /* i kończy po wystąpieniu pierwszej sekwencji znaków kończących komentarz */, a więc poniższe zagnieżdżenie komentarzy jest nieprawidłowe:
...
/* początek komentarza 1
komentarz 1
/* początek komentarza 2
komentarz 2
koniec komentarza 2 */
komentarz 1
koniec komentarza 1*/
...
Wróćmy do analizowania kodu naszego programu:
2
using namespace std;
Na razie przyjmijmy, że gdy dołączamy plik nagłówkowy "iostream"
to ta linia jest zalecana (a nawet wymagana) ale to wyjaśnię nieco później.
Teraz najważniejsza linia naszego programu, definicja głównej funkcji programu:
int main()
{ //ciało funkcji
...
}
słowo kluczowe int określa typ zwracanej wartości przez daną funkcję. Dla funkcji "main" będzie to zawsze int.
Następnie podawana jest nazwa funkcji (w tym przypadku jest to "main",
czyli główna funkcja programu). Nazwa ta jest zastrzeżona i nie można jej zmienić. Funkcja "main" jest wywoływana przez powłokę, która przekazuje jej także argumenty.
Nawiasy "()" oznaczają, że mamy do czynienia z funkcją.
Następnie następuje otwarcie bloku (znaki "{" - otwarcie, "}"
- zamknięcie bloku).
Blok kodu to jedyne miejsce gdzie można umieszczać instrukcje programu.
6
cout << "Hello world!";
Funkcja "cout" pozwala nam na wypisanie tekstu poprzez strumienie na standardowe wyjście - najczęściej jest to konsola.
Dzięki tej funkcji możemy wypisywać nie tylko tekst ale także wartości zmiennych,
return 0; /* zwrócenie wartości 0 - (zazwyczaj
oznacza poprawne wykonanie programu) */
Jak każda funkcja, (prawie każda ;), funkcja "main"
musi zwracać wartość odpowiedniego dla niej typu, czyli w tym przypadku jest to
liczba całkowita typu int.
WSZYSTKIE instrukcje w c++ oraz deklaracje zmiennych muszą kończyć się znakiem ";"!
Zmienne pozwalają nam na przechowywanie danych w programie. Jest kilka podstawowych
typów zmiennych, które umożliwiają przechowywanie różnego rodzaju informacji.
Deklaracja zmiennych
Zmienne deklarujemy w następujący sposób:
<modifikator> <typ> nazwa_zmiennej;
Podstawowe typy zmiennych:
char - zmienna przechowuje znaki (litery, cyfry, znaki
interpunkcyjne). Za pomącą tego typu zmiennej można także przechowywać niewielkie
liczby.
int - zmienna służy do przechowywania liczb całkowitych.
bool - zmienna służy do przechowywania wartości
logicznych true/false (prawda/fałsz).
float - zmienna przechowuje liczby rzeczywiste
(zmiennoprzecinkowe - do 7 cyfr po przecinku).
double - zmienna przechowuje liczby rzeczywiste
podobnie jak powyższy typ ale posiada dużo większą dokładność (do 15 miejsc
po przecinku).
C++ pozwala także na użycie pewnych kwalifikatorów przed typem zmiennej:
signed - zmienna może przechowywać wartości dodatnie i ujemne (zmienna posiada znak +/-).
unsigned - zmienna może przechowywać tylko
wartości dodatnie.
short - zmienna jest typu krótkiego - wpływa na
długość zajmowanej pamięci (a więc również na zakres zmiennej).
long - zmienna jest typu długiego.
Istnieje także możliwość określenia klasy zmiennej. Należy jednak podkreślić, że TYP ZMIENNEJ (char,int itp.) decyduje o sposobie interpretacji przechowywanych w pamięci bitów, natomiast KLASA ZMIENNEJ decyduje o sposobie przechowywania zmiennej w pamięci. W C++ występują następujące klasy zmiennych:
const - stała - nie można zmieniać wartości raz nadanej
static - zmienna w momencie uruchomienia programu
otrzymuje stałe miejsce w pamięci. Przykładowe zastosowanie tej klasy zmiennej
znajduje się w dalszej części kursu.
Słowo kluczowe static ma inne zastosowanie przy deklaracji funkcji.
auto - przydział miejsca w pamięci dla zmiennej następuje dynamicznie (na stosie) w czasie wykonywania bloku, w którym zmienna została zadeklarowana. Po zakończeniu wykonywania instrukcji z danego bloku pamięć po zmiennej zostaje zwolniona.
Jest to domyślna klasa zmiennych.
register - zmienne lokalne (tzn. dostępne tylko w bloku,w którym zostały zadeklarowane). Zmienne te są umieszczane w miarę możliwości w rejestrach procesora. Jeżeli w programie pojawi się więcej niż 2 zmienne tej klasy to zostaną one umieszczone na stosie. Praktyczne zastosowanie znajduje np. jako licznik w pętlach, co przyspiesza działanie programu.
extern - jeżeli zmienna została - raz i TYLKO RAZ- zadeklarowana w pojedynczym segmencie programu, zostanie w tym segmencie umieszczona w pamięci i potraktowana podobnie jak zmienna klasy static.
Po zastosowaniu w innych segmentach deklaracji tej samej zmiennej jako extern, zmienna ta może być używana również w tamtych segmentach programu.
volatile - oznacza zmienną, z której mogą korzystać także inne procesy. Oznacza to np., że inny proces może zmieniać wartość tej zmiennej przez co przed każdym jej użyciem musi zostać odczytana na nowo.
Deklarując zmienne musimy pamiętać, że kompilator rozróżnia małe i duże litery.
Zatem zmienna A nie jest zmienną a i vice versa;
Zmienne NIE mogą mieć nazwy, która jest jednym ze słów kluczowych.
Operatory arytmetyczne
* operator mnożenia
/ operator dzielenia
% operator dzielenia modulo
+ operator dodawania
- operator odejmowania
Bardzo podobne operatory do powyższych to:
*= pomnóż przez
/= podziel przez
%= podziel modulo przez
+= dodaj
-= odejmij
Operatory bitowe operują na bitach zmiennych.
<< przesuń bity w lewo
>> przesuń bity w prawo
~ operator negacji bitowej
& koniunkcja bitowa
| alternatywa bitowa
^ różnica bitowa
wersje skrócone
<<= operator przypisania
>>= operator przypisania
~= operator przypisania
&= operator przypisania
|= operator przypisania
^= operator przypisania
Operatory relacji
== operator porównania
!= operator nierówności
> operator większości
>= większe bądź równe
< operator mniejszości
<= mniejsze bądź równe
Operatory relacji zwracają wartości logiczne true/false (liczbowo 1/0).
Operator porównania == zwraca wartość true wtedy i tylko wtedy gdy oba argumenty
mają tą samą wartość.
Operator nierówności != zwraca wartość true wtedy gdy oba argumenty różnią się co do
wartości (nie są sobie równe).
Operator > (>=) zwraca wartość true wtedy pierwszy z argumentów (ten po lewej
stronie :) ma wartość większą (większą bądź równą) od drugiego argumentu.
Operator rozmiaru to sizeof zwraca rozmiar danego wyrażenia lub typu w bajtach.
}
Operatory selekcji
. operator selekcji
-> operator selekcji wskaźników
.* operator selekcji klas
->* operator selekcji wskaźników klas
Funkcje w programowaniu przypominają funkcje w matematyce. Np. funkcja sinus pobiera
jako argument dowolną liczbę rzeczywistą i zwraca wartość rzeczywistą z przedziału [-1,1].
Podobnie funkcje w c++ mogą pobierać pewne argumenty i zwracać określony typ wartości.
Funkcję deklarujemy w następujący sposób:
<typ_zwracanej_wartości> nazwa_funkcji( <argumenty_funkcji> );
Na początku wskazujemy jaki typ wartości będzie zwracany przez funkcję. Może to być
jeden z typów podstawowych (char, int) jak również typy złożone (struktury i klasy).
Następnie podajemy nazwę funkcji a po niej w nawiasach po przecinku wskazujemy
jakie argumenty będzie przyjmować.
Funkcje, które nie zwracają żadnej wartości deklarujemy jako void:
#include <iostream>
using namespace std;
void napis()
{ //definicja ciała funkcji
cout << "Funkcja dziala poprawnie." << endl;
}
int dodaj(int a, int b)
{
return a+b;
}
int main()
{
napis(); //wywołanie funkcji
int wynik = dodaj(5,7);
cout << "5 + 7 = " << wynik << endl;
return 0;
}
Jak widać w powyższym przykładzie wartość zwracamy poprzez słowo kluczowe return po którym podajemy wartość jaki ma zwrócić dana funkcja. Jeżeli w ciele funkcji następuje zwrócenie wartości poprzez return to funkcja jest przerywana (jeżeli dalej są jakieś instrukcje to już się nie wykonają).
Funkcje inline
Jeżeli definicja (nie deklaracja) funkcji jest poprzedzona słowem inline oraz funkcja nie jest rekurencyjna i nie zawiera żadnych pętli to w miejscu wywołania tej funkcji kompilator wstawi jej kod, co spowoduje zwiększenie rozmiaru pliku wykonywalnego ale może spowodować także przyspieszenie jego działania.
inline int dodaj(int a, int b)
{
return a+b;
}
int main()
{
int a,b,c;
a = 5;
b = 9;
c = dodaj(a,b);
return 0;
}
Rekurencja polega na odwoływaniu się funkcji do samej siebie. Należy przy tym uważać
na to, aby taka rekurencja miała koniec.
Dobrym przykładem ilustrowania rekurencji jest obliczanie silni:
unsigned long silnia(unsigned a)
{
if(a <= 1) return 1;
return a*silnia(a-1);
}
Rekurencja jest mało wydajna i gdy tylko można zastąpić ją pętlą (czasem jest to
bardzo trudne) należy to czynić:
unsigned long silnia(unsigned a)
{
unsigned long x=1;
while(a > 1) x *= a--;
return x;
}
Funkcje statyczne
Jeżeli deklaracja funkcji globalnej jest poprzedzona słowem kluczowym static to taka funkcja ma zasięg lokalny tzn., że nie możemy używać jej w innej jednostce kompilacji.
Pliki nagłówkowe
pliki te pozwalają nam deklarować prototypy funkcji, klasy (struktury), szablony i tym podobne rzeczy. Takie postępowanie często zwiększa przejrzystość kodu.
Pliki nagłówkowe zazwyczaj mają rozszerzenie "*.h", rzadziej "*.hpp". Pliki te możemy
dołączać do naszego programu na dwa sposoby:
#include <cstdio>
#include "moj.h"
Definicje funkcji zadeklarowanych w plikach nagłówkowych umieszcza się w plikach "*.cpp". Na początku takiego pliku dołączamy plik nagłówkowy po czym defniujemy nasze funkcje
Instrukcje warunkowe
Jak sama nazwa wskazuję są to instrukcje, które wykonują się tylko wtedy gdy spełniony
jest podany warunek. Dzięki instrukcjom warunkowych program może "zachowywać" się
zależnie od spełnienia pewnych warunków.
Intstrukcja if - else
Podstawowa instrukcja warunkowa wygląda następująco:
if( <warunek> )
{//blok1
...
}
else
{//blok2
...
}
Jeżeli spełniony jest warunek to wykonane zostaną instrukcje zawarte w bloku1, a gdy warunek nie jest spełniony to wykonane zostaną instrukcje z bloku2.
Wartość zwracana przez warunek w instrukcjach warunkowych nie musi być typu
bool ale może być także wartością liczbową i w takim przypadku warunek nie jest spełniony wtedy i tylko wtedy gdy wartość ta wynosi 0
Gdy wartość jest różna od zera (również mniejsza od zera) to warunek jest spełniony.
Przykład:
#include <iostream>
using namespace std;
int main()
{
int x;
cout << "Podaj liczbę całkowitą:" << endl;
cin >> x;
if(x & 1) cout << "Liczba nieparzysta.";
else cout << "Liczba parzysta.";
return 0;
}
Po instrukcji warunkowej if nie musi występować słowo kluczowe else (oczywiście nie ma wtedy bloku2
).
Jeżeli w jednym z bloków znajduję się tylko jedna instrukcja to nie musi być ona zawarta w klamrach {} (czyli nie musimy tworzyć bloku) tak jak ma to miejsce w przedstawionym przykładzie.
Operator warunkowy
Operator warunkowy bardzo przypomina konstrukcje if - else:
( <warunek> ) ? <wyrażenie1> : <wyrażenie2>;
Jeżeli spełniony jest
<warunek>
to operator zwróci wartość
<wyrażenia1>,
w przeciwnym wypadku wartość
<wyrażenia2>.
<wyrażenie1> nie jest zakończone średnikiem natomiast
<wyrażenie2> może (a nawet musi) być zakończone średnikiem gdy wartość zwracana przez operator nie jest przekazywana jako argument.
operator warunkowy pozwala w wielu sytuacjach skrócić zapis kodu i zwiększać
przejrzystość kodu.
Instrukcja switch - case
Ostatnią instrukcją warunkową jest konstrukcja switch - case, która pozwala nam na wybór więcej niż jednej opcji:
switch( <wyrażenie> )
{
case <wartość1>:
instrukcja1;
instrukcja2;
//...
break;
case <wartość2>:
instrukcja1;
instrukcja2;
//...
break;
//...
default:
instrukcja1;
instrukcja2;
//...
}
Instrukcja switch oblicza wartość
<wyrażenia> i dopasowywuje go do jednej z podanych opcji.
Wszystkie opcje muszą być zawarte w bloku. Po słowie kluczowym case podajemy
<wartość>, a następnie dwukropek. Po dwukropku podajemy instrukcje, które z kolei nie muszą być już zawarte w nowym bloku.
Jeżeli wartość <wyrażenia> będzie odpowiadała jednej z <wartości> to wykonywane są wszystkie instrukcje występujące po niej aż do napotkania słowa kluczowego break
Jeżeli żadna z <wartości> nie będzie pasowała do wartości <wyrażenia> to wykonane zostaną instrukcje znajdujące się po słowie kluczowym default.
Jeżeli nie występuje opcja default i inne możliwości także nie pasują to nie zostanie
wykonana żadna instrukcja.
Przyład:
#include <iostream>
using namespace std;
int main()
{
short x;
cout << "Podaj cyfrę od 0 do 5" << endl;
cin >> x;
switch(x)
{
case 0: cout << "Wybrano 0" << endl;
break;
case 1: cout << "Wybrano 1" << endl;
break;
case 2: cout << "Wybrano 2" << endl;
break;
case 3:
case 4:
case 5: cout << "Wybrano 3, 4 lub 5" << endl;
break;
default: cout << "Wybrana liczba nie zawiera się w [0,5]" << endl;
}
return 0;
}
Instrukcja goto jest instrukcją skoku bezwarunkowego. Powoduje ona "przeskoczenie"
programu do innego miejsca w tym samym bloku wskazanego etykietą:
goto <etykieta>;
//...
<etykieta>:
//...
Instrukcja skoku bezwarunkowego goto może być najczęściej zastąpiona przez pozostałe
instrukcje warunkowe, może być także używana w połączeniu z nimi. Powinna być używana w sposób rozsądny i tylko tam gdzie rzeczywiście powoduje ona przyspieszenie programu bądź zwiększa jego czytelność (np. przerywanie zagnieżdżonych pętli).
Modyfikator const
Modyfikator const przy deklaracji wskaźnków podobnie jak przy deklaracji zwykłych zmiennych powoduje, że obiekt jest stały. Oznacza to, że nie możemy zmieniać wartości takiego obiektu.
Przy wskaźnikach możemy użyć słowa kluczowego const na dwa sposoby. Możemy deklarować bowiem wskaźnik na stały obiekt (wskaźnik na stałą) lub stały wskaźnik na obiekt (stały wskaźnik na zmienną). Już wyjaśniam o co chodzi w tym całym zamieszaniu.
Wskaźnik na stałą deklarujemy w następujący sposób:
const <typ> *nazwa;
Deklaracja taka oznacza, że wskazywaną wartość możemy jedynie odczytywać,
natomiast nie wolno nam próbować zmieniać wartości wskazywanej przez wskaźnik:
int x=5,y; //deklaracja zmiennych
const int *ptr = &x;//dekaracja wskaźnika na stałą i jego inicjalizacja
y = *ptr; //poprawnie - możemy odczytywać zmienną wskazywaną przez wskaźnk
*ptr = 3; //błąd - nie wolno nam zapisywać do zmiennej wskazywanej przez wskaźnik
//mimo tego, że zmienna ta przy deklaracji nie miała modyfikatora const
Sposób deklaracji stałego wskaźnika na zmienną różni się tym, że słowo kluczowe const
występuje po znaku '*':
<typ> * const nazwa;
Zapis ten oznacza, że to wskaźnik jest stały a nie obiekt przez niego wskazywany. Oznacza to, że nie wolno nam zmieniać wartości wskaźnika czyli adresu na jaki on wskazuje. Zatem przy deklaracji wskaźnika musimy go od razu zainicjować.
Wolno nam za to zmieniać wartość wskazywaną przez taki wskaźnik:
int x,y;
int * const ptr = &x; //obowiązkowa inicjalizacja
*ptr = 5; //ok
ptr = &y; //błąd - nie wolno zmieniać wartości wskaźnika
Można także deklarować stałe wskaźniki na stałe. Taki wskaźnik dziedziczy cechy obu deklaracji:
int x,y;
const int * const ptr = &x;
y = *ptr; //ok - możemy czytać wskazywaną wartość
ptr = &y; //błąd - nie wolno zmieniać wartości wskaźnika
*ptr = y; //bląd - nie wolno zmieniać wskazywanej wartości
Otóż jeśli mamy zadeklarowany wskaźnik na stały obiekt to wolno nam jedynie wywoływać stałe metody takiego obiektu (funkcje zadeklarowane w obiekcie ze słowem kluczowym const, które zapewnia kompilator,
że funkcja taka nie będzie modyfikować zmiennych zawartych w obiekcie.
Struktury danych
Struktury danych pozwalają nam "zebrać" różne dane. Pozwala to na wygodniejsze operowanie danymi. Deklaracja struktury wygląda następująco:
struct <nazwa> {
... //deklaracja pól i metod strutury
};
polami struktury nazywamy wszystkie zmienne zawarte w strukturze danych, a metodami wszystkie funkcje, jakie posiada dana struktura.
Konstuktor to metoda (funkcja) w strukturze danych posiadająca taką samą nazwę jak typ naszej struktury. Jeżeli obiekt nie ma jawnie zadeklarowanego konstruktora (np. w naszym poprzednim przykładzie) to jest on tworzony automatycznie w czasie kompilacji (podobnie sytacja wygląda z operatorem kopiującym tzn. metodą "operator =()").
Konstutor jest wywoływany tylko w czasie tworzenia obiektu. Jeżeli przeciążyliśmy konstruktor (zadeklarowaliśmy kilka funkcji o różnych argumentach) to o wywołaniu konkretnego konstruktora decydują argumenty podane przy definicji naszego obiektu. Kompilator tak jak w przypadku zwykłego przeciążania funkcji postara się o wywołanie
konstruktora do którego najlepiej pasują podane argumenty. Jeśli ich nie ma wtedy wywoływany jest konstruktor nie posiadający argumentów.
Jeśli zadeklarowaliśmy choć jeden konstruktor to kompilator nie doda już za nas konstruktora, który nie posiada żadnych argumentów. W takim przypadku musimy już jawnie zadeklarować i zdefiniować taki konstruktor. Oczywiście nie jest on konieczny, ale bez niego nie możemy tworzyć obiektów bez podawania żadnych argumentów.
Jeżeli jawnie nie zadeklarujemy konstruktora kopiującego to jest on zawsze automatycznie dodany.
Konstuktor nie zwraca żadnego typu i w czasie jego deklaracji nie podajemy żadnego typu.
Destruktor to funkcja o nazwie identycznej z nazwą typu struktury poprzedzona znakiem tyldy "~". Destruktor nie zwraca żadnego typu ani nie posiada, żadnego argumentu. Jego deklarację (i definicję) również nie poprzedzamy żadną nazwą nazwą typu.
Jak można się domyślać destruktor wywoływany jest automatycznie gdy niszczony jest obiekt. Dzieje się tak gdy program wychodzi z bloku kodu w którym zadeklarowy był nasz obiekt. Jeżeli był on tworzony dynamicznie to destuktor wywoływany jest gdy użytkownik jawnie usuwa zmienną z pamięci. Destruktor możemy także wywołać jawnie - nie oznacza to jednak automatycznego zwolnienia miejca po obiekcie na rzecz którego został on wywołany.
ALGORYTM
Algorytm, opis rozwiązywania problemu (zadania) wyrażony za pomocą takich operacji, które wykonawca algorytmu rozumie i potrafi wykonać. Pierwsze opisy, które później nazywano algorytmami, dotyczyły rozwiązywania zadań matematycznych. Już w starożytnym Egipcie i Grecji stworzono wiele takich metod, które pozwalały rozwiązywać pewne zadania w sposób "algorytmiczny". Spośród nich najbardziej znane to opracowana przez matematyka gr. Euklidesa metoda znajdowania największego wspólnego dzielnika dwóch liczb naturalnych, zwany obecnie algorytmem Euklidesa, oraz sposób podziału kąta na dwie równe części za pomocą cyrkla i linijki, zw. bisekcją kąta.
Nazwa "algorytm" wywodzi się od nazwiska arabskiego matematyka i astronoma Alchwarizmiego (IX w.). W tłumaczeniu łacińskim pracy Alchwarizmiego poświęconej arytmetyce występuje on pod nazwiskiem Algoritmi; jej wersja arabska nie zachowa ła się (w odróżnieniu od pracy poświęconej algebrze).
Intuicyjnie algorytm kojarzy się z metodą rozwiązywania zadania, z przepisem postępowania czy ze schematem działania. Jednak nie każda metoda, nie każdy schemat jest algorytmem. Przyjmuje się, że algorytm powinien mieć wyraźnie określony początek (start), tzn. wskazaną operację (czynność), od której zaczyna się realizacja tego algorytmu, precyzyjnie określoną kolejność wykonywania poszczególnych operacji (działań) oraz wyróżniony koniec (stop). Wymaga się także, aby algorytm składał się ze skończonej liczby operacji (poleceń) sformułowanych w sposób jednoznaczny i możliwy do wykonania w skończonym (rozsądnym) czasie. Cały algorytm musi być sformułowany w sposób zrozumiały dla określonego wykonawcy, czy inaczej mówiąc, musi być napisany w języku zrozumiały dla danego wykonawcy.
Schemat blokowy
Jako przykład posłuży algorytm wyznaczania wartości całkowitej pierwiastka kwadratowego z danej liczby naturalnej n, czyli algorytmicznego obliczania wartości funkcji (sqrt(n)), gdzie n jest liczbą naturalną. Algorytm ten jest oparty na bardzo prostym pomyśle. Bierzemy liczbę naturalną i, a następnie sprawdzamy czy (i+1)²>n; Jeśli warunek ten nie jest spełniony, to bierzemy kolenją liczbę naturalną i dla niej sprawdzamy warunek. Jeżeli warunek jest spełniony, to i jest szukaną wartością funkci E(sqrt(n)). Przyjmuje się, że wykonawca tego algorytmu potrafi dodawać, podnosić do kwadratu i porównywać dwie liczby naturalne.
Algorytmy sortowania:
Sortowanie bąbelkowe
Sortowanie przez wybieranie
Sortowanie przez wstawianie
Szybkie sortowanie
Sortowanie polega na uporządkowaniu pewnej grupy elementów względem danego kryterium. Kryterium tym może być np. wielkość (przy sortowaniu liczb), kolejność słownikowa (w przypadku sortowania ciągu znaków), wielkość pliku (przy sortowaniu plików).Sortowanie jest bardzo ważną operacją zarówno w algorytmice, jak i przy codziennym użytkowaniu komputera. Korzystając z różnego typu baz danych w firmach, bez sortowania również ciężko by sobie było wyobrazić pracę. Podobnie, korzystają np. z książki adresowej, wyszukiwania w systemie operacyjnym, pośród wielu wpisów, znacznie łatwiej nam odnaleźć daną informację, jeśli informacje są w jakiś sposób ułożone.
Sortowanie bąbelkowe (ang. Bubble sort) często bywa uważane za najprostszy sposób sortowania.
Sprecyzujmy warunki sortowania:
Dane: n elementów oznaczonych x[1], x[2], x[3], ..., x[n] oraz operator porównania tych elementów, za pomocą którego możemy stwierdzić który z dwóch porównywanych elementów jest mniejszy, a który większy.
Wynik: n elementów uporządkowanych w taki sposób, że pierwszy element jest najmniejszy w sensie operatora porównania elementów, a ostatni jest elementem największym w sensie tego samego operatora. Sortowanie bąbelkowe to prosty algorytm sortowania o złożoności O(n2).
Niestety jest to algorytm mało wydajny i nie stosuje się go do dużych tablic (np. powyżej 1000 elementów).
Sortowanie bąbelkowe polega na porównywaniu dwóch sąsiednich elementów. Jeśli ich kolejność jest niepoprawna to są zamieniane miejscami.
Przykładowa tablica o elementach [3, 9, 5, 2, 4].
Zaczynamy od ostatniego elementu i sprawdzamy czy jest on mniejszy od poprzedniego. W tym przypadku 4>2 więc porównujemy
następną parę. 2<5 a więc zamieniamy je miejscami ([3, 9, 2, 5, 4]). Sprawdzamy kolejną parę - 9 i 2.
Ich kolejność jest "zła" więc zamieniamy ([3, 2, 9, 5, 4]). Ostatnia para także jest w złej kolejności.
Tablica w tym momencie wygląda następująco [2, 3, 9, 5, 4].
Zaczynamy sprawdzanie od początku (tym razem już jednak nie sprawdzamy ostatniej pary). Tablica będzie kolejno zmieniać się:
[2, 3, 9, 4, 5] -> [2, 3, 4, 9, 5] -> [2, 3, 4, 9, 5]
[2, 3, 4, 5, 9] -> [2, 3, 4, 5, 9]
[2, 3, 4, 5, 9]
Sortowanie przez wybór (selection sort)
Sortowanie przez wybór jest w zasadzie jednym z najprostszych do zrozumienia i zaimplementowania w danym języku programowania algorytmem sortowania.
Polega ono na wyszukaniu najmniejszego elementu spośród nieposortowanych elementów i ustawniu go na pierwszej pozycji. Następnie znowu wyszukujemy najmniejszy element i ustawiamy go na drugiej pozycji, itd...
Złożoność obliczniowa O(n2).
Przykładowa implementacja w c++:
void selectionSort(int *tablica, int rozmiar)
{
int i,j,m;
for(i=0; i<rozmiar-1 ;++i) //od pierwszego elementu do przedostatniego...
{
m = i; //i-ty element przyjmujemy jako najmniejszy
for(j=i+1; j<rozmiar ;++j) //od następnego do ostaniego elementu
if(tablica[j] < tablica[m]) m=j; //jeżeli j-ty jest mniejszy to ...
j = tablica[i]; //ustawiamy element najmniejszy na i-tej pozycji
tablica[i] = tablica[m];
tablica[m] = j;
}
Sprecyzujmy warunki sortowania:
Dane: n elementów oznaczonych x[1], x[2], x[3], ..., x[n] oraz operator porównania tych elementów, za pomocą którego możemy stwierdzić który z dwóch porównywanych elementów jest mniejszy, a który większy.
Wynik: n elementów uporządkowanych w taki sposób, że pierwszy element jest najmniejszy w sensie operatora porównania elementów, a ostatni jest elementem największym w sensie tego samego operatora.
Sortowanie przez wstawianie
Sortowanie przez wstawianie należy do prostych algorytmów sortowania o złożoności O(n2).
Polega ono na tym, że bierzemy kolejne elementy do posortowania i wstawiamy je pomiędzy posortowane już elementy na odpowiedniej pozycji.
Weźmy przykładową tablicę o elementach [3,9,5,2,4].
Zaczynamy od drugiego elementu tablicy i sprawdzamy czy jest on mniejszy od elemetu po lewej stronie. Jeśli tak to zamieniamy je miejscami i sprawdzamy następny, aż napotkany element będzie miał wartość mniejszą od obecnie wstawianego.
Po pierwszym kroku 9-tka pozostanie na swojej pozycji ponieważ nie jest mniejsza od swojego lewego sąsiada.
Teraz bierzemy 5-tke i sprawdzamy czy jest mniejsza od poprzedniego elementu. Ponieważ jest to zamieniamy miejscami te elementy. Następnie sprawdzamy czy znowu 5-tka jest mniejsza od poprzednika - nie jest a więc zostaje na tej pozycji (tablica wygląda tak [3,5,9,2,4]).
Następnie bierzemy kolejny element (2-ke) i dopóki poprzednie elementy są większe od 2-ki to zamieniamy je miejscami. Tablica zmieni się następująco:
[3,5,9,2,4] -> [3,5,2,9,4] -> [3,2,5,9,4] -> [2,3,5,9,4]
Ostatni element podobnie zamieniamy miejscami z poprzednikami, aż ich wartość będzie niewiększa od wstawianego elementu.
Szybkie sortowanie
Szybkie sortowanie polega na tym, że brany jest pierwszy (w niektórych implementacjach może być inny) element tablicy a następnie jest ustawiany na ostatecznej pozycji. Osiąga się to przerzucając wszystkie mniejsze elementy tablicy na jego lewą stronę, a większe na prawą. Następnie rekurencyjnie sortuje się lewą część tablicy do danego elementu, potem prawą część od danego elementu.Sortowanie szybkie (ang. Quick sort) jest uważane za najszybszą w praktyce metodę prostego sortowania. Algorytm jest łatwy do zrozumienia, trochę trudniejsza jest implementacja. Na bazie tego algorytmu powstają również mieszane metody sortowania.