Soluzioni esercizi Homework 3

Esercizio 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


char* leggi_input(){
  char* T = (char*) calloc(1, sizeof(char));
  long int caratteri = 1;
  int curr_char;
  while((curr_char = getchar())!='-'){
    T = (char*) realloc(T, (caratteri+1)*sizeof(char));
    if (T == NULL) return NULL;
    T[caratteri-1] = curr_char;
    caratteri++;
  }
  T[-1] = '\0';
  return T;
}


/* Prende in input una stringa e un puntatore ad un long.
 Ritorna in output il prossimo token e pone *currchar al carattere
 successivo del token ritornato.*/
char* next_token (char* T, long* currchar){
  int i= (*currchar);
  char* token = NULL;
  if (T == NULL){
    *currchar = -1;
    return NULL;
  }
  while ((i <= strlen(T)) && isalnum(T[i])) i++;
  if (i == (*currchar)) {
    (*currchar) ++;
    return NULL;
  }
  token = (char*) calloc((i-(*currchar)+1), sizeof(char));
  if (token == NULL){
    (*currchar) = -1;
    return NULL;
  }
  token[(i-(*currchar))] = '\0';
  token = strncpy(token, T+(*currchar), i-(*currchar));
  *currchar = i + 1;
  return token;
}


/* Prende in input una stringa T e un puntatore ad un long.
   Ritorna in output la lista di parole di T e *numero punta al numero
   degli elementi della lista ritornata. */
char** tokenizza (char* T, long int* numero){
  long currchar = 0;
  int i;
  int token_number = 0;
  char** token_list = NULL;
  if (T == NULL){
    *numero = -1;
    return NULL;
  }
  while (currchar < strlen(T)){
    char* currtoken =  next_token(T, &currchar);
    if (currchar < 0){
      *numero = -1;
      return NULL;
    }
    if (currtoken != NULL){
      if ((token_list = (char**) realloc(token_list, (token_number + 1)*sizeof(char*))) == NULL){
        *numero = -1;
        return NULL;
      }
      token_list[token_number] = (char*)malloc(strlen(currtoken) * sizeof(char*));
      if (token_list[token_number] == NULL) {
        *numero = -1;
        return NULL;
      }
      token_list[token_number] = strcpy(token_list[token_number], currtoken);
      free(currtoken);
      token_number ++;
    }
  }
  *numero = token_number;
  return token_list;
}


/* Controlla se s1 e' diversa a s2. */
int diversi(char* s1, char* s2){
  int i;
  if (strlen(s1) != strlen(s2)) return 1;
  for (i = 0; i < strlen(s1); i++){
    if (s1[i] != s2[i]) return 1;
  }
  return 0;
}


void stampa_parola(char * parola, int frequenza){
  printf("%s %d\n", parola, frequenza);
  return;
}


/* Stampa le 10 parole piu' frequenti in token_list con la relativa
   frequenza affianco. */
void stampa_frequenze(char** token_list, int* frequenze, long int n) {
  long int index_max = 0;  // indice della parola corrente di massima frequenza
  long int i = 0;  // contatore ciclo for
  int parole_da_stampare = 10;
  if ((token_list == NULL) || (frequenze == NULL)) return;
  if (n == 1) return;
  while (parole_da_stampare > 0) {
    for (i = 0; i < n; i++) {
      if ((frequenze[index_max] < frequenze[i])) index_max = i;
    }
    if (frequenze[index_max] > 0) {
      stampa_parola(token_list[index_max], frequenze[index_max]);
      frequenze[index_max] = -1;
    }
    parole_da_stampare--;
  }
  return;
}


/* calcola la frequenza di ciascuna parola in token_list */
int* calcola_frequenze (char** token_list, long int token_number){
  long int i, j;
  int* frequenze = (int*) calloc(token_number, sizeof(int));
  if ((token_list == NULL) || (frequenze == NULL)) return NULL;
  for (i = 0; i < token_number; i++){
    if (token_list[i] != NULL){
      frequenze[i] = 1;
      for (j = i+1; j < token_number; j++){
        if ((token_list[j] != NULL) && (!diversi(token_list[i], token_list[j]))){
          char* da_cancellare = token_list[j];
     if (da_cancellare != NULL) free(da_cancellare);
          token_list[j]= NULL;
          frequenze[j] = -1;
          frequenze[i] = frequenze[i]+1;
        }
      }
    }
  }
  return frequenze;
}


