Newsgroup: it.comp.lang.c
Titolo: Implementazione di un dizionario

Salve a tutti!
Dovrei implementare un programma per la gestione di un dizionario (ossia un
insieme di parole) sul quale poter operare tramite le seguenti funzioni:
- Dizionario(inputfile), costruisce un dizionario a partire dalle parole
contenute nel file inputfile (un file di testo in cui le parole compaiono
separate da uno o più spazi o newline). Se inputfile non corrisponde ad un
nome di file esistente, viene creato un dizionario vuoto.
- Mostra(), mostra a video il dizionario corrente.
- Inserisci(x), inserisce nel dizionario la parola x (sempre che non sia già
presente, nel qual caso non fa nulla)
- Elimina(x), cancella dal dizionario la parola x (se esiste)
- Prefisso(m), restituisce l'insieme di parole del vocabolario che ammettono
m come prefisso (sia ad esempio m="pre", allora restituisce "preferire,
prefisso, prestare...")
- Lunghezza(k), restituisce l'insieme di parole di lunghezza k.
Cosa vorrei sapere? Qualsiasi informazione è gradita: come lo
implementereste (liste o alberi o cos'altro), se esistono sorgenti simili a
questi in rete, come implementereste dizionario e procedure, qualche
esempio...

Mi sa tanto di progetto di Algoritmi e Strutture dati
cmq per fare una cosa del genere ti serve una sola struttura "una albero
TRIE"
La struttura è la seguente
struct nodo
   {
       int v;
       struct nodo * percorso[26];
   }
typedef    struct nodo *trie;
come si usa :
Ogni nodo dell'albero è formato da un campo v (booleano),che assume il
valore VERO se la parola è presente FALSO se non è presente, e da un arry di
26 elementi di tipo puntatore a nodo
partendo dalla posizione 0 fino a 25 fai corrispondere tutte le lettere
dell'alfabato (inglese)
Inizialmente poni v=0 (falso) e tutti i puntatori a NULL
trie crea_nodo()
  {
      trie n;
      n=(trie) malloc(sizeof(struct nodo));
      n->v=0
     for (i=0;i<26;i++)
        n->percorso[i]=NULL;
    return(n);
  }
Ad ogni casella dell'array corrisponde una lettera dell'alfabeto (inglese)
percorso[0] è A, percorso[1] è B e così via fino a 25.
Se devi inserire una parola es.: ALBERO
prendi il codice ascii della prima lettera e gli sottrai 65 in questo
i=parola[0]-65;
Controlli se percorso[i] è NULL in questo caso  crei un nuovo nodo e associ
il puntatore al percorso[0] fai questo per tutti i caratteri si parola
trie inserisci (trie t, char *s)
   {
       trie nuovo=t;
       int i;
       for (i=0; i<strlen(s); i++)
          {
              if  (nuovo->percorso[*s[i]-65]==NULL)
                 nuovo-> percorso[*s[i]-65]=crea_nodo();
             nuovo=nuovo->percorso[*s[i]-65];
           }
        nuovo->v=1;
        return(t);
   }
int trova(trie t, char *s)
 {
       trie appoggio=t;
       int i=0;
       while (i<strlen(s) && (appoggio->percorso[*s[i]-65] !=NULL)
          {
               appoggio=appoggio->percorso[*s[i]-65];
               i++;
           }
        if ((i==strlen(s)) && (appoggio->v==1)
          return(1);
        else
           return(0);
   }
Queste sono le due funzioni fondamentali, da qui puoi implementare tutto il
resto ad esempio la ricerda di tutte le
stringe con un determinato prefisso, prima controlli esistenza del prefisso
nel tuo dizionario se il prefisso esiste controlli tutte le possibili
derivazioni e quando trovi  "v=1" allora hai trovato una nuova stringa da
stampare
Ps. per la stampa ti conviene utilizzare una variabile stringa di appoggio
che costruisci man mano che attraversi l'albero
             s[i]=j+65;
dove j è il puntatore nell'array percorso.
In un dizionario solitamente non si cancellano le parole cmq ricerca la
parola magari modificando la funzione di inserimento per farti ritornale il
puntatore all'ultimo nodo quello che contiene v=1 e poni v=0 così la parola
è cancellata senza dover cancellare fisicamente tutti i nodi e quindi
riorganizzare l'albero.
Se hai altre domande postale
Ciao Re Di Cuori
Il trucco è semplice (A = 65   B=66 ) se "pa" è la variabile stringa che
contiene la parola
"Alessandro "oVeRRiDe"" <oVeRRiDe@i.i> ha scritto nel messaggio
news:kmp06.152690$hk4.5...@news.infostrada.it...


Bravo è proprio un progetto di algoritmi e strutture dati! ;-) Non il mio,
ma quello per gli studenti di un altro anno... Ti ringrazio per l'aiuto, ora
mi metto al lavoro! Ciao!
"ReDiCuori" <redicu...@NOSPAMlibero.it> ha scritto nel messaggio
news:o1v06.156628$hk4.5...@news.infostrada.it...


 riorganizzare l'albero.
è vero che le parole non si cancellano ma se tu avessi la necessità di
rimuovere
dalla memoria l'intera struttura dovrai scriverti l'apposita routine!
E' una mezza rottura scriverla questo è vero.
ciao Marco