AJS

AJS

Programiści na ogół wyróżniają

pięć obszarów pamięci

1. obszar zmiennych globalnych
2. wolna pamięć (sterta, stos - heap)

np. zmienne

dynamiczne

3. rejestry

do wewnętrznego zarządzania funkcjami

4. kod programu

program

5. stos procesora (stos - stack)

zmienne lokalne wraz z

parametrami funkcji

AJS

AJS

Zmienne

-reprezentują pewien obszar pamięci o ściśle
określonym rozmiarze,

-istnieją od momentu przydzielenia pamięci do momentu
jej zwolnienia,

Podział zmiennych ze względu na zasięg i widoczność:

lokalne

globalne

Podział zmiennych ze względu na czas trwania:

statyczne

pamięć przydzielana statycznie

tryby

automatyczne

pamięć przydzielana automatycznie

zarządzania

dynamiczne

pamięć przydzielana dynamicznie

pamięcią

AJS

AJS

Zarządzanie
pamięcią

automatyczne przydzielanie pamięci

–

dotyczy zmiennych

lokalnych, można użyć słów kluczowych

auto

lub

register

pamięć

przydzielana jest przez system operacyjny w momencie napotkania
definicji zmiennej i automatycznie zwalniana po zakończeniu bloku
zawierającego definicję tej zmiennej

auto

– jest przyjmowany domyślnie

register

– informuje kompilator o umieszczeniu zmiennej w rejestrach

statyczne przydzielanie

pamięci

–

dotyczy zmiennych

globalnych oraz zmiennych zadeklarowanych z użyciem słów
kluczowych

static

lub

extern

, pamięć przydzielana jest jednorazowo od

momentu napotkania definicji zmiennej do momentu zakończenia
programu

static –

zmienne są widoczne tylko w obrębie modułu,

extern

- informacja dla kompilatora że zmienna została

zadeklarowana w innym module i tam przydzielono jej pamięć

AJS

AJS

#include<iostream.h>
#include<conio.c>
int zmiana(void);
int a;

//zmienna globalna

extern int d;
main()
{
static float c;
a=1;
cout<<"wartosc zmiennej a="<<a<<endl;
a=zmiana();
cout<<"wartosc zmiennej a="<<a<<endl;
getch();
return 0;
}
int zmiana(void)
{
int b=100;

//zmienna lokalna

a+=b;
return a;
}

AJS

AJS

Zarządzanie
pamięcią

Programista nie ma bezpośredniego wpływu na
tworzenie i usuwanie zmiennych statycznych i
automatycznych

dynamiczne przydzielanie pamięci

–

umożliwia programiście

tworzenie i usuwanie zmiennych a tym samym pełne sterowanie
czasem ich istnienia. Zmienne przechowywane są w specjalnie
wydzielonym obszarze pamięci zwanym stosem zmiennych
dynamicznych (ang. heap). Do przydzielania i zwalniania służą słowa
kluczowe

new

i

delete.

new –

do

przydzielania pamięci dynamicznej

delete –

do zwalniania pamięci dynamicznej

Dostęp do zmiennych dynamicznych umożliwiają

wskaźniki

AJS

AJS

Zarządzanie
pamięcią

dynamiczne przydzielanie pamięci

Składnia

int *p;

p=new int (45);

lub

int *p=new int (45);

delete p;

deklaracja
wskaźnika

alokacja pamięci

dynamicznej na stosie

zainicjowanie wartości

zwalnianie pamięci

AJS

AJS

#include<iostream.h>
#include<conio.c>

main()
{
int *p=new int (45);
if(p==0)

//zabezpieczenie przed brakiem alokacji pamięci

{
cout<<"nie przydzielono pamieci"<<endl;
return 1;
}
cout<<"*p="<<*p<<endl;
cin>>*p;
cout<<"*p="<<*p<<endl;
delete p;
cout<<*p;
getch();
return 0;
}

AJS

AJS

Dynamiczna alokacja tablic

Zarządzanie
pamięcią

Składnia

int *p;

p=new int [10];

lub

