PDA

Visualizza la versione completa : [C] Problema lista linkata ordinata


Prog13
06-12-2011, 13:36
Ho un problema con la lista linkata ordinata alfabeticamente. Quando una parola deve essere inserita in testa, la inserisce senza problemi, ma quando deve essere inserita in mezzo o in coda, non la inserisce in un nuovo nodo, ma in uno preesistente cancellando così la parola che c'era prima. Ad esempio se inserisco cane e poi abaco mi visualizza giustamente:

abaco
cane

Quando poi inserisco zembra la lista risulta essere:

abaco
zebra

Qualcuno sa aiutarmi?


#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#define MAX_DIM 20

struct Elenco;
typedef Elenco * puntElenco;
typedef struct Elenco{
char info[MAX_DIM];
puntElenco next;
} Elenco;


puntElenco inserisci(puntElenco L, char*word){
puntElenco q;
q=(puntElenco)malloc(sizeof(Elenco));
strcpy(q->info,word);
q->next=L;
return(q);
}

puntElenco InserisciElementoInLista(puntElenco L,char*parola){
puntElenco q=L, prec;
int PosTrovata=0;
if(q==NULL){
q=inserisci(L,parola);
return(q);
}
if(strcmp(q->info,parola)==1){
q=inserisci(L,parola);
return q;
}

prec=q;
while((q->next!=NULL) && (PosTrovata==0)){
if(strcmp(q->info,parola)==-1){
prec=q;
q=q->next;
}
else PosTrovata=1;
}
prec->next=inserisci(q->next,parola);
return (L);
}


void VisualizzaLista(puntElenco L){
puntElenco q=L;
printf("\nLista parole:\n\n");
while(q!=NULL){
printf("%s\n",q->info);
q=q->next;
}
printf("\n");
}

main (){
puntElenco el_parole;
el_parole = NULL;
int scelta,a=1,vocali=0,i;
char word[MAX_DIM]={'\0'},lunga[MAX_DIM]={'\0'};
do{
system("cls");
printf("SCELTA OPERAZIONE \n");
printf("\nPREMI 1:-----------INSERISCI PAROLA---------------------\n");
printf("PREMI 2:-----------VISUALIZZA LISTA-----------------\n");
printf("PREMI 3:----------------USCITA-----------------\n");
printf("\nScelta: ");
scanf("%d",&scelta);

if(scelta==1){
printf("Digita la parola da inserire: ");
scanf("%s",word);
el_parole=InserisciElementoInLista(el_parole,word) ;
}

if(scelta==2) VisualizzaLista(el_parole);



if(scelta==3) a=0;

if(scelta!= 1 && scelta!= 2 && scelta!= 3) printf("\nScelta non valida\n\n");

system("PAUSE");
} while(a!=0);
return 0;
}

Prog13
06-12-2011, 21:36
Dato il problema che riscontro, credo che il problema sia in questa parte del codice:


while((q->next!=NULL) && (PosTrovata==0)){
if(strcmp(q->info,parola)==-1){
prec=q;
q=q->next;
}
else PosTrovata=1;
}
prec->next=inserisci(q->next,parola);
return (L);
}


Nessuno sa aiutarmi?

ramy89
06-12-2011, 23:09
if(strcmp(q->info,parola)==-1)

strcmp ritorna 0 se le stringhe sono uguali, un valore maggiore di zero se le stringhe sono diverse.
Ma non sai precisamente che valore ritorna, in generale ti conviene controllare se è diverso da zero o no.

oregon
06-12-2011, 23:13
Originariamente inviato da ramy89


if(strcmp(q->info,parola)==-1)

strcmp ritorna 0 se le stringhe sono uguali, un valore maggiore di zero se le stringhe sono diverse.
Ma non sai precisamente che valore ritorna, in generale ti conviene controllare se è diverso da zero o no.

No ... non è così ... la strcmp restituisce 0, un valore >0 o un valore <0 a seconda del confronto tra le stringhe ...

