Strukture podataka i algoritmi 1

SPA1 - Vežbe 10

Jednostruko povezane liste

Jednostruko povezane liste su osnovna struktura podataka u programiranju, često korišćena za organizaciju podataka u sekvenci. Svaki čvor u jednostruko povezanoj listi sastoji se od dva dela: podatka i pokazivača na sledeći čvor u listi. Ova struktura omogućava efikasno dodavanje i uklanjanje elemenata sa početka ili kraja liste, ali je manje efikasna za pristupanje elementima po indeksu.

Evo osnovnih karakteristika jednostruko povezanih listi:

  1. Struktura čvora: Svaki čvor u listi sadrži dva polja - podatak koji čuva vrednost i pokazivač na sledeći čvor u listi.

  2. Glava liste: Glava liste je pokazivač na prvi čvor u listi. Ona omogućava pristup početku liste.

  3. Prazna lista: Prazna lista predstavlja specijalni slučaj u kojem glava liste pokazuje na NULL, što znači da lista ne sadrži nijedan čvor.

  4. Dodavanje elemenata: Novi elementi se dodaju na početak ili kraj liste. Da biste dodali element na početak liste, jednostavno alocirate memoriju za novi čvor, postavite podatak i ažurirate pokazivač glave liste da pokazuje na novi čvor. Ako želite da dodate element na kraj liste, morate iterirati kroz listu sve do poslednjeg čvora i postaviti pokazivač poslednjeg čvora na novi čvor.

  5. Uklanjanje elemenata: Slično dodavanju, elementi se mogu ukloniti s početka ili kraja liste. Da biste uklonili element s početka liste, jednostavno ažurirajte pokazivač glave liste da pokazuje na drugi čvor, a oslobodite memoriju prvog čvora. Za uklanjanje elementa s kraja liste, morate iterirati kroz listu sve do poslednjeg čvora, a zatim osloboditi memoriju poslednjeg čvora.

  6. Prolazak kroz listu: Za prolazak kroz listu koristi se iteracija pomoću pokazivača na čvorove. Prolazak kroz listu obično se vrši pomoću petlje while ili for, dok se ne dođe do kraja liste (kada pokazivač na čvor postane NULL).

Jednostruko povezane liste su fleksibilna struktura podataka koja se često koristi u implementaciji različitih algoritama i rešavanju problema, poput upravljanja memorijom, algoritama pretrage i sortiranja, kao i u implementaciji apstraktnih podataka kao što su stekovi i redovi.

Primer

typedef struct element
{
    int broj; // podatak. moze biti i vise podataka a ne samo jedan int
    struct element *sledeci; // koristi 8 bajtova za skladistenje u memoriji kao bilo koji drugi pokazivac
} Element;

Sada se možda pitate kako prilikom definisanja strukture, unutar same strukture imamo pokazivač koji pokazuje na tu istu strukturu. To je moguće jer struct element *sledeci služi da označi promenljivu u kojoj će biti smeštena memorijska adresa na kojoj se nalazi jedan int i jedan pokazivač.

Dodavanje elementa u listu

Dodavanje na kraj prolazeći celu listu

#include <stdio.h>
#include <stdlib.h>

typedef struct element
{
    int broj;
    struct element *sledeci;
} Element;

Element *alocirajElement(int x) {
  Element *el = malloc(sizeof(Element));
  el->broj = x;
  el->sledeci = NULL;

  return el;
}

void dodaj(Element **p, int x)
{
  Element *novi = alocirajElement(x);

  if (*p == NULL)
    *p = novi;
  else
  {
    Element *pom = *p;
    while (pom->sledeci != NULL) // sve dok postoji sledeci element pomeri pokazivac
      pom = pom->sledeci;
    pom->sledeci = novi; // sledeci element poslednjeg elementa ce biti novi element
  }
}

void ispis(Element *lista) {
  if (lista == NULL) {
    printf("Lista je prazna\n");
    return;
  }

  while(lista) {
    printf("%d ", lista -> broj);
    lista = lista->sledeci;
  }

  printf("\n");
}

int main() {
  Element *glava = NULL; // prazna lista

  dodaj(&glava, 10); // prosledjuje se pokazivac na promenljivu glava kako bi se u promenljivu glava upisala adresa glave liste
  dodaj(&glava, 20);
  dodaj(&glava, 30);
  dodaj(&glava, 40);

  ispis(glava);

  return 0;
}

Dodavanje na kraj koristeći pokazivač na kraj liste

