Newsgroup: it.comp.lang.c
Titolo: Problema con ordinamento lista tramite puntatori

Ciao,
ho qualche problema ad ordinare (selection sort se non sbaglio) una lista
tramite i puntatori :( ho provato e riprovato ma ho sempre qualche errore.
Per ora faccio in questo modo ed utilizzo strcpy() per scambiare il
contenuto delle due struct che devono cambiarsi di posto:
parole *ptr=testaLista;
 parole *ptr2=testaLista;
 parole *minore=testaLista;
char temp[DIM_PAROLA];
 //Ordina la lista (selection sort)
 for(ptr=testaLista; ptr != NULL; ptr=ptr->next)
{
      for(ptr2=ptr, minore=ptr2; ptr2 != NULL; ptr2=ptr2->next)
      {
           if(strcmp(strlwr(ptr2->parola), strlwr(minore->parola)) < 0)
           {
                minore=ptr2;
           }
      }
  strcpy(temp, ptr->parola);    //Cambia ordine delle 2 parole
  strcpy(ptr->parola, minore->parola);
  strcpy(minore->parola, temp);
 }
La struct motlo semplice è questa:
struct parole {
  char parola[DIM_PAROLA];
  int ripetizioni;
  struct parole *next;
  };
Invece di swappare la stringa "parola" vorrei che fossero i puntatori *next
a cambiare di posizione. Qualcuno può darmi una mano? Ho bisogno di un
puntatore che punti all'elemento precedente a quello da swappare? Basta
quello o ne serve un altro? La teoria la so... so cosa devo fare per
riordinarla ma è nella pratica che sbagliosempre qualcosa.
Grazie a chi mi darà una mano
(Scusate se ho postato anche su free.it.programmazione.c per errore)

 puntatore che punti all'elemento precedente a quello da swappare? Basta
La seconda che hai detto.
Ma dato che sapevi come fare, perche' non c'hai provato, che tutt'al 
piu' postavi il codice sbagliato per sapere dov'era l'errore?
-- 
Mat/tia Belletti - Undergraduate student @ 
cs.unibo.it
ICQ: 33292311    - email: 
mbel...@cs.unibo.it
IRC: RedGlow     - site(s): 
http://mbellett.web.cs.unibo.it/
Linux registered user 299762 @ Linux registered machine 213003

 piu' postavi il codice sbagliato per sapere dov'era l'errore?
Dunque... a livello teorico dovrebbe essere così giusto?? :)
Mettiamo che ho una lista con 5 elementi e voglio scambiare di posto il
secondo con il quarto.
Ptr1 punta al primo elemento (quello prima del secondo che è quello che
voglio swappare)
Ptr2 al secondo
Ptr3 al quarto (l'altro che voglio swappare col secondo)
Ptr4 al quinto (quello successivo al quarto che voglio swappare)
Dovrei eseguire queste istruzioni:
ptr1->next=ptr3;
ptr3->next=ptr2->next;
ptr3->next->next=ptr2;
ptr2->next=ptr4;
E' corretto?
Però tipo se sevo swappare il primo della lista con l'ultimo?? Come faccio a
puntare a quelloprecedente del primo che non c'è? :) Devo prevedere i casi
eccezionali in cui siano il primo o l'ultimo (o entrambi) a dover cambiare
posizione?

E altra cosa.... ogni volta dovrei far puntare un puntatore all'elemento
precedente del primo che voglio swappare di posto ed uno a quello successivo
al secondo.
Quindi o li tengo sempre aggiornati o ogni volta devo far scorrere tutta la
lista e quindi non diventa motlo performante... a questo punto conviene
usare strcpy() in un esmpiotipo il mio in cui èsolo un dato a dover cambiare
di posto.


Ciao,
non mi è chiaro se questa cosa la stai facendo per esercizio o per
un'applicazione perché
nel secondo caso ti consiglierei l'uso della qsort. In ogni caso, secondo
me, stai utilizzando un tipo di dato complesso che non è idoneo all'utilizzo
ma se è proprio una lista quella che vuoi utilizzare, allora crea una lista
doppiamenta linkata e quindi con un puntatore alla struttura precedente ed
uno a quella successiva. così facendo, potrai sganciare un record (curr)
della struttura con
curr->prev->next  = curr->next
curr->next->prev = curr->prev
ed identificata la nuova posizione (pos) inserirlo in append con
curr->next  =  pos->next
curr->next->prev = pos->next = curr
curr->prev = pos
il primo e l'ultimo record li puoi riconoscere perché i puntatori, per l'uno
il prev e per l'altro il next, varranno NULL. Spero di essere stato
abbastanza chiaro e d'aiuto. Un saluto.

 abbastanza chiaro e d'aiuto. Un saluto.
Grazie per la risposta, quello che sto facendo è un esercizio da presentare
come progetto per un esame.
Non ero a conoscenza di una funzione qsort()!! Grazie per avermela fatta
scoprire :) Cmq sia è utilizzabile solo per ordinare array a quanto ho
capito. Io devo per forza utilizzare una lista perchè il numero di elementi
è molto variabile e non ne conosco il numero massimo all'inizio
(praticamente sono le parole contenute in una pagina web di cui non conosco
nulla).
Avevo pensato anche ad una lista doppiamente linkata ma mi sembrava un pò
incasinata da implementare cmq proverò...