PROGRAMIRANJE 2
VEŽBE
POKAZIVAČI NA FUNKCIJE.
BIBLIOTEČKE FUNKCIJE
QSORT, BSEARCH, LFIND, LSEARCH.
Staša Vujičić Stanković
POKAZIVAČI NA FUNKCIJE

Funkcije u C-u nisu promenljive,
ali se može definisati promenljiva
koja će biti pokazivač na funkciju.
2
POKAZIVAČI NA FUNKCIJE

Binarne instrukcije koje čine funkciju su takođe
negde u memoriji i imaju svoju adresu.
Samim tim, moguće je definisati pokazivač na
funkciju. Deklaracija:
int (*fp)(int);
definiše promenljivu fp, koja je tipa
"pokazivač na funkciju koja prihvata int, i vraća int".
Ova promenljiva sadrži adresu neke funkcije tog tipa.
3

Ako je deklarisana funkcija:
int f(int a);
Tada je moguće dodeliti:
fp = &f;
Sada fp sadrži adresu funkcije f.
Funkcija f se može pozivati sa:
(*fp)(3);
4
Zagrade oko izraza *fp su neophodne zbog
prioriteta operatora!
 Dereferenciranjem pokazivača na funkciju dobija
se funkcija, koja se onda poziva na uobičajen
način.
 Ovo ima najviše smisla kada unutar neke funkcije
želimo da koristimo neku drugu funkciju,
koja nije uvek ista, i bira se prilikom poziva.
Tada se kao argument funkcije predaje pokazivač
na funkciju odgovarajućeg tipa.
Putem tog pokazivača se iznutra poziva
odgovarajuća funkcija.

5
ZAGLAVLJE MATH.H

