lista.c

#include <stdio.h>
#include <malloc.h>

typedef struct elem {
  int elemento;
  struct elem* next;
} elem_lista;


/* Quando creo una lista, questa non contiene nessun elemento pertanto
   la inizializzo a NULL */
elem_lista *creaLista() {
  return NULL;
}

/* tutte le procedure devono restituire un puntatore al primo elemento
   della lista (testa) */
elem_lista* inserisciInTesta(elem_lista *lista, int dato) {
  
  elem_lista *nuovo;

  /* Alloco lo spazio per il nuovo elemento */
  nuovo = (elem_lista *)malloc(sizeof(elem_lista));
  /* Copio il valore di dato nel nuovo elemento */
  nuovo->elemento = dato;
  /* Quindi faccio puntare l'elemento appena creato al primo elemento
     della lista */
  nuovo->next = lista;

  /* Restituisco come testa il puntatore all'elemento appena creato
     che diventa così il primo elemento della lista */
  return nuovo;

}

elem_lista* inserisciInCoda(elem_lista *lista, int dato) {
  elem_lista *corrente;

  elem_lista *nuovo;

  /* Alloco lo spazio per il nuovo elemento e gli assegno il valore
     desiderato */
  nuovo = (elem_lista *)malloc(sizeof(elem_lista));
  nuovo->elemento = dato;
  /* Siccome il nuovo elemento sarà l'ultimo della lista, dovrà
     puntare a NULL */
  nuovo->next = NULL;
  
  if(lista == NULL) {
    /* se la lista è vuota, allora il puntatore al primo elemento
       (cioè lista) dovrà puntare a nuovo */
    lista = nuovo;
  }
  else {
    corrente = lista;
    /* scorro la lista fino ad arrivare in fondo */
    while(corrente->next != NULL) {
      corrente = corrente->next;
    }
    /* corrente è l'ultimo elemento della lista e quindi per inserire
       il nuovo elemento è sufficiente far puntare corrente a nuovo */
    corrente->next = nuovo;
  }
  return lista;
}

/* size restituisce la dimensione della lista */   
int size(elem_lista *lista) {
  int cont;
  elem_lista *corrente;

  corrente = lista;
  cont = 0;

  /*scorro la lista, incrementando ad ogni iterazione il contatore
    cont */
  while(corrente != NULL) {
    cont = cont + 1;
    corrente = corrente->next;
  }

  return cont;
}
 
elem_lista* inserisci(elem_lista *lista, int dato, int pos) {

  elem_lista *precedente, *corrente, *nuovo;
  int cont;

  /* Alloco il nuovo elemento e gli assegno il valore desiderato */
  nuovo = (elem_lista *)malloc(sizeof(elem_lista));
  nuovo->elemento = dato;

  if(pos >= size(lista) || pos < 0) {
    printf("Errore");
    return lista;
  }
  else {
    /* Inserire in posizione zero è equivalente ad inserire in
       testa */
    if(pos == 0) {
      lista = inserisciInTesta(lista, dato);
    }
    else {
      corrente = lista;
      cont = 0;
      /* scorro la lista, tenendo memorizzato sia il puntatore
	 corrente sia il puntatore all'elemento precedente */
      while(cont < pos) {
	cont = cont + 1;
	precedente = corrente;
	corrente = corrente->next;
      }
      /* per inserire un elemento nella posizione voluta, devo far
	 puntatore l'elemento precedente al nuovo elemento e far
	 puntare quest'ultimo all'elemento corrente */
      precedente->next = nuovo;
      nuovo->next = corrente;
    }
  }
  return lista;
}

elem_lista * rimuoviInTesta(elem_lista *lista) {
  elem_lista *corrente;

  /* memorizzo l'indirizzo del primo elemento della lista */
  corrente = lista;

  /* per eliminare l'elemento di testa è sufficiente far puntare lista
     (cioè il puntatore al primo elemento della lista) al secondo
     elemnto della lista... */
  lista = lista->next;

  /* ...quindi libero la memoria relativo al primo elemento */
  free(corrente);

  return lista;

}

elem_lista *rimuoviInCoda(elem_lista *lista) {
  elem_lista *corrente, *precedente;

  /* se la lista è vuota ho ha un solo elemento, restituisco una lista
     nulla */
  if(size(lista) == 1 || size(lista) == 0) {
    return NULL;
  }
  else {
    corrente = lista;
    /* scorro la lista fino ad arrivare in fondo, memorizzando sia il
       puntatore all'elemento corrente sia all'elemento del
       precedente */
    while(corrente->next != NULL) {
      precedente = corrente;
      corrente = corrente->next;
    }
    /* per eliminare l'elemento, faccio puntare l'elemento precedente
       a NULL ... */
    precedente->next = NULL;
    /* ...e libero la memoria */
    free(corrente);
  }

  return lista;
}

elem_lista *rimuovi(elem_lista *lista, int pos) {
  elem_lista *corrente, *precedente;
  int cont;

  if(pos >= size(lista) || pos < 0) {
    printf("Errore");
    return lista;
  }
  else {
    /* Rimuovere in posizione zero è equivalente ad rimuovere in
       testa */
    if(pos == 0) {
      lista = rimuoviInTesta(lista);
    }
    else {
      cont = 0;
      corrente = lista;
      /* scorro la lista memorizzando il puntatore corrente e quello
	 precedente */
      while(cont < pos) {
	cont = cont + 1;
	precedente = corrente;
	corrente = corrente->next;
      }
      /* faccio puntare l'elemento precedente al successivo di quello
	 corrente, "aggirando" così l'elemento corrente */
      precedente->next = corrente->next;
      /* libero la memoria relativa all'elemento corrente */
      free(corrente);
    }
  }
  return lista;
}
      
int cerca(elem_lista *lista, int el) {
  elem_lista *corrente;
  int found, cont;

  found = 0;
  cont = 0;
  corrente = lista;
  /* scorro la lista fin quando trovo l'elemento cercato oppure sono
     arrivato in fondo */
  while(corrente != NULL && found == 0) {
    if(corrente->elemento == el) {
      found = 1;
    }
    else {
      cont = cont + 1;
      corrente = corrente->next;
    }
  }
  if(found == 1) {
    return cont;
  }
  else {
    return -1;
  }

}

/* restituisco l'elemento alla posizione pos */    
int get(elem_lista *lista, int pos) {
  elem_lista *corrente;
  int cont = 0;
 
  if(pos >= size(lista) || pos < 0) {
    printf("Errore");
    return -1;
  }
  else {
    corrente = lista;
    while(cont < pos) {
      corrente = corrente->next;
      cont = cont + 1;
    }
    return corrente->elemento;
  }
}



void stampa(elem_lista *lista) {

  elem_lista *i;

  i = lista;
  printf("Size: %d --- ", size(lista)); 
  while(i!=NULL) {
    printf("%d ", i->elemento);
    i = i->next;
  }
  printf("\n");
}

void main() {

  elem_lista* lista, *corrente;
  int cont, num, trovato;

  lista = creaLista();

  printf("Inserisci un numero (0 per uscire): ");
  scanf("%d", &num);

  while(num != 0) {
    /* scorro la lista, fin quando incontro un elemento maggiore di
       num oppure arrivo in fondo */
    corrente = lista;
    trovato = 0;
    cont = 0;
    while(corrente != NULL && trovato == 0) {
      if(corrente->elemento > num) {
	trovato = 1;
      }
      else {
	cont = cont + 1;
      }
    }
    if(trovato) {
      lista = inserisci(lista, num, cont);
    }
    else {
      lista = inserisciInCoda(lista, num);
    }
    printf("Inserisci un numero (0 per uscire): ");
    scanf("%d", &num);
  }
  printf("Hai inserito questi valori: ");
  stampa(lista); 
}

Generated by GNU enscript 1.6.4.