Programowanie  GÅ‚owacki  podsumowanie tego badziewia
Wykład 2 (reprezentacja danych)
Zmienne GLOBALNE  deklarowane na początku, przed funkcją main(), dostępne w każdym
miejscu programu
Zmienne LOKALNE  dostępne tylko w bloku gdzie zostały zdeklarowane (np. w funkcjach),
mają charakter tymczasowy, zanikają po zakończeniu funkcji
Zmienne STATYCZNE  dostępne tylko w bloku (funkcji) ale zachowują swoją wartość
podczas ponownego wywołania funkcji
Typy zmiennych:
int Typ całkowity 4 bajty
float Typ zmiennoprzecinkowy (7 4 bajty
znaków po przecinku)
double Typ zmiennoprzecinkowy 8 bajtów
podwójnej długości (15
znaków po przecinku)
char Typ znakowy 1 bajt
void Typ pusty -
Definicja przez typedef  jak nie chce nam się ciągle wpisywać długiej nazwy typu; tworzony
jest SYNONIM, a nie nowy typ,
np. typedef unsigned short int USHORT  od teraz możemy używać USHORT jako typu
zmiennej
Stałe
1. Literały  wpisywane bezpośrednio w danym miejscu programu, np. int a=9 (9 jest
literałem)
2. Stałe symboliczne
a. #define a=9; stała nie ma określonego typu
b. const int=9  kod jest łatwiejszy dla kompilatora, bardziej odporny na błędy
3. Stałe wyliczeniowe  enum,
np. enum Kolor {red, green, blue, yellow}  wtedy red=0, green=1, blue=2, yellow=3;
sam  Kolor to jest nowa stała wyliczeniowa
1
Wykład 3 (rzutowanie typów)
Przestrzeń nazw std jest wbudowana
1. Definicja globalna  przed main deklarujemy - using namespace std
2. Definicja lokalna  w main lub innych funkcjach - using std::cout
3. Bezpośrednie wkazanie przestrzeni nazw  std::cout <<  Coś tam
Zmienne znakowe char  1 bajt; wystarczą do przechowywania jednej z 256 wartości (28) 
kod ASCII
Znaki specjalne w C++ (moim zdaniem znaczÄ…ce)
\n Nowa linia
\t Tabulator
Konwersje / rzutowanie typów
1. Niejawne  próba automatycznego dopasowania przez kompilator typu zmiennych
do wykonywanej operacji
2. Jawne  wywoływane świadomie przez programistę; są 2 formy zapisu:
a. typ(wyrażenie)  np. int(1.454);
b. (typ)wyrażenie  np. (int)1.454;
Wykład 3add (operacje wejścia/wyjścia)
W języku C :
1. printf  wypisanie czegoś na ekranie (strasznie się o tym rozpisał& .)
2. puts  działa jak printf, ale może działać szybciej, zawsze na końcu przechodzi do
wejścia
nowej linii
3. fputs  jak puts, ale nie przechodzi do nowej linii
4. putchar  wypisywanie pojedynczych znaków
5. scanf  pobieranie danych od użytkownika; niezbędny operator &, który oznacza
przekazanie do funkcji adresu zmiennej
6. gets ()  nie używać :D
wyjścia
7. fgets ()  czyta tekst do napotkania znaku przejścia do nowej linii
8. getchar ()  wczytuje jeden znak z klawiatury
Stosowanie funkcji z rodziny printf/scanf +/-
Plusy Minusy
Są bardzo wygodne Trudno je rozszerzyć o nowe typy
Cały szablon w jednym miejscu Kompilator nie zawsze może sprawdzić ich
poprawność
Umożliwiają łatwe dodawanie informacji, Konieczna znajomość typu każdego
formatowanie przetwarzanego wyrażenia
2
W języku C++ :
1. cout  strumień standardowego wyjścia, domyślnie skierowany na ekran
2. cin  strumień standardowego wejścia, domyślnie dołączony do klawiatury
3. cerr  komunikaty o błędach (errors), skierowane na ekran
4. clog  komunikaty o dzienniku (log), skierowane na ekran
Operatory << >>
Flagi stanu formatowania, np.
Modyfikacje flag formatowania
1. left  justowanie lewe
2. right  justowanie prawe
1. Użycie prostych funkcji setf, unsetf
3. internal  justowanie środkowe
2. Użycie złożonych funkcji, np. width,
4. dec  konwersja dziesiętna
precision, fill - (cout.width(8))
5. hex  konwersja ósemkowa
3. Manipulatory
6. scientific  notacja wykładnicza
7. fixed  notacja zwykła
Wykład 4 (instrukcje decyzyjne, cykliczne)
Operatory arytmetyczne: +, -, =, *, /, %, ++& ..
Operatory relacyjne: >, <, >=, <=, ==, !=
Operatory logiczne: &&(koniunkcja AND), II (alternatywa OR), ! (negacja NOT)
Operatory bitowe:
Koniunkcja - & Alternatywa  I
10110011 (179) 00100010 (34)
00100110 (38) 01000001 (65)
-------- --------
00100010 (34) 01100011 (99)
Przesunięcie w lewo << Przesunięcie w prawo >>
00111100 >> 2 = 00001111
00001111 << 3 = 01111000
10000000 >> 3 = 00010000
00000001 << 5 = 00100000
Inkrementacja ++
Dekrementacja 
3
Instrukcje decyzyjne:
1. if
2. if & else
3. switch (break, default)
4. while (continue)
5. do & while (continue, break)
6. for
Wykład 5 (funkcje)
Deklaracja funkcji  na początku, samo wypisanie nazwy i argumentów
Definicja funkcji  na końcu, zawiera instrukcje
Przekazywanie argumentów:
1. przez wartość (klasycznie)
2. przez referencje (& - dostęp do adresu zmiennej, zmieniasz wartość globalną)
Domyślne argumenty funkcji  podawane już przy deklaracji funkcji np.
void Suma (int a=20, int b=4, int c=8)
Możemy pominąć tylko wszystkie argumenty począwszy od tego którego pominiemy jako
pierwszy.
Przeciążenie funkcji  nadajemy funkcjom te same nazwy, różnią się jednak ilością i typem
parametrów
Wykład 7 (tablice i wskaz
niki)
Zmienne wskaz
nikowe  wartościami wskaz
ników są adresy wskazujące na miejsce w
pamięci operacyjnej obiektu
Wskaz
nik zajmuje 4 bajty pamięci (2 bajty adresu segmentu i 2 bajty adresu offsetu)
int *w  deklaracja zmiennej wskaz
nikowej
int a=10
wa=&a  w zaczyna wskazywać na  a
cout << aa ==== cout << *w
Tablice  uporządkowany zbiór obiektów tego samego typu, jednowymiarowe to wektory, a
wielowymiarowe to macierze
Tablice sÄ… indeksowane od 0!!
Nazwa tablicy podaje adres  jest wskazaniem na pierwszy element tablicy o indeksie 0
Element tab[0]=*tab
4
Element tab[3] == *(tab+3) <- w tablicy jednowymiarowej
Element tab[2][2] == *(*(tab+2)+2) <- w tablicy wielowymiarowej
Wykład 8 (tablice znakowe)
Teksty przechowuje siÄ™ w tablicach typu char
1. pojedyncze znaki w pojedynczych apostrofach  Z
2. wyrazy/zdania w cudzysłowie  MARCIN
char Imie [] =  MARCIN ;
char Imie [] = {  M ,  A ,  R ,  C ,  I ,  N ,  \0 }
6 znaków, ale 7 elementów
 \0  specjalny znak oznaczający koniec tekstu w tablicy, trzeba o tym pamiętać, gdy