Prednost ovog pristupa je ta da ako želimo da dodamo novi element na kraj liste ne moramo da prolazimo celu listu već to možemo uraditi u kompleksnosti O(1). Mana ovog pristupa je ta da za svaku listu moramo da imamo dva pokazivača i da moramo da vodimo računa o tome kako menjamo njihove vrednosti.

#include <stdio.h>
#include <stdlib.h>

typedef struct element
{
    int broj;
    struct element *sledeci;
} Element;

Element *alocirajElement(int x) {
  Element *el = malloc(sizeof(Element));
  el->broj = x;
  el->sledeci = NULL;

  return el;
}

void dodaj(Element **pocetak, Element **kraj, int x)
{
  Element *novi = alocirajElement(x);

  if (*pocetak == NULL)
    *pocetak = *kraj = novi;
  else {
    (*kraj)->sledeci = novi;
    *kraj = novi;
  }
}

void ispis(Element *lista) {
  if (lista == NULL) {
    printf("Lista je prazna\n");
    return;
  }

  while(lista) {
    printf("%d ", lista -> broj);
    lista = lista->sledeci;
  }

  printf("\n");
}

int main() {
  Element *glava = NULL, *krajListe = NULL; // prazna lista

  dodaj(&glava, &krajListe, 10);
  dodaj(&glava, &krajListe, 20);
  dodaj(&glava, &krajListe, 30);
  dodaj(&glava, &krajListe, 40);

  ispis(glava);

  return 0;
}

Dodavanje elementa na početak liste

#include <stdio.h>
#include <stdlib.h>

typedef struct element
{
    int broj;
    struct element *sledeci;
} Element;

Element *alocirajElement(int x) {
  Element *el = malloc(sizeof(Element));
  el->broj = x;
  el->sledeci = NULL;

  return el;
}

void dodaj(Element **p, int x)
{
  Element *novi = alocirajElement(x);

  if (*p == NULL)
    *p = novi;
  else
  {
    novi->sledeci = *p; // nakon novog elementa u listi treba da se nalazi trenutna glava liste
    *p = novi; // novi element postaje nova glava
  }
}

void ispis(Element *lista) {
  if (lista == NULL) {
    printf("Lista je prazna\n");
    return;
  }

  while(lista) {
    printf("%d ", lista -> broj);
    lista = lista->sledeci;
  }

  printf("\n");
}

int main() {
  Element *glava = NULL; // prazna lista

  dodaj(&glava, 10); // prosledjuje se pokazivac na promenljivu glava kako bi se u promenljivu glava upisala adresa glave liste
  dodaj(&glava, 20);
  dodaj(&glava, 30);
  dodaj(&glava, 40);

  ispis(glava);

  return 0;
}

dodavanje na pocetak

Dodavanje elementa bilo gde u listi

Neka je lista sortirana u neopadajućem poretku i treba da u nju dodamo novi element tako da poredak ostane isti.
Tada moramo da pokrijemo sva tri slučaja koja mogu da se dese:

  1. Slučaj 1 - lista je prazna
  2. Slučaj 2 - treba da promenim vrednost glave, tj. glava treba da pokazuje na neki drugi element
  3. Slučaj 3 - ne treba da menjam vrednost glave, već samo da umetnem novi element nakon nekog elementa

Napomena: Ove slučajeve UVEK treba pokriti kada se radi dodavanje u listu, bez obzira na to kako treba da dodamo elemente. Iste ove slučajeve moramo da pokrijemo i prilikom brisanja elementa iz liste.

#include <stdio.h>
#include <stdlib.h>

typedef struct element
{
    int broj;
    struct element *sledeci;
} Element;

Element *alocirajElement(int x) {
  Element *el = malloc(sizeof(Element));
  el->broj = x;
  el->sledeci = NULL;

  return el;
}

void dodajSortirano(Element **p, int x)
{
  Element *novi = alocirajElement(x);

  if (*p == NULL) { // slucaj 1
    *p = novi;
    return;
  }

  Element *pom = *p; // trenutni element koji razmatramo
  Element *pret = NULL; // cuvamo i prethodni element elementa kojeg razmatramo kako bi mogli da ubacimo novi element izmedju ova dva

  if (pom->broj > x) { // slucaj 2
    //radimo dodavanje na pocetak
    novi->sledeci = pom;
    *p = novi;
    return;
  }

  while (pom && pom->broj < x) { // slucaj 3
    // trazimo elemente izmedju kojih treba da umetnemo novi element
    pret = pom;
    pom = pom->sledeci;
  }

  // nasli smo element izmedju kojih treba da umetnemo novi element
  novi->sledeci = pret->sledeci;
  pret->sledeci = novi;
}

