Newsgroup: it.comp.lang.c
Titolo: AIUTO DISPERATO !!!!

Ho un probelma con il seguente progetto . Non riesco a trovare una struttura
dati adatta per implementare il seguente progetto . All'inizio avevo pensato
ad una struttutra dati del seguente tipo : una lista di puntatori in cui il
campo info punta ad una albero Trie che contiene una classe di sinomini ma
tale schema è stato scartato dal prof. La struttura dati ideale , secondo il
prof. , dovrebbe essere un unico albero trie che racchiude tutte le parole
del dizionario dei sinonimi ed al massimo due puntatori ..........
Qui in pratica si tratta di individuare per esempio in tre insiemi distinti
di parole, la parola in comune e quindi elencare di conseguenza tutte le
altre .
Ogni possibile aiuto rappresenta un enorme passo in avanti !
Ti ringrazio anticipatamente e spero vivamente di trovare un aiuto valido
per la risoluzione di tale progetto .
Grazie mille !
Attendo notizie ,
Ciao
Matrix
Progetto di Algoritmi e Strutture Dati
Traccia :
Sia dato un file di nome Sinonimi.txt contenente insiemi di sequenze di
parole . Ogni insieme è delimitato da un carattere di fine linea ed è
costituito da parole che sono sinonime tra loro ; le parole di ogni insieme
sono separate da uno o più spazi .
Scrivere un programma in C che costruisca un vocabolario dei sinonimi a
partire dal file Sinonimi.txt e che consenta l'interrograzione del
vocabolario viusalizzando tutti i sinonimi di una data parola fornita
dall'utente .
Se la parola di input appartiene a più insiemi , la visualizzazione dei
sinonimi appartenenti a un insieme differente ( es. gli insiemi possono
essere separati da una linea , oppure da una scritta del tipo : Accezione
N. ) . Le parole di un dato insieme possono essere visualizzate sensa una
ordine particolare .
Ai fini dell'implementazione si suggerisce agli studenti l'impiego congiunto
di liste puntate e strutture ad albero Trie .
Le scelte implementative sono tuttavia da considerarsi libere , a patto
ovviamente che si fornisca adeguate giustificazioni delle scelte operate (
in termini di tempo di esecuzione , memoria ecc. )
Di seguito sono riportati alcuni esempi del funzionamento atteso del
programma . Gli esempi sono da considerarsi come possibili istanze e sono
riportati solo ai fini di chiarificazione della presente proposta di
progetto . Il programma finale dovrà ricevere in ingresso un qualunque file
che abbia struttura identica a quella riportata in seguito .
Esempio :
Sinonimi.txt
dirigere ordinare richiedere disporre
ordinare elencare
rassettare disporre ordinare
ES.1
INPUT : elencare
OUTPUT :
ordinare
ES.2
INPUT : ordinare
OUTPUT :
dirigere richiedere disporre
elencare
rassettare disporre
ES.3
INPUT : disporre
OUTPUT :
dirigere ordinare richiedere
rassettare ordinare
ES.4
INPUT : parlare
OUTPUT :
** parola non presente nel vocabolario **

Dovrebbe andare bene, testalo.
<CODE>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct tagNodoLista {
               int Indice;
               struct tagNodoLista *prox;
        } NodoLista, *PNodoLista;
typedef struct tagNodoListaParole {
               char *Stringa;
               struct tagNodoListaParole *prox;
        } NodoListaParole, *PNodoListaParole;
typedef struct tagNodoAlbero {
               char *Stringa;
               PNodoLista TestaListaIndici;
               struct tagNodoAlbero *sx, *dx;
        } NodoAlbero, *PNodoAlbero;
static PNodoListaParole VettoreSinonimi[100] = {0};
void InserisciInAlbero(PNodoAlbero *PTesta, 
                       const char *Stringa)
{
     if (!*PTesta)
     {
        *PTesta = malloc(sizeof **PTesta);
        (*PTesta)->Stringa = malloc(strlen(Stringa)+1);
        strcpy((*PTesta)->Stringa, Stringa);
        (*PTesta)->sx = (*PTesta)->dx = 0;
        (*PTesta)->TestaListaIndici = 0;
     }
     else
     {
        int cmp = strcmp(Stringa, (*PTesta)->Stringa);
        if (cmp < 0)
          InserisciInAlbero(&(*PTesta)->sx, Stringa);
        else
        if (cmp > 0)
          InserisciInAlbero(&(*PTesta)->dx, Stringa);
     }
}
void InserisciInLista(PNodoLista *PTesta, int Indice)
{
     if (!*PTesta)
     {
        *PTesta = malloc(sizeof **PTesta);
        (*PTesta)->Indice = Indice;
        (*PTesta)->prox = 0;
     }
     else
       InserisciInLista(&(*PTesta)->prox, Indice);
}
void InserisciInListaParole(PNodoListaParole *PTesta,
                            const char *Stringa)
{
     if (!*PTesta)
     {
        *PTesta = malloc(sizeof **PTesta);
        (*PTesta)->Stringa = malloc(strlen(Stringa)+1);
        strcpy((*PTesta)->Stringa, Stringa);
        (*PTesta)->prox = 0;
     }
     else
       InserisciInListaParole(&(*PTesta)->prox, Stringa);
}
void AssegnaIndice(PNodoAlbero *PTesta,
                   const char *Stringa,
                   int Indice)
{
     int cmp = strcmp(Stringa, (*PTesta)->Stringa);
     if (cmp == 0)
     {
        InserisciInLista(&(*PTesta)->TestaListaIndici,
                         Indice);
     }
     else
     if (cmp < 0)
        AssegnaIndice(&(*PTesta)->sx, Stringa, Indice);
     else
        AssegnaIndice(&(*PTesta)->dx, Stringa, Indice);
}
void ScriviLista(PNodoLista P)
{
     if (P)
     {
        printf("%3d", P->Indice);
        ScriviLista(P->prox);
     }
     else
       printf("\n");
}
void ScriviNodiAlbero(PNodoAlbero P)
{
     if (P)
     {
        ScriviNodiAlbero(P->sx);
        printf("%s\n", P->Stringa);
        ScriviLista(P->TestaListaIndici);
        ScriviNodiAlbero(P->dx);
     }
}
void ScriviAlbero(PNodoAlbero P)
{
     ScriviNodiAlbero(P);
     printf("\n");
}
void ScriviListaSinonimi(PNodoListaParole P, 
                         const char *Stringa)
{
     for (; P; P = P->prox)
     {
         if (strcmp(P->Stringa, Stringa))
         {
            printf("%s; ", P->Stringa);
         }
     }
     printf("\n");
}
void OrdinaSinonimi(PNodoAlbero P)
{
     if (P)
     {
        PNodoLista L;
        for (L = P->TestaListaIndici;
             L;
             L = L->prox)
        {
InserisciInListaParole(&VettoreSinonimi[L->Indice],
                                   P->Stringa);
        }
        OrdinaSinonimi(P->sx);
        OrdinaSinonimi(P->dx);
     }
}
void TrovaSinonimi(PNodoAlbero P, const char *Stringa)
{
    if (P)
    {
       int cmp = strcmp(Stringa, P->Stringa);
       if (cmp == 0)
       {
          PNodoLista L;
          printf("Sinonimi trovati:\n");
          for (L = P->TestaListaIndici;
               L;
               L = L->prox)
          {
ScriviListaSinonimi(VettoreSinonimi[L->Indice],
                                  P->Stringa);
          }
       }
       else
       if (cmp < 0)
         TrovaSinonimi(P->sx, Stringa);
       else
         TrovaSinonimi(P->dx, Stringa);
    }
    else
      printf("*** parola non presente ***\n");
}
int main()
{
    PNodoAlbero Radice = 0;
    char Parola[64];
    InserisciInAlbero(&Radice, "dirigere");
    InserisciInAlbero(&Radice, "ordinare");
    InserisciInAlbero(&Radice, "richiedere");
    InserisciInAlbero(&Radice, "disporre");
    InserisciInAlbero(&Radice, "ordinare");
    InserisciInAlbero(&Radice, "elencare");
    InserisciInAlbero(&Radice, "rassettare");
    InserisciInAlbero(&Radice, "disporre");
    InserisciInAlbero(&Radice, "ordinare");
    // gli indici assegnati sono gli indici di riga
    // in cui compare la parola
    AssegnaIndice(&Radice, "dirigere", 0);
    AssegnaIndice(&Radice, "ordinare", 0);
    AssegnaIndice(&Radice, "richiedere", 0);
    AssegnaIndice(&Radice, "disporre", 0);
    AssegnaIndice(&Radice, "ordinare", 1);
    AssegnaIndice(&Radice, "elencare", 1);
    AssegnaIndice(&Radice, "rassettare", 2);
    AssegnaIndice(&Radice, "disporre", 2);
    AssegnaIndice(&Radice, "ordinare", 2);
    OrdinaSinonimi(Radice);
    do
    {
       printf("inserisci una parola (FINE per uscire): ");
       gets(Parola);
       if (!strcmp(Parola, "FINE")) break;
       TrovaSinonimi(Radice, Parola);
       while (getchar() != '\n');
    } while (1);
    return 0;
}
</CODE>
-- 
Andrea Laforgia (
walkie...@libero.it
)
"Usenet is a strange place" [Dennis Ritchie]