Impara a Programmare, Lezione 1: Le Liste in C

Algoritmi e Strutture Dati Avanzate in C, Lezione 1: Le Liste in C

Benvenuti in questa prima lezione della serie “Scuola Serale di Italian Geek“.

Queste brevi lezioni sono state progettate in modo tale da risultare volutamente sintetiche, dunque, per approfondimenti contattateci usando i commenti a fine articolo. Il codice presente nelle lezioni e’ funzionante ed e’ stato testato su compilatore gcc version 3.4.6 20060404 (Red Hat 3.4.6-9). Ricordiamo che queste lezioni sono state create per utenti avanzati con una conoscenza di base del linguaggio C e dei paradigmi di programmazione.

Le Liste

Per molte applicazioni la scelta della struttura dati adatta e` l’unica decisione importante della fase di implementazione: una volta fatta questa scelta, sara` necessario adattare anche il giusto algoritmo. Infatti, per lo stesso insieme di dati, alcune strutture dati richiedono piu` o meno risorse di altre. E per lo stesso insieme di operazione sugli stessi dati, alcune strutture dati portano ad implementare algoritmi piu` o meno efficienti di altri.

Focalizzeremo la nostra attenzione sulle rappresentazione dei dati e sulla loro manipolazione e faremo uso di esempi in linguaggio C per agevolarne la spiegazione.

Il linguaggio C (come anche il Lisp), non considera le “liste” come strutture dati primitive, ma mette a disposizione una serie di operazioni che consentono l’uso delle liste concatenate in modo abbastanza semplice.

Le strutture dati possono essere distinte in due grosse unita`:

• Statiche: array e vettori ne sono un esempio
• Dinamiche: come ad esempio liste, alberi e grafi.

Analizziamo vantaggi e svantaggi dell’uso delle liste

Il vantaggio principale dell’uso delle liste come strutture dati dinamiche consiste percio’ nella intrinseca capacita’  “dinamica” a crescere o decrescere a secondo dell’esigenza del programma che ne fa uso. Usando le liste, non e’ necessario conoscere a priori lo spazio di memoria massimo necessario per la struttura dati (come avviene per gli array statici). Questo comporta un vantaggio nell’uso ottimizzato della memoria.

Un altro vantaggio consiste nella flessibilita` con la quale e` possibile riordinare in modo efficiente gli elementi di una qualunque lista.

Tuttavia questa sua “flessibilita`” o “dinamicita`” vanno a discapito della velocita` di accesso ad un elemento arbitrario  della struttura dati. Contrariamente ad un array dove si puo` accedere direttamente all’i-esimo elemento, attraverso l’indice i, in una lista per accedere all’i-esimo elemento bisogna, partento dalla sua testa, scorrere i suoi i-1 elementi precedenti. Quindi, se ad esempio una lista ha n elementi, nel cas peggiore, servira` scorrere gli n-1 elementi precedenti.

Una lista concatenata e` un insieme di oggetti organizzati in modo sequenziale, proprio come un array. Ma a differenza di un array dove si allocano indirizzi di memoria, necessariamente consecutivi, attraverso una serie di indici successivi, in una lista concatenata sono necessari alcuni arrangiamenti per i quali ciascun elemento e` parte di un “nodo” contenente in modo tipicamente “ricorsivo” un riferimento al nodo successivo.

Figura 1

La seppur semplice rappresentazione della figura 1 evidenzia due semplici ma importanti dettagli:

1. Ogni nodo deve avere un riferimento. Anche l’ultimo elemento di ogni lista deve avere un riferimento al prossimo nodo.
2. Ogni lista deve avere un nodo fittizio denominato “head” (o testa), il cui scopo e` puntare alla testa della lista.

Eccovi pertanto un esempio di lista di numeri interi, implementata in linguaggio C:

struct node {
	int key;
	struct node *next;
};
struct node *head, *z, *t;
listinitialize() {
	head = (struct node *)malloc(sizeof *head);
	z=(struct node*)malloc(sizeof *z);
	head->next=z;
	z->next = z;
}
deletenext(struct node *t) {
	t->next = t->next->next;
}
struct node *insertafter(int v, struct node *t) {
	struct node *x;
	x=(struct node *)malloc(sizeof *x);
	x->key = v;
	x->next=t->next;
	t->next=x;
return x;
}

Le linee 1-4 rappresentano una lista di numeri interi e cioe` la struttura dati di tipo lista, a cui abbiamo fatto riferimento.