int *p=new int [10];

delete []p;

deklaracja
wskaźnika

alokacja pamięci

dynamicznej na stosie

wymiar tablicy

zwalnianie pamięci

AJS

AJS

#include<iostream.h>
#include<conio.c>

main()
{
int i;
int *p=new int[10];
if(p==0)

//zabezpieczenie przed brakiem alokacji

pamięci

{
cout<<"nie przydzielono pamieci"<<endl;
return 1;
}
for(i=0;i<10;i++)
{
p[i]=i;
cout<<p[i]<<endl;
}
delete []p;
getch();
return 0;
}

AJS

AJS

Rekurencja

(rekursja)

pewien mechanizm rozwiązywania problemów

Rozwiązanie rekurencyjne charakteryzuje się
następującymi cechami

-zakończenie algorytmu jest jasno określone,

-"duży" problem został rozłożony na problem
elementarny (który umiemy rozwiązać) i na problem o
mniejszym stopniu skomplikowania.

AJS

AJS

Funkcje

rekurencyjne są

to funkcje, które

wywołują same

siebie.

Funkcje rekurencyjne

muszą zawsze zawierać

warunek stopu

(zatrzymania)

AJS

AJS

Problem

Znaleźć w tablicy składającej się z n liczb

całkowitych liczbę x

Jak postępować w sposób rekurencyjny:

1. Wziąć pierwszy niezbadany element tablicy n-

elementowej,

2. Jeśli aktualnie analizowany element jest równy x to:

wypisz "sukces" i zakończ;

w przeciwnym wypadku

zbadaj pozostałą część tablicy n-1-elementowej;

Warunkiem zakończenia programu jest albo znalezienie x albo wyjście

poza obszar poszukiwań.

AJS

AJS

#include <iostream.h>
#include <conio.h>
const

n=10;

int

tab[n]={1,2,3,2,-7,44,5,1,0,-3};

void szukaj(int tab[n],int lewa,int prawa,int x)

// lewa, prawa = lewa i prawa

granica obszaru poszukiwan

// tab = tablica

{

// x = wartosc do odnalezienia

if (lewa>prawa)
cout << "Element " << x << " nie zostal odnaleziony\n";

else

if (tab[lewa]==x)

cout << "Znalazlem szukany element "<< x << endl;

else

szukaj(tab,lewa+1,prawa,x);

}
void main()
{
clrscr();
szukaj(tab,0,n-1,7);
szukaj(tab,0,n-1,5);
getch();
}

Funkcja wywołuje samą
siebie

Deklaracja i
definicja funkcji
rekurencyjnej

AJS

AJS

Jak wykonują się programy rekurencyjne

1 dla n=0

n!=

n*(n-1)! dla n>=1

unsigned

long

int

silnia(int x)

{
if (x==0)

return 1;

else

return x*silnia(x-1);

}

Funkcja wywołuje samą
siebie

AJS

AJS

Drzewo wywołań funkcji silnia(4)

4*3

!

x==

0

nie!

I

3*2

!

x==

0

nie!

II

2*1

!

x==

0

nie!

II

I

1*0

!

x==

0

nie!

IV

1

x==

0

tak!

V

AJS

AJS

Niebezpieczeństwa rekurencji

-czasami

znaczna

część

obliczeń

jest

wykonywana więcej niż jeden raz,

-przepełnienie stosu (stack overflow), programy
rekurencyjne

są

zazwyczaj

pamięciożerne

(zawieszenie komputera)

:nieprawidłowe

lub

niejasne

określenie warunków zakończenia programu,

:brak pamięci

-nieskończona ilość wywołań rekurencyjnych,

AJS

AJS

#include <iostream.h>
int StadDoWiecznosci(int n)

//deklaracja i

definicja funkcji

{
if (n==1)
return 1;
else

if ((n %2) == 0) // n parzyste
return StadDoWiecznosci(n-2)*n;
else
return StadDoWiecznosci(n-1)*n;

}
void main()
{
int x;
cout<<"Podaj wartosc x:";
cin>>x;
cout << StadDoWiecznosci(x) << endl;

//wywołanie funkcji

}

