Matematika E21

1. maja 2017.

Задаци из математике које су припремили ученици Е21

Jednostruko povezane liste

25. aprila 2017.

Jedan oblik organizacije dinamičkog čuvanja podataka je jednostruko povezana lista. Lista prestavlja skup čvorova, elemenata, povezani pokazivačima u jednom smeru. Svaki čvor je strukturna promenljiva koja ima najmanje dva polja: jedno za čuvanje podataka, ili informacija o čuvanju podataka,  drugo za čuvanje pokazivača na sledećeg čvora liste.

Deklaracija jednostruko povezanih lista

struct cvor
{
char inf;
struct cvor *sledeci;
};
struct cvor *pocetak_liste;

lista1

Na početak liste pokazuje pokazivačka promenljiva početak_liste. Krajnji čvor liste u elementu za vezu (sledeći) sadrži vrednost NULL. Ako je lista prazna početak_liste takođe, ima vrednost NULL.

Formiranje jednostruke liste

Da bi formirali listu, prvo inicijaliziramo praznu listu dodelom

pocetak_liste=NULL;      

pocetakliste

Kako bi se kreirao prvi dinamički objekat (čvor liste), neophodno je da se dodeli memorijski prostor,
novi=new cvor;, gde je novi pokazivač na strukturu cvor  lista2

Dinamičkom objektu novi, mogu se dodeliti vrednosti
novi→inf= „A“;
novi→ sledeci=pocetak_liste; lista3.PNG

Da bi promenljiva pocetak_liste pokazivala na početak, treba joj dodeliti vrednost promenljivve novi, pocetak_liste=novi; 

lista5.PNG

Prostor za novi cvor liste se odvaja operatorom novi=new cvor;

lista4

Nakon novi→inf=“B“;
            novi→sledeci=pocetak_liste; Informacioni deo čvora dobija vrednost, uključuje se u  listu i to na njen početak lista 6

Da bi promenljiva pocetak_liste pokazivala na početak, ponavlja se dodela pocetak_liste=novi;

 lista7

Pr.1 
Formirati i ispisati jednostruko spregnutu listu?

Rešenje:

#include <cstdlib>
#include <iostream>

using namespace std;
/* Definicija cvora liste*/
struct cvor
{
char pod;
cvor* sledeci;
};
/*Funkcija za ispis liste*/
void ispis(cvor *tekuci)
{
while(tekuci!=NULL)
{
cout<<tekuci->pod<<;
tekuci=tekuci->sledeci;
}
return;
}

int main(int argc, char *argv[])
{
char ceo;
cvor *pocetni, *novi;
pocetni=NULL;
cout<<„Unesi sadrzaj liste“<<endl;
cout<<endl;
while ((ceo=getchar())!=’ ‘)
{
novi= new cvor;
novi->pod=ceo;
novi->sledeci=pocetni;
pocetni=novi;

}
ispis(pocetni);

system(„PAUSE“);
return EXIT_SUCCESS;
}

Pr. 2
Kreiraj i ispisi jednostruko spregnutu listu ciji elementi su celi brojevi?

Rešenje:

#include <cstdlib>
#include <iostream>

using namespace std;
/* Definicija cvora liste*/
struct cvor
{
int pod;
cvor* sledeci;
};
/*Funkcija za ispis liste*/
void ispis(cvor *tekuci)
{
while(tekuci!=NULL)
{
cout<<tekuci->pod<<endl;
tekuci=tekuci->sledeci;
}
return;
}

int main(int argc, char *argv[])
{
int ceo;
cvor *pocetni, *novi;
pocetni=NULL;
cout<<„Unesi sadrzaj liste“<<endl;
cout<<endl;
while (ceo!=9999)
{
cout<<„Unesi ceo broj kao element liste“<<endl;
cout<<„Za kraj unesi 9999″<<endl;
cin>>ceo;
if (ceo!=9999)
{
novi= new cvor;
novi->pod=ceo;
novi->sledeci=pocetni;
pocetni=novi;
cout<<endl;
}
}
ispis(pocetni);
system(„PAUSE“);
return EXIT_SUCCESS;
}

 

