Simulazione ambulatorio

Questo è il problema: http://vinello.isti.cnr.it:10000/#/task/Lez1101/statement
Comunque, anche senza stare a leggerlo tutto, dovreste poter vedere un errore nella porzione di codice che ho evidenziato sotto. Ottengo segmentation fault, anche solo digitando solo 1 e poi un nome.

Valgrind dice:
==3223== Use of uninitialised value of size 8
==3223== at 0x4008DE: main (in /home/cristina/simEsame)
==3223==
==3223== Invalid write of size 8
==3223== at 0x4008DE: main (in /home/cristina/simEsame)
==3223== Address 0x8 is not stack'd, malloc'd or (recently) free'd
==3223==
[...]
==3223== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
Errore di segmentazione

...ma non vedo l'errore.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _elem {
  char* key;
  struct _elem *next;
} elem;

int compare(const void *a, const void *b){
return strcmp(*(char**)a, *(char**)b);
}

[b]elem* InserisciCoda(char *s){
elem *new;
new=(elem*)malloc(sizeof(elem));
new->key=s;
new->next=NULL;
return new;
}
[/b]
elem* RimuoviPrimo(elem *head){
elem *curr = head;
head=head->next;
free(curr);
return head;
}

void OrdinaLista(elem *head){
int len, i;
elem *curr = head;
while(curr!=NULL) len++;
curr=head;
char **a;
a = (char **) malloc(len*sizeof(char*));
i=0;
while(i<len && curr!=NULL){
   a[i] = curr->key;
   i++;
   }
qsort(a,len,sizeof(char*),compare);
for(i=0;i<len;i++) printf("$%s\n",a[i]);
for(i=0;i<len;i++) free(a[i]);
}


[b]int main () {
elem *head;
elem *tail = head;
elem *curr;
char s[101];
int x = -1;

while(x!=0){
  scanf("%d", &x);
  if (x==1){
    scanf("%s", s);
    tail->next=InserisciCoda(s);
    tail=tail->next;
    }
[/b]  if (x==2)
   head=RimuoviPrimo(head);
  }
if (head==NULL) {printf("$\n"); return 0;}
OrdinaLista(head);
while(head!=NULL){
  curr=head;
  head=curr->next;
  free(curr);
  }
return 0;
}

Comments

  • Non ho letto tutto il codice ma credo che il problema sia proprio l'inizializzazione della struttura dati: quando nel main fai
    elem *head;
    elem *tail = head;
    
    dentro head trovi garbage e la stessa garbage va a finire anche in tail. Quando legge x=1 il tuo codice crea l'elemento lista e la main cerca di assegnare il puntatore al campo next di tail (che come detto prima contiene garbage, causando il crash perché non sono variabili di tipo elem e non hanno un campo next).

    Dovresti inizializzare head con NULL e poi dentro il while gestire il caso in cui la lista sia ancora vuota nel caso in cui crei un nuovo elemento (assegnando a head e a tail il puntatore a tale nuovo elemento, piuttosto che assegnarlo a tail.next), oppure inizializzare head con una malloc come fai in InserisciCoda e poi andando a mettere lì la stringa al primo inserimento.
  • YmirYmir Posts: 183
    Ho usato la lista bidirezionale adesso, ma vabbè. Comunque, intendevi così?
    Ora il ciclo non termina.
    int main () {
    elem *head = (elem*)malloc(sizeof(elem));
    elem *first = (elem*)malloc(sizeof(elem));
    elem *curr = (elem*)malloc(sizeof(elem));
    char s[101];
    int x = -1;
    first=NULL;
    
    scanf("%d",&x);
    scanf("%s",s);
    head->key=s;
    head->next=NULL;
    head->prec=NULL;
    first=head;
    
    while(x!=0){
      scanf("%d", &x);
      if (x==1){
        scanf("%s", s);
        head->next=InserisciCoda(head, s);
        head=head->next;
        }
      if (x==2)
       first=RimuoviPrimo(first);
      }
    
  • Alessandro PagiaroAlessandro Pagiaro Posts: 20
    edited February 2016
    A me non compila neanche il codice
    Untitled.c:58:7: error: no member named 'prec' in 'struct _elem'
    head->prec=NULL;
    ~~~~  ^
    Untitled.c:65:36: error: too many arguments to function call, expected single argument 's', have 2 arguments
        head->next=InserisciCoda(head, s);
                   ~~~~~~~~~~~~~       ^
    Untitled.c:14:1: note: 'InserisciCoda' declared here
    elem* InserisciCoda(char *s){
    ^
    Untitled.c:70:2: error: expected '}'
    }
     ^
    Untitled.c:46:13: note: to match this '{'
    int main () {
                ^
    3 errors generated.
    

    Il codice che ho provato a compilare è quello del primo messaggio il cui main è stato sostituito con quello del terzo. Risultato: http://pastebin.com/Vjiuu45M

    Puoi postare il codice con le tue ultime correzioni?
  • YmirYmir Posts: 183
    Sì, scusa.
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct _elem {
      char* key;
      struct _elem *next;
      struct _elem *prec;
    } elem;
    
    int compare(const void *a, const void *b){
    return strcmp(*(char**)a, *(char**)b);
    }
    
    elem* InserisciCoda(elem *head, char *s){
    elem *new;
    new=(elem*)malloc(sizeof(elem));
    new->key=s;
    new->next=NULL;
    new->prec=head;
    return new;
    }
    
    elem* RimuoviPrimo(elem *first){
    elem *curr = (elem*)malloc(sizeof(elem)); 
    curr=first;
    first=first->next;
    first->prec=NULL;
    free(curr);
    return first;
    }
    
    void OrdinaStampaLista(elem *head){
    int len, i;
    elem *curr = (elem*)malloc(sizeof(elem));
    curr=head;
    while(curr!=NULL) len++;
    curr=head;
    char **a;
    a = (char **) malloc(len*sizeof(char*));
    i=0;
    while(i<len && curr!=NULL){
       a[i] = curr->key;
       i++;
       }
    qsort(a,len,sizeof(char*),compare);
    for(i=0;i<len;i++) printf("$%s\n",a[i]);
    for(i=0;i<len;i++) free(a[i]);
    }
    
    
    int main () {
    elem *head = (elem*)malloc(sizeof(elem));
    elem *first = (elem*)malloc(sizeof(elem));
    elem *curr = (elem*)malloc(sizeof(elem));
    char s[101];
    int x = -1;
    first=NULL;
    
    scanf("%d",&x);
    scanf("%s",s);
    head->key=s;
    head->next=NULL;
    head->prec=NULL;
    first=head;
    
    while(x!=0){
      scanf("%d", &x);
      if (x==1){
        scanf("%s", s);
        head->next=InserisciCoda(head, s);
        head=head->next;
        }
      if (x==2)
       first=RimuoviPrimo(first);
      }
    if (first==NULL) {printf("$\n"); return 0;}
    OrdinaStampaLista(first);
    while(first!=NULL){
      curr=first;
      first=curr->next;
      free(curr);
      }
    return 0;
    }
    
  • Non hai inizializzato len.
  • Se compili con gcc, impostando come opzione -g, valgrind ti esplicita la riga che ha causato il segFault. In questo caso, inserendo
    1
    ale
    2
    
    Alla riga 28, dentro la funzione RimuoviPrimo viene settata un'area di memoria non allocata. Difatti il problema si genera quando in lista c'è un solo cliente, cosa che comporta nella funzione alla riga 27 l'assegnamento first = NULL, con conseguente errore poi alle riga 28.

    Modificherei intanto la funzione come segue:
    elem* RimuoviPrimo(elem *first){
    	elem *curr = (elem*)malloc(sizeof(elem)); 
    	curr=first;
    	first=first->next;
    	if(first!=NULL) first->prec=NULL;
    	free(curr);
    	return first;
    }
    

    E poi verifica se ti dà ancora problemi o no.
  • Alessandro PagiaroAlessandro Pagiaro Posts: 20
    edited February 2016
    MindFlyer wrote: »
    Non hai inizializzato len.
    Il problema qui è diverso. I compilatori di solito quando la variabile non è inizializzata la inizializzano a 0. O almeno il mio fa così. Il problema principale, secondo me, di questa funzione è invece che se curr!=NULL, entro nel ciclo, ma non ci esco più!! curr non viene mai modificata all'interno del ciclo quindi una volta che sto dentro, incremento len (qualunque sia il suo valore) ma non ho possibilità di uscirne
  • YmirYmir Posts: 183
    edited February 2016
    Avevo dimenticato degli incrementi in alcuni while che non terminavano.
    Ho modificato anche con quello che mi hai suggerito. In basso incollo gli errori.
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct _elem {
      char* key;
      struct _elem *next;
      struct _elem *prec;
    } elem;
    
    int compare(const void *a, const void *b){
    return strcmp(*(char**)a, *(char**)b);
    }
    
    elem* InserisciCoda(elem *head, char *s){
    elem *new;
    new=(elem*)malloc(sizeof(elem));
    new->key=s;
    new->next=NULL;
    new->prec=head;
    return new;
    }
    
    elem* RimuoviPrimo(elem *first){
    elem *curr = (elem*)malloc(sizeof(elem)); 
    curr=first;
    first=first->next;
    if (first!=NULL)first->prec=NULL;
    free(curr);
    return first;
    }
    
    void OrdinaStampaLista(elem *head){
    int len, i;
    elem *curr = (elem*)malloc(sizeof(elem));
    curr=head;
    while(curr!=NULL){ len++; curr=curr->next;}
    curr=head;
    char **a;
    a = (char **) malloc(len*sizeof(char*));
    i=0;
    while(i<len && curr!=NULL){
       a[i] = curr->key;
       i++;
       curr=curr->next;
       }
    qsort(a,len,sizeof(char*),compare);
    for(i=0;i<len;i++) printf("$%s\n",a[i]);
    for(i=0;i<len;i++) free(a[i]);
    }
    
    
    int main () {
    elem *head = (elem*)malloc(sizeof(elem));
    elem *first = (elem*)malloc(sizeof(elem));
    elem *curr = (elem*)malloc(sizeof(elem));
    char s[101];
    int x = -1;
    first=NULL;
    
    scanf("%d",&x);
    scanf("%s",s);
    head->key=s;
    head->next=NULL;
    head->prec=NULL;
    first=head;
    
    while(x!=0){
      scanf("%d", &x);
      if (x==1){
        scanf("%s", s);
        head->next=InserisciCoda(head, s);
        head=head->next;
        }
      if (x==2)
       first=RimuoviPrimo(first);
      }
    if (first==NULL) {printf("$\n"); return 0;}
    OrdinaStampaLista(first);
    while(first!=NULL){
      curr=first;
      first=curr->next;
      free(curr);
      }
    return 0;
    }
    

    Solo così funziona:
    1
    aaa
    2
    0
    $
    

    Invece:
    1
    aaa
    1
    aab
    2
    0
    $aab
    *** Error in `./sim2': double free or corruption (out): 0x00007ffd00749590 ***
    Annullato
    
    1
    aaa
    1
    abb
    0
    $abb
    $abb
    *** Error in `./sim2': double free or corruption (out): 0x00007ffd048d0c50 ***
    Annullato
    
  • Oltre a quel len non inizializzato (che è un errore, a prescindere da cosa facciano poi di solito i compilatori), devi anche calcolare len nel modo giusto.

    Al posto di quel
    while(curr!=NULL) len++;
    

    metti
    len=0;
    while(curr!=NULL){
        len++;
        curr=curr->next;
    }
    

    A parte questo, c'è solo un errore di formattazione dell'output (rileggi nelle specifiche come dev'essere formattato l'output).
  • Ora hai messo malloc ogni volta che dichiari una variabile puntatore, ma non serve, non era quello che intendevo!
    Nel main di queste tre malloc bastava fare la prima, gli altri due puntatori puoi dichiararli senza allocare:
    elem *head = (elem*)malloc(sizeof(elem));
    elem *first = (elem*)malloc(sizeof(elem));
    elem *curr = (elem*)malloc(sizeof(elem));
    
    anche perché più avanti assegni sia a first che a curr altri valori, quindi lo spazio allocato qui è allocato inutilmente (perché non lo usi, e visto che sovrascrivi i puntatori first e curr nemmeno volendo potresti).
    Lo stesso vale anche in RimuoviPrimo e OrdinaStampaLista quando dichiari curr.

    A parte questo ho notato una cosa, anche se forse non è il motivo per cui va in loop: in questo modo hai gestito l'inizializzazione (cioè il passaggio della coda da vuota, cioè head=first=NULL, a quando ha il primo utente, cioè head e first diversi da NULL). Però non tieni conto del fatto che dopo l'arrivo del primo paziente la coda potrebbe tornare ad essere vuota, in seguito a una o più rimozioni: in questo caso il codice non funzionerebbe in varie parti. Ad es. in RimuoviPrimo dovresti gestire il caso in cui ci sia un unico paziente in coda da rimuovere (in quel caso first->next sarà NULL e otterresti un errore), e poi dovresti mettere anche head a NULL (perché con un solo paziente in coda il primo è anche l'ultimo). Nel caso in cui x=1 dovresti prima controllare se head è uguale a NULL, cioè se il paziente che arriva trova davanti a se una coda vuota, perché in quel caso non puoi assegnare il nuovo elemento di lista a head->next, e così via.
  • MindFlyerMindFlyer Posts: 436
    edited February 2016
    C'è anche il problema che dicendo "new->key=s;" stai usando sempre lo stesso puntatore alla stessa stringa. Quindi tutti gli elementi della lista avranno alla fine lo stesso valore key. Tra l'altro, questo causerà anche un errore quando andrai a fare free su quegli elementi.

    Per farlo nel modo giusto, al posto di fare "new->key=s;", devi riallocare una nuova stringa per new->key, e copiarci dentro s.

    Poi: dopo "a[ i] = curr->key;" ci vuole "curr=curr->next;".

    E non ti serve quel campo prec. Puoi toglierlo.
  • Ah, e non mi pare che stai implementando una coda FIFO nel modo giusto... Consiglio di riscrivere tutto da zero.
  • MindFlyerMindFlyer Posts: 436
    edited February 2016
    Riscritto. Adesso è ok.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct _elem{
        char *key;
        struct _elem *next;
    }elem;
    
    typedef struct{
        elem *primo;
        elem *ultimo;
        int lung;
    }coda;
    
    coda *CreaCoda(){
        coda *c=(coda*)malloc(sizeof(coda));
        c->primo=c->ultimo=NULL;
        c->lung=0;
        return c;
    }
    
    void InserisciElemento(coda *c,char *s){
        elem *n=(elem*)malloc(sizeof(elem));
        n->key=(char*)malloc(1+strlen(s));
        strcpy(n->key,s);
        n->next=NULL;
        if(c->primo){
            c->ultimo->next=n;
            c->ultimo=n;
        }
        else c->primo=c->ultimo=n;
        c->lung++;
    }
    
    void RimuoviElemento(coda *c){
        if(c->lung){
            elem *secondo=c->primo->next;
            free(c->primo->key);
            free(c->primo);
            c->primo=secondo;
            if(c->primo==NULL) c->ultimo=NULL;
            c->lung--;
        }
    }
    
    void DistruggiCoda(coda *c){
        while(c->lung) RimuoviElemento(c);
        free(c);
    }
    
    int compare(const void *a, const void *b){
        return strcmp(*(char**)a,*(char**)b);
    }
    
    void OrdinaStampa(coda *c){
        char **a=(char**)malloc(c->lung*sizeof(char*));
        elem *iter=c->primo;
        int i=0;
        while(iter){
            a[i++]=iter->key;
            iter=iter->next;
        }
        qsort(a,c->lung,sizeof(char*),compare);
        for(i=0;i<c->lung;i++) printf("%s\n",a[i]);
        printf("$\n");
        free(a);
    }
    
    int main(){
        char s[101];
        coda *c=CreaCoda();
        int x;
        do{
            scanf("%d",&x);
            if(x==1){
                scanf("%s",s);
                InserisciElemento(c,s);
            }
            else if(x==2) RimuoviElemento(c);
        }while(x);
        OrdinaStampa(c);
        DistruggiCoda(c);
        return 0;
    }
    
Sign In or Register to comment.