Proces
upraszczania nie
doprowadzi do
przypadku
elementarnego
czyli n=1

nieskończona

ilość

wywołań

rekurencyjnych

AJS

AJS

Algorytmy sortowania

Sortowanie wewnętrzne –używanie wyłącznie pamięci

wewnętrznej komputera

sortowanie przez wstawianie (insert),

sortowanie bąbelkowe (bubble),

sortowanie szybkie (quicksort).

AJS

AJS

Sortowanie przez wstawianie (insert),

Metoda ta jest informatyczną techniką

sortowania analogiczną do techniki stosowanej

przez graczy przy układaniu kart

2

3

7

9

1
0

6

8

5

4

2

3

7

9

1
0

6

8

5

4

Karty
posortowane

Karty do
posortowania

AJS

AJS

#include <iostream.h>
#include <conio.h>
void wstawianie(int *tab);
const inst n=13;
int tab[n]={40,2,1,12,6,18,20,29,32,23,34,39,41};
void main()
{
clrscr();
cout<<"Tablica przed sortowaniem"<<endl;
for (int i=0;i<n;i++)
cout << tab[i] <<" ";
cout << endl;
wstawianie(tab);
cout<<"Tablica po sortowaniu"<<endl;
for (i=0;i<n;i++)
cout << tab[i] <<" ";
cout << endl;
getch();
}

Sortowanie przez wstawianie (insert) -

program

AJS

AJS

void wstawianie(int *tab)
{
for(int i=1; i<n;i++)
{
int j=i;

//

0..i-1 jest juz

posortowane

int tymczas=tab[j];
while ((j>0) && (tab[j-1]>tymczas))
{
tab[j]=tab[j-1];
j--;
}
tab[j]=tymczas;
}
}

Sortowanie przez wstawianie (insert) –

program cd.

AJS

AJS

Sortowanie bąbelkowe (bubble),

W sortowaniu bąbelkowym analizowane są ze sobą zawsze

dwa sąsiadujące elementy i jeśli nie są uporządkowane to

następuje ich zamiana

4
0
2
3
9
6
1
8
4
2

0

2

4
0
4
3
9
6
1
8
2

0

2

4

4
0
6
3
9
1
8
2

0

2
4

6

4
0
1
8
3
9
2

0

2
4
6

1
8

4
0
2
0
3

9

2
4
6
1
8

2
0

4
0
3

9

2
4
6
1
8
2
0

3
9

4

0

0

1

2

3

4

5

6

indeks w
tablicy

etapy sortowania

0 1 2 3 4
5 6

AJS

AJS

#include <iostream.h>
#include <conio.h>
const int n=7;
int tab[n]={40,2,39,6,18,4,20};
void babelki(int *tab);
void main()
{
clrscr();
cout<<"Tablica przed

sortowaniem"<<endl;
for (int i=0;i<n;i++)
cout << tab[i] <<" ";
cout << endl;
babelki(tab);
cout<<"Tablica po sortowaniu"<<endl;
for (i=0;i<n;i++)
cout << tab[i] <<" ";
cout << endl;
getch();
}

Sortowanie bąbelkowe (bubble) - program

AJS

AJS

void babelki(int *tab)

{

for (int i=1;i<n;i++)

{

for (int j=n-1;j>=i;j--)

if (tab[j]<tab[j-1])

{

//zamiana

int tmp=tab[j-1];

tab[j-1]=tab[j];

tab[j]=tmp;

}

}

}

Sortowanie bąbelkowe (bubble) – program

cd.

AJS

AJS

"Puste przebiegi" -

Niekorzystne konfiguracje danych

Sortowanie bąbelkowe (bubble) – wady

void ShakerSort(int *tab)
{
int lewa=1,prawa=n-1,k=n-1;
do
{
for(int j=prawa; j>=lewa; j--)
if(tab[j-1]>tab[j])

{ zamiana(tab[j-1],tab[j]);

k=j; }

lewa=k+1;
for(j=lewa; j<=prawa; j++)
if(tab[j-1]>tab[j])

{ zamiana(tab[j-1],tab[j]);
k=j; }

prawa=k-1;
}
while (lewa<=prawa);
}