Pr.
Kreiraj jednostruko spregnutu listu pri čemu novi čvor se ubacuje na kraj liste?

Rešenje:

#include <cstdlib>
#include <iostream>

using namespace std;
/* definicija strukturnog podatka cvor*/
struct cvor
{
char inf;
struct cvor *sledeci;
};
void pisi (cvor *tekuci)
{
while (tekuci!=NULL)
{
cout<<tekuci->inf<<endl;
tekuci=tekuci->sledeci;
}
return ;
}
int main(int argc, char *argv[])
{
cvor *novi;
cvor *pocl=NULL;
cvor *krajl=NULL;
char ch;
cout<<„Ünesi sadryaj liste“<<endl;
while ((ch=getchar())!=’ ‘)
{
novi= new cvor;
novi->inf=ch;
if(pocl==NULL)
{
pocl=novi;
}
else
{
krajl->sledeci=NULL;
}
krajl=novi;
krajl->sledeci=NULL;
cout<<„Sadrzaj liste“<<endl;
pisi(pocl);
}

system(„PAUSE“);
return EXIT_SUCCESS;
}

 

 

 

Zadaci- dinamicki nizovi

18. aprila 2017.

Pr. 1. 

Napravite program koji sumira elemente celobrojnog niza koristeći dinamičke nizove, alociranu memoriju?

Rešenje:

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
int i,n, s=0;
cout<<„Unesi broj elemenata niza“<<endl;
cin>>n;
int *pniz= new int (n);
for( i=0;i<n;i++)
{
cout<<“ Unesi „<<i+1<<“ element niza „<<endl;
cin>>pniz[i];
s+=pniz[i];
}
cout<<“ Suma elemenata alociranog niza je s=“<<s<<endl;
delete[]pniz;
system(„PAUSE“);
return EXIT_SUCCESS;
}

Isti zadatak, ali uradjen korišćenjem funkcije suma koja unosi elemente alociranog, dinamičkog niza i iste sumira

#include <cstdlib>
#include <iostream>

using namespace std;
int suma(int *pniz, int duzina)
{
int i, s=0;
for( i=0;i<duzina;i++)
{
cout<<“ Unesi „<<i+1<<“ element niza „<<endl;
cin>>pniz[i];
s+=pniz[i];
}
return s;
}
int main(int argc, char *argv[])
{
int i,n, s=0;
cout<<„Unesi broj elemenata niza“<<endl;
cin>>n;
int *pniz= new int [n];
cout<<“ Suma elemenata alociranog niza je s=“<<suma(pniz,n)<<endl;
delete[]pniz;
system(„PAUSE“);
return EXIT_SUCCESS;
}

Pr. 2. Šta ispisuje sledeći program?

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
int a[]={0, 1, 2, 3, 4};
int *p;
int i;
for (p=a, i=0;p<&a[4];p++)
{
cout<<*p<<endl;
}
cout<<“ „<<endl;
for (p=&(a[0]), i=0;p+i<a+4;p++,i++)
{
cout<<*(p+i)<<endl;

}
cout<<“ „<<endl;
for (p=a+4, i=0;i<=4;i++)
{
cout<<p[-i]<<endl;
}

system(„PAUSE“);
return EXIT_SUCCESS;
}

Rešenje:

dinamickiniz2

 

Dinamički nizovi

11. aprila 2017.

Dinamička dodela memorije omogućava rad sa nizovima čiji broj elemenata se definiše u toku izvršavanja programa. To je moguće zato što pokazivač na neki tip podataka može da pokazuje ne samo na memorijski prostor veličine jednog takvog podatka, već  i na prostor proizvoljne veličine.

Pr.  Napišite program koji:

  • kreira dinamički niz čiji broj elemenata specificira korisnik?
  • elemente niza unosite preko tastature?
  • koliko je broj elemenata niza koji su negativni?
  • kreirajte novi niz čiji elementi su negativni elementi prvog niza?

