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