ramy89
06-12-2011, 23:43
Originariamente inviato da oregon
No ... non è così ... la strcmp restituisce 0, un valore >0 o un valore <0 a seconda del confronto tra le stringhe ...

Già...

Penso di aver capito il perchè del problema: la funzione inserisci alloca un nuovo elemento di tipo puntElenco,e il suo successivo punterà all' elemento che gli hai passato cioè L.
Ma se gli passi un L che sta in mezzo alla lista perdi tutti gli elementi precedenti, perchè:
1)Allochi un nuovo elemento e ci inserisci la stringa;
2)Il nuovo elemento -> successivo punterà ad L;
3)Ritorni il nuovo elemento.

Per cui perdi traccia di quelli precedenti.

ramy89
06-12-2011, 23:48
Per fare un esempio se nella lista ci sono:
"uno" "due" "quattro" "cinque"
E tu vuoi aggiungere l' elemento "tre" in mezzo alla lista, hai un puntatore che punta alla cella che contiene "quattro", allochi una nuova cella, gli copi "tre" con la strcpy, il successivo della cella allocata lo fai puntare alla cella che contiene "quattro" e ritorni la nuova cella allocata.
Per cui ovviamente ti stampa "tre" "quattro" "cinque"

Prog13
07-12-2011, 11:19
No non succede così, praticamente ogni volta che inserisco una nuova parola, se deve andare in cima la inserisce correttamente, mentre se deve andare in mezzo, rimuove la parola che dovrebbe stare dopo, e se deve inserirla in fondo, rimuove quella precedente, e non riesco proprio a capirne il motivo.

oregon
07-12-2011, 12:03
L'errore "logico" è evidentemente in



prec=q;
while((q->next!=NULL) && (PosTrovata==0))
{
if(strcmp(q->info,parola)==-1)
{
prec=q;
q=q->next;
}
else
PosTrovata=1;
}

prec->next=inserisci(q->next,parola);


Riesamina riga per riga quello che fai e chiediti se il ragionamento è corretto nel caso in cui hai il problema.

P.S. Dai un'occhiata a

http://www.dis.uniroma1.it/~liberato/struct/liste/inmezzo.shtml

ramy89
07-12-2011, 19:17
Originariamente inviato da Prog13
No non succede così, praticamente ogni volta che inserisco una nuova parola, se deve andare in cima la inserisce correttamente, mentre se deve andare in mezzo, rimuove la parola che dovrebbe stare dopo, e se deve inserirla in fondo, rimuove quella precedente, e non riesco proprio a capirne il motivo.

Ma guarda qua:


puntElenco inserisci(puntElenco L, char*word){
puntElenco q;
q=(puntElenco)malloc(sizeof(Elenco));
strcpy(q->info,word);
q->next=L;
return(q);
}


Se tu gli passi un L che sta in mezzo alla lista è ovvio che te le "taglia".
q è un elemento della lista allocato che avrà come successivo L.
Poi dichiari:


return (q);

Allora tu quando dichiari nel main:


el_parole=InserisciElementoInLista(el_parole,word) ;

Ciò implica:


q=inserisci(L,parola);

Ma allora q non sarà più la lista di prima, sarà una nuova lista contenente il nuovo elemento inserito, più tutti gli elementi che ci sono da metà lista in poi (dipende da cosa gli passi come L).

ramy89
07-12-2011, 19:21
Insomma prova a modificare la funzione così e vedi se funziona:


puntElenco inserisci(puntElenco L, char*word){
puntElenco temp=L->next;
L->next=(puntElenco)malloc(sizeof(Elenco));
strcpy(L->next->info,word);
L->next->next=temp;
return L->next;
}

Così com'è dovrebbe funzionare tranne per il fatto che ti inserisce l' elemento nella posizione successiva a quella che vuoi te.Gli devi quindi passare un L che sia il precedente di quello che gli passi nel tuo codice.

Loading