int main () {
  long int np = 0;
  long int i = 0;
  char* T = leggi_input();
  char** token_list = tokenizza(T, &np);
  int* frequenze =  calcola_frequenze(token_list, np);
  stampa_frequenze(token_list, frequenze, np);
  for (i = 0; i < np; i++)  // libera la memoria allocata per le
             // parole diverse di token_list 
    if (token_list[i]!= NULL) free(token_list[i]); 
  free (token_list);  // libera la memoria allocata per l'array token_list
  free(frequenze);  // libera la memoria allocata per l'array frequenze
  return 1;
}

Esercizio 2

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


/* Prende in input una stringa e un puntatore ad un long.
 Ritorna in output il prossimo token e pone *currchar al carattere
 successivo del token ritornato.*/
char* next_token (const char T[], long* currchar){
  int i= (*currchar);
  char* token = NULL;
  while ((i <= strlen(T)) && isalnum(T[i])) i++;
  if (i == (*currchar)) {
    (*currchar) ++;
    return NULL;
  }
  token = (char*) calloc((i-(*currchar)+1), sizeof(char));
  if (token == NULL){
    (*currchar) = -1;
    return NULL;
  }
  token[(i-(*currchar))] = '\0';
  token = strncpy(token, T+(*currchar), i-(*currchar));
  *currchar = i + 1;
  return token;
}

/* Prende in input una stringa T e un puntatore ad un long.
   Ritorna in output la lista di parole di T e *numero punta al numero
   degli elementi della lista ritornata. */
char** tokenizza (const char T[], long int* numero){
  long currchar = 0;
  int i;
  int token_number = 0;
  char** token_list = NULL;

  while (currchar < strlen(T)){
    char* currtoken =  next_token(T, &currchar);
    if (currchar < 0){
      *numero = -1;
      return NULL;
    }
    if (currtoken != NULL){
      if ((token_list = (char**) realloc(token_list, (token_number + 1)*sizeof(char*))) == NULL){
        *numero = -1;
        return NULL;
      }
      token_list[token_number] = (char*)malloc(strlen(currtoken) * sizeof(char*));
      token_list[token_number] = strcpy(token_list[token_number], currtoken);
      free(currtoken);
      token_number ++;
    }
  }
  *numero = token_number;
  return token_list;
}

/* Controlla se s1 e' uguale a s2. */
int diversi(char* s1, char* s2){
  int i;
  if (strlen(s1) != strlen(s2)) return 1;
  for (i = 0; i < strlen(s1); i++){
    if (tolower(s1[i]) != tolower(s2[i])) return 1;
  }
  return 0;
}


/* Crea la lista con le parole differenti che appaiono un unica volta
   in ordine di apparizione nel testo iniziale. */
char** copia_differenti (char** token_list,
                         int* frequenze,
                         long int token_number,
                         long int np){
  long int i = 0;  // contatore for
  long int curr_token = 0;
  char** differenti = (char**) calloc(np, sizeof(char*));
  for (i = 0; (i < token_number); i++){
    if ((frequenze[i] != 0) && (token_list[i] != NULL)){
      differenti[curr_token] = (char*)calloc(strlen(token_list[i]), sizeof(char));
      if (differenti[curr_token] == NULL) return NULL;
      strcpy(differenti[curr_token], token_list[i]);
      curr_token = curr_token + 1;
    }
  }
  return differenti;
}

/* Data la lista token_list di parole, calcola il vettore di frequenze
   per ciascuna parola in essa.*/
int* calcola_frequenze (char** token_list, long int token_number){
  int i, j;
  int* frequenze = (int*) calloc(token_number, sizeof(int));
  for (i = 0; i < token_number; i++){
    if (token_list[i] != NULL){
      frequenze[i] = 1;
      for (j = i+1; j < token_number; j++){
        if ((token_list[j] != NULL) && (!diversi(token_list[i], token_list[j]))){
          char* da_cancellare = token_list[j];
     if (da_cancellare != NULL) free(da_cancellare);
          token_list[j]= NULL;
          frequenze[i] = frequenze[i]+1;
        }
      }
    }
  }
  return frequenze;
}


