Inserimento in lista ordinata

Si risolva il seguente problema: sia data una lista di interi, ordinata in ordine crescente (prima il più piccolo, poi quelli più grandi); è dato un intero, che va inserito nella lista in modo tale che questa resti ordinata. Di seguito si danno alcuni file che contengono liste ordinate in questo modo: si provi a inserire l'elemento 2 in ciascuna di esse.

  1. listaord1.txt
  2. listaord2.txt
  3. listaord3.txt
  4. listaord4.txt
  5. listaord5.txt
  6. listaord6.txt
  7. listaord7.txt (lista vuota)
  8. listaord8.txt

Il problema consiste in un inserimento in mezzo a una lista. Si tratta infatti di trovare il primo elemento della lista che è superiore a quello dato, e inserire l'elemento prima di esso. Va anche tenuto conto che la lista può inizialmente essere vuota, e che la posizione in cui l'elemento va inserito può essere sia la prima che l'ultima.

Consideriamo inizialmente il caso in cui l'elemento va inserito in mezzo. Come si è detto, l'elemento va inserito subito prima del primo elemento della lista che è superiore ad esso. Questo significa che dobbiamo fare una scansione della lista, confrontando ogni elemento con quello da inserire. Va tenuto conto che, una volta trovata la posizione in cui l'elemento va inserito, questo va inserito prima. In altre parole, la situazione è la seguente:

Dopo l'inserimento, la situazione deve essere invece la seguente:

In altre parole, ci serve confrontare l'elemento da inserire con ogni elemento della lista. Una volta trovato l'elemento maggiore, la struttura che viene modificata è la precedente. Dalla figura si vede chiaramente come la freccia della struttura che precede quella che contiene 3 è stata spostata, ossia il valore del puntatore è cambiato.

Quello che ci serve fare è semplicemente usare un puntatore s per fare la scansione della lista. Una volta trovato l'elemento superiore a quello da inserire, ci serve sapere l'indirizzo della struttura precedente. Per questo motivo, facciamo il confronto con s->next->val invece che con s->val. In questo modo, se il valore è superiore a quello dell'elemento, allora l'indirizzo della struttura da modificare è scritto in s.

In altre parole, facendo la scansione fino al punto in cui s->next->val è maggiore dell'elemento da inserire, ci troviamo nella situazione di poter modificare la struttura precedente, perchè l'indirizzo di questa è scritto in s.

Per inserire l'elemento in mezzo, occorre allocare una nuova struttura, e metterci dentro il valore da inserire. Il campo next di questa nuova struttura deve contenere l'indirizzo della struttura che contiene l'elemento superiore. L'indirizzo di questa struttura si trova in s->next. Quindi, facciamo:

  t=malloc(sizeof(struct NodoLista));
  t->val=e;
  t->next=s->next;

Questo produce la situazione seguente:

Ora, l'indirizzo della nuova struttura va messo in s->next. Abbiamo usato una variabile temporanea t per memorizzare questo indirizzo, quindi possiamo eseguire l'ultimo collegamento facendo:

  s->next=t;

Questo produce la situazione seguente.

A questo punto la modifica alla lista è ultimata: a parte le due variabili temporanee s e t, la lista contiene effettivamente tutti gli elementi di prima più quello nuovo, e questi elementi si trovano in ordine crescente (a partire dal più piccolo).

Vediamo ora i casi particolari. La prima cosa da tenere presente è che la lista può essere vuota. In questo caso, l'algoritmo di sopra non funziona, dal momento che si deve fare un ciclo in cui si controlla s->next->val, e s vale inizialmente NULL. Il caso in cui la lista è vuota va quindi trattato separatamente. D'altra parte, questo caso è facile: basta allocare una struttura, il cui indirizzo va messo in l.

Il caso in cui l'elemento va iserito in prima posizione richiede anche esso un trattamento a sè. Infatti, alla prima iterazione del ciclo il confronto viene fatto fra l'elemento da inserire e il secondo, e comunque l'elemento viene inserito fra il primo e il secondo. Quindi, se la lista non è vuota, controlliamo se l'elemento va inserito in prima posizione, ed eventualmente lo inseriamo in testa.

L'ultimo caso da analizzare è quello in cui l'elemento va inserito in coda alla lista. Nel ciclo di scansione della lista, dobbiamo terminare se troviamo un elemento superiore a quello da inserire. Nel caso in cui si arriva alla fine della lista, l'elemento va inserito in coda.

Il programma completo inmezzo.c contiene la seguente funzione di inserimento in lista ordinata.

void InserisciListaOrdinata(TipoLista *pl, int e) {
  TipoLista s, r;

		/* la lista non contiene elementi */
  if(*pl==NULL) {
    *pl=malloc(sizeof(struct NodoLista));
    (*pl)->val=e;
    (*pl)->next=NULL;
    return;
  }


		/* l'elemento va inserito in prima posizione */
  if((*pl)->val>=e) {
    s=*pl;
    *pl=malloc(sizeof(struct NodoLista));
    (*pl)->val=e;
    (*pl)->next=s;
    return;
  }



			/* la lista ha piu' di un elemento */
  s=*pl;
  while(s->next!=NULL) {

    if(s->next->val>e) {
      r=s->next;
      s->next=malloc(sizeof(struct NodoLista));
      s->next->val=e;
      s->next->next=r;
      return;
    }

    s=s->next;
  }


			/* se arrivo qui, l'elemento va inserito in fondo */
  s->next=malloc(sizeof(struct NodoLista));
  s->next->val=e;
  s->next->next=NULL;


  return;
}