C Wykład V 2005 2006 s

background image

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

background image

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ą

background image

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ęć

background image

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;
}

background image

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

background image

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

background image

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;
}

background image

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

background image

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;
}

background image

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.

background image

AJS

AJS

Funkcje

rekurencyjne są

to funkcje, które

wywołują same

siebie.

Funkcje rekurencyjne

muszą zawsze zawierać

warunek stopu

(zatrzymania)

background image

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

background image

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

background image

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

background image

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

background image

AJS

AJS

Niebezpieczeństwa rekurencji

-czasami

znaczna

część

obliczeń

jest

wykonywana więcej niż jeden raz,

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

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,

background image

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

background image

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

background image

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

background image

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

background image

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.

background image

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

background image

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

background image

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.

background image

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);
}

background image

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

background image

AJS

AJS

Zasada działania procedury

quicksort

'P'

<'P'

'P'

>='P'

quicks
ort

quicks
ort

quicks
ort

ETAP I

ETAP
II

background image

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

background image

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

background image

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();
}

background image

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

background image

AJS

AJS

Algorytmy przeszukiwania

przeszukiwanie liniowe

przeszukiwanie binarne

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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


Document Outline


Wyszukiwarka

Podobne podstrony:
Pedagogika specjalna - wykłady 2005-2006, niepełnosprawność intelektualna
C Wykład I 2005 2006 s
C Wykład IV 2005 2006 s
C Wykład III 2005 2006 s
C Wykład II 2005 2006 s
Wyklad3 2005
Wyklad 09 2006
SZKOLNY KONKURS 2005 - 2006, Klasa VI(1)
Międzyszkolne Zawody Matematyczne 2005-2006, Klasa IV(1)
grupa 1clostridia, studia, 3 rok, Mikrobiologia, pytania, testy, ROK AKADEMICKI 2005-2006, MEDYCYNA
Pytania na komisyjny sprawdzian, studia, 3 rok, Mikrobiologia, pytania, testy, ROK AKADEMICKI 2005-2
grupa 6, studia, 3 rok, Mikrobiologia, pytania, testy, ROK AKADEMICKI 2005-2006, MEDYCYNA 2005-2006
Medycyna spr1, studia, 3 rok, Mikrobiologia, pytania, testy, ROK AKADEMICKI 2005-2006, MEDYCYNA 2005
Stomatologia test3, studia, 3 rok, Mikrobiologia, pytania, testy, polski, STOMATOLOGIA 2005-2006 wsz
3 wyklad - 8[1].10.2006, Edukacyjnie, K, Kosmetologia, Technik usług kosmetycznych, Farmakognozja, w
Sieci i systemy elektroenergetyczne wyklad # 10 2006

więcej podobnych podstron