Rešenje:

#include
#include

using namespace std;
/* funkcija unos unosi elemente prvog niza*/
int unos (int *pok, int vrednost)// funkcija vraca vrednost, prebrojava koliko elemenata je negativno
{
int br=0, i;
for (i=0;i<vrednost;i++) { cin>> pok[i];
if (pok[i]<0)
{
br++;
}
}
return br;
}
/* funkcija ispis ispisuje elemente niza*/
void ispis (int *pok, int vrednost)
{
int i=0;
cout<<„elementi niza“<<endl;
for (i=0;i<vrednost;i++)
{
cout<<pok[i]<<endl;
}
return;
}
/* funkcija koji kreira novi niz ciji broj elemenata zavisi od broja negativnih elemenata prvog niza*/
void noviniz (int *pok1, int *pok2, int vrednost)
{
int i, j;
i=0;
j=0;
for (i=0;i<vrednost;i++)
{
if (pok1[i]<0)
{
pok2[j]=pok1[i];
j++;
}
}
return ;
}

int main(int argc, char *argv[])
{
int n1, n2;
cout<<„Unesi velicinu prvog niza?“<<endl; cin>>n1;
int *pokazivac1=new int (n1);//alociranje prvog niza

n2=unos(pokazivac1,n1);// pozivom funkcije unos dobija se broj elemenata drugog niza
cout <<„U prvom nizu koji ima „<<n1<<“ elemenata, negativni su „<<n2<<“ elementi“<<endl;
cout<<“ „<<endl;
cout <<“ Prikaz elemenata prvog niza“<<endl;
ispis(pokazivac1,n1);// elemeni prvog niza
delete []pokazivac1;
int *pokazivac2= new int(n2);// alokacija drugog niza
noviniz(pokazivac1, pokazivac2, n1);//kreiranje drugog niza
cout <<“ Prikaz elemenata drugog niza“<<endl;
ispis (pokazivac2,n2);
delete [] pokazivac2;
pokazivac1=0;
pokazivac2=NULL;
system(„PAUSE“);
return EXIT_SUCCESS;
}

Dinamickinizresenje

Izvor:

Dinamički podaci

11. aprila 2017.

Korišćenjem naredbama za definisanje podataka vrši se statička dodela memorijskog prostora, što znači, u vreme prevođenja programa se zna broj podataka koji se koriste u toku izvršavanja programa.

Deklaracijom niza definiše se tačan, maksimalan,  broj elemenata niza, što može dovesti do nepotrebno zauzimanje memorije. U slučajevima kada je velik broj podataka može se desiti da obrada bude nemoguća.

Deo memorije u koji se smeštaju statički definisani podaci naziva se statička zona memorije. 

Ponekad, veličina memorije koja će se zauzeti se nemože specificirati. Primer, šta ako treba kreirati niz elemenata tipa student, a broj studenata se može otkriti samo za vreme izvršavanja programa, kao parametar koji je specificiran od strane korisnika?

Ovaj problem se rešava dinamičkimim alociranjem memorije. Deo memorije u kojem se vrši dinamička dodela prostora u vreme izvršavanja programa, naziva se dinamička zona memorije. Podaci u dinamičkoj zoni memorije nazivaju se dinamički podaci. Dinamički podaci stvaraju se na zahtev programera i postoje dok programer ne zatraži njihovo uništenje. Neophodno je brisanje dinamičke zone memorije, kako bi se oslobodio memorijski prostor koji je bio zauzet stvanjem iste.

C++ omogućava dinamičko alociranje memorije korišćenjem operatora new, ako je potrebno alociranje za jedan element ili new[n], ako je potrebno alociranje memorije za n elemenata. Rezultat ovih operacija je pokazivač do bloka memorije koji je rezervisan.

Veoma je bitno, nakon korišćenja rezervisane memorije, da se ista obriše. C++ briše alociranu memoriju pomoću operatora delete, za jedan element i delete[], za više elemenata.

Pr. 

