In questo articolo andiamo a raccogliere le quattro funzioni caratteristiche delle liste, le funzioni che analizzeremo sono:

  • Is Empty;
  • Get;
  • Add;
  • Remove;

Ricordiamo brevemente la definizione data all’interno dell’articolo Analisi Strutture Dati: ogni elemento della struttura dati andrà a contenere il valore del campo e il puntatore al blocco successivo (quindi alla struttura dati successiva). In alcuni casi può essere più pratico creare un campo aggiuntivo in cui conservare anche il puntatore al nodo precedente. Per maggiori informazioni circa la sintassi del linguaggio si faccia riferimento alla guida al Linguaggio C.

algo_str1

Iniziamo definendo la struttura che conterà i nostri valori:

struct node {
 int value;
 struct node *next;
};
typedef struct node node;

struct node *first = null;

Funzione Is Empty

La funzione IS_EMPTY(node *first) permette la verifica dell’esistenza della lista passata come parametro, la funzione accetta in input un riferimento ad una struttura dati di tipo node (il seme della lista) e restituisce in output un valore intero (1 se la struttura esiste, 0 in caso contrario). Ricordiamo che nel linguaggio C non esiste un tipo nativo Boolean.

int is_empty(node *first) {
  if(first == NULL) {
    return 1;
  }
  else {
    return 0;
  }
}

Funzione Get

La funzione GET(node *first, int index) permette di acquisire il valore contenuto all’interno di un determinato nodo della lista (quello rappresentato dall’indice index).
Inizialmente si definisce un puntatore alla struttura dati interessata, tale puntatore viene denominato “current”. Successivamente il riferimento viene modificato, utilizzando come nuovo valore l’indirizzo al nodo successivo.
Il processo vene poi ripetuto fino all’esaurimento della lista o al raggiungimento dell’indice desiderato.

int get(node *first, int index) {
  node *current = first;
  int i = 0;

  while(current->next != NULL && i<index) {
    current = current->next;
    i++;
  }

  return current->value;
}

Funzione Add

La funzione ADD(node *first, int index, int value) permette l’inserimento di un nuovo nodo (contenente il valore scelto value) nella posizione index della lista indicata.

Come si può vedere dal codice sottostante, la funzione si comporta in modo diverso a seconda della posizione scelta dall’utente e in base alla condizione che la lista sia già stata creata oppure no. La prima condizione verifica la validità della lista e la posizione decisa dall’utente, se l’utente decide di lavorare all’inizio della lista (o su una lista vuota), la funzione inizializza un nuovo nodo e v’inserisce all’interno il valore scelto dall’utente. Il puntatore al nodo successivo viene impostato a NULL se la lista era precedentemente vuota, oppure viene settato con il puntatore al precedente nodo iniziale. Il valore NULL come indirizzo di blocco successivo permette di identificare l’ultimo nodo della lista.

Se si sceglie di lavorare in una posizione diversa dalla prima, la funzione dovrà scorrere tutti nodi della lista e aggiungerne uno nuovo risolvendo le dipendenze.

node *add(node *first, int index, int value) {
  node *current, *new;
  int i = 0;

  new = malloc(sizeof(node)); 
  if(new == NULL) {
    printf("Allocazione fallita");
    return NULL;
  } 

  if(is_empty(first) == 1 || index == 0) {
    new->value = value;
    new->next  = first;
  
    first = new;
  }
  else {
    current = first;
 
    while(current->next != NULL && i<index-1) {
      current = current->next;
      i++;
    }
 
    new->value = value;
    new->next  = current->next;

    current->next = new;
  }

  return first;
}

Funzione Remove

La funzione REMOVE(node *first, int index) consente l’eliminazione di un nodo, di posizione note, contenuto all’interno della lista passata come primo argomento.

node *remove(node *first, int index) {
  node *current = first;
  int i = 0;

  if(is_empty(first) == 1) {
    return NULL;
  }
  else if(index == 0) {
    first = first->next;
  }
  else {
    while(current->next != NULL && i<index-1) {
      current = current->next;
      i++;
    }

    current->next = current->next->next;
    free(current->next);
  }

  return first;
}

Altre informazioni

Per altre informazioni potete leggere anche: