Problema di allocazione

di il
9 risposte

Problema di allocazione

Buongiorno a tutti

Premetto subito che la soluzione che sto cercando di trovare è in C e non in C++.

Vengo alla questione.

Ho la necessità di memorizzare in un contenitore che non deve essere un file, delle parole passate in input. Consideriamo parola una sequenza di caratteri (escluso lo spazio e i caratteri speciali - non bisogna preoccuparsi di questo perchè si suppone che chi invia la parola sia diligente e la scriva giusta) chiusa da INVIO . Le parole inviate possono essere ovviamente ripetute e per ognuna di esse deve essere tenuta traccia delle occorrenze con un contatore. La parola non ha dimensione definita a priori. Per esempio:
Parola          Rip.
vino              2
zuzzurellone      1
aurelia           3
onnipresente      1
Io pensavo ad una matrice, ma, non avendo nè lunghezza predefinita della parola nè tantomeno dimensioni della matrice stessa (il numero delle parole è n) non so come fare per allocarla.

Spero che qualcuno mi possa aiutare.

Ringrazio e saluto cordialmente.

9 Risposte

  • Re: Problema di allocazione

    Il modo più semplice, secondo me, per risolvere il problema è quello di usare una lista di strutture. Dove ogni struttura contiene un puntatore alla parola e il numero di ripetizioni.
    Per fare ciò hai bisongo di usare l'allocazione dinamica della memoria, sia per creare la lista che per creare le stringhe che contengono le parole.

    Se non sai copsa siano le liste ti consiglio di cercare in formazioni in internet, poichè le liste sono lunghe da spiegare pertendo da zero. In ogni caso se vuoi chiedere cerchero di rispondere come riesco.....
  • Re: Problema di allocazione

    DPD ha scritto:


    Se non sai copsa siano le liste ti consiglio di cercare in formazioni in internet..... In ogni caso se vuoi chiedere cerchero di rispondere come riesco.....
    Ti ringrazio per la disponibilità.
    Dunque, io so cosa sono le liste e le cose semplici riesco a farle, dichiarazioni, allocazione, inserimento in coda o in testa e ricerca.

    Il consiglio di usarle è valido, ma ho due problemi:
    1) Come dichiaro la parola se questa può essere di lunghezza variabile ?
    2) Una volta data in input la parola, dovrei cercarla nella lista e fin quì tutto OK. Come faccio ad aggiornare il contatore delle ripetizioni se essa esiste già?

    Forse un esempio su questi due punti potrebbe risultarmi utile.

    Ciao e grazie ancora
  • Re: Problema di allocazione

    Ciao, allora....

    Per il primo punto potresti fare in due modi:
  • Re: Problema di allocazione

    DPD ha scritto:


    Scriverti una funzione di input che prenda i caratteri inseriti uno alla volta e li metta in un buffer, quando il buffer è pieno ne allochi uno nuovo e continui a scrivere null'ultimo buffer, continui così finchè non hai preso in input tutta la parola. I buffer puoi tenerli memorizzati in una lista.
    Interessante questo metodo. Supponga che si debba utilizzare le funzioni malloc e realloc; mi puoi suggerire un esempio o qualche link dove trovarli ?

    Grazie per il prezioso aiuto e cordiali saluti.
  • Re: Problema di allocazione

    Ecco una funzione di esempio che legge dallo standard input. La funzione restituisce 0 (zero) in caso di successo, diverso da 0 in caso di errore. In caso di successo nella variabile puntata dal parametro out scrive l'indirizzo della stringa con la parola letta in input, questa l'ultima viene allocata.
    I buffer vengono creati con una dimensione pari a MAX_READ_BUFFER_LEN.
    La variabile 'buf' contiene il carattere letto, 'i' il numero di caratteri scritti nel buffer corrente, 'n' il numero di buffer creati, 'cur' punta all'elemento della lista che contiene il buffer corrente ed 'first' è il primo elemento della lista. Il primo elemento della lista non lo alloco dinamicamente perchè è difficile che venga inserita una parola molto lunga, ed in ogni caso faccio un'allocazione in meno usando, così, meno risorse.
    #define MAX_READ_BUFFER_LEN  4096  // 4KB
    
    typedef struct _read_ele{
      struct _read_ele *succ;
      char buf[MAX_READ_BUFFER_LEN];
    } read_ele;
    
    int Input(char **out){
      char buf;
      int i=0, n=1;
      read_ele first, *cur=&first, *t;
      first.succ=NULL;
    
      // Svuoto l'stdin per evitare che eventuali
      // ritorni a capo rimasti da input precedenti
      // mi diano fastidio, il fflush può anche essere
      // tolto il codice funziona lo stesso ma può
      // ritornare stringa vuota
      fflush(stdin);
    
      fread(&buf, sizeof(char), 1, stdin);
      while(buf!=10){
        if(i<MAX_READ_BUFFER_LEN){
          cur->buf[i]=buf;
          i++;
        }else{
          cur->succ=malloc(sizeof(read_ele));
          if(cur->succ==NULL){
            // ERRORE: Memoria esaurita
            if(n>1){
              cur=first.succ;
              while(cur){
                t=cur->succ;
                free(cur);
                cur=t;
              }
            }
            return 1;
          }
          cur=cur->succ;
          cur->succ=NULL;
          cur->buf[0]=buf;
          i=1;
          n++;
        }
        fread(&buf, sizeof(char), 1, stdin);
      }
    
      // Calcolo la lunghezza della parola inserita
      // e alloco la memoria necessaria
      *out=malloc(n*MAX_READ_BUFFER_LEN+i+1);
      if(out==NULL){
        // ERRORE: Memoria esaurita
        if(n>1){
          cur=first.succ;
          while(cur){
            t=cur->succ;
            free(cur);
            cur=t;
          }
        }
        return 1;
      }
    
      // Copio la parola inserita nel buffer di *out
      if(n>1){
        memcpy(*out, first.buf, MAX_READ_BUFFER_LEN);
        n=MAX_READ_BUFFER_LEN;
      }else{
        memcpy(*out, first.buf, i);
        n=i;
      }
    
      if(first.succ){
        cur=first.succ;
        while(cur->succ){
          memcpy((*out)+n, cur->buf, MAX_READ_BUFFER_LEN);
          n+=MAX_READ_BUFFER_LEN;
    
          t=cur->succ;
          free(cur);
          cur=t;
        }
    
        memcpy((*out)+n, cur->buf, i);
        n+=i;
    
        free(cur);
      }
    
      (*out)[n]='\0';
    
      return 0;
    }
    Ciao.
  • Re: Problema di allocazione

    DPD ha scritto:


    In caso di successo nella variabile puntata dal parametro out scrive l'indirizzo della stringa con la parola letta in input, questa l'ultima viene allocata.
    Grazie mille per l'aiuto.
    Potressti chiarirmi meglio il significato della frase quotata ?
    Se volessi chiudere la parola con un Invio (cioè stabilire che l'input finisce con un INVIO) come posso modificare ?

    Ciao e saluti cordiali.
  • Re: Problema di allocazione

    Ciao.

    Con la frase 'questa l'ultima viene allocata' intendevo dire che l'area di memoria in cui viene memorizzata la stringa contenete la parola inserita viene allocata dinamicamente con malloc, pertanto ti devi ricordare, quando non ti serve più, di deallocarla con free.
    Per esempio questo pezzo di codice legge una parola e la stampa sullo standard output:
    char *parola;
    
    // Attenzione che passo un puntatore a parola e non parola
    if(Input(&parola)==0){
      printf("%s\n", parola);
      free(parola);  // La parola letta non mi serve più e la dealloco
    }else{
      printf("Errore nella funzione di input\n");
    }
    Nell'esempio le parole lette in input sono già terminate con INVIO. Il controllo viene fatto nella righa con 'while(buf!=10)', infatti il carattere con codice ascii 10 è propio quello che viene letto se si preme invio. Se vuoi modificare la condizione che fa terminare l'inserimento edlla parola è sufficente che cambi la condizione del 'while'.
  • Re: Problema di allocazione

    DPD ha scritto:


    Nell'esempio le parole lette in input sono già terminate con INVIO.
    Tutto molto chiaro.
    Sulla base dei tuoi suggerimenti ho scritto un programma server per una esercitazione di cui allego il codice. Certamente si può fare molto meglio, ma considera che sto imparando.
    
    #include <sys/types.h>
    #include <sys/socket.h>
    #include <netinet/in.h>
    #include <stdio.h>
    #include <ctype.h>
    #include <signal.h>
    #include <errno.h>
    #include <malloc.h>
    
    #define MAXCONN 5
    #define BENVENUTO  "Benvenuto nel server conta occorrenze \r\n"
    #define RICHIESTA "Invia la parola\r\n"
    
    struct Tag_Nodo {
    		  char *Parola;
          int Ripetizioni;
    		  struct Tag_Nodo *Next;
    		 };
    
    typedef struct Tag_Nodo Tipo_Nodo;
    typedef Tipo_Nodo *Tipo_Lista;
    
    // Prototipi
    void addressInit(struct sockaddr_in *indirizzo, int port, long IPaddr);
    void parolaRicevuta(int sockDesc,char *s);
    Tipo_Lista Insert(Tipo_Lista l, char *parola, int ripetizioni);
    Tipo_Nodo  *Search(Tipo_Lista l, char *parola);
    void Is_Empty(Tipo_Lista l);
    Tipo_Lista Inizializza(Tipo_Lista l);
    
    int main (unsigned argc, char **argv) {
    int SERVER_PORT, sock, client_len, fd;
    struct sockaddr_in server, client;
    char risposta[40];
    Tipo_Lista listaParole = NULL;
    Tipo_Nodo *NodoTrovato;
    int ripetizioni;
    //char parola;
    char *parola;
    listaParole            = Inizializza(listaParole);
    
     if (argc != 2) {
       fprintf(stderr, "Sintassi: %s <porta>\n", argv[0]);
       exit(4);
     }
    
    SERVER_PORT = atoi(argv[1]);
    
    /* impostazione del transport end point */
    if((sock = socket(AF_INET, SOCK_STREAM, 0)) == -1) {
    	perror("chiamata alla system call socket fallita");
    	exit(1);
    }
    
    /* inizializzo la struttura dell'indirizzo internet del server 
       la funzione utilizzata copia 0 nei primi strlen(myServer) byte dell'oggetto puntato
       da &server, operando in pratica un azzeramento della struttura. */
    memset ( &server, 0, sizeof(server) );
    addressInit(&server, SERVER_PORT, INADDR_ANY);
    
    /* binding dell'indirizzo al transport end point */
    if (bind(sock, (struct sockaddr *)&server, sizeof server) == -1) {
    	perror("chiamata alla system call bind fallita");
    	exit(2);
    }
    
    /* imposto il server in modo che possa gestire 5 richieste
       contemporaneamente */
    listen(sock, MAXCONN);
    
    /* inserisco questa chiamata per evitare che il figlio resti 'zombie'
       dovendo restituire il codice di ritorno al padre */
    signal(SIGCHLD,SIG_IGN);
    
    /* gestione delle connessioni dei client */
    while (1) {
    	client_len = sizeof(client);
    	if ((fd = accept(sock, (struct sockaddr *)&client, &client_len)) < 0) {
    		perror("Errore di accept della connessione");
    		exit(3);
    	}
    
    	/* ogni volta che il server accetta una nuova connessione,
         quest'ultima viene gestita da un nuovo processo figlio */
    	switch(fork()) {
    		case -1:
    			perror("Errore nella chiamata alla fork");
    			exit(4);
    		case 0:
    			fprintf(stderr, "Aperta connessione (PID %d).\n",getpid());
    			send(fd, BENVENUTO, strlen(BENVENUTO), 0);
    			send(fd, RICHIESTA, strlen(RICHIESTA), 0);
          parolaRicevuta(fd,parola);
          /* Se la parola non esiste la inserisce nella lista con
             ripetizione = 0
             Se la parola esiste incrementa di 1 il contatore */
          NodoTrovato = Search(listaParole, parola);
    //      ripetizioni = NodoTrovato;
          if (NodoTrovato != NULL){
          	ripetizioni = 0;
          	listaParole = Insert(listaParole, parola, ripetizioni);
          	}
          else {
          	ripetizioni = listaParole->Ripetizioni;	
          }	
         sprintf(risposta,"Il numero di occorrenze e' %d\n",ripetizioni);
         send(fd,risposta,strlen(risposta),0);
    
    			close(fd);
    			fprintf(stderr, "Chiusa connessione (PID %d).\n",getpid());
    }
    }
    }
    
    /**************************************************************************************************************************/
    void addressInit(struct sockaddr_in *indirizzo, int port, long IPaddr)
    {
      // Creo l'indirizzo Internet locale
       indirizzo->sin_family = AF_INET;
       indirizzo->sin_port = htons((u_short) port); // ordinamento dei Byte da Host a Rete
    
      /* indicando INADDR_ANY viene collegato il socket all'indirizzo locale IP
      *  dell'interaccia di rete che verrà utilizzata per inoltrare il datagram IP */
       indirizzo->sin_addr.s_addr = IPaddr;
    }
       
    void parolaRicevuta(int sockDesc,char *s){
    int i=0;
    int charRecv = 0;
    char c;
    
    charRecv = recv(sockDesc, &c, 1, 0);
    while (c !='\n'){
    	s[i++]=c;
    	charRecv = recv(sockDesc, &c, 1, 0); 
    } // End while (c !='\n')
    s[i]='\0';
    }
    
    Tipo_Lista Inizializza(Tipo_Lista l)
     {
       return (l = NULL);
     }
     
    Tipo_Lista Insert(Tipo_Lista l, char *parola, int ripetizioni)
     {
       Tipo_Lista Prec = NULL;
       Tipo_Lista Succ = l;
       Tipo_Lista Temp;
    
       while ( (Succ != NULL) && (strcmp(parola,Succ->Parola) > 0) )
         {
       	Prec = Succ;
    	  Succ = Succ->Next;
         }
       
       Temp = (Tipo_Lista) malloc(sizeof(Tipo_Nodo));
       if (Temp == NULL)
         {
          	printf("\nErrore nell'allocazione.\n");
            exit(1);
         }
       
       if (Prec == NULL)
         { 
    	      Temp->Parola = parola;
            Temp->Ripetizioni = 0;
    	      Temp->Next  = Succ;
    	      return Temp;
         }
       else
         {  
            Temp->Parola = parola;
            Temp->Ripetizioni = ripetizioni;
          	Temp->Next = Succ;
    	      Prec->Next = Temp;
            return l;
         }
     }
    
    Tipo_Nodo *Search(Tipo_Lista l, char *parola)
     { 
       while ( (l != NULL) && (strcmp(parola,l->Parola) > 0) )
         l = l->Next;
       if ( (l != NULL) && (strcmp(l->Parola,parola) == 0) ){
       	  l->Ripetizioni++;
          return l;}
       else
          return NULL; 
     }
    
    Si tratta di un Server in attesa su una porta di più connessioni client (max 5). Quando arriva una richiesta di connessione, permette l'invio di una parola da parte del client e dovrebbe rispondere con il numero di occorrenze di quella parola se già vi è stata una trasmissione della stessa.

    Compilato con Cygwin, non mi dà errori.
    Il problema è nel momento in cui lo lancio. Funziona tutto fino alla procedura parolaRicevuta. Al primo carattere trasmesso dal client ho questo messaggio in Cygwin:
    5 [main] myserver 2736 _cygtls:: handle_exception: Error while dumping state (probably corrupted stack). Ovviamente 2736 è il PID.

    Ci sto ammattendo, ma non riesco a trovare l'inghippo. Cosa ne pensi ?

    Ciao e grazie ancora.
  • Re: Problema di allocazione

    Ciao....da quello che ho capito, nella funzione main, tu dichiari la variabile parola come
    char *parola
    e poi la passi alla funzione parolaRicevuta, quest'ultima scrive dei byte nell'area di memoria puntata da parola. Il problema è che non hai inizializzato la variabile parola quindi la funzione parolaRicevuta scrive in un'area di memoria a caso generando l'errore.
    Potresti risolvere il problema dichiarando la variabile parola come un vettore di caratteri e non come un puntatore. Esempio:
    char parola[DIMENSIONE_MASSIMA_PAROLA];
Devi accedere o registrarti per scrivere nel forum
9 risposte