Corso di informatica Athena – Periti Informatici Liste Code e Pile! Docente: Daniele Prevedello.

Corso di informatica Athena – Periti Informatici

Liste

Code e Pile!

Docente: Daniele Prevedello


In informatica, una lista concatenata (o linked list) è una delle strutture dati fondamentali usate nellaprogrammazione. Essa consiste di una sequenza di nodi, ognuno contenente campi di dati arbitrari ed uno o due riferimenti ("link") che puntano al nodo successivo e/o precedente.



Il modo più semplice di creare una lista è una lista semplicemente concatenata, che utilizza un collegamento per nodo.

Questo collegamento punta al nodo successivo della lista o a un valore nullo.



Un tipo più sofisticato di lista è una lista doppiamente concatenata o lista concatenata a due vie.

Ogni nodo possiede due collegamenti: uno punta al nodo precedente o ad un valore nullo se è il primo nodo;

l'altro punta al nodo successivo o ad un valore nullo se è il nodo finale.



Le liste concatenate hanno vari vantaggi nei confronti degli array:


Gli elementi possono essere inseriti nelle liste indefinitamente;

Le operazioni di inserimento e cancellazione sono molto più veloci.


Però presentano anche alcuni svantaggi rispetto agli array:


Mentre gli array permettono un accesso casuale, le liste concatenate permettono soltanto un accesso sequenziale agli elementi ;

Nelle liste concatenate viene usato più spazio per memorizzare i riferimenti agli elementi successivi (e precedenti).


typedef struct ns {

int data;

struct ns* next;

} node;


int o qualunque altro tipo

semplice o complesso

(array o altra struttura)


node *list_add(node** p, int i) {

node *n = (node*)malloc(sizeof(node));

n->next = *p;

*p = n;

n->data = i;

return n;

}


Inserimento


void list_remove(node** p) { /* rimuove head */

if (*p != NULL) {

node *n = *p;

*p = (*p)->next;

free(n);

}

}


Cancellazione


node** list_search(node** n, int i) {

while (*n != NULL) {

if ((*n)->data == i) {

return n;

}

n = &(*n)->next;

}

return NULL;

}


Ricerca


void list_print(node* n) {if (n == NULL) {

printf("la lista è vuota\n");}while (n != NULL) {

printf("print %p %p %d\n", n, n->next, n->data);

n = n->next;}

}


Scorrimento


int main(void) { node *n = NULL; list_add(&n, 0); /* lista: 0 */ list_add(&n, 1); /* lista: 1 0 */ list_add(&n, 2); /* lista: 2 1 0 */ list_add(&n, 3); /* lista: 3 2 1 0 */ list_add(&n, 4); /* lista: 4 3 2 1 0 */ list_print(n); list_remove(&n); /* rimuove il primo elemento (4) */ list_remove(&n->next); /* rimuove il nuovo secondo (2) */ list_remove(list_search(&n, 1)); /* rimuove la cella che contiene 1 (primo) */ list_remove(&n->next); /* rimuove il successivo (0) */ list_remove(&n); /* rimuove l'ultimo (3) */ list_print(n); return 0;}



CodeDocente: Daniele Prevedello


In Informatica per coda si intende una struttura dati di tipo FIFO, First In First Out (il primo in ingresso è il primo ad uscire).

Un esempio pratico sono le code che in un paese civile si fanno per ottenere un servizio, come pagare al supermercato o farsi tagliare i capelli dal parrucchiere: idealmente si viene serviti nello stesso ordine con cui ci si è presentati.



Operazioni su una coda:Operazioni su una coda:

Accodamento di un elemento Detta anche operazione di enqueue, serve a

mettere un elemento in coda. Estrazione di un elemento

Detta anche operazione di dequeue, serve a rimuovere un elemento dalla testa della coda.



Per implementare una coda viene utilizzato normalmente una lista concatenata.

Ogni elemento della lista è un elemento della coda. Inoltre, viene conservata la testa coda come un puntatore.

L'operazione di accodamento consiste nella normale operazione di inserimento di un elemento nella lista.

L'operazione di estrazione consiste nel sostituire il puntatore che conserva la testa della coda con il secondo elemento della coda.

È possibile inoltre utilizzare un array che può essere trattato come array circolare.



Pile oStack



In informatica, il termine stack o pila viene usato per riferirsi a strutture dati le cui modalità d'accesso seguono una politica LIFO (Last In First Out).

I dati vengono estratti (letti) in ordine rigorosamente inverso rispetto a quello in cui sono stati inseriti (scritti).



Si immagini ad esempio una "pila di piatti" o una "pila di giornali“; l'idea è che quando si pone un piatto nella pila lo si metta in cima, e che quando si preleva un piatto si prelevi, analogamente, quello in cima.

In generale la pila è un particolare tipo di lista in cui le operazioni di inserimento ed estrazione si compiono dallo stesso estremo.



Esercizi

Realizzare una lista che permetta di memorizzare un numero non definito di valori interi inseriti da un utente.

Stampare la lista. Permettere la ricerca di un valore nella lista. Permettere la cancellazione di un elemento.



Ultimo compito:

IMPARARE A MEMORIA IMPARARE A MEMORIA COME IMPLEMENTARE UNA COME IMPLEMENTARE UNA LISTA (CODA O PILA) E LE LISTA (CODA O PILA) E LE OPERAZIONI SU DI ESSE!OPERAZIONI SU DI ESSE!


Corso di informatica Athena – Periti Informatici Liste Code e Pile! Docente: Daniele Prevedello.

Documents

Transcript of Corso di informatica Athena – Periti Informatici Liste Code e Pile! Docente: Daniele Prevedello.