AJS

AJS

Sortowanie szybkie (quicksort)

Procedura sortowania dzieli się na :

- część służącą do właściwego sortowania, która nic nie

robi tylko wywołuje sama siebie zapewniając "sklejanie"

wyników cząstkowych,
- procedurę (funkcji) rozdzielania elementów tablicy

względem pewnej komórki służącej za oś podziału

element<'P'

element

osiowy 'P'

element >='P'

Podział tablicy w metodzie

quicksort

AJS

AJS

Zasada działania procedury

quicksort

'P'

<'P'

'P'

>='P'

quicks
ort

quicks
ort

quicks
ort

ETAP I

ETAP
II

AJS

AJS

2
9

4
0

2 1 6 1

8

2
0

3
2

2
3

34 39 41

2
9

2 1 6 1

8

2
0

2
3

4
0

3
2

3
4

3
9

4
1

1

6 1

8

2
0

2
3

2

4
0

3
2

3
4

3
9

4

1

AJS

AJS

Zwięzły zapis procedury quicksort

void quicksort (int *tab, int lewa, int prawa)
{
if (lewa<prawa)

{
int m;
//podziel tablicę względem elementu osiowego;
// P=pierwszy element, czyli tab[lewa];
//pod koniec podziału element 'P' zostanie
//przeniesiony do komórki numer 'm';
quicksort(tab,lewa,m-1);
quicksort(tab,m+1,prawa);
}

}

Wywołania
rekurencyjne

AJS

AJS

#include <iostream.h>
#include <conio.h>
const int n=15;
int

tab[n]={34,56,23,40,29,2,1,6,18,20,32,34,39

,23,41};
void zamiana(int &a,int &b);
void quicksort(int *tab,int lewa, int prawa);
void main()
{
clrscr();
cout<<"Tablica przed sortowaniem"<<endl;
for (int i=0;i<n;i++)
cout << tab[i] <<" ";
cout << endl<<endl;
quicksort(tab,0,n-1);
cout<<"Tablica po sortowaniu"<<endl;
for (i=0;i<n;i++)
cout << tab[i] <<" ";
cout << endl;
getch();
}

AJS

AJS

Funkcja zamiana

void zamiana(int

&a,int &b)
{
int tymczas=a;
a=b;
b=tymczas;
}

void quicksort(int *tab,int lewa,

int prawa)
{
if (lewa < prawa)

{
int m=lewa;
for(int

i=lewa+1;i<=prawa;i++)

if

(tab[i]<tab[lewa])

zamiana(tab[+

+m],tab[i]);

zamiana(tab[lewa],tab[m]);

quicksort(tab,lewa,m-1);

quicksort(tab,m+1,prawa);

}

}

Procedura (funkcja)

quicksort

AJS

AJS

Algorytmy przeszukiwania

przeszukiwanie liniowe

przeszukiwanie binarne

AJS

AJS

#include <iostream.h>
#include <conio.h>
const int n=10;
int tab[n]={1,2,3,2,-7,44,5,1,0,-3};

int szukaj(int tab[n],int x)
{
for(int i=0;(i<n)&&(tab[i]!=x);i++);
return i;
}

void main()
{
clrscr();
cout << szukaj(tab,7) <<endl;
cout << szukaj(tab,-3) <<endl;
getch();
}

Postać iteracyjna

przeszukiwania
liniowego

Przeszukiwanie liniowe

AJS

AJS

void szukaj(int tab[n],int lewa,int prawa,int x)

{

if (lewa>prawa)

cout << "Element " << x << " nie zostal
odnaleziony\n";

else

if (tab[lewa]==x)

cout << "Znalazlem szukany element

"<< x << endl;

else

szukaj(tab,lewa+1,prawa,x);

}

Postać rekurencyjna przeszukiwania
liniowego

AJS

AJS

Przeszukiwanie binarne

