[C++] Errore nell'inserimento in una lista

[pietrol83]

in questo modo non viene spostato di una posizione l'elemento attuale che si trova in posizione pos. con la inslista, l'inserimento del nuovo elemento in posizione pos viene messo prima dell'eaatuale elemento di posizione pos facendolo scalare dalla posizione pos alla posizione (pos + 1). se facessi come dici tu, il nuovo elemento verrebbe inserito dopo l'attuale elemento di posizione pos. secondo me l'anomalia sta nelle condizioni del metodo inslista (la if o il for), però non riesco a capire quale sia questa maledetta anomalia.

[LeaderGL]

funzione:

template<class tipoelem>
void listav<tipoelem>::inslista(typename listav<tipoelem>::posizione pos, tipoelem elem)
{
   if(lunglista < maxdim) //si può inserire l'elemento?
   {
      if(pos <= (lunglista - 1)) //ci sono elementi da spostare?
      {
         for(int i = (lunglista - 1); i >= pos; i--) //spostamento degli elementi
            array[i + 1] = array[i];
         
         array[pos] = elem;
      }
      else
         array[pos] = elem;
      
      ++lunglista;
   }
   else
      cerr << "lista piena.\n\n";
}

Precedenti:
E' stato inserito un elemento.
L'elemento si trova in posizione 0.

Condizioni:
lunglista = 1

Parametri inslista:
pos = 0
elem = 20

Controllo del for originale:
for(int i = (lunglista - 1); i >= pos; i--)

ovvero:
for(int i = 0; i >= 0; i--)

Risultato:
il for non viene eseguito, nessun elemento viene spostato; tutti gli elementi vengono messi nella prima posizione.

Il metodo inslista() non va bene.

[pietrol83]

bhe che il metodo inslista non andasse bene l'avevo capito. gli elementi vengono messi tutti in prima posizione perchè ho creato un test che fa questo, ma gli elementi dovrebbero poter essere inseriti in qualsiasi posizione. se facessi il for come hai scritto tu, il metodo sposterebbe sempre tutti gli elementi di una posizione quando gli elementi da sposstare sono solo quelli che si trovano dopo pos.

[LeaderGL]

così pensi possa andare?

template<class tipoelem>
void listav<tipoelem>::inslista(typename listav<tipoelem>::posizione pos, tipoelem elem)
{
   if( lunglista < maxdim )
   {
      cerr << "lista piena.\n\n";
      return;
   }

   int i = lunglista - 1;
   if ( pos <= i )
      do
      {
         array[i+1] = array[i];
         --i;
      }
      while ( i > pos );
   }

   array[pos] = elem;
   ++lunglista;
}

[ramy89]

Originariamente inviato da LeaderGL
[...]
ovvero:
for(int i = 0; i >= 0; i--)

Risultato:
il for non viene eseguito, nessun elemento viene spostato; tutti gli elementi vengono messi nella prima posizione.

Il metodo inslista() non va bene.

Non è vero, i=0 soddisfa la condizione i>=0, viene eseguito una volta.
Il corpo del for dice array[i+1]=array[i], per cui array[1]=array[0] e l' elemento viene spostato.

[LeaderGL]

Originariamente inviato da ramy89
Non è vero, i=0 soddisfa la condizione i>=0, viene eseguito una volta.
Il corpo del for dice array[i+1]=array[i], per cui array[1]=array[0] e l' elemento viene spostato.

Hai ragione, scusate; stavo ragionando sul suggerimento di togliere l'uguale.
In effetti il for così com'è fa il suo sporco lavoro.
Andrebbe debuggato il codice per vedere dov'è l'anomalia.

[pietrol83]

si ma facendo così sposta sempre tutti gli elementi dell'array. se io avessi un array di 20 elementi e volessi inserirne uno in decima posizione, come dici tu, sposterebbe comunque tutti gli elementi, dal primo all'ultimo, di una posizione mentre il metodo dovrebbe spostare gli elementi dal decimo al ventesimo.

[ramy89]

Originariamente inviato da LeaderGL
Hai ragione, scusate; stavo ragionando sul suggerimento di togliere l'uguale.
In effetti il for così com'è fa il suo sporco lavoro.

Più guardo il codice e più mi sembra giusto, e se penso di trovare un errore poi se guardo bene non c'è.Per me la inslista è corretta.

Andrebbe debuggato il codice per vedere dov'è l'anomalia.

Mi pare l' unica cosa da fare

Forse sarebbe stato più semplice ( e tra l' altro più efficiente) usare una lista linkata.
L' inserzione avrebbe costo O(1).

[pietrol83]

il test che ho creato io inserisce gli elementi in prima posizione ma il metodo dovrebbe essere in grado di inserirli ovunque si voglia.
per quanto riguarda la lista concatenata, dovrò fare anche quella. devo farne una con vettore, con puntatori e con cursori.

[ramy89]

Prova a mettere i membri lunglista e *array pubblici (solo per ora, poi li rimetti privati).
Fai:

listav<int> list(20);
for(int i=0;i<5;i++)
{
    list.inslista(0,i);
    for(j=0;j<list.lunglista;j++)
        printf("%d\t",list.array[j];
    printf("\n");
}

Che output ti esce?