[C] Problema lista linkata ordinata

[Prog13]

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]

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]

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]

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]

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]

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]

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]

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.../inmezzo.shtml

[ramy89]

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]

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.