Predavanje 6 - Polja

1. Osnovno o poljima

Polje mozemo definirati kao skup podataka istog tipa slozenih na uzastopne memorijske lokacije i do kojih se moze pristupati indeksom.
Pojam polja i pokazivaca u C-u su povezani (prakticki nerazdvojni) kao sto to ce biti objasnjeno nize.
Primjeri rada sa poljima.

/* deklariramo cijelobrojno polje od 10 elemenata */ int a[10]; /* elementi polja su a[0], a[1], ..., a[9], primjer koristenja polja */ for(i=0; i<10; i++) a[i]=5*i; /* deklariramo polje koje sadrzi slozeni tip podatka kojeg smo definirali zadnji puta */ typedef struct { float x; float y; } tocka; tocka polje_tocaka[10]; /* primjer koristenja */ polje_tocaka[0].x=1.5; polje_tocaka[0].y=2.3; /* jos jedno polje ali sada od dva elementa: tocke sa koordinatama (3, 4) i (0, 0) */ tocka polje_tocka[]={3.0, 4.0, 0, 0}; /* cesto je korisno imati polje pokazivaca -ono se deklarira ovako */ tocka *polje_pokazivaca_na_tocke[12]; /* deklarirati i dvodimenzionalno polje */ int matrica[3][4]; /* deklarira dvodimenzionalno cjelobrojno polje koje ima 3 retka i 4 stupca sama reprezentacija u racunalu je jednodimezionalno cjelobrojno polje; tako da se element koji se nalazi u matrici na mjestu (i, j) nalazi zapravo na mjestu (broj stupaca)*i+j elementima takvog polja pristupa se na ovaj nacin */ matrica[1][2]=12;

Vazno je napomenuti nekoliko stvari:

2. Dinamicka alokacija memorije

Dinamicka alokacija memorije desava se tokom izvrsavanja programa, a ne za vrijeme prevodjenja programa.
Za dinamicko alociranje memorije koristi se funkcija malloc deklarirana u sistemskom zaglavlju stdlib.h.
Nakon upotrebe alocirana memorija se vraca izvedbenoj okolini koristeci funkciju free deklarirane stdlib.h

3. Polja kao formalni argumenti funkcija

Funkcija koja ima polje kao formalni argument moze biti deklarirana na dva ekvivalentna nacina:

void f(int a[]) /* ili */ void f(int* b) /* funkciju mozemo pozvati na bilo kojem pokazivacu na cjelobrojni tip podatka */ int* a; /* nekako inicijaliziramo pokazivac a te pozovemo funkciju ovo je POTENCIALNI IZVOR PROBLEMA -moguce da u funkciji radimo sa memorijskim lokacijama koje nisu alocirane za to polje. Kako je ime polja pokazivac na prvi element polja mi u stvari u funkciji mijenjamo originalno polje. */ f(a); POTPUNI PRIMJER PROBLEMA #include<stdio.h> void f(int* a){ int i; for (i=0; i<5;i++){ a[i]=2*i; printf("%d\n", a[i]); } } int main(){ int b[2]; f(b); return 0; }
-uocimo da smo originalno deklarirali polje od samo dva elementa
-kako prenosimo pokazivac u funkciji mozemo raditi u principu pretpostavljajuci da polje ima elemenata koliko hocemo
-kod se normalno prevodi, ali kod izvrsavanja programa nalazimo access violation error
-problem je u tome da funkcija ne zna duljinu polja.
Kako rijesiti ovakav problem? Kod stringova nema tih problema jer oni uvijek zavrsavaju sa karakterom \0 te uvijek mozemo tesirati za kraj stringa. Opcenito trebalo bi prenijeti duljinu polja kao jos jedan argument funkcije.
JEDNO MOGUCE RJESENJE GORNJEG PROBLEMA #include<stdio.h> void f(int* a, int duljina_polja){ int i; for (i=0; i< duljina_polja;i++){ a[i]=2*i; printf("%d\n", a[i]); } } int main(){ int b[2]; f(b, sizeof(b)/sizeof(int)); return 0; }

I na kraju tipican primjer gdje se uz argument koji je polje prenosi i broj elemenata polja jest puna deklaracija funkcije main.

int main(int argc, char*[] argv) /*ili ekvivalentna forma */ int main(int argc, char** argv) /*kratki primjer koji ispisuje argumente sa komande linije uvijek je argc>=1, jer je argv[0] ime programa */ int main(int argc, char** argv){ int i; for (i=0; i< argc; i++){ printf("%s\n", argv[i]); } return 0; }

4. Zadaci za vjezbu

  1. Napisite test program u kojem cete testirati opisane veze izmedju aritmetike pokazivaca i polja. Isprobajte sve mogucnosti.
  2. Niz slucajnih cijelih i realnih brojeva koristeci standardne biblioteku moze se generirati ovako
    #include <stdio.h> #include <stdlib.h> #include <time.h> float randFloat(){ return (float)rand()/RAND_MAX; } int main(int argc, char** argv){ int i; srand((unsigned)time(NULL)); //seed for(i=0;i<10; i++) printf("%f\n", randFloat()); return 0; }
    Prevedite ovaj kod i generirajte neke nizove slucajnih realnih brojeva. Napisite i generator cijelih brojeva.
  3. Koristeci Knuth, The art of computer programming, Volume III, napiste svoje generatore slucajnih brojeva.
  4. Napisite funkciju koja uzima kao argument proizvoljni broja tocaka u Kartezijevoj ravnini i integer d. Funkcija vraca broj parova tocaka koji se nalaze na udaljenosti manjoj ili jedankoj d. Napisite i glavni program koji testira funkciju. Testirajte vasu funkciju za veliki broj tocaka. Neka glavni program kreira proizvoljan broj tocaka tokom izvrsavanja programa koristeci drugi zadatak.
  5. Napisite funkciju koja uzima kao argument proizvoljni broja tocaka u Kartezijevoj ravnini. Funkcija vraca broj trojki tocaka koji tvore trokut. Napisite i glavni program koji testira funkciju. Testirajte vasu funkciju za veliki broj tocaka. Neka glavni program kreira proizvoljan broj tocaka tokom izvrsavanja programa koristeci drugi zadatak.
  6. Napisite funkciju koja uzima kao argument proizvoljni broja tocaka T_1, ..., T_n i trazi njihovu permutaciju Q_1,..., Q_n tako da je suma udaljenost |Q_1Q_2|+...+ |Q_n-1Q_n| minimalna. Testirajte vasu funkciju za veliki broj tocaka.
  7. Napisite i implementirajte sucelje koje mnozi matrice, zbraja matrice, mnozi matrice sa skalarom, racuna transponiranu matricu i njezinu determinantu. Matrice trebaju biti proizvoljnog broja stupaca i redaka, koji se zadaju tokom izvrsavanja programa.