zadajemy rozmiar tablicy
Gotowe funkcje przetwarzania tekstów:
1. size_t strlen (char str)  oblicza długość tekstu
2. int strcmp (char str1, char str2)  porównuje 2 teksty (który jest dłuższy)
3. int strncmp (char str1, char str2, n)  porównuje 2 teksty do n-tego znaku
4. int strcpy (char przeznaczenie, char z
ródło)  kopiowanie dwóch tekstów

5. int strncpy (char przeznaczenie, char z
ródło, n)  kopiowanie dwóch tekstów do n-
.>
tego znaku
6. char strcat (char przeznaczenie, char z
ródło)  kopiowanie przez dopisanie na końcu
7. char strncat (char przeznaczenie, char z
ródło, n)  kopiowanie przez dopisanie na
końcu do n-tego znaku
8. int toupper (char c)  mała litera na dużą
9. int tolower (char c)  duża litera na małą

10. int atoi (char c)  ASCII do int
Konwersje
11. int atol (char c)  ASCII do long
typów
12. int atof (char c)  ASCII do double
Funkcja cin.getline ()  umożliwia ustawienie granicznej liczby pobieranych znaków, aby nie
przekroczyć pojemności tablicy
5
Wykład 9 (struktury, unie, przeciążenia)
Struktura  nowy typ zdefiniowany przez programistę, ale pośrednio lub bezpośrednio
składa się z typów wbudowanych.
Operator  . (kropka)  dostęp do zmiennych struktury
Operator  ->  wskaz
nik na strukturÄ™
Unia  dane przetwarzane pojedynczo we wspólnej przestrzeni pamięci; ogólnie mało
praktyczna.
Ma rozmiar największego elementu.
Przeciążenie operatorów (w sumie nie ogarniam tego :D )
arg1 @ arg2
typ operatora @ (typ arg1, typ arg2)
Nie można przeciążyć:
. .* :: ?:
Wykład 10 (zmienne i struktury dynamiczne)
new  dynamicznie tworzy zmienną w trakcie działania programu
delete  kasuje zmiennÄ… utworzonÄ… przez new
new typ zwraca WSKAy
NIK na nowo utworzonÄ… zmiennÄ… danego typu
int *wd = new int;
Int x = (*wd)++ <- pamiętać o nawiasach!
Tablice tworzymy dynamicznie ale musimy zadać rozmiar!
Dynamiczne struktury danych:
1. Stos  posiada dno i wierzchołek, dane ułożone są w sekwencji od dna do
wierzchołka, nowe dane zapisywane są na szczycie i stają się nowym wierzchołkiem,
pobieranie danych w odwrotnej kolejności (LIFO  last in first out)  pobierane od
góry do dołu
2. Kolejka  posiada początek i koniec, dane ułożone od końca, nowe dane zapisywane
na końcu, a pobieranie zachodzi od początku (FIFO  first in first out)
3. Lista  ciÄ…g zmiennych dynamicznych powiÄ…zanych wskazaniami, zmienne posiadajÄ…
pole wskaz
nikowe (na inne zmienne), powiązania mogą być jedno- lub
dwukierunkowe
6
Wykład 11 (operacje na plikach)
Plik jest identyfikowany w każdym systemie operacyjnym w postaci nazwy
Plik jest sekwencyjny od początku do końca. Przy zapisie/odczycie operacje odbywają się na
aktualnej pozycji pliku
Plik przechowuje dane o określonych typach
1. Pliki tekstowe, podczas dostępu następuję konwersja znaków specjalnych
2. Pliki binarne  brak konwersji
#include
Odczyt ifstream
Zapis ofstream
7
Wykład 12 (wskaz
niki na funkcje, rekurencja)
Wskaz
niki do funkcji  zawierajÄ… adresy
typ (*wskaz
nik)(arg1, arg2,& .)
Rekurencja  wywołanie funkcji w treści innej (lub tej samej) funkcji
1. Bezpośredni  funkcja wywołuje samą siebie
2. Pośrednia  funkcja wywołuje inną funkcję
Metoda iteracyjna  bez funkcji, poprzez pętle, w ciele main()
Metoda rekurencyjna  funkcja w funkcji w funkcji&
Bardziej złożone algorytmy rekurencyjne mogą szybko zużyć całą przestrzeń pamięci stosu i
zakłócić działanie programu
Wykład 13 (drzewa)
Drzewo jest strukturą przypominającą graf, składa się z węzłów i połączeń miedzy węzłami
(krawędziami).
Korzeń jest jedynym węzłem, który nie posiada węzłów poprzednich.
Dla każdego innego węzła określany jest dokładnie jeden węzeł poprzedni.
Węzły ostatnie nazywane są liśćmi.
Węzeł poprzedni == przodek
Węzły dowiązane (następne) == potomek
Głębokość węzła u  liczba węzłów przez które trzeba przejść od korzenia do do węzła u (z
korzeniem włącznie, sam korzeń ma głębokość 1)
Wysokość węzła u  maksymalna liczba węzłów po drodze począwszy od u do najbardziej
oddalonego liścia w jego poddrzewie (z węzłem u włącznie)
Stopień węzła  liczba jego bezpośrednich następników
Stopień drzewa  maksymalny stopień węzłów drzewa
8
 Na przykładzie:
Głębokość drzewa  5
Stopień drzewa  3
Drzewo binarne  drzewo, w którym liczba następnych elementów wynosi dokładnie 2
(drzewo stopnia 2).
W drzewie binarnym każdy z węzłów zawiera wskazania na dwa inne węzły: lewy i prawy.
Kopiec (stog)  uporządkowane drzewo binarne spełniające tzw. warunek kopca tzn. każdy
następnik jest nie większy (może być równy!) od poprzednika
1. W korzeniu jest największy element
2. Na ścieżkach od korzenia do liścia elementy są posortowane nierosnąco (max-heap)
lub niemalejÄ…co (min-heap)
3. Drzewo musi być kompletne  wypełnione od lewej do prawej i kompletne na
wszystkich poziomach (za wyjątkiem ostatniego który może być niedopłeniony od
prawej)
4. Tablica posortowana w porzÄ…dku nierosnÄ…cym jest kopcem max-heap
9
Binarne drzewo poszukiwań  BST  elementy są uporządkowane wg ustalonego klucza
Wszystkie węzły lewego poddrzewa są wartością mniejszą od danego węzła, a wszystkie
węzły prawego poddrzewa są wartością większą lub równą
Metody przeszukiwania drzewa (K-korzeń, L-lewy
węzeł, P-prawy węzeł)
1. Pre-order: KLP
2. In-order: LKP
3. Post-order: LPK
4. Poziomami
10
Wykład 14 (złożoność obliczeniowa, algorytmy sortowania)
Złożoność obliczeniowa algorytmu  ilość zasobów komputera jakiej potrzebuje algorytm,
inaczej: złożoność czasowa, złożoność pamięciowa
Za jednostkę złożoności pamięciowej przyjmuję się np. bajt
Liczba wykonań operacji dominującej jest proporcjonalna do wykonań wszystkich operacji
Złożoność (niewygodna w użyciu, zależy od komputera):
1. Pesymistyczna  w najgorszym wypadku
2. Oczekiwana  średnia, wartość zmiennej losowej
Złożoność asymptotyczna:
1. Notacja O
2. Notacja © (duże omega)
3. Notacja Ś (duże teta)
Sortowanie  proces ustawieniu zbioru elementów w określonym porządku liniowym
1. Sortowanie wewnętrzne  sortowanie tablic
2. Sortowanie zewnętrzne  sortowanie plików
Dobra metoda sortowania powinna zachować porządek względny obiektów identycznych 
stabilność algorytmu
Algorytm sortowania Optymistyczne Åšrednie Pesymistyczne
BÄ…belkowe (BubbleSort) n n2 n2
Wstawianie (InsertionSort) n n2 n2
Wybieranie (SelectionSort n2 n2 n2
Scalanie (MergeSort) n log n n log n n log n
Szybkie (QuickSort) n log n n log n n2
Kopcowanie (HeapSort) n log n n log n n log n
Zliczanie (CountingSort) n+k n+k n+k
11
 Sortowanie BÄ…belkowe (BubbleSort)
Sortowanie przez Wstawianie (InsertionSort)
Sortowanie przez Wybieranie (SelectionSort)
12
Sortowanie szybkie (QuickSort) 
podział tablicy, wybór piv ota
Sortowanie stogowe (HeapSort)
Sortowanie przez Scalanie (MergeSort)
13