Liste in C

Scopriamo cosa sono e come utilizzare le liste concatenate in C.

Cos’è una lista

Supponiamo di dover salvare una serie di elementi ma non sappiamo quanti potrebbero essere. Per dichiarare un array è necessario sapere il numero di elementi, quindi siamo costretti a scartare questa opzione. C’è forse un altro modo?

La risposta è si, bisogna utilizzare le liste.

Una lista è una serie di nodi collegati tra di loro. Per fare questo in C ogni nodo sarà una struct contenente un elemento e un puntatore al prossimo nodo. Un puntatore, chiamato testa della lista punterà al primo nodo. Il puntatore dell’ultimo invece verrà chiamato coda e punterà a NULL. Abbiamo appena descritto una lista semplice.

liste c

Tipi di liste

Esistono quattro tipi di liste:

Liste Semplici
Liste a doppio collegamento
Liste Circolari
Liste Circolari a doppio collegamento

Le Liste Semplici hanno un solo puntatore per nodo. In questo modo è possibile scorrere la lista ma solo per un senso, cioè dalla testa alla coda.

lista semplice c

//LISTA SEMPLICE
struct nodo{
    int elemento;
    struct nodo* successivo;
}

Le Liste a doppio collegamento hanno due puntatori per nodo. Questo rende possibili scorrerle in entrambe le direzioni.

lista doppia c

//LISTA DOPPIA
struct nodo{
  int elemento;
  struct nodo* precedente;
  struct nodo* successivo;
}

Nelle Liste Circolari l’ultimo puntatore anziché puntare a NULL punterà al primo nodo della lista formando appunto un cerchio.

lista circolare c

Le liste circolari a doppio collegamento uniscono le caratteristiche delle precedenti e permettono quindi di scorrere un lista circolare in entrambe le direzioni.

lista circolare doppia c

Funzioni per liste

Qui sotto ho scritto una serie di funzioni che permettono di svolgere le operazioni principali con delle liste semplici, prova a darci un occhiata e se dovessi averne bisogno, sei libero di usarle!

Funzioni

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


typedef struct nodo{

  int elemento;
  struct nodo* successivo;

} nodo;


//AGGIUNTA DI NODI NELLA LISTA
nodo* aggiungi_in_testa(int n, nodo* testa);
nodo* aggiungi_in_coda(int n,nodo* testa);
nodo* aggiungi_in_posizione(int n, int posizione, nodo* testa);

//RIMOZIONE DI NODI DALLA LISTA
nodo* rimuovi_in_testa(nodo* testa);
nodo* rimuovi_in_coda(nodo* testa);
nodo* rimuovi_in_posizione(int posizione,nodo* testa);

//ALTRE FUNZIONI
void stampa_lista(nodo* testa);
int cerca(int n, nodo* testa);
int conta(nodo* testa);

nodo* aggiungi_in_testa(int n, nodo* testa){
	if(testa != NULL){
		nodo* nodoSuccessivo = testa;
		testa = (nodo*) malloc(sizeof(nodo));
		testa -> elemento = n;
		testa -> successivo = nodoSuccessivo;
	}
	else{
		testa = (nodo*) malloc(sizeof(nodo));
		testa -> elemento = n;
		testa -> successivo = NULL;
	}
	return testa;
}

nodo* aggiungi_in_coda(int n, nodo* testa){
	if(testa != NULL){
		nodo* nodoSuccessivo = testa;
		while(nodoSuccessivo -> successivo != NULL){
			nodoSuccessivo = nodoSuccessivo -> successivo;
		}
	    nodoSuccessivo -> successivo = aggiungi_in_testa(n, NULL);
	}
	else{
		testa = aggiungi_in_testa(n, testa);
	}
	return testa;
}

nodo* aggiungi_in_posizione(int n, int posizione, nodo* testa){

	if(posizione == 0 || testa == NULL){
		testa = aggiungi_in_testa(n, testa);
	}
	else if(posizione > 0){
		int i=1;
		nodo* nodoSuccessivo = testa;
		while(i < posizione && nodoSuccessivo -> successivo != NULL){
			nodoSuccessivo = nodoSuccessivo -> successivo;
			i++;
		}
		nodoSuccessivo -> successivo = aggiungi_in_testa(n, nodoSuccessivo -> successivo);
	}
	return testa;
}