Dotyczy przeszukiwania tablicy posortowanej

Łatwo można wyeliminować obszary tablicy w

których szukany element na pewno nie

wystąpi.

przeszukiwanie liniowe a przeszukiwanie

binarne

Liniowe jest bardziej czasochłonne

Np. w tablicy 20000 elementowej

- 20000 porównań -liniowe

- 14 porównań -binarne

AJS

AJS

#include <iostream.h>

#include <conio.h>

const int n=12;

int tab[n]={1,2,6,18,20,23,29,32,34,39,40,41};
int szukaj(int tab[],int x);

void main()

{

clrscr();

cout << szukaj(tab,6)<<endl;

getch();

}

Przeszukiwanie binarne

iteracyjna wersja algorytmu

AJS

AJS

int szukaj(int tab[],int x)
{
enum {TAK,NIE} Znalazlem=NIE;
int lewa=0,prawa=n-1,srodek;
while(lewa<=prawa && Znalazlem!

=TAK)
{
srodek=(lewa+prawa)/2;
if(tab[srodek]==x)

Znalazlem=TAK;

else

if(tab[srodek]<x)

lewa=srodek+1;

else

prawa=srodek-1;

}
if(Znalazlem==TAK)

return srodek;

else

return -1;

}

Przeszukiwanie binarne -

iteracja

AJS

AJS

#include <iostream.h>

#include <conio.h>

int szukaj_rec(int * tab,int x,int lewa,int prawa);

void main()

{

clrscr();

int tabl[12]={1,2,6,18,20,23,29,32,34,39,40,41};

cout << "wynik="<<szukaj_rec(tabl,23,0,11)<<endl;

getch();

}

Przeszukiwanie binarne

rekurencyjna wersja algorytmu

AJS

AJS

int szukaj_rec(int * tab,int x,int lewa,int prawa)

{

if(lewa>prawa) return -1;

// element nie

znaleziony

else

{

int srodek=(lewa+prawa)/2;

if(tab[srodek]==x) return srodek;

// element

został znaleziony!

else

if(x<tab[srodek])return

szukaj_rec(tab,x,lewa,srodek-1); else

return

szukaj_rec(tab,x,srodek+1,prawa);

}

}

Przeszukiwanie binarne

-rekurencja

AJS

AJS

Przeszukiwanie tekstów

Algorytm typu

brute-force

poszukiwanie wzorca

K O

T E L

E E K S

Z

T E L

E F O N

wzorzec w

badany

tekst t

0 j M-1

0 i

N-1

fragmenty (jeszcze)
zgodne

AJS

AJS

#include <iostream.h>

#include <conio.h>

#include <string.h>

// z

uwagi na strlen

int szukaj(char *w,char *t)

void main()

{

clrscr();

char *b="abrakadabra",*a="rak";

cout << szukaj(a,b) << endl;

getch();

}

Przeszukiwanie tekstów -

program

AJS

AJS

int szukaj(char *w,char *t)

{

int
i=0,j=0,M=strlen(w),N=strlen(t);

while(j<M && i<N)

{

if(t[i]!=w[j]) {i-=j-1;j=-1;}

i++;j++;

}

if(j==M) return i-M; else return -1;

}

Algorytm typu brute-force

AJS

AJS

Grafika tekstowa

Zarządzanie ekranem w trybie

tekstowym

C++ - funkcje

Funkcje pozwalają na:

- zmianę trybu tekstowego,
- sterowanie atrybutami znaków wysyłanymi na ekran,
- realizację operacji we-wy,
- obsługę pamięci obrazu,
- sterowanie położeniem i kształtem kursora.

Prototypy tych funkcji są umieszczone w bibliotece

conio.h conio.c

constream.h

AJS

AJS

Organizacja ekranu w trybie

tekstowym

Ekran podzielony jest na jednakowe

komórki.

W komórce może znaleźć się tylko

jeden znak

1 2 3 4 5 6 7 8 9

1
2
3
4
5

D

6
7
8

(left,to
p)

(right,bott
om)

współrzędne
względne (3,2)