void ispis(Element *lista) {
  if (lista == NULL) {
    printf("Lista je prazna\n");
    return;
  }

  while(lista) {
    printf("%d ", lista -> broj);
    lista = lista->sledeci;
  }

  printf("\n");
}

int main() {
  Element *glava = NULL; // prazna lista

  dodajSortirano(&glava, 10); // prosledjuje se pokazivac na promenljivu glava kako bi se u promenljivu glava upisala adresa glave liste
  dodajSortirano(&glava, 9);
  dodajSortirano(&glava, 12);
  dodajSortirano(&glava, 11);
  dodajSortirano(&glava, 15);

  ispis(glava);

  return 0;
}

dodavanje u sredini

Brisanje elementa iz liste

Slično kao kod dodavanja, postoje 3 slučaja koja mogu da se dogode prilikom brisanja:

  1. Slučaj 1 - lista je prazna i ne treba da radimo ništa
  2. Slučaj 2 - treba da izbrišem glavu liste, tj. glava liste će nakon brisanja biti drugi element u listi (glava = glava->sledeci)
  3. Slučaj 3 - ne treba da menjam vrednost glave, već samo da izbrišem element tako što ću da promenim prethodni element

Pre nego što obrišemo element moramo da ga prvo “otkačimo” tj. da ga uklonimo iz liste. Kada ga uklonimo iz liste, tek onda možemo da radimo free ili da ga dodamo u neku drugu listu.

#include <stdio.h>
#include <stdlib.h>

typedef struct element
{
    int broj;
    struct element *sledeci;
} Element;

Element *alocirajElement(int x) {
  Element *el = malloc(sizeof(Element));
  el->broj = x;
  el->sledeci = NULL;

  return el;
}

void dodajSortirano(Element **p, int x)
{
  Element *novi = alocirajElement(x);

  if (*p == NULL) { // slucaj 1
    *p = novi;
    return;
  }

  Element *pom = *p; // trenutni element koji razmatramo
  Element *pret = NULL; // cuvamo i prethodni element elementa kojeg razmatramo kako bi mogli da ubacimo novi element izmedju ova dva

  if (pom->broj > x) { // slucaj 2
    //radimo dodavanje na pocetak
    novi->sledeci = pom;
    *p = novi;
    return;
  }

  while (pom && pom->broj < x) { // slucaj 3
    // trazimo elemente izmedju kojih treba da umetnemo novi element
    pret = pom;
    pom = pom->sledeci;
  }

  // nasli smo element izmedju kojih treba da umetnemo novi element
  novi->sledeci = pret->sledeci;
  pret->sledeci = novi;
}

void izbrisi(Element **p, int broj) {
  if (*p == NULL) // slucaj 1
    return;

  Element *pom = *p;
  Element *pret = NULL; // cuvamo pokazivac na prethodni element u listi

  while (pom && pom->broj == broj) { // slucaj 2. ovaj uslov bi ovako glasio u opstem slucaju: pom && uslovZaBrisanje
    *p = pom->sledeci;

    free(pom);
    // ili
    /*
    pom->sledeci = NULL;
    dodajUNovuListu(&novaLista, pom);
    */

    pom = *p;
  }

  pret = *p;
  pom = pret->sledeci;

  while (pom) { // slucaj 3
    if (pom->broj == broj) {
      pret->sledeci = pom->sledeci;

      free(pom);

      pom = pret->sledeci;
    } else {
      pret = pom;
      pom = pom->sledeci;
    }
  }
}

void ispis(Element *lista) {
  if (lista == NULL) {
    printf("Lista je prazna\n");
    return;
  }

  while(lista) {
    printf("%d ", lista -> broj);
    lista = lista->sledeci;
  }

  printf("\n");
}

int main() {
  Element *glava = NULL; // prazna lista

  dodajSortirano(&glava, 10); // prosledjuje se pokazivac na promenljivu glava kako bi se u promenljivu glava upisala adresa glave liste
  dodajSortirano(&glava, 9);
  dodajSortirano(&glava, 12);
  dodajSortirano(&glava, 11);
  dodajSortirano(&glava, 15);

  ispis(glava);

  izbrisi(&glava, 9);
  izbrisi(&glava, 11);

  ispis(glava);

  return 0;
}

brisanje elementa iz liste

This site is open source. Improve this page.