1

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
znaków po przecinku)

4 bajty

double

Typ zmiennoprzecinkowy
podwójnej długości (15
znaków po przecinku)

8 bajtów

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

2

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 (2

8

) –

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 <stdio.h> :

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

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
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,
formatowanie

Konieczna znajomość typu każdego
przetwarzanego wyrażenia

wejścia

wyjścia

3

W języku C++ <iostream> :

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.

1. left – justowanie lewe
2. right – justowanie prawe
3. internal – justowanie środkowe
4. dec – konwersja dziesiętna
5. hex – konwersja ósemkowa
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 - &

10110011

(179)

00100110

(38)

--------

00100010

(34)

Alternatywa – I

00100010

(34)

01000001

(65)

--------

01100011

(99)

Przesunięcie w lewo <<

00001111 << 3 = 01111000
00000001 << 5 = 00100000

Przesunięcie w prawo >>

00111100 >> 2 = 00001111
10000000 >> 3 = 00010000

Inkrementacja ++

Dekrementacja –

Modyfikacje flag formatowania

1. Użycie prostych funkcji setf, unsetf
2. Użycie złożonych funkcji, np. width,

precision, fill - (cout.width(8))

3. Manipulatory <iomanip>

4

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 wskaźniki)

Zmienne wskaźnikowe – wartościami wskaźników są adresy wskazujące na miejsce w
pamięci operacyjnej obiektu

Wskaźnik zajmuje 4 bajty pamięci (2 bajty adresu segmentu i 2 bajty adresu offsetu)

int *w – deklaracja zmiennej wskaź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

5

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 źródło) – kopiowanie dwóch tekstów
5. int strncpy (char przeznaczenie, char źródło, n) – kopiowanie dwóch tekstów do n-

tego znaku

6. char strcat (char przeznaczenie, char źródło) – kopiowanie przez dopisanie na końcu
7. char strncat (char przeznaczenie, char ź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
11. int atol (char c) – ASCII do long
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

<ctype.h>

<string.h>
.>

Konwersje

typów

6

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 ‘->’ – wskaź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 WSKAŹ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 wskaźnikowe (na inne zmienne), powiązania mogą być jedno- lub
dwukierunkowe

7

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 <fstream>

Odczyt ifstream

Zapis ofstream

8

Wykład 12 (wskaźniki na funkcje, rekurencja)

Wskaźniki do funkcji – zawierają adresy

typ (*wskaź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

9

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

10

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

11

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

n

2

n

2

Wstawianie (InsertionSort)

n

n

2

n

2

Wybieranie (SelectionSort

n

2

n

2

n

2

Scalanie (MergeSort)

n log n

n log n

n log n

Szybkie (QuickSort)

n log n

n log n

n

2

Kopcowanie (HeapSort)

n log n

n log n

n log n

Zliczanie (CountingSort)

n+k

n+k

n+k

12

Sortowanie Bąbelkowe (BubbleSort)

Sortowanie przez Wstawianie (InsertionSort)

Sortowanie przez Wybieranie (SelectionSort)

13

Sortowanie szybkie (QuickSort) –
podział tablicy, wybór piv’ota

Sortowanie stogowe (HeapSort)

Sortowanie przez Scalanie (MergeSort)