/* Dato l'array frequenze contenente le frequenze di ciascuna
   parola, conta il numero di parole differenti. */
long conta_differenti (int* frequenze, long int token_number){
  long int i = 0;
  long int differenti = 0;
  for (i = 0; i < token_number; i++){
    if (frequenze[i] != 0) differenti++;
  }
  return differenti;
}


char** Parole (const char T[], long int* np){
  long int token_number = 0;
  char** token_list = tokenizza (T, &token_number);
  int i;
  int* frequenze = NULL;
  if (token_number <= 0){
    *np = -1;
    return NULL;
  }
  if (token_list == NULL) {
    *np = 0;
    return NULL;
  }
  frequenze = calcola_frequenze(token_list, token_number);
  *np = conta_differenti (frequenze, token_number);
  return copia_differenti(token_list, frequenze, token_number, *np);
}

Esercizio 3

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


/* Pone agli adiacenti di una casella di distanza k-1 la distanza k,
   nel caso in cui la distanza corrente sia non ancora calcolata
   oppure maggiore di k. */
void sistema_adiacenti(int** M, int n, int i, int j, int k){
  if (i != 0) {  // Elemento corrente non e' della prima riga
    if ((M[i-1][j] == -1) || (M[i-1][j] > k))
      M[i-1][j] = k;
    if ((j != 0) && ((M[i-1][j-1] == -1) || (M[i-1][j-1] > k)))
      M[i-1][j-1] = k;
    if ((j != n-1) && ((M[i-1][j+1] == -1) || (M[i-1][j+1] > k)))
      M[i-1][j+1] = k;
  }
  if ((j != 0) && ((M[i][j-1] == -1) || (M[i][j-1] > k)))
    M[i][j-1] = k;
  if ((j != n-1) && ((M[i][j+1] == -1) || (M[i][j+1] > k)))
    M[i][j+1] = k;
  if (i != n-1) {  // Elemento corrente non e' dell'ultima riga
    if ((j != 0) && ((M[i+1][j-1] == -1) || (M[i+1][j-1] > k)))
      M[i+1][j-1] = k;
    if ((M[i+1][j] == -1) || (M[i+1][j] > k))
      M[i+1][j] = k;
    if ((j != n-1) && ((M[i+1][j+1] == -1) || (M[i+1][j+1] > k)))
      M[i+1][j+1] = k;
  }
}



/* Calcola le eventuali caselle a distanza k dall'acqua*/
void calcola_distanti(int ** A, int n, int k){
  int i, j;
  if (k == 0) return;  // caso base: casella di acqua.
  calcola_distanti (A, n, k-1);
  for (i = 0; i<n; i++){  // sistema gli adiacenti delle caselle
    for (j = 0; j<n; j++) // di distanza k-1
      if (A[i][j] == (k-1)) sistema_adiacenti(A, n, i, j, k);
  }  
}


/* Ritorna una matrice di supporto di 0: acqua e -1: terra. */
int ** calcola_territorio_iniziale(int** A, int n){
  int i, j;
  int ** T = (int **) calloc(n, sizeof(int*));
  if (T == NULL) return NULL;  
  for (i = 0; i < n; i++){
    T[i] = (int*) calloc(n, sizeof(int));
    if (T[i] == NULL) return NULL;
  }
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      if (A[i][j] == 1){ 
        T[i][j] = -1;
      }
      else T[i][j] = 0;
  return T;
}


/* Conta le caselle di distanza k in T e cancella la matrice
   di supporto T. */
int conta_distanti (int** T, int n, int k) {
  int i, j, distanti = 0;
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) if (T[i][j] == k) distanti++;
  for (i = 0; i < n; i++) if (T[i] != NULL) free(T[i]);
  if (T != NULL) free(T);
  return distanti;
}


int terre_distanti (int ** M, int n, int k){
  int i = 0;  // contatore righe
  int j = 0;  //contatore colonne
  int ** T = NULL;

  if ((k >= n) || (k < 0)) return 0;
  T = calcola_territorio_iniziale(M, n);
  if (T == NULL) return -1;

  if (k == 0) return conta_distanti(T, n, k);
  calcola_distanti(T, n, k);
  return conta_distanti(T,n,k);
}

-- JulindaStefa - 10 Dec 2007