Ciao a tutti ho un problema con l'ordinamento di una lista qualcuno mi può dare una mano? Grazie per l'aiuto.
Ho provato a fare così ma niente
codice:void ordine(struct elemento *p) { int valore; struct elemento *aux; aux=p->succ; while(aux!=NULL){ if(p->val>aux->val){ valore=p->val; p->val=aux->val; aux->val=valore; } aux=aux->succ; } /*Visualizzazione ordinamento */ while(p!=NULL){ printf("%d --->",p->val); p=p->succ; } printf("NULL\n\n"); }
Il problema è che qua:
Scorri la lista una sola volta.codice:while(aux!=NULL){ if(p->val>aux->val){ valore=p->val; p->val=aux->val; aux->val=valore; }
Se i valori sono [3,2,1], al primo confronto trascini il tre in seconda posizione e diventa:
[2,3,1]
Al secondo confronto trascini il tre in terza posizione e diventa:
[2,1,3]
Poi aux diventa NULL e si esce dal while.
Hai bisogno di fare più confronti, se non vuoi badare all' efficienza puoi fare N^2 confronti (cioè scorri la lista N volte).
Anche se in realtà lo potresti fare più efficientemente.Ma intanto ti suggerisco di fare la versione che non si preoccupa dell' efficienza, giusto per capire come funziona.
E il mio problema è proprio questo di fare ripete il ciclo n volte...non saprei come fare...pensavo con un ciclo for tipo:
Il problema è che n non ce l'ho perchè l'ho dichiarato in crealistacodice:for(i=1;i<=n;i++) while(aux!=NULL){ if.... ..... }
ti metto il codice completo:
codice:#include <stdio.h> #include <malloc.h> struct elemento{ int val; struct elemento *succ; struct elemento *prec; }; struct elemento *crealista(); void visualizza(struct elemento *); void maggiore(struct elemento *); void ordine(struct elemento *); main() { struct elemento *puntlista; puntlista=crealista(); visualizza(puntlista); maggiore(puntlista); ordine(puntlista); getchar(); getchar(); } struct elemento *crealista() { int i,n; struct elemento *testa,*corpo; printf("Quanti valori vuoi inserire? : "); scanf("%d",&n); testa=(struct elemento *)malloc(sizeof(struct elemento)); testa->prec=NULL; printf("Inserisci il 1%c valore: ",248); scanf("%d",&testa->val); corpo=testa; for(i=2;i<=n;i++){ corpo->succ=(struct elemento *)malloc(sizeof(struct elemento)); (corpo->succ)->prec=corpo; corpo=corpo->succ; printf("Inserisci il %d%c valore: ",i,248); scanf("%d",&corpo->val); } corpo->succ=NULL; return(testa); } void visualizza(struct elemento *p) { printf("\nLista: "); while(p->succ!=NULL){ printf("%d",p->val); printf("---> "); p=p->succ; } printf("%d",p->val); printf("---> NULL\n\n"); printf("Lista: "); while(p!=NULL){ printf("%d",p->val); printf("---> "); p=p->prec; } printf("NULL\n\n"); } void maggiore(struct elemento *p) { int i,max; while(p->succ!=NULL){ p=p->succ; } max=p->val; while(p!=NULL){ if(p->val > max){ max=p->val; } p=p->prec; } printf("Il valore massimo inserito %c: %d.\n\n",138,max); } void ordine(struct elemento *p) { int valore; struct elemento *aux; aux=p->succ; while(aux!=NULL){ if(p->val>aux->val){ valore=p->val; p->val=aux->val; aux->val=valore; } aux=aux->succ; } while(p!=NULL){ printf("%d --->",p->val); p=p->succ; } printf("NULL\n\n"); }
Con il for non si ottiene nulla ...come posso fare?
In questo caso fai all' incirca N^2/2 confronti, ma dovrebbero essere sufficienti per ordinare il vettore, è una variante del bubblesort.codice:void ordine(struct elemento *p) { int valore; struct elemento *aux,*temp; aux=p->succ; while(aux!=NULL) { temp=aux; while(temp!=NULL) { {...} // fai il confronto temp=temp->succ; } aux=aux->succ; } }
Non funziona neanche così
codice:void ordine(struct elemento *p) { int valore; struct elemento *aux,*temp; aux=p->succ; while(aux!=NULL){ temp=aux; while(temp!=NULL){ if(p->val>aux->val){ valore=p->val; p->val=aux->val; aux->val=valore; temp=temp->succ; } aux=aux->succ; } }
Il confronto nel while interno ovviamente va fatto su temp e temp->succ,non au aux, visto che stai scorrendo temp e non aux.
Comunque sbagli a scorrere la lista.Perchè lo confronti sempre con p, che è il primo?
L' ordinamento deve essere dinamico, devi confrontare gli elementi adiacenti, perchè confrontarlo sempre col primo elemento?
Scorri la lista così:
codice:void ordine(struct elemento *p) { int valore; struct elemento *aux,*temp; aux=p; while(aux->succ!=NULL) { temp=aux; while(temp->succ!=NULL) { {...} // fai il confronto tra temp e temp->succ temp=temp->succ; } aux=aux->succ; } }
Sarò stupido ma non lo capisco...
codice:void ordine(struct elemento *p) { int valore; struct elemento *aux,*temp; aux=p; while(aux->succ!=NULL){ temp=aux; while(temp->succ!=NULL){ if(temp>temp->succ){ valore=temp; temp=temp->val; temp->val=valore; temp=temp->succ; } } aux=aux->succ; }
Stavi assegnando valore che è un intero, a temp che è un puntatore.
Poi ho sostituito temp=aux con temp=p perchè in effetti stavo considerando solo la parte finale della lista.Per capirlo fai finta che è uguale a un vettore, dove temp e temp->succ sono adiacenti in memoria (anche se in realtà non è così).
Allora stai confrontando due elementi adiacenti del vettore.Se l' elemento i-esimo è maggiore dell' elemento (i+1)-esimo li scambi.
Eidt: Altra cosa,il confronto va fatto sui valori (il campo val), non sui puntatori.Così stai solo confrontando due indirizzi.Il che non ha senso.codice:void ordine(struct elemento *p) { int valore; struct elemento *aux,*temp; aux=p; while(aux->succ!=NULL){ temp=p; while(temp->succ!=NULL){ if(temp->val>temp->succ->val){ valore=temp->val; temp->val=valore; temp->succ->val=valore; } temp=temp->succ; } aux=aux->succ; }
Poi temp va scorso fuori dall' if, altrimenti lo scorri solo se il temp->val è maggiore di temp->succ->val.
Così dovrebbe essere ok, almeno spero.Dimmi se funziona
Non capisco questa parte:
Ok il confronto dell'if ci sono ma xkè prima copi il valore temp->val in valore e poi viceversa copi valore in temp->val??? Così hai che temp->val e valore sono uguali.codice:if(temp->val>temp->succ->val){ valore=temp->val; temp->val=valore; temp->succ->val=valore; }
Non dovrebbe essere
o sbaglio?? (probabilecodice:valore=temp->val; temp->val=(temp->succ)->val; (temp->succ)->val=valore;)
Permessi di invio
Rispondi quotando