okno
tekstowe

współrzędne
bezwzględne

kolumna
3

wiersz 2

AJS

AJS

Definiowanie okien tekstowych

void window (int left, int top, int right, int bottom);

(funkcja ta służy do określenia obszaru ekranu zajmowanego

przez okno tekstowe)

dla całego ekranu

window(1,1,80,25);

tryb 80-kolumnowy

window (1,1,40,25);

tryb 40-kolumnowy

Sterowanie trybem pracy ekranu

void textmode (int newmode);

textmode(C80);

C40

1 tryb kolorowy, 40

kolumn

C80

3 tryb kolorowy, 80

kolumn

MONO

7 tryb

monochromatyczny

80 kolumn

AJS

AJS

Sterowanie atrybutami znaków wysyłanymi na ekran

Bajt atrybutu znaków określa

kolor znaku,
podwyższoną jasność.
kolor jego tła,
migotanie

7

6

4

3

2

1

0

4

void textbackground(int newcolor);

kolor tła

textbackground(4);

czerwony kolor tła.

void textcolor(int newcolor);

kolor znaku

textcolor(2);

zielony kolor znaku.

void highvideo(void);

podwyższona jasność

void lowvideo(void);

normalna jasność

void normvideo(void);

przywraca stan

początkowy

AJS

AJS

stała

warto

ść

kolor

zastosowanie

BLACK

0

czarny

tło i znak

BLUE

1

niebieski

tło i znak

GREEN

2

zielony

tło i znak

CYAN

3

turkusowy

tło i znak

RED

4

czerwony

tło i znak

MAGENTA

5

karmazynowy

tło i znak

BROWN

6

brązowy

tło i znak

LIGHTGRAY

7

jasnoszary

tło i znak

DARKGRAY

8

ciemnoszary

znak

LIGHTBLUE

9

jasnoniebieski

znak

LIGHTGREEN

10

jasnozielony

znak

LIGHTCYAN

11

jasnoturkusowy

znak

LIGHTRED

12

jasnoczerwony

znak

LIGHTMAGENT
A

13

jasnokarmazyno

wy

znak

YELLOW

14

żółty

znak

WHILE

15

biały

znak

BLINK

128

migotanie

znak

Stałe kolorów

AJS

AJS

Sterowanie pozycją i wyglądem kursora

void gotoxy(int x, int y);

umieszcza kursor w

pozycji x,y okna

gotoxy(20,3);

int wherex(void);

wartością jest

współrzędna x kursora

x=wherex;

int wherey(void);

wartością jest

współrzędna y kursora

y=wherey;

void setcursortype(int cur_t);

zmiana wyglądu

kursora

setcursortype(_NOCURSOR);

wyłącza kursor,

setcursortype(_SOLIDCURSOR);

kursor jako pełny prostokąt,

setcursortype(_NORMALCURSOR); normalny kursor w postaci podkreślenia,

AJS

AJS

Czyszczenie ekranu, usuwanie,

wstawienie wierszy,

void clreol(void);

usuwa wszystkie znaki od

pozycji kursora do

końca

wiersza

clreol();

void clrscr(void);

usuwa wszystkie znaki z

ekranu

clrscr();

void delline(void);

usuwa wiersz w pozycji

kursora

delline();

void insline(void);

wstawia pusty wiersz w

pozycji kursora

insline();

Operacje wejścia z konsoli (klawiatury)

int getch(void);

odczytuje znak z klawiatury

getch();

int getche(void);

odczytuje znak z klawiatury

i wysyła go na ekran

getche();

AJS

AJS

#include<iostream.h>
#include <conio.h>
main()
{
clrscr();
int i;
textmode(C40);
textbackground(15);
window(20,10,40,25);
for (i=0; i<=15; i++)
{
textcolor(i);
cout<<i<<"\t";
cprintf("kolor \r\n");
}
getch();
return 0;
}

Wydruk kolorów – od 0 do 15

0

kolor

1

kolor

2

kolor

3

kolor

4

kolor

5

kolor

14

kolor

15

kolor