Programmazione 1    (P-Z) a.a. 2007-08

Data una matrice M con n righe e m colonne, la matrice trasposta M^T ha come colonne le righe di M. Scrivere un programma che prende in input da tastiera le dimensioni di M, costruisce la matrice M con valori interi casuali ed utilizza una funzione per trovare la matrice trasposta corrispondente. Non si devono utilizzare variabili globali o definire dimensioni massime.

Dati due insiemi A e B, con |A| = n e |B| = m, scrivere le funzioni che permettono di gestire le seguenti operazioni:

1) cercare un elemento in un insieme.
2) inserire un elemento in un insieme (solo se non è già presente).
3) unione di due insiemi.
4) intersezione di due insiemi.
5) differenza tra due insiemi.
6) stampa del contenuto di un insieme.

Si richede allo studente di integrare le funzioni descritte in un programma che costruisce due insiemi di dimensioni diverse e contenenti valori interi casuali in [0,100], di eseguire le diverse operazioni e di stampare di volta in volta il risultato. Non si devono utilizzare variabili globali o definire dimensioni massime.
Nota: la differenza tra due insiemi A\B può essere implementata come unione(A,B) - B oppure A - intersezione(A,B).

Date due stringhe di caratteri testuali minuscoli str1 e str2 (punteggiatura e caratteri whitespaces esclusi) di una lunghezza qualsiasi (l), costruire un'array che contiene le stringhe così costituite: dati due caratteri nella stessa posizione in str1 e str2, costruire la stringa in cui i caratteri estremali sono i due stessi caratteri, mentre i caratteri intermedi sono tutti i caratteri dell'alfabeto compresi tra questi due.
Come esempio se le due stringhe sono abcdef e dgddab, la struttura avrà la seguente composizione:

abcd
bcdefg
cd
dd
edcba
fedcb

Nota: i caratteri nelle ultime due righe sono in sequenza invertita.

Fornire in seguito una funzione di filtro che elimina le vocali da ogni stringa della struttura, e fornisce in output un nuovo array di stringhe, costituite soltanto dai caratteri eliminati. Seguendo l'esempio precedente avremmo come risultato dell'operazione di filtro delle vocali, le seguenti due strutture:

bcd
bcdfg
cd
dd
dcb
fdcb

a
e
ea
e

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

typedef int* Matrix;
Matrix* allocaMatrix(int, int);
Matrix* trasponi(Matrix *, int, int);
void printMatrix(Matrix *, int, int);

int main(void) {
  
  int n, m;

  printf ("Inserisci il numero di righe: ");
  scanf ("%d", &n);

  printf ("Inserisci il numero di colonne: ");
  scanf ("%d", &m);
  
  Matrix* matrix = allocaMatrix(n, m);
  Matrix* matrixT = trasponi(matrix, n, m);
  
  printMatrix(matrix, n ,m);
  printf("\n");
  printMatrix(matrixT, m, n);

  return 0;
}

Matrix* allocaMatrix(int r, int c) {
  
  int i, j;

  srand(time(NULL));

  Matrix* m = (Matrix*)malloc(sizeof(Matrix) * r);
  if (!m) exit(1);
  
  for (i = 0; i < r; i++) {
    int* tmp = (int *)malloc(sizeof(int) * c);
    if (!tmp) exit(1);

    for (j = 0; j < c; j++) tmp[j] = rand() % 10;
    m[i] = tmp;
  }
  
  return m;
}


Matrix* trasponi(Matrix *m, int r, int c) {

  int i, j;
  Matrix* mt = allocaMatrix(c ,r);

  for (i = 0; i < r; i++) {
    for (j = 0; j < c; j++) {
      mt[j][i] = m[i][j];
    }
  }
  return mt;
}

void printMatrix(Matrix* m, int r, int c) {
  
  int i, j;
  for (i = 0; i < r; i++) {
    for (j = 0; j < c; j++) {
      printf ("%d ", m[i][j]);
    }
    printf ("\n");
  }
}

Dato un Set costituito da interi positivi, con l'intero -1 di terminazione, considerare le seguenti funzioni:

short int find(Set s, int e) {
  // indica se è presente o no l'elemento "e" nel Set s.
  short int i = 0;
  
  while(s && s[i] >= 0) {
    if (s[i] == e) return 1; 
    i++;
  }
  return 0;
}

short int cardinality(Set s) {
  // conta il numero di elementi nel Set s
  short int i = 0, len = 0;

  while(s[i++] >= 0) len++;
  return len;
}

Set unione (Set s1, Set s2) {
  short int dim1 = cardinality(s1), dim2 = cardinality(s2);
  short int dim = 0, i;

  // tmp è il Set temporaneo.
  Set tmp = (Set)malloc(sizeof(int) * (dim1 + 1));
  if (!tmp) exit(1);

  // copiamo tutti il Set s1 in tmp, l'elemento di terminazione è il "-1".
  for (i = 0; i < dim1; i++) tmp[i] = s1[i];
  tmp[dim1] = -1;
  dim = dim1;

  for (i = 0; i < dim2; i++) {
    if (!find(tmp, s2[i])) {
      // se nel Set tmp non compare già l'elemento corrente in s2
      // lo aggiungiamo nel Set.
      tmp = (Set)realloc(tmp, sizeof(int) * (dim + 2));
      tmp[dim] = s2[i];
      tmp[dim + 1] = -1;
      dim++;
    }
  }
  return tmp;
}

Set intersezione(Set s1, Set s2) {
  short int i, j;
  short int dim = 0, dim1 = cardinality(s1), dim2 = cardinality(s2);

  Set tmp = NULL;

  for (i = 0; i < dim1; i++) {
    for (j = 0; j < dim2; j++) {
      if (s1[i] == s2[j]) {
	short int k;
        // il Set tmp2 contiene l'intersezione corrente
	Set tmp2 = (Set)malloc(sizeof(int) * (dim + 2));
        if (!tmp2) exit(1);
	// copiamo il vecchio Set tmp nel Set di appoggio tmp2
	for (k = 0; k < dim; k++) tmp2[k] = tmp[k];
	tmp2[dim] = s1[i];
	tmp2[++dim] = -1;
	if (tmp) free(tmp);
	tmp = tmp2;
      }    
    }
  }
  return tmp;
}

Set differenza(Set a, Set b) {
  short int dim1 = cardinality(a), dim2 = cardinality(b), i, j, dim = 0;
  Set tmp = NULL;

  for (i = 0; i < dim1; i++) {
    short int found = 0;
    for (j = 0; j < dim2 && !found; j++) if (b[j] == a[i]) found = 1;
    if (!found) {
      tmp = (Set)realloc(tmp, sizeof(int) * (dim + 2));
      if (!tmp) exit(1);
      tmp[dim++] = a[i];
    }
  }
  tmp[dim] = -1;
  
  return tmp;
}