[c++] Problemi con le liste (scambio di 2 elementi)

[unit1]

Salve,

le liste sono dei dati:

struct nodo{
       int key;
       nodo* next;};
typedef nodo* pnodo;

delle strutture composte da un dato e un puntatore alla struttura nodo succeva fino ad arrivare alla struttora con next=0, che rappresenta la fine della lista.

La mia domanda è: come posso creare una funzione che sia in grado di scambiare due elementi nella lista?

con gli array farei una cosa del genere:

tmp = a[i];
a[i] = a[j];
a[j] = tmp;

se volete vi posto altre funzioni per operare nella lista come esempio.
Grazie in anticipo.

[giacomins87]

Prendi questo esempio

x = { prev=null; next=y }
y = { prev=x; next=z }
z = { prev=y; next=k }
k = { prev=z; next=null }

voi scambiare y con z.

y.prev = z
z.next = y

z.prev = y.prev
y.next = z.next

Aiutandoti con variabili temporanee chiaramente.

Avendo solo il campo next ti basta fare

y.next = z.next
z.next = y

I dati all'interno della struttura non vanno toccati, ti basta cambiare i puntatori

[mondobimbi]

se conosci i puntatori a node allora fai

struct nodo{
       int key;
       nodo* next;
};
typedef nodo* pnodo;

bool switch ( nodo * n1, nodo *n2 ) {
  if ( n1 && n2 ) {
    nodo * t = n1->next;
    n1->next = n2->next;
    n2->next = t;
    return true;
  }
  else
    return false;
}

se invece conosci solo chiave prima devi trovare il nodo che corrisponde a quella chiave e poi fare come sopra

nodo * find ( nodo *root, int key ) {
  nodo * n = root;
  while (  n && n->key != key )
    n=n->next;
  return n;
}

[unit1]

Credo che ci sia un problema con il collegamento che collega al primo.

Vi posto il mio codice:

#include <iostream>

using namespace std;


struct nodo{
       int key;
       nodo* next;};
typedef nodo* pnodo;

pnodo cons(int x, pnodo testa); //per creare un elemento
void stampa(pnodo testa); //stampa la lista 
pnodo leggi(); // legge da tastiera
bool cambia(nodo *n1, nodo*n2); 

pnodo cons(int x, pnodo testa){
   pnodo nuovo=new nodo;
   nuovo->key=x;
   nuovo->next=testa;
   return nuovo;
}


void stampa(pnodo testa){
     pnodo p;
     for(p=testa;p!=0;p=p->next)
        cout << p->key << " ";
}

pnodo leggi(){
   int x;
   pnodo testa,ultimo;
   int n,i;
   cout << "Inserire il numero di elementi: ";
   cin >> n;
   if(n==0) return 0;
   for(i=0;i<n;i++){
      cout << "Inserire il "<< i+1 <<" elemento: ";
      cin >> x;
      if(i==0){
         testa=cons(x,0);
         ultimo=testa;
      }else{
         pnodo nuovo=cons(x,0);
         ultimo->next=nuovo;
         ultimo=nuovo;
      }
   }
   return testa;
}

bool cambia(nodo *n1, nodo*n2) {
  if ( n1 && n2 ) {
    nodo * t = n1->next;
    n1->next = n2->next;
    n2->next = t;
    return true;
  }
  else
    return false;
}

int main(){
    pnodo a=leggi();
    cambia(a,a->next);
    stampa(a);
    return 0;
}

Vi posto l'output:

Inserire il numero di elementi: 4
Inserire il 1 elemento: 2
Inserire il 2 elemento: 3
Inserire il 3 elemento: 4
Inserire il 4 elemento: 5
2 4 5

Non capisco perchè!

[Stoicenko]

il cambia è errato..

essendo linked list ti serve il puntatore anche al nodo precedente a n1 sennò sballi il link se esiste un precedente

bool cambia(nodo* n0, nodo *n1, nodo*n2) {
  if ( n1 && n2 && n0 ) {
    n1->next = n2->next;
    n0->next = n2;
    n2->next = n1;   
    return true;
  }
  else if(n1 && n2)
  {
      n1->next = n2->next;
      n2->next = n1;
      return true;
  }
  else
    return false;
}

[unit1]

Funziona! Grazie!
Anche se ho alcune domande:

1) n0 non è la testa della lista vero? ma è il puntatore a quello prima di n1, giusto?

2)Nel caso n1 sia il primo come la devo chiamare la funzione? "cambia(0,n1,n2);"

[Stoicenko]

si, se vuoi puoi anche fare 2 funzioni ma così è più generico ed elegante

[unit1]

E nell'eventualita che n1 e n2 non sono consegutivi? mi serve anche il precedente di n2?

che ne dici di una cosa del genere per trovare il precedente con la ricerca lineare:

pnodo cerca_prec(pnodo testa, pnodo n1){
    pnodo p;
    for(p=testa;p!=0;p=p->next)
       if(p->next==n1) return p;
    return 0;
}

[Stoicenko]

si è una buona idea.. per migliorare lo scambio devi per forza cercare in modo dinamico il precedente del primo e del secondo nodo nel caso non siano consecutivi.. cmq una cosa migliore sarebbe avere una bouble-linked list cioè avere un puntatore al precedente

[unit1]

Originariamente inviato da Stoicenko
si è una buona idea.. per migliorare lo scambio devi per forza cercare in modo dinamico il precedente del primo e del secondo nodo nel caso non siano consecutivi.. cmq una cosa migliore sarebbe avere una bouble-linked list cioè avere un puntatore al precedente

Questo non lo posso fare. Il professore vuole, per la didattica che usiamo il suo modello di pnodo.

non riesco a creare la funzione scambia con il puntatore prima di n2..