Matematika E21

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

Advertisements

Jednostruko povezane liste

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

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

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

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

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

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