#include
#include

using namespace std;

int main(int argc, char *argv[])
{
int *pniz;
pniz = new int;
*pniz = 2;
cout << *pniz << endl; //stampa ‘2’
delete pniz; // VAZNO

int N = 100;
pniz = new int[N]; //niz od 100 elemenata
pniz[5] = 3;
cout << pniz[5] << endl; //stampa ‘3’
delete [] pniz; // VAZNO!!!
system(„PAUSE“);
return EXIT_SUCCESS;
}

alociranje

Alociranje memorije

Pr. Kreiranje anonimne promenljive

anonimna varijabla

Nabrajanja

14. februara 2017.

Nabrajanje  konstante su celobrojne simbolicke konstante kojima su vrednosti dodeljene eksplicitno ili  implicitno, nabrajanjem njihovih imena u jednom nizu. Skup odjednom nabrojenih konstanti cini jedno nabrajanje, koje se moze smatrati tipom podataka koji je definisao programer.

Definisanje nabrajanja:

enum ime_nabrajanja {IME_KONSTANTE=vrednost,

IME_KONSTANTE=vrednost,…};

Ime nabrajanja je identifikator koji sluzi za identifikaciju datog nabrajanja. Moze da se izostavi, ali kasnije nije moguce definisati podaci tipa nabrajanja.

IME KONSTANTE je identifikator, koji predstavlja po jednu simbolicku konstantu. Uobicajeno je da imena konstante se pisu samo velikim slovima.

Vrednosti pojedinih simbolickih konstanti mogu da se odrede konstantnim celobrojnim izrazima. Ako iza konstante nema =vrednost, konstanta ce imati vrednost koja je za jedan veca od predhodne konstante u nizu. Ako iza prvog identifikatora u nizu nema vrednosti, prva konstanta imace vrednost 0.

Pr.

enum {NE, DA};

enum { MIN=10, MAX=100, POZELJNO=20};

enum Kvartal1{JAN=1, FEB, MART, APRIL};

typedef enum {CRNA, SIVA, SMEDJA, CRVENA} Boja;

typedef enum Kvartal1 mesec=JAN;

Boja booja=CRVENA +2;

Unije

17. januara 2017.

Unije su složeni tipovi podataka koji omogućavaju da se u isti memorijski prostor, u različitim trenucima, smeštaju podaci različitih tipova.

Unije se difinišu naredbom union, sve ostalo je kao i kod struktura, navode se polja koja su različitog tipa.

Za razliku od struktura, kod kojih sva polja imaju definisanu vrednost, kod unije samo jedno polje u datom trenutku ima definisanu vrednost, polje kome je posljednje dodeljena vrednost.

Ako se inicijalizira unija, u zagradama se stavlja samo jedna vrednost i ako se ne navede čija je vrednost, dodeljuje se  prvom polju

Pr.

struct s {                                                                 union u {
int i;                                                                                int i;
float d;                                                                            float d;
char *c;                                                                          char *c;
};                                                                                 };

Prikaz u operativnoj memoriji:

s: s.i, s.d, s.c -sizeof s, polja se smeštaju u operativnoj memoriji jednoza drugim i svakom od polja se može dodeliti vrednost. Veličina strukture je  jednaka zbiru veličine polja.

U slučaju unije, sva polja se smeštaju počev od iste adrese. Dodela vrednosti jednog polja uništava ranije dodeljenu vrednost nekom drugom polju. Veličina unije odgovara veličini najvećeg polja. (u: u.i
u.d
u.c
– sizeof u)

Pr.1

typedef union u{
int i;
float f;
char c;
} u;

main()
{
u unija;
unija.c=’A’;
unija.i=5;

/* Dozvoljen je pristup samo poslednje dodeljenom clanu unije */
cout<<„Trenutna vrednost unije je,unija.i“<<unija.i; /* U redu je */

/* Pogresno bi bilo da se napise
cout<<„Trenutna vrednost unije je unija.c“<<unija.c;
*/
}

Pr.2 

