Liste e puntatori

di il
4 risposte

Liste e puntatori

Sono alle prese con le liste ed in particolare con una funzione che prende elemento in pozione i (che è $>=1$) e lo sposto alla posizione immediatamente precedente, quindi se cerco l'elemento con posizione 4 lo sposto in posizione 3.
Mi è chiaro che devi aver traccia di almeno 3 puntatori, quello in posizione $i$ e dei due precedenti che sono nel mio caso $r$ e $q$.
La mia difficoltà è nella relazione tra r e q nel seguente codice dove non capisco come faccia ad essere r antecedente a q.

r = q; // r rimane due passi indietro a p
q = p; // q rimane un passo indietro a p
p = p->pun;

Comprendo che p è spostato di un elemento in avanti rispetto a q, ma non riesco a comprendere la relazione tra r e q.
Mi aiutate please?
void Calcolo::controlla(unsigned int i) {
  // controllo validita' indice e caso lista vuota
  if (i < 1 || _testa == NULL)
    return;

  // caso particolare: controllo del primo elemento
  if (i == 1) {
    _testa->controllato = true;
    return;
  }

  unsigned int c = 1;
  pezzo *p = _testa;
  pezzo *q = p;
  pezzo *r;
  while (p != NULL && c < i) {
    r = q; // r rimane due passi indietro a p
    q = p; // q rimane un passo indietro a p
    p = p->pun;
    c++;
  }

  // ho raggiunto la fine della lista
  // (non esiste l'i-esimo pezzo)
  if (p == NULL)
    return;

 // caso particolare: sono sul secondo elemento e lo
  // devo spostare in testa
  if (r == q) {
    _testa->pun = p->pun;
    p->pun = _testa;
    _testa = p;
  } else {
    q->pun = p->pun;
    r->pun = p;
    p->pun = q;
  }
}

4 Risposte

  • Re: Liste e puntatori

    Potresti chiarire cosa dovrebbe fare tale funzione?
    Il codice postato lo stai scrivendo o stai cercando di capirlo?
  • Re: Liste e puntatori

    Sto cercando di comprenderlo.
    Comunque non l'ho scritto io ed è preso da un testo di esame, quindi codice collaudato.
    Supposto avere una lista con elementi dalla posizione 1 a n, la funzione prende un elemento dalla lista in pos $i$, parametro passato alla funzione, e lo sposta nella posizione precedente. Quindi se passo alla funzione i=3 cerco l'elemento in posizione tre nella lista e lo metto in posizione due quindi in pratica scambio i due elementi.
  • Re: Liste e puntatori

    Da quello che ho capito non riesci a comprendere come faccia r ad essere indietro a q. In realtà r è indietro di un elemento a "partire" dalla seconda iterazione. Infatti, considerando la testa in posizione 0, p e q partono da 0(la testa). Entriamo nel while r lo fa puntare alla posizione 0, q lo fa puntare ancora alla posizione 0 e p lo sposta alla posizione 1. Passiamo alla seconda iterazione:
    - r lo facciamo puntare ancora alla posizione 0, la posizione a cui punta q al passo precedente(iterazione 1)
    - q lo facciamo puntare alla posizione 1, la posizione a cui punta p alla passo precedente(iterazione 1)
    - p lo aggiorniamo e lo facciamo puntare alla posizione 2.
    Quindi dopo la seconda iterazione r punta all'elemento in posizione 0, q punta all'elemento in posizione 1 e p punta all'elemento in posizione 2.
    E cosi le altre iterazioni finchè la condizione del while risulta vera.
  • Re: Liste e puntatori

    Da leggere con massima attenzione e adesso è il momento giusto.
    Grazie spiegazione eccellente.
Devi accedere o registrarti per scrivere nel forum
4 risposte