nodo* rimuovi_in_testa(nodo* testa){
	if(testa != NULL){
		nodo* daEliminare = testa;
		testa = testa -> successivo;
		free(daEliminare);
	}

	return testa;
}

nodo* rimuovi_in_coda(nodo* testa){
	if(testa != NULL){
		if(testa -> successivo != NULL){

			nodo* attuale = testa;
			nodo* daEliminare = testa -> successivo;

			while(daEliminare -> successivo != NULL){
				attuale = daEliminare;
				daEliminare = daEliminare -> successivo;
			}
	    	attuale -> successivo = rimuovi_in_testa(daEliminare);
		}
		else{
			testa = rimuovi_in_testa(testa);
		}
	}

	return testa;
}

nodo* rimuovi_in_posizione(int posizione, nodo* testa){


	if(posizione == 0 || testa -> successivo == NULL){
		testa = rimuovi_in_testa(testa);
	}
	else if(posizione > 0){
		int i=1;

		nodo* attuale = testa;
		nodo* daEliminare = testa -> successivo;

		while(i < posizione && daEliminare-> successivo != NULL){
                        attuale = daEliminare;
			daEliminare = daEliminare -> successivo;
			i++;
		}
		attuale -> successivo = rimuovi_in_testa( daEliminare -> successivo);

	}
	return testa;
}


void stampa_lista(nodo * testa){
	if(testa != NULL){
		printf("TESTA -> ");
		while(testa != NULL){
			printf("%d -> ",testa->elemento);
			testa = testa -> successivo;
		}
	    printf("NULL \n");
	}
	else {
		printf("LISTA VUOTA \n");
	}
}

int cerca(int n,nodo* testa){
	int posizione = -1;
	int trovato = 0;
	int i=0;
	while(testa != NULL && trovato == 0){
		if(testa -> elemento == n){
			posizione = i;
			trovato = 1;
		}
		i++;
		testa = testa -> successivo;
	}
	return posizione;
}

int conta(nodo* testa){
	int i=0;
	while(testa != NULL){
		i++;
		testa = testa -> successivo;
	}
	return i;
}

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


typedef struct nodo{

  int elemento;
  struct nodo* successivo;

} nodo;


//AGGIUNTA DI NODI NELLA LISTA
void aggiungi_in_testa(int n, nodo** testa);
void aggiungi_in_coda(int n,nodo** testa);
void aggiungi_in_posizione(int n, int posizione, nodo** testa);

//RIMOZIONE DI NODI DALLA LISTA
void rimuovi_in_testa(nodo** testa);
void rimuovi_in_coda(nodo** testa);
void rimuovi_in_posizione(int posizione,nodo** testa);

//ALTRE FUNZIONI
void stampa_lista(nodo* testa);
int cerca(int n, nodo* testa);
int conta(nodo* testa);

void aggiungi_in_testa(int n, nodo** testa){
	nodo* nuovo = (nodo*) malloc(sizeof(nodo));
	nuovo -> elemento = n;
	nuovo -> successivo = *testa;
	*testa = nuovo;
}

void aggiungi_in_coda(int n, nodo** testa){
	if(*testa != NULL){
		nodo* nodoSuccessivo = *testa;
		while(nodoSuccessivo -> successivo != NULL){
			nodoSuccessivo = nodoSuccessivo -> successivo;
		}
	    aggiungi_in_testa(n, &(nodoSuccessivo -> successivo));
	}
	else{
		aggiungi_in_testa(n, testa);
	}
}

void aggiungi_in_posizione(int n, int posizione, nodo** testa){

	if(posizione == 0 || *testa == NULL){
		aggiungi_in_testa(n, testa);
	}
	else if(posizione > 0){
		int i=1;
		nodo* nodoSuccessivo = *testa;
		while(i < posizione && nodoSuccessivo -> successivo != NULL){
			nodoSuccessivo = nodoSuccessivo -> successivo;
			i++;
		}
		aggiungi_in_testa(n, &(nodoSuccessivo -> successivo));
	}
}

