Confronto testi

1990 – Maturità scientifica sperimentale

Sono dati due testi scritti e si desidera costruire un programma che stampi tutte e sole le parole che compaiono in ambedue i testi insieme alle occorrenze di ciascuna di esse nel primo e nel secondo.
I testi si possono considerare già memorizzati su disco magnetico.
Si descriva la struttura generale della procedura che s’intende seguire e se ne codifichi una parte in un linguaggio a scelta.

Ipotesi aggiuntive

1. Le parole sono già disposte una per ogni riga
2. Le parole sono al massimo 1000 (quindi si fa tutto su array…)

#include 
#include 
#include 
#define MAX 80
#define NUMERO 1000
 
typedef struct par
{
   char parola[MAX];
   int  conta;
} PAROLA;
/* -------------------------------------------------------------- */
FILE   *f;
PAROLA p1[NUMERO];
PAROLA p2[NUMERO];
int    n1,
       n2;
void   carica(PAROLA *, int *);
void   scarica();
int    confronta(const void *a, const void *b);
/* -------------------------------------------------------------- */
int main()
{  
   n1=n2=0;                                // inizializza?
   for(int i=0; i < NUMERO; i++)
      p1[i].conta=p2[i].conta=0;
   
   f=fopen("input1.txt", "r"); carica(p1, &n1); fclose(f);
   f=fopen("input2.txt", "r"); carica(p2, &n2); fclose(f);
   f=fopen("output.txt", "w"); scarica();       fclose(f);                   
                               return 0;
}
/* -------------------------------------------------------------- */
int confronta(const void *a, const void *b)
{
   char *parola1=(char *)a;
   char *parola2=(char *)b;
     
   return strcmp(parola1, parola2);
}
void carica(PAROLA p[], int *n)
{  
   char buffer[MAX];
   while(fgets(buffer, MAX, f) != NULL)
   {    
      buffer[strlen(buffer)-1]=''; // il new line...
 
      strcpy(p[(*n)].parola, buffer);
      p[(*n)].conta=1;
      (*n)++;
   }
 
   qsort(p, (*n), sizeof(PAROLA), confronta);           // ordina
 
   int prima=0;                                         // elimina rpetizioni
   for(int i=1; i < (*n); i++)
   {
      if(strcmp(p[i].parola, p[prima].parola) == 0)
         p[prima].conta++;
      else
      {
         prima++;
         strcpy(p[prima].parola, p[i].parola);
      }
   }
   (*n)=prima+1;
}
void scarica()
{
   int i=0,
       j=0;
   while(i < n1 && j < n2)
   {
      int ris=strcmp(p1[i].parola, p2[j].parola);
      
      if(ris < 0)       
         i++;
      else if(ris == 0) 
      {
         fprintf(f, "[%s]: %d %dn", p1[i].parola, p1[i].conta, p2[i].conta);
         i++;
         j++;    
      }
      else              
         j++;
   }
}

si passa da un array a un albero binario di ricerca con due contatori in ogni nodo...

#include 
#include 
#include 
#define MAX 80

typedef struct nodo
{
   char parola[MAX];
   int  c1,
        c2;
   nodo *sx,
        *dx;
};
typedef nodo *pnodo;
/* -------------------------------------------------------------- */
FILE *f;
void carica(pnodo *, int),
     scarica(pnodo);
/* -------------------------------------------------------------- */
int main()
{
   pnodo radice=NULL;
 
   f=fopen("input1.txt", "r"); carica(&radice, 1); fclose(f);
   f=fopen("input2.txt", "r"); carica(&radice, 2); fclose(f);
   f=fopen("output.txt", "w"); scarica(radice);    fclose(f);
 
   return 0;
}
/* -------------------------------------------------------------- */
void aggParola(pnodo *pt, char *p, int c_12)
{
   if((*pt) == NULL)
   {
      (*pt)=(nodo *)malloc(sizeof(nodo));
       
      strcpy((*pt)->parola, p);
      if(c_12 == 1)      {
                            (*pt)->c1=1;
                            (*pt)->c2=0; 
                         }
      else if(c_12 == 2) {
                            (*pt)->c1=0;
                            (*pt)->c2=1; 
                         }       
      (*pt)->sx=NULL;
      (*pt)->dx=NULL;
   }
   else
   {
      int cmp=strcmp(p, (*pt)->parola);
       
      if(cmp < 0)
         aggParola(&((*pt)->sx), p, c_12);
      else if(cmp == 0)
      {
         if(c_12 == 1)      ((*pt)->c1)++;
         else if(c_12 == 2) ((*pt)->c2)++;       
      }
      else
         aggParola(&((*pt)->dx), p, c_12);       
   }
}
/* -------------------------------------------------------------- */
void carica(pnodo *pt, int a_b)
{
   char buffer[MAX];
   while(fgets(buffer, MAX, f) != NULL)
   {
      buffer[strlen(buffer)-1]=''; // new line...
      aggParola(pt, buffer, a_b);
   }
   fclose(f);
}
void scarica(pnodo pt)               // visita inorder...
{
   if(pt != NULL)
   {
      scarica(pt->sx);
      if(pt->c1 != 0 && pt->c2 != 0)
         fprintf(f, "[%s]: %d, %dn", pt->parola, pt->c1, pt->c2);
      scarica(pt->dx);       
   }
}