Liste

Lista je struktura podataka koja se odlikuje linearnom raspodelom pripadajućih elemenata. Najsličnija je nizu, a član liste je struktura koja sadrži podatke i pokazivač na sledeći član liste.

Svaka lista mora da zadovoljava sledeće osobine:

• Lista može biti prazna
• Moguće je ubacivanje elemenata u listu
• Moguće je izbaciti bilo koji element iz liste
• Lista ima svoju veličinu tj broj elemenata

Po povezanosti liste mogu da budu:

1. Jednostruko povezane
   
2. Dvostruko povezane
   

Po svom obliku dele se ne :

1. Linearne
   
2. Kružne
   

Jednostruko povezane liste podržavaju pretrazivanje članova samo u jednom smeru. Član liste je struktura koja sadrži podatke i pokazivač na sledeći član u listi.

Struktura

 
struct lista{
int podatak;
struct lista *sledeci;
};

Najčešće se koriste kada je pretraživanje u jednom smeru dovoljno za dati problem.

Kod dvostruko povezanih lista moguće je pretraživanje u oba smera. Član ove liste je struktura koja sadrži podatke i pokazivače na sledeći i prethodni clan liste.

Struktura

 
struct lista{
int podatak;
struct lista *sledeci,*prethodni;
};

Kružna liste se odlikuje po tome sto nema početak. Za razliku od linearnih lista kod kojih su jasno izraženi početni i krajnji clan liste, kod kružne liste poslednji ubačeni clan liste se postavlja da pokazuje na prvi. Svaki element može da bude prvi element nez remećenja strukture.

Program koji formira i ispisuje listu na ekran

 
#include <stdio.h>
#include <stdlib.h>
 
struct lista{
int broj;
struct lista *rep;
};
 
#define novi(x) x=(struct lista*)malloc(sizeof(struct lista))
 
void dodaj(struct lista **p,int k){
struct lista *temp;
novi(temp);
if (!temp) {
printf("Greska pri alokaciji memorije\n");
exit(0);
}
temp->broj=k;
temp->rep=*p;
*p=temp;
}
 
struct lista *form_list(){
int m;
struct lista *p;
p=NULL;
scanf("%d",&m);
while(m){
dodaj(&p,m); 
scanf("%d",&m);
}
return p;
}
void ispis(struct lista *p){
while(p) {
printf("%5d",p->broj);
p=p->rep;
}
printf("\n");
}
 
main(){
struct lista *p;
p=form_list();
ispis(p);
}

Više o listama na SPA2

Nazad