Nella linea 5 abbiamo una dichiarazione di tre variabili: head, z, t di tipo nodo.

Nelle linee 6-11 troviamo la procedura di inizializzazione di una lista, con allocazione dinamica della memoria necessaria (attraverso la chiamata a “malloc”).

Nelle linee 12-14 abbiamo la cancellazione di un elemento i di una lista, che fa puntare l’elemento i–1 all’elemento i+1.

Nelle linee 15-22 abbiamo un semplice inserimento di un elemento in una posizione qualunque della lista.

Di seguito un esempio completo funzionante di gestione di una Lista di caratteri in C, sono presenti le funzioni base di stampa di una lista, ordinamento di una lista, inserimento ordinato di un elemento in una lista, inserimento in testa, ed il metodo semplifica che rimuove le occorrenze di un carattere :

# include

typedef struct lista *plista;
typedef struct lista {
        char info;
        plista next;
}slista;

plista initlist();
void stampals(plista);
plista ordina(plista);
plista push(plista,char);
plista ins_ord(plista,char);
void semplifica(plista);

main()
{
 plista head=NULL,t=NULL;

 head=initlist();
 printf("lista inserita ->>> ");
 stampals(head);
 t=ordina(head);
 printf("lista ordinata ->>> ");
 stampals(t);

 semplifica(t);
 printf("Lista semplificata ->>> ");
 stampals(t);printf("\n");
 scanf("\n");
}

void ins_coda(plista *h,plista *t,char c)
{
  plista new=(plista)malloc(sizeof(*new));
  plista head=*h,tail=*t;

  new->info=c;
  new->next=NULL;

  if (head==NULL) head=new;
  else tail->next=new;
  tail=new;

  *h=head;
  *t=tail;
}

plista initlist()
{
 char s[100];
 char *p=s;
 plista head=NULL,tail=NULL;

 printf("Inserisci una stringa: ");scanf("%s",&s);
 while (*p != '\0') {
     ins_coda(&head,&tail,*p);
     p++;
  }
  return head;
}

void stampals(plista h)
{
 while (h!=NULL)
 {  putchar(h->info);
    h=h->next;
 }
 printf("\n");
}

plista push(plista head,char x)
{
  plista new=(plista)malloc(sizeof(*new));

  new->info=x;
  new->next=head;
  head=new;

  return (head);
}

plista ins_ord(plista head,char x)
{
  if (head==NULL || xinfo) head=push(head,x);
  else head->next=ins_ord(head->next,x);

  return (head);
}

plista ordina(plista head)
{
 plista newh=NULL;

 while (head !=NULL) {
   newh=ins_ord(newh,head->info);
   head=head->next;
 }

 return (newh);
}

void semplifica(plista head)
{
 plista x;

 while(head !=NULL & head->next !=NULL) {
  while(head->info==(head->next)->info){
        x=head->next;
        head->next=(head->next)->next;
        free(x);
       }
  head=head->next;
 }
}

La lezione si conclude qui, per qualsiasi chiarimento potete lasciare un commento in fondo alla pagina.

Download

• PDF: Lezione 1: Le Liste in C
• .c: lista.c

L’indice delle lezioni si trova qui.

Il prossimo appuntamento e’ per venerdi 28 ottobre 2011, la lezione avra’ per argomento Algoritmi di ordinamento: Insertion Sort e Counting Sort.

Alla prossima!

---

Puoi seguire Massimo Orazio Spada, l’autore di questo post, su Twitter.

Sei veramente bravo in qualcosa e desideri condividere questa conoscenza con gli altri? Stiamo cercando collaboratori per creare altri corsi nella Scuola Serale di Italian Geek. Se sei interessato, scrivici all’indirizzo: info@italiangeek.com

Non ci sono articoli correlati.