Domanda Lista Linkata Ordinata

[Zast]

Salve a tutti, sto cercando di sviluppare una lista ordinata.
Errori sintattici non ce ne sono, tuttavia, una volta inseriti gli elementi, non vengono stampati tutti gli elementi inseriti.
Ho sviluppato la lista tamite funzioni ricorsive, perchè richiesto dal mio professore.
Con il main che ho scritto, i valori stampati sono 5,2,1 in questo ordine(la lista effettivamente è ordinata, ma mancano due valori )
Qui riporto il codice e grazie a tutti in anticipo

lista.h

class lista{
public:

    lista(){testa=0;}
    ~lista(){clear();}

    bool inserisci_testa(const value_type& );
    bool rimuovi_testa(value_type&);
    bool empty()const{return testa==0;}
    bool full()const{return false;}

    bool insert(const value_type &);
    bool erase(const value_type&);
    bool inList(const value_type&);
    void print();
    void clear();

private:
    struct Nodo{
        Nodo* next;
        value_type valore;
    };
    Nodo* testa;
};

lista.cpp

bool lista::inserisci_testa(const value_type& elemento){
    if(full()) return false;
    Nodo* nodo=new Nodo;
    nodo->valore=elemento;
    nodo->next=testa;
    testa=nodo;
    return true;
}


bool lista::insert(const value_type& elemento){

    if(full())    return false;
    if(testa==0 || testa->valore<elemento)    inserisci_testa(elemento);
    else {
        testa=testa->next;
        return insert(elemento);
    }
}


void lista::print(){
    if(testa!=0) {
             cout << testa->valore << "\t";
             testa=testa->next;
             print();
    }
}

main

int main(){
    lista l;

    if(l.insert(1))    cout<<"\n inserimento riuscito!";
        else cout<<"\n lista piena!";
    if(l.insert(3))    cout<<"\n inserimento riuscito!";
        else cout<<"\n lista piena!";
    if(l.insert(4))    cout<<"\n inserimento riuscito!";
        else cout<<"\n lista piena!";
    if(l.insert(2))    cout<<"\n inserimento riuscito!";
        else cout<<"\n lista piena!";
    if(l.insert(5))    cout<<"\n inserimento riuscito!";
        else cout<<"\n lista piena!";

    cout<<endl;
    l.print();
}

 

[Barbossa]

Un errore si trova qui:

bool lista::insert(const value_type& elemento){

    if(full())    return false;
    if(testa==0 || testa->valore<elemento)    inserisci_testa(elemento);
    else {
        testa=testa->next;//ERRORE!
        return insert(elemento);
    }
}

In quanto vai a modificare il puntatore del primo elemento della lista che non punterà più al primo elemento della lista, perdendo vari elementi.

Un consiglio: non assegnare il valore 0 ai puntatori, ma utilizzare il valore NULL che fa la medesima cosa, ma rende il codice più leggibile (in C++11 mi sembra che assegnare 0 a puntatori sia considerato errore, ma non ne sono sicuro).

 

[Barbossa]

Ho anche trovato il motivo per cui ti stampa solo gli elementi 5, 2, 1. Infatti al termine del codice sono state generate due liste distinte con il nodo contenente 1 in comune e il puntatore testa punterà solo alla lista contenente 2 e 5.
Le due liste sono strutturate in questo modo:

4 -> 3 -> 1

testa -> 5 -> 2 ->1

 

[Zast]

Penso di aver capito l'errore, grazie mille .
Solo che ora, non potendo far scorrere il puntatore al nodo successivo in questo modo, come faccio a passare al prossimo nodo per poter effettuare l'inserimento?
La funzione è ricorsiva, quindi ritorna su se stessa, ma omettendo quella riga di codice il puntatore punta sempre allo stesso nodo, giusto?

 

[Barbossa]

bool lista::insert(const value_type& elemento){

    if(full())    return false;
    if(testa==0 || testa->valore<elemento)    inserisci_testa(elemento);
    else {
        Nodo *local=testa;
        testa=testa->next;
        bool ret= insert(elemento);
        testa=local;
        return ret;
    }
}

 

[Zast]

Ho provato come hai fatto, solo che l'output non è comunque completo, vengono stampati 5-4-3-1 .
Penso che succeda questo perchè una volta che viene eseguita la riga "bool ret=insert(elemento)", questa riesegue la funzione ed esce solo quando "testa==0 || testa->valore<elemento", e di conseguenza la testa non viene mai settata a local, perchè non si arriva mai in quel punto del codice, almeno credo xD

 

[Scanetatore]

Non avevo mai provato ad implementare una lista linkata singolarmente e ordinata. Mi sono divertito a farlo stamattina visto che avevo un po' di tempo, anche se il risultato non mi piace molto.
Perché sia eseguito correttamente il codice è un po' più complesso di quello che ti è stati proposto. Ci sono diversi casi particolari da verificare in modo che tutto funzioni correttamente.

Personalmente mi sono creato una funzione privata ad-hoc per quest'operazione, ti lascio il prototipo:

void lista::insert_nodo_ord(lista::Nodo* curr, lista::Nodo* prev, lista::Nodo* nodo);

Come spero sia intuibile, ho trovato comodo portarmi dietro anche il predecessore dell'elemento corrente che sto scorrendo per poter sistemare tutti i vari puntatori correttamente nel caso ci sia da inserire nel mezzo della lista.

Inoltre il metodo print() è sbagliato: stai andando a modificare testa, perdendo quindi tutti gli elementi prima dell'ultimo. Anche per questa il mio suggerimento è di crearti una funzione privata con un parametro (questa la versione che userà la ricorsione).

P.S.
Il mio C++ è pessimo, avevo solo cominciato a vederne le basi qualche mese fa.

P.P.S.
Il metodo full() è concettualmente sbagliato: una lista linkata si prefigge lo scopo di poter aggiungere un numero arbitrario (anche molto elevato) di elementi, non potrà mai essere "piena". A patto, ovviamente, di non aver finito la memoria (stack/heap) ma a quel punto dovresti lanciare un'eccezione magari.