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;

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;      

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  

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

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

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

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

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

 

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

 

 

 

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

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 memorije

Pr. Kreiranje anonimne promenljive