[C++] Inserimento in lista ordinata(ricorsivamente)

[gaten]

Finalmente ci sono riuscito.
Volevo solo chiarire 2 dubbi, per farveli individuare ho preferito mettere dei punti "?".

1) perchè il programma mi funziona solo se passo la testa in questo modo:

lista insert( lista *&head, int elemento);

cioè, perchè passare *&

2) precisamente con:

head=temp;              // ?

questo cosa faccio? perchè?


Questo il codice:

#include<iostream>

using namespace std;

/* Tipo di dato lista */
typedef struct nodo{
    int valore;
    nodo *link;
} lista;



/* Prototipi delle functions */
lista insert( lista *&head, int elemento);
void stampa(lista *head);



int main()
{

    lista *head=NULL;

    char choise;
    int elemento;

    do {
        cout << "Elemento da inserire: "<<endl;
        cin>>elemento;
        insert(head, elemento);
        cout<<"Continuare l'inserimento?(s/n)"<<endl;
        cin>>choise;

    } while(choise=='s' || choise=='S');


    stampa(head);


    return 0;
}


/* function per inserire in modo ordinato gli elementi nella lista */
lista insert(lista *&head, int elemento) {

    lista *temp, *prec, *current;

    current=head;

    /* se il nodo corrente, cioè nel primo caso la testa(NULL) => vedi [ current=head ] e' nullo
     * o l'elemento e' <= del valore del puntatore corrente => nel nostro caso sempre NULL, poichè non
     * esiste alcun nodo,
     * INSERISCO L'ELEMENTO IN TESTA ALLA LISTA
     */
    if(current == NULL || elemento <= current->valore){

        temp=new lista;         // alloco dinamicamente memoria per un nodo temporaneo(temp)
        temp->valore=elemento;  // salvo l'elemento nel nodo temporaneo
        temp->link=current;     // il nuovo nodo creato, punterà a current che equivale alla testa, quindi il valore viene messo dietro la testa
        head=temp;              // ?

    } else {

        /* altrimenti se il nodo corrente non è nullo, cioè vale a dire esiste almeno un nodo
         * e l'elemento da inserire è maggiore di quelli precedenti,
         * fin quando il nodo corrente non punterà a NULL e l'elemento da inserire
         * è > di quelli già presenti nella lista,
         * salverò ad ogni iterazione il nodo subito precedente a quello che ha valore più grande dell'elemento da inserire.
         * es. |3|->|8|->|22|->NULL, se volessi inserire 5, savlerei il nodo con valore 3, in quanto alla itererazione successiva,
         * avremo un nodo che ha valore > dell'elemento da inserire(uscendo così dal while).
         */
        while(current != NULL && elemento > current->valore){

            prec=current;           // salvo il nodo precedente
            current=current->link;  // scorro la lista

        }

        temp=new lista;         // alloco dinamicamente memoria per un nodo temporaneo(temp)
        temp->valore=elemento;  // salvo l'elemento nel nodo temporaneo
        temp->link=current;     // il nodo che viene inserito, punterà a quello successivo, nel nostro esempio al nodo ->|8|
        prec->link=temp;        // il nodo precedente, nel nostro caso |3|-> punterà al nuovo nodo inserito, nel nostro esempio |5|
    }
}


/* function per stampare gli elementi della lista */
void stampa(lista *head) {

    lista *tmp;
    tmp=head;

    cout<<"Lista stampata:"<<endl;

    while (tmp != NULL) {
        cout<<tmp->valore<<endl;
        tmp=tmp->link;
    }
}