Двоструко повезане листе

Радећи са једноструко повезаним листама могли смо уочити следеће проблеме:
1. Једноструко повезане листе омогућавају кретање кроз листу само у једном правцу.
2. Брисање елемента из листе захтева стално чување претходног елемента током кретања кроз листу, како би се знао претходник елемента који је потребно обрисати.
3. Уколико дође до губљења везе у неком елементу, остали елементи постају недоступни.

Ови проблеми код једноструко повезаних листа могу бити превазиђени увођењем показивача на претходника у сваком елементу. Када сваки елемент листе садржи показивач на свог следбеника и претходника, такву листу називамо двоструко повезана листа.

Шематски приказ двоструко повезане листе

Шематски приказ двоструко повезане листе

Као и једноструко повезана листа и двоструко повезана листа може бити у облику ланца или кружна. Уколико је листа у облику ланца, показивачи на претходника првог елемента и следбеника последњег елемента морају бити NULL показивачи.

Реализација двоструко повезане листе може се обавити помоћу следеће структуре:

struct delement 
{ 
int podatak; 
struct delement *levi,*desni; 
};

Следећи програм креира и штампа двоструко повезану листу:

# include <stdio.h> 
# include <stdlib.h> 
 struct delement 
{ int podatak;struct delement *levi, *desni;}; 
 struct delement *dodaj(struct delement *p, struct delement **q, int n) 
{ 
struct delement *pom; 
if(p==NULL) 
{ 
p=(struct delement *)malloc(sizeof(struct delement)); 
if(p==NULL) { printf("Greska.\n"); exit(0); } 
 p‐>podatak = n; 
p‐>levi = p‐>desni = NULL; 
*q = p; 
} 
else 
{ 
pom = (struct delement *)malloc(sizeof(struct delement)); 
if(pom == NULL) { printf("Greska.\n"); exit(0); } 
 pom‐>podatak = n; 
pom‐>levi = (*q);  
pom‐>desni = NULL;   
(*q)‐>desni = pom; 
(*q) = pom; 
} 
 return (p); 
} 
 void stampaj_desno( struct delement *p ) 
{ 
printf("Podaci u listi stampani u desno su:\n"); 
while (p!= NULL) 
{ 
printf("%d\t",p‐>podatak); 
p = p‐>desni; 
} 
} 
 void stampaj_levo( struct delement *p ) 
{ 
printf("Podaci u listi stampani u levo su:\n"); 
while (p!= NULL) 
{ 
printf("%d\t",p‐>podatak); 
p = p‐>levi; 
} 
} 
 void main() 
{ 
int n,i; 
int x; 
  struct delement *pocetak = NULL ; 
  struct delement *kraj = NULL; 
  printf("Unesite broj elementa liste:\n"); 
  scanf("%d",&n); 
  for(i=0; i<n; i++) 
  { 
  printf( "Unesi vrednost:\n"); 
  scanf("%d",&x); 
  pocetak = dodaj( pocetak, &kraj, x ); 
  } 
  printf("Kreirana lista je:\n"); 
  stampaj_desno( pocetak ); 
  stampaj_levo( kraj ); 
}

За креирање двоструко повезане листе овај програм користи функцију dodaj која има три параметра: показивач на почетак листе, показивач на крај листе и вредност податка који треба додати у листу. Користећи задату вредност, функција креира нови елемент, додаје га на крај листе и враћа показивач на почетак листе.

На почетку је листа празна, тако да је показивач на почетак листе NULL. Након првог позива функције dodaj нови елемент постаје и почетни елемент листе. Уколико листа није била празна, функција смешта показивач на нови елемент у помоћни показивач. Затим се лева веза новог елемента поставља да показује на последњи елемент постојеће листе, а десна веза постаје NULL. На крају се десна веза последњег елемента постојеће листе поставља да показује на нови елемент, а затим показивач на крај досадашње листе поставља да показује на нови елемент.
Главни програм више пута позива функцију додај у циљу креирања двоструко повезане листе са задатим бројем елемената.

Оставите одговор

Попуните детаље испод или притисните на иконицу да бисте се пријавили:

WordPress.com лого

Коментаришет користећи свој WordPress.com налог. Одјавите се /  Промени )

Google+ photo

Коментаришет користећи свој Google+ налог. Одјавите се /  Промени )

Слика на Твитеру

Коментаришет користећи свој Twitter налог. Одјавите се /  Промени )

Фејсбукова фотографија

Коментаришет користећи свој Facebook налог. Одјавите се /  Промени )

Повезивање са %s