#include
#include
using namespace std;
union ceo_ili_realan{
int ceo;
float realan;
};
int main(int argc, char *argv[])
{
ceo_ili_realan x;
cout<<„Unesi ceo broj?“<<endl; cin>>x.ceo;
cout<<“ Unija ima vrednost „<<x.ceo<<endl;
cout<<„Unesi realan broj ?“<<endl; cin>>x.realan;
cout<<“ Unija ima vrednost „<<x.realan<<endl;
system(„PAUSE“);
return EXIT_SUCCESS;
}

Uređivanje niza

26. decembra 2016.

Složeniji proces od  pretraživanja niza je uređivanje. Da bi se niz uredio neophodno je da se svaki element uporedi sa ostalim elementima, po potrbi, izvršiti njihovu međusobnu zamenu.

Metod izbora (selection sort)

Zasniva se na veoma jednostavnoj ideji, izabrati najmanji element niza i dovesti ga na prvo mesto, zatim drugi najmanji, na drugo mesto, itd. do kraja niza.

Pr1.

Napravite program koji niz a čiji elementi su celi brojevi uređuje u rastućem redosledu?

Rešenje:

#include
#include
using namespace std;
void ucitajniz(int a[], int n)
{
int i;
for (i=0;i<n;i++)
{
cout<<“ Unesi „<<i+1<<“ element niza“<<endl; cin>>a[i];
}
}
void razmeni(int *a, int *b)
{
int pom=*a;
*a=*b;
*b=pom;
}
void sortiraj(int a[], int n)
{
int i, j;
for (i=0;i<n-1;i++)
{
for (j=i+1;j<n;j++) { if (a[i]>a[j])
razmeni(&a[i], &a[j]);
}
}
}
void ispisiniz(int a[], int n)
{
int i;
for (i=0;i<n;i++)
cout<<“ a[„<<i+1<<„] je „<<a[i]<<endl;

}

int main(int argc, char *argv[])
{
int a[10],n;
cout<<„Unesi broj elemenata niza“<<endl; cin>>n;
ucitajniz(a,n);
sortiraj (a,n);
cout<<“ Sortirani niz:“<<endl;
ispisiniz(a,n);
system(„PAUSE“);
return EXIT_SUCCESS;
}

Pretraživanje nizova

26. decembra 2016.

Veoma često javlja se potreba ispitivanja da li određeni element pripada određenom skupu, da li je moguće elemente skupa urediti po nekom kriterijumu? Znamo da skup istih elemenata po tip daju niz, kada je reč o programiranju, pa tehnika pretraživnja i uređivanja nizova čini jednu od najznačajniih grupa obrade podataka.

Za pretraživanje nizova postoje dva algoritma koji se načešće koriste u praksi

Sekcencionalno pretraživanje

Uzastopno upoređivanje elemenata niza sa traženom vrednošću (provera da li se vrednost nalazi  u nizu), sve dok se vrednost ne pronađe ili kada se dođe do kraj niza (tražena vrednost nije u nizu) su karakteristike sekvencionalnog pretraživana. 

Sekvencionalno pretraživanje          Funkcija za sekvencionalno pretraživanje

Da je tražena vrednost pronađena zna se po tome što je ciklus pretraživanja završen pre kraja niza (i<n). Vrednost funkcije je 1 u slučaju uspeha, 0 u slučaju neuspeha.

Jednostavnost je dobra strana pretraživanja, mana je relativno veliki broj proba da bi se došlo do rezultata.

Pr1.

U jednom razredu ima n učenika. Prosečna standardna visina je b. da li u razredu ima učenika sa standardnom visinom?

Rešenje:

#include <cstdlib>
#include <iostream>

using namespace std;

/*Funkcija za pretrazivanje*/
int sektra1 (int a[],int n,int b)
{
int i;
for (i=0;i<n && a[i]==b;i++)
return i<n;
}

/*glavni program*/
int main(int argc, char *argv[])
{
int a[30];
int b, n, i;
cout<<„Unesi standardnu visinu?“<<endl;
cin>>b;
cout<<„Unesi broj ucenika u razredu?“<<endl;
cin>>n;
cout<<„Unesi visine svakog ucenika?“<<endl;
for (i=0;i<n;i++)
{
cout<<„Unesi visinu ucenika sa rednim brojem „<<i+1<<endl;
cin>>a[i];

}
cout <<sektra1(a,n,b);

if (sektra1 (a,n,b)==1)
{
cout <<„Postoje ucenici cija visina je „<< b<< „, prosecna visina „<<endl;
}
else
{
cout <<“ Ne postoje ucenici cija visina je „<< b<< „(prosecna visina) „<<endl;
}
system(„PAUSE“);
return EXIT_SUCCESS;
}

 

Pokazivači

29. oktobra 2016.

Svaki podatak u računarskom sistemu ima svoju memorijsku lokaciju. C++ omogučava preko promenljivih određenog tipa pristup podacima, pri čemu nije neophodno da se vodi računa o memorijskoj lokaciji gdegde se podatak nalazi.

Pokazivači su specijalni tipovi podataka koji omogućavaju rad sa memorijskim lokacijama. C++ definiše pokazivače tako što posle tipa pokazivača, ispred naziva stavlja * ( int *pokazivač). Ako želimo da saznamo koja je adresa definisanog pokazivača ispred naziva pokazivača se stavlja & (pr. &pokazivac).

Pr:

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
int a = 5;
/* pokayivac ka podatku koji je po tip intedjer*/
int *b;
//b je adresa promenljive a („b pokayuje ka a“)
b = &a;
/*
double *k;
k = &a; //GRESKA: pogresen tip na pokazhuvac (double)
*/
cout << a << endl; //stampa ‘5’ (vrednosta promenljive a)
cout << b << endl; //stampa ‘0x27ff44’ (adresa memorijske lokacije a)
system(„PAUSE“);
return EXIT_SUCCESS;
}

pokazivac

Veoma često, kada se kreiraju pokazivači, potrebno je znati koja je vrednost promenljive ka kojoj pokazuje pokazivač. Sa znakom * pristupamo podatku koji se nalazi na odredjenoj memorijskoj lokaciji. Važno je da se zna da pristupom sa znakom * može vrednost memorijske lokacije da se promeni.

Pr.

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
int a = 5; //promenliva ‘a’ ima vrednost 5
int *p; //pokazhuvac ka podatkom od tipa int

p = &a; //p ja adresa a („p pokazuje ka a“)

cout << a << endl; //stampa ‘5’
cout << *p << endl; //stampa ‘5’

*p = 3; //promena vrednosti

cout << p << endl; //stampa adresu
cout << *p << endl; //stampa ‘3’ (vrednost)
cout << a << endl; //stampa ‘3’
system(„PAUSE“);
return EXIT_SUCCESS;
}

pok2

Jedan pokazivač može se koristiti više puta pri čemu može  da pokazuje i ka različitim promenljivima i memorijskim lokacijama.

Veličina pokazivača zavisi od arhitekturu računarskog sistema, i operativnog sistema, 32 bitni računarski sistem koristi 32 bitne memorijske adrese, veličina pokazivača je 4 bajta.

Pr.

#include <iostream>
using namespace std;

struct typeX
{
int t1, t2, t3, t4;
double t5, t6, t7, t8;
};

int main()
{
int a = 5, b = 2;
double c = 3.8;
char d = ‘Z’;
typeX e;

int *pa = &a, *pb = &b;
double *pc = &c;
char *pd = &d;
typeX *pe = &e;

cout << sizeof(pa) << endl; //stampa ‘4’
cout << sizeof(pb) << endl; //stampa ‘4’
cout << sizeof(pc) << endl; //stampa ‘4’
cout << sizeof(pd) << endl; //stampa ‘4’
cout << sizeof(pe) << endl; //stampa ‘4’

system(„PAUSE“);
return EXIT_SUCCESS;
}

pok3

Niz i pokazivači