Zaglavlje math.h sadrži deklaracije razih
matematičkih funkcija. Između ostalih:
double sin(double x);
double asin(double x);
double cos(double x);
double acos(double x);
double tan(double x);
double atan(double x);
double sinh(double x);
double cosh(double x);
double exp(double x);
double log(double x);
double log10(double x);
double sqrt(double x);
double pow(double x, double y);
double ceil(double x);
double floor(double x);
double fabs(double x);
...
6
ZADATAK
1. Napisati funkciju koja ,,tabelira” datu realnu funkciju
realnog argumenta f(x),
tj. Izračunava vrednosti date funkcije na diskretnoj
ekvidistantnoj mreži od n tačaka intervala [a,b].
7
/* Funkcija tabela() prihvata granice intervala a i b, broj koraka n,
kao i pokazivač f koji pokazuje na funkciju koja prihvata double argument,
i vraća double rezultat.
Za tako datu funkciju ispisuje njene vrednosti u intervalu [a,b] sa korakom
h */
void tabela(double a, double b, int n, double (*f)(double x))
{
int i;
double x;
printf("-----------------------\n");
for(i=0; i<n; i++)
{
x= a + i*(b-a)/(n-1);
printf("| %8.5f | %8.5f |\n", x, (*f)(x));
}
printf("-----------------------\n");
8
}
/* Umesto da koristimo stepenu fju iz zaglavlja
math.h -> pow(a,2) pozivaćemo korisničku
kvadrat(a) */
double kvadrat (double a)
{
return a*a;
}
9
int main()
{
double a, b;
int n;
printf("Unesite krajeve intervala: \t" );
scanf("%lf%lf", &a, &b);
printf("Koliko tacaka ima na ekvidistantnoj mrezi
(ukljucujuci krajeve intervala)? ");
scanf("%d", &n );
/* mreza mora da ukljucuje bar krajeve intervala,
tako da se mora uneti broj veci od 2 */
if (n<2)
{
fprintf(stderr, "Broj tacaka mreze mora biti bar 2!\n");
exit(EXIT_FAILURE);
10
}
printf(" f(x) = sin(x).\n");
tabela(a,b,n, &sin);
printf("\n f(x) = cos(x).\n");
tabela(a,b,n, &cos);
printf("\n f(x) = exp(x).\n");
tabela(a,b,n, &exp);
printf("\n f(x) = x^2.\n");
tabela(a,b,n, &kvadrat);
exit(EXIT_SUCCESS);
}
11
FUNKCIJA QSORT()
Funkcija je definisana u standardnoj biblioteci i za njeno
korišćenje dovoljno je uključiti zaglavlje stdlib.h.
 Funkcija qsort() vrši sortiranje niza metodom sortiranja
razdvajanjem.
Deklaracija ove funkcije je sledeća:

void qsort(void *b, int n, int s,
int(*comp)(const void *, const void *));
12
void qsort(void *b, int n, int s,
int(*comp)(const void *, const void *));

void *b – adresa početka niza koji se sortira.
Obzirom da se ne zna tačan tip elemenata niza,
koristi se generički pokazivač (void *).

int n – broj elemenata niza.

int s – veličina svakog od elemenata niza.

int(*comp)(const void *, const void *) –
pokazivač na funkciju poređenja.
13
GENERIČKI POKAZIVAČ (VOID
*)
Pokazivač na void je pokazivač koji može da
sadrži adresu bilo kog podatka u memoriji.
 Svaki pokazivač se može bez konverzije dodeliti
ovom pokazivaču, kao i obrnuto.
 Može se koristiti za čuvanje adrese podatka za
koji unapred ne znamo kog će biti tipa.
 Njegova glavna karakteristika je da se ne može
dereferencirati, zato što se ne zna kog je tipa
ono na šta on pokazuje.
Programer mora na drugi način da utvrdi kog je
tipa podatak na toj adresi, pa da najpre
konvertuje void pokazivač u odgovarajući tip
pokazivača, a zatim da ga tako konvertovanog
dereferencira.

14
int(*comp)(const void *, const void *) –
pokazivač na funkciju poređenja.
Ova funkcija treba da prihvata adrese elemenata niza
koji se porede.
Treba da vraća:

>0 ako je prvi element veći,
 <0 ako je prvi element manji,
 0 ako su elementi koji se porede jednaki.

Na ovaj način se može sortirati bilo koji niz,
dovoljno je da je na neki način funkcijom poređenja
definisan potpuni poredak među elementima niza.
Argumenti funkcije poređenja su takođe generički
pokazivači, opet zato što ne znamo tačno kog su tipa
elementi niza.
Ovi pokazivači su još kvalifikovani ključnom rečju const.
15
KLJUČNA REČ CONST
Ključna reč const u programskom jeziku C služi
za definisanje konstanti.
 Ako napišemo:
const int a = 2;
tada se u daljem toku programa promenljivoj a
ne može dodeljivati vrednost.
 Za razliku od konstanti definisanih define
direktivom ova konstanta ima jasno definisan tip
koji prevodilac proverava prilikom upotrebe.

16
Treba naglasiti, međutim, da ako se napiše:
const int *p = &a;
tada se const ne odnosi na promenljivu p,
već na podatak tipa int na koji p pokazuje.
 Dakle, nije pokazivač konstantan,
već on pokazuje na konstantan podatak.
 Na primer:
int b; p = &b;
je dozvoljeno, ali:
*p = 4;
nije dozvoljeno,
zato što je p pokazivač na konstantan int.

17
Ovo se može razumeti tako što se deklaracija pročita
zdesna u levo:
const int * p;
- p je pokazivač na int koji je konstantan
 Slično bi bilo i ako napišemo:
int const * p;
- p je pokazivač na konstantan int.
 Međutim, ako napišemo:
int * const p;
- p je konstantan pokazivač na int.
 Kombinacija ovoga je:
const int * const p;
- p je konstantan pokazivač na int koji je
konstantan.
Dakle, u ovom poslednjem slučaju konstantni su i
pokazivač i ono na šta on pokazuje.

18
FUNKCIJA BSEARCH
()
Funkcija je definisana u standardnoj biblioteci
i za njeno korišćenje dovoljno je uključiti zaglavlje
stdlib.h.
 Funkcija bsearch() vrši pretraživanje sortiranog niza
metodom binarne pretrage.
 Funkcija ima sledeću deklaraciju:

void *bsearch(const void *x, const void *b,
int n, int s, int (*comp)(const void *, const void *));
19
void *bsearch(const void *x, const void *b,
int n, int s,
int (*comp)(const void *, const void *));

const void *x – pokazivač na podatak koji se
traži u nizu.

const void *b – adresa početka niza.

int n – veličina niza.

int s – veličina elementa niza.
20

int (*comp)(const void *, const void *) –
pokazivač na funkciju poređenja koja definiše
poredak u skladu sa kojim je sortiran niz.
Funkcija vraća adresu elementa u nizu koji je
jednak traženom elementu,
ili NULL ukoliko element nije pronađen.
21
FUNKCIJA LSEARCH()
void *lsearch(const void *x, void *b, int *n, int s,
int (*comp)(const void *, const void *));
ima potpuno iste argumente kao i bsearch() –
jedina razlika je u tome što se kao treći argument ne
predaje dužina niza već adresa celobrojne promenljive u
kojoj se nalazi dužina niza.
Ovo je zato što funkcija lsearch() ukoliko linearnom
pretragom ne pronađe element koji se traži,
umeće traženi element na kraj niza,
a dužinu niza uvećava za jedan
(što čini tako što promenljivoj pozivajuće funkcije pristupa
22
preko pokazivača i menja je).
Funkcija za upoređivanja elemenata na koju
pokazuje pokazivač comp treba da zadovoljava
ista pravila kao i kod prethodnih funkcija.
 Međutim, obzirom da se kod linearne pretrage
koristi isključivo poređenje na jednakost,
dovoljno je da funkcija za upoređivanje vraća 0
ako su objekti koji se upoređuju jednaki, a
različito od nule u suprotnom.

23
FUNKCIJA LFIND()
void *lfind(const void *x, void *b, int *n,
int s, int (*comp)(const void *, const void *));
Funkcioniše isto kao i lsearch(),
s tom razlikom što ne umeće novi element
u slučaju neuspešne pretrage,
već vraća NULL.
24
ZADATAK
2. Korišćenjem funkcije qsort napisati program koji
sortira:
1)
2)
Niz brojeva opadajuće.
Niz prirodnih brojeva po broju delilaca.
Proširiti program tako da na tako sortiran niz,
primeni binarnu pretragu, koristeći funkciju bsearch.
25
/* Funkcija poredi dva cela broja */
int compare_int(const void *a, const void *b){
/* Konvertujemo void pokazivace u int pokazivace
koje zatim dereferenciramo,
dobijamo int-ove koje oduzimamo i razliku
vracamo. */
return *((int *)a) - *((int *)b);
}
26
int compare_int_desc(const void* a, const void* b){
/* Za obrnuti poredak mozemo samo oduzimati a od b*/
/* return *((int *)b) - *((int *)a); */
return -compare_int(a,b);
}
27
int no_of_deviders(int x){
int i; int br;
if(x<0) x= -x;
if(x==0) return 0;
if(x==1) return 1;
/* svaki broj veci od 1 ima bar 2 delioca, (1 i samog sebe)*/
br=2;
for(i=2; i<sqrt(x); i++)
if(x%i == 0)
br+=2; /* ako i deli x onda su delioci: i,
x/i */
if(i*i == x) br++;
return br;
}
28
int compare_no_deviders(const void* a, const void* b)
{
int ak = *(int *)a;
int bk = *(int *)b;
return no_of_deviders(ak) - no_of_deviders(bk);
}
29
int main(){
int n, i, x;
int a[MAX], *p;
/* Unosimo dimenziju */
printf("Uneti dimenziju niza: ");
scanf("%d", &n);
/* Unosimo elemente niza */
printf("Uneti elemente niza:\n");
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
/* Sortiramo niz */
qsort(a, n, sizeof(int), &compare_int);
30
/* Prikazujemo sortirani niz */
printf("Sortirani niz u rastucem poretku:\n");
for(i = 0; i < n; i++)
printf("%d ", a[i]); putchar('\n');
/* Sortiramo niz */
qsort(a, n, sizeof(int), &compare_int_desc);
/* Prikazujemo sortirani niz */
printf("Sortirani niz u opadajucem poretku:\n");
for(i = 0; i < n; i++)
printf("%d ", a[i]); putchar('\n');
31
/* Unosimo trazeni broj */
printf("Uneti trazeni broj: ");
scanf("%d", &x);
/* Binarna pretraga */
/* prosledjujemo pokazivac na funkciju
compare_int_desc jer nam je niz sada sortiran u
opadajucem poretku.*/
p = bsearch(&x, a, n, sizeof(int), &compare_int_desc);
if(p != NULL)
printf("Broj %d pronadjen u nizu\n", *p);
else
printf("Broj %d nije pronadjen u nizu\n", x);
/* p == NULL pa ispisujemo trazeni broj x*/
32
/* Sortiramo niz po broju delilaca */
qsort(a, n, sizeof(int), &compare_no_deviders);
/* Prikazujemo sortirani niz */
printf("Sortirani niz po broju delilaca:\n");
for(i = 0; i < n; i++)
printf("%d ", a[i]);
putchar('\n');
return 0;
}
33
ZADATAK
3. Korišćenjem funkcije qsort napisati program koji
sortira:
1) Niz niski leksikografski.
2) Niz niski po dužini.
Proširiti program tako da na tako sortiran niz,
primeni binarnu pretragu, koristivši funkciju
bsearch.
34
REŠENJE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NISKI 1000
#define MAX_DUZINA 30
int poredi_leksikografski(const void *a, const void*b)
{ return strcmp((char *)a,(char*)b); }
int poredi_duzine(const void *a, const void*b)
{ return strlen((char*)a) - strlen((char*)b);}
35
int main(){
int i,n;
FILE *fp;
char niske[MAX_NISKI][MAX_DUZINA];
char* p;
char x[MAX_DUZINA];
if(( fp = fopen("niske.txt", "r"))== NULL) {
fprintf(stderr, "Neupesno otvaranje datoteke
za upis vremena pretrage.\n" );
exit(EXIT_FAILURE); }
for(i=0; fscanf(fp, "%s", niske[i] )!=EOF; i++);
fclose(fp);
n=i;
36
qsort(niske, n, MAX_DUZINA*sizeof(char),poredi_duzine);
printf("\n-----------Niske sortirane po duzini------------\n");
for(i=0; i<n; i++)
printf("\t%s\n",niske[i]);
qsort(niske, n, MAX_DUZINA*sizeof(char),poredi_leksikografski);
printf("\n-----------Leksikografski sortirane niske------------\n");
for(i=0; i<n; i++)
printf("\t%s\n",niske[i]);
37
/* Unosimo trazeni nisku */
printf("Uneti trazenu nisku: ");
scanf("%s", x);
/* Binarna pretraga */
/* prosledjujemo pokazivac na funkciju
poredi_leksikografski jer nam je niz sada sortiran
leksikografski.*/
p = bsearch(&x, niske, n, MAX_DUZINA*sizeof(char),
&poredi_leksikografski);
if(p != NULL)
printf("Niska \"%s\" je pronadjena u nizu\n", p);
else
printf("Niska nije pronadjena u nizu\n");
exit(EXIT_SUCCESS);
}
38
Download

Pokazivači na funkcije. Bibliotečke funkcije qsort, bsearch, lfind