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