PDA

Visualizza la versione completa : [C] lista da ordinare in base al membro word


VYCanisMajoris
18-02-2012, 18:04
Salve ragazzi è ormai una decina di ore che mi sto cervelland per scrivere un codice che funzioni e sono senza risultati... L'obiettivo è quello di creare una funzione che ordini una lista di struct in base al campo word di ogni elemento.
La faccenda l'ho organizzata cosi:
Una funzione scorre la lista(quella disordinata) grazie ad un ciclo while e dentro al ciclo chiamo una seconda funzione a cui li passo ogni volta l'elemento a cui sono arrivato. All'interno di questa seconda funzione piglio il nuovo elemento e lo posiziono in ordine rispetto a quelli che ho posizionato prima.

ecco le due funzioni:

WList wl_sort(WList L) {
WList e = L;
L = NULL;
while( e != NULL ) {
L = wl_new_sort( L, e );
e = e->next;
}
return L;
}

WList wl_new_sort( WList L, WList e ) {

if( L == NULL ) return e;
else if( (strcmp(e->word, L->word)) <= 0 ) {
e->next = L;
return e;
}
else {
WList R = L;
while( L->next != NULL ) {
if( (strcmp(e->word, (L->next)->word)) < 0 ) {
e->next = L->next;
L->next = e;
return R;
}
L = L->next;
}
e->next = NULL;
L->next = e;
return R;
}
}

Qui vi ripropongo le stesse funzioni di prima ma ambientate insieme ad un main e una funzione che stampa la lista cosi se vi va potete fare direttamente delle prove.

#include <stdio.h>
#include <string.h>

typedef struct WElem {
char* word;
struct WElem* next;
} WElem, *WList;

WList wl_sort(WList L);
WList wl_new_sort( WList L, WList e );
void stampa_lista( WList p );

int main( void ) {

WList L;
WElem X, Y, W, V, Z;
L = &X;

X.word = "napoli";
X.next = &Y;

Y.word = "livorno";
Y.next = &W;

W.word = "hotel";
W.next = &V;

V.word = "firenze";
V.next = &Z;

Z.word = "dadada";
Z.next = NULL;

stampa_lista( L );
printf( "---\n" );

L = wl_sort(L);

printf( "---\n" );
stampa_lista( L );

}

WList wl_sort(WList L) {
WList e = L;
L = NULL;
while( e != NULL ) {
L = wl_new_sort( L, e );
e = e->next;
}
return L;
}

WList wl_new_sort( WList L, WList e ) {

if( L == NULL ) return e;
else if( (strcmp(e->word, L->word)) <= 0 ) {
e->next = L;
return e;
}
else {
WList R = L;
while( L->next != NULL ) {
if( (strcmp(e->word, (L->next)->word)) < 0 ) {
e->next = L->next;
L->next = e;
return R;
}
L = L->next;
}
e->next = NULL;
L->next = e;
return R;
}
}

/* riceve come argomento puntatore
* a primo elemento della lista */
void stampa_lista( WList p ) {
while( p != NULL ) {
printf( "%s -> ", p->word );
p = p->next;
}
printf( "NULL\n" );
}

Avendo esaurito le idee riaffronterò il problemada un altro punto di vista... memorizzo ogni membro word in un array di stringhe, ordino l'array di stringhe e ricostruisco una listascorrendo l'array di stringhe ordinato. So che fa abbastanza schifo come cosa infatti spero che voi mi diate un occhiata al codice sopra proposto

Vi ringrazio e vi saluto! :ciauz:

premoli
18-02-2012, 23:06
ciao!!!

prima di tutto devi cambiare la struttura



typedef struct WElem
{
char* word;
struct WElem* next;
} WElem, *WList;

in

typedef struct WElem
{
char word[50];
struct WElem* next;
} WElem, *WList;

e di conseguenza il main in:

..
strcpy(X.word, "napoli");
X.next = &Y;

strcpy(Y.word, "livorno");
Y.next = &W;

strcpy(W.word, "hotel");
W.next = &V;

strcpy(V.word, "firenze");
V.next = &Z;

strcpy(Z.word, "dadada");
Z.next = NULL;
...


a meno che tu non voglia occuparti anche dell'allocazione dello spazio per contenere le parole...

per il problema dell'ordinamento ho provato a buttare giù qualcosa vedi un po' se fa al caso tuo...



WList wl_sort(WList L)
{
WList sorgente = L;
WList destinazione = NULL;
WList temp, temp1;
int trovato;

if(sorgente != NULL)
{
destinazione = (WList)malloc(sizeof(WElem));
strcpy(destinazione->word, sorgente->word);
destinazione->next = NULL;
sorgente = sorgente->next;

while(sorgente != NULL)
{
if(strcmp(sorgente->word, destinazione->word) < 0)
{
temp1 = (WList)malloc(sizeof(WElem));
strcpy(temp1->word, sorgente->word);
temp1->next = destinazione;
destinazione = temp1;
}
else
{
temp1 = destinazione;
trovato=0;
while(temp1->next != NULL && trovato != 1)
if(strcmp(temp1->next->word, sorgente->word) < 0)
temp1 = temp1->next;
else
trovato = 1;

temp = (WList)malloc(sizeof(WElem));
strcpy(temp->word, sorgente->word);
temp->next = temp1->next;
temp1->next = temp;
}
sorgente = sorgente->next;
}
}

return destinazione;
}


All'interno del codice ci sono delle imperfezioni infatti quando effettui una allocazione dovresti controllare che l'allocazione sia andata a buon fine, ti devi ricordare di deallocare tutto prima che il programma termini ecc ecc...

VYCanisMajoris
20-02-2012, 00:34
Ti ringrazio infinitamente della tua risposta, l'ho letta e quasi tutta compresa. Per ora però mi concentro sulla scrittura dei files poichè l'esame che ho verterà piu su quello che altro, domani o dopodomani riprenderò con le liste :fighet:

Loading