void rimuovi_in_testa(nodo** testa){
	if(*testa != NULL){
		nodo* daEliminare = *testa;
		*testa = (*testa) -> successivo;
		free(daEliminare);
	}

}

void rimuovi_in_coda(nodo** testa){
	if(*testa != NULL){
		if( (*testa) -> successivo != NULL){

			nodo* attuale = *testa;
			nodo* daEliminare = (*testa) -> successivo;

			while(daEliminare -> successivo != NULL){
				attuale = daEliminare;
				daEliminare = daEliminare -> successivo;
			}
	    	rimuovi_in_testa(&attuale->successivo);
		}
		else{
			rimuovi_in_testa(testa);
		}
	}

}

void rimuovi_in_posizione(int posizione, nodo** testa){


	if(posizione == 0 || (*testa) -> successivo == NULL){
		rimuovi_in_testa(testa);
	}
	else if(posizione > 0){
		int i=1;

		nodo* attuale = *testa;
		nodo* daEliminare = (*testa) -> successivo;

		while(i < posizione && daEliminare-> successivo != NULL){
			attuale = daEliminare;
			daEliminare = daEliminare -> successivo;
			i++;
		}
		rimuovi_in_testa( &(attuale -> successivo));

	}

}


void stampa_lista(nodo * testa){
	if(testa != NULL){
		printf("TESTA -> ");
		while(testa != NULL){
			printf("%d -> ",testa->elemento);
			testa = testa -> successivo;
		}
	    printf("NULL \n");
	}
	else {
		printf("LISTA VUOTA \n");
	}
}

int cerca(int n,nodo* testa){
	int posizione = -1;
	int trovato = 0;
	int i=0;
	while(testa != NULL && trovato == 0){
		if(testa -> elemento == n){
			posizione = i;
			trovato = 1;
		}
		i++;
		testa = testa -> successivo;
	}
	return posizione;
}

int conta(nodo* testa){
	int i=0;
	while(testa != NULL){
		i++;
		testa = testa -> successivo;
	}
	return i;
}

Programma di esempio

Utilizziamo le funzioni scritte in precedenza per gestire una lista di elementi.

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

typedef struct nodo{

    int elemento;
    struct nodo* successivo;

} nodo;


//AGGIUNTA DI NODI NELLA LISTA
nodo* aggiungi_in_testa(int n, nodo* testa);
nodo* aggiungi_in_coda(int n,nodo* testa);
nodo* aggiungi_in_posizione(int n, int posizione, nodo* testa);

//RIMOZIONE DI NODI DALLA LISTA
nodo* rimuovi_in_testa(nodo* testa);
nodo* rimuovi_in_coda(nodo* testa);
nodo* rimuovi_in_posizione(int posizione,nodo* testa);

//ALTRE FUNZIONI
void stampa_lista(nodo* testa);
int cerca(int n, nodo* testa);
int conta(nodo* testa);


int main(){

	//Creo il nodo di testa e lo inserisco nella lista
	nodo *lista = NULL;
	lista = aggiungi_in_testa(1, lista);

	//LISTA: 1 -> NULL
	stampa_lista( lista );

	//Aggiungo un nodo alla fine della lista
	lista = aggiungi_in_coda(3, lista);

	//LISTA: 1 -> 3 -> NULL
	stampa_lista( lista );

	//Aggiungo nodo tra il primo e il secondo
	lista = aggiungi_in_posizione(2, 1, lista);

	//LISTA: 1 -> 2 -> 3 -> NULL
	stampa_lista( lista );

	//Conto il numero di nodi
	printf("Nodi: %d\n", conta( lista ) );

	//Cerco il nodo con elemento di valore 3 e lo elimino
	int posizioneDaEliminare = cerca(3, lista);
	lista = rimuovi_in_posizione(posizioneDaEliminare, lista);

	//LISTA: 1 -> 2 -> NULL
	stampa_lista( lista );

	return 0;

}



nodo* aggiungi_in_testa(int n, nodo* testa){
	if(testa != NULL){
		nodo* nodoSuccessivo = testa;
		testa = (nodo*) malloc(sizeof(nodo));
		testa -> elemento = n;
		testa -> successivo = nodoSuccessivo;
	}
	else{
		testa = (nodo*) malloc(sizeof(nodo));
		testa -> elemento = n;
		testa -> successivo = NULL;
	}
	return testa;
}

nodo* aggiungi_in_coda(int n, nodo* testa){
	if(testa != NULL){
		nodo* nodoSuccessivo = testa;
		while(nodoSuccessivo -> successivo != NULL){
			nodoSuccessivo = nodoSuccessivo -> successivo;
		}
	    nodoSuccessivo -> successivo = aggiungi_in_testa(n, NULL);
	}
	else{
		testa = aggiungi_in_testa(n, testa);
	}
	return testa;
}

nodo* aggiungi_in_posizione(int n, int posizione, nodo* testa){

	if(posizione == 0 || testa == NULL){
		testa = aggiungi_in_testa(n, testa);
	}
	else if(posizione > 0){
		int i=1;
		nodo* nodoSuccessivo = testa;
		while(i < posizione && nodoSuccessivo -> successivo != NULL){
			nodoSuccessivo = nodoSuccessivo -> successivo;
			i++;
		}
		nodoSuccessivo -> successivo = aggiungi_in_testa(n, nodoSuccessivo -> successivo);
	}
	return testa;
}

nodo* rimuovi_in_testa(nodo* testa){
	if(testa != NULL){
		nodo* daEliminare = testa;
		testa = testa -> successivo;
		free(daEliminare);
	}

	return testa;
}

nodo* rimuovi_in_coda(nodo* testa){
	if(testa != NULL){
		if(testa -> successivo != NULL){

			nodo* attuale = testa;
			nodo* daEliminare = testa -> successivo;

			while(daEliminare -> successivo != NULL){
				attuale = daEliminare;
				daEliminare = daEliminare -> successivo;
			}
	    	attuale -> successivo = rimuovi_in_testa(daEliminare);
		}
		else{
			testa = rimuovi_in_testa(testa);
		}
	}

	return testa;
}

nodo* rimuovi_in_posizione(int posizione, nodo* testa){


	if(posizione == 0 || testa -> successivo == NULL){
		testa = rimuovi_in_testa(testa);
	}
	else if(posizione > 0){
		int i=1;

		nodo* attuale = testa;
		nodo* daEliminare = testa -> successivo;

		while(i < posizione && daEliminare-> successivo != NULL){
                        attuale = daEliminare;
			daEliminare = daEliminare -> successivo;
			i++;
		}
		attuale -> successivo = rimuovi_in_testa( daEliminare -> successivo);

	}
	return testa;
}


void stampa_lista(nodo * testa){
	if(testa != NULL){
		printf("TESTA -> ");
		while(testa != NULL){
			printf("%d -> ",testa->elemento);
			testa = testa -> successivo;
		}
	    printf("NULL \n");
	}
	else {
		printf("LISTA VUOTA \n");
	}
}

int cerca(int n,nodo* testa){
	int posizione = -1;
	int trovato = 0;
	int i=0;
	while(testa != NULL && trovato == 0){
		if(testa -> elemento == n){
			posizione = i;
			trovato = 1;
		}
		i++;
		testa = testa -> successivo;
	}
	return posizione;
}

int conta(nodo* testa){
	int i=0;
	while(testa != NULL){
		i++;
		testa = testa -> successivo;
	}
	return i;
}

TESTA -> 1 -> NULL
TESTA -> 1 -> 3 -> NULL
TESTA -> 1 -> 2 -> 3 -> NULL
Nodi: 3
TESTA -> 1 -> 2 -> NULL

Saturday, January 18th 2020

Liste in C

Cos’è una lista

Tipi di liste

Funzioni per liste

Programma di esempio