Newsgroup: it.comp.lang.c++
Titolo: Inserimento arbitrario in una lista bidirezionale

Come faccio con una lista bidirezionale ad aggiungere un elemento in un 
punto arbitrario della lista stessa?
Se ho una lista del genere:
 1 2 3 4 5
Come posso aggiungere un nuovo elemento (es. 9) tra 2 e 3?
 1 2 9 3 4 5 ???
Ho cercato di aggiungere l'elemento con questa istruzione:
--------------------------------------------------------------------
 Con un ciclo mi posiziono sul 2,
 poi utilizzo la seguente istruzione per aggiungere l'elemento tra 2 e 3:
 testa->next = new elem (val, testa, testa->next);
 ...ma...il risultato è il seguente:
 - Se visualizzo la lista in ordine di inserimento
   2 9 3 4 5
 - Se visualizzo la lista in ordine inverso:
   1 2 3 4 5  (non ha inserito nulla)
--------------------------------------------------------------------
La struttura utilizzata è :
  struct elem
   {
    int val;
    elem* pre;
    elem* next;
    elem(int Val, elem* Pre, elem* Next)
     {
      val = Val;
      pre = Pre;
      next = Next;
     }
   };
 ...
 elem* testa;
 elem* coda;
 ..
-------------------------------------------------------------------
Grazie anticipatamente per le vostre risposte. 

 Grazie anticipatamente per le vostre risposte.
 
Hai fatto dei gravi errori alcuni di design e altri di tipo algoritmico. Ti
consiglio di leggerti un buon testo sulle strutture dati.
1) [design] i puntatori testa e coda dovrebbero essere variabili private
della classe doubly_linked_list (quella che tu chiami lista bidirezionale è
meglio descritta come lista doppiamente collegata: doubly linked list).
2) [design] alla creazione di un nuovo elemento è necessario solo passare
il puntatore all' elemento oltre il quale vuoi inserire il nuovo (oppure
all'elemento prima del quale voui inserire il nuovo, più "standard"):
nel tuo caso, visto che vuoi inserire un 9 tra la posizione 2 e 3, è meglio
che passi il puntatore all'elemento 2, oltre al valore da conservare, ad una
funzione bool insert(val 9, pos 3).
Non serve passare elem->next e elem->prev perchè i rispettivi valori li
trovi memorizzati all'elemento 3.
3) [algo] l'istruzione "testa->next = new elem (val, testa, testa->next);"
è assolutamente non adatta ad inserire il nuovo elemento nel modo corretto.
Come fare?
Nell'ipotesi che tu abbia già trovato il puntatore all'elemento 3 (cioè
all'elemento prima del quale vuoi inserire) e lo abbia assegnato a "elemento
*p = puntatore_all_elemento_3":
 elemento *tmp = new elemento(9); // crei nuovo elem e lo assegni a tmp;
 tmp->prev = p->prev; // assegni a prev del nuovo elem. il 3->prev, cioè
l'elemento 2
 tmp->next = p; // assegni a next del nuovo elem. il valore p, che è
l'indirizzo dell'elem. 3
 p->prev->next = tmp; // assegni al next dell'elem. 2 l'indirizzo del nuovo,
che è tmp
 p->prev = tmp; // assegni al prev di p, che è l'indirizzo di 3, l'indirizzo
di tmp
    // attenzione questa assegnazione DEVE essere l'ultima
Come vedi il costruttore di elemento necessita solo del valore che vuoi
assegnare al campo dati di elemento. L'indirizzo "p" lo trovi con un loop
fino al terzo elemento assegnando inizialmente p = testa e poi, ad ogni
ciclo p = p->next. Stai attento al numero dei cicli per non andare oltre, o
fermarti troppo presto.
Spero di essere stato utile. Fammi sapere se è sufficente a rielaborare
l'algoritmo, o se vuoi discutere altro che non ti è chiaro.
Buon lavoro,
fabiomdf
 
--------------------------------
Inviato via 
http://arianna.libero.it/usenet/

da quello che ho capito stati utilizzando una funzione membro di una
classe es: CLista
per spostarti dentro le strutture dati
se questo è quanto, l'istruzione è corretta, patto che aggiorni in
maniera coerente -testa-
ma ho dei seri dubbi x' mi fa pensare che -testa- sia il principio
della lista e
utilizzando la -testa- per aggiornare la posizione corrente nei dati
nella lista perdi la lista...
rimedio...
pElemCur= testa;
da qui in avanti puoi spostarti per cercare la posizione ed
inserire.eliminare.ricercare
con pElemCur <<<
bye duido


Ora io non voglio dire che la mia risposta è corretta e definitiva in
assoluto. Però per dare un migliore servizio a chi ha un problema, e se
già c'è una traccia di soluzione sarebbe il caso di fare due cose:
1) fornire una soluzione alternativa
2) mostrare che una precedente risposta manca di completezza e/o è errata,
e fornire gli aggiustamenti possibili.
Se ti limiti a scrivere che quell'algoritmo fa la cosa per cui è stato
progettato, mentre già qualcun'altro ha spiegato che l'algo è errato,
tenta almeno di spiegare dove il discorso di quest'ultimo fa acqua.
Ripeto che così darai un migliore servizio a chi ha postato il problema, al
posto di abbandonarlo con due visioni opposte e non concilianti.
Ciao,


Con un ciclo mi posiziono sul 2,
 poi utilizzo la seguente istruzione per aggiungere l'elemento tra 2 e
3:
 testa->next = new elem (val, testa, testa->next);
 ...ma...il risultato è il seguente:
 - Se visualizzo la lista in ordine di inserimento
   2 9 3 4 5
 - Se visualizzo la lista in ordine inverso:
   1 2 3 4 5  (non ha inserito nulla)
campione non tutti sono geni come te... ;)
volevo solo dare una mano, se poi ho sbagliato scusa tanto, stasera
salterò la cena ;)
ecco come ho ragionato:
testa è l'elemento 2
mi crea un nuovo elemento 9
testa->next = new elem ( val,   // nuovo elemento 9
                         testa, // elemento corrente 2 diventa il
precedente del successivo 9
                         testa->next); // elemento successivo 3 del
corrente 2 diventa il successivo del nuovo 9
buone pappe duido ;)


Ciao e buone pappe(?) anche a te,
