Newsgroup: it.comp.lang.c
Titolo: matrici indicizzate

Ciao a tutti,
ho il seguente problema: devo memorizzare in una matrice m x n dei
valori interi.
Ho inoltre bisogno di dare un nome ad ogni riga e ogni colonna della
matrice.
Ora, vorrei definire una struttura dati che, dato un nome di colonna, mi
restituisca "velocemente" l'indice di colonna corrispondente, e lo
stesso con le righe.
Il problema nasce quando devo eseguire l'operazione contraria: dato un
indice, devo risalire al nome corrispondente.
La maniera piu' semplice di avere un accesso immediato e' quella di
realizzare due mappe (dizionari), una con key=indice e informazione=nome
e l'altra con key=nome e informazione=indice.
Qualcuno di voi conosce altri tipi di trutture che possano fare al mio
caso?
--
____________________________________________
           Gianfranco Ciaschetti
    UNIVERSITA' DEGLI STUDI DI L'AQUILA
Dipartimento di Matematica Pura e Applicata
via Vetoio, 67010 Coppito (L'Aquila) ITALIA
          tel: (+39) 862 433 736
          fax: (+39) 862 433 180
         e-mail:  
ci...@univaq.it
____________________________________________

caso?
In realta' non esiste un metodo realmente "immediato" per ottenere da
una stringa il corrispondente indice, sia perche' le stringhe non
possono essere usate come indici degli array, sia perche' un eventuale
calcolo sulla stringa, per ottenerne un valore numerico (la classica
operazione di hashing) richiede tempo.
Per la trasformazione da stringhe a indici io utilizzerei per
l'appunto un meccanismo di hashing, come nel programma che ti riporto
di seguito e che scrissi e postai all'epoca su questo stesso ng.
Prima di postarlo, ho aggiunto due routine :
void hash_list_write ( hash_list_item_ptr p )
void hash_table_write ( hash_list_item_ptr ht [] )
che servono a visualizzare la struttura della tabella hash, piu' che
altro per facilitare il debug.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _hash_list_item { char * s ;
                                 struct _hash_list_item * next ;
                               } hash_list_item ;
typedef hash_list_item *  hash_list_item_ptr ;
/* definizione di una lista concatenata come elemento della tabella
hash */
#define HASH_SIZE  256
/* la dimensione della tabella hash e' di massimo 256 liste
concatenate */
/* per cui l'indice e' compreso tra 0 e 255 */
unsigned  hash_func ( const char * key )
/* funzione che ritorna l'indice corrispondente alla stringa passata.
*/
/* Il metodo utilizzato non e' certo dei migliori */
{
          unsigned r = 0 ;
          while ( *key ) r += *key++;
          r %= HASH_SIZE ;
          return ( r ) ;
}
void  hash_list_insert ( hash_list_item_ptr * p , const char * s )
/* inserisce una nuova stringa nella lista corrispondente */
{
      if (*p == NULL)
      {
         *p = malloc ( sizeof **p ) ;
         (*p)->next = NULL ;
         (*p)->s = malloc ( strlen ( s ) + 1 ) ;
         strcpy ( (*p)->s, s ) ;
      }
      else hash_list_insert ( &(*p)->next, s ) ;
}
void  hash_table_insert ( hash_list_item_ptr ht[], const char * s )
/* calcola l'indice della lista in cui inserire la nuova stringa */
/* e provvede a chiamare la funzione di inserimento */
{
      unsigned index ;
      index = hash_func ( s ) ;
      hash_list_insert ( & ht[ index ], s ) ;
}
int   hash_table_find ( hash_list_item_ptr ht[], const char * s )
/* cerca la stringa specificata nella tabella hash */
{
      hash_list_item_ptr  cursor ;
      cursor = ht [  hash_func ( s ) ] ;
      while ( cursor )
      {
            if ( !strcmp( cursor->s, s ) ) return 1 ;
            cursor = cursor->next ;
      }
      return 0 ;
}
void hash_list_write ( hash_list_item_ptr p )
/* scrive una lista singola */
{
     if ( p != NULL )
     {
        printf ( "%s -> ", p->s ) ;
        hash_list_write ( p->next ) ;
     }
     else printf ("(NULL)\n") ;
}
void hash_table_write ( hash_list_item_ptr ht [] )
/* scrive le sole liste presenti nella tabella hash */
{
     unsigned i ;
     for ( i = 0 ; i < HASH_SIZE ; i++ )
         if ( ht [i] != NULL )
         {
            printf ( "%3d) ", i ) ;
            hash_list_write ( ht [i] ) ;
         }
}
int main()
{
    hash_list_item_ptr  ht [ HASH_SIZE ] ;
    unsigned idx ;
    for ( idx = 0 ; idx < HASH_SIZE ; idx++ )
        ht [ idx ] = NULL ;
    hash_table_insert ( ht, "armadio" ) ;
    hash_table_insert ( ht, "computer" ) ;
    hash_table_insert ( ht, "libro" ) ;
    hash_table_insert ( ht, "dinosauro" ) ;
    hash_table_insert ( ht, "lavagna" ) ;
    hash_table_insert ( ht, "valanga" ) ;
    printf ( "\n" ) ;
    hash_table_write ( ht ) ;
    return 0 ;
}

 wrote:
[ snip ]
AL>void hash_list_write ( hash_list_item_ptr p )
AL>/* scrive una lista singola */
AL>{
AL>     if ( p != NULL )
AL>     {
AL>        printf ( "%s -> ", p->s ) ;
AL>        hash_list_write ( p->next ) ;
AL>     }
AL>     else printf ("(NULL)\n") ;
AL>}
C'e' qualche ragione per usare una funzione ricorsiva ?
Perche' non qualcosa di piu' semplice, tipo
void hash_list_write (hash_list_item_ptr p)
{
        while (p) {
                printf ("%s -> ", p->s);
                p = p->next;
        }
        printf ("(NULL)\n");
}
?
Ciao ciao,
Andrea
-- 
"...Unix, MS-DOS, and Windows NT (also known as the Good, the Bad, and 
 the Ugly)."
(by Matt Welsh)

Perche' non qualcosa di piu' semplice, tipo
"Piu' semplice" da che punto di vista ?

>Perche' non qualcosa di piu' semplice, tipo
AL>"Piu' semplice" da che punto di vista ?
Ahem...sarai d'accordo che usare la ricorsione e' piu' 
complicato che limitarsi a scorrere la lista, o no ?


complicato che limitarsi a scorrere la lista, o no ?
Non vedo tutta questa difficolta' per il programmatore.
Tra l'altro la ricorsione si adatta bene a scorrere la lista, che e'
una struttura dati definibile in modo ricorsivo, ovvero come : 
"una lista L e' un puntatore a una lista L o nullo".

>complicato che limitarsi a scorrere la lista, o no ?
AL>Non vedo tutta questa difficolta' per il programmatore.
Non ho detto che e' una cosa complicatissima: ho detto che e'
piu' complicata del banale scorrere la lista.
O tu pensi che la soluzione ricorsiva sia piu' semplice ?


O tu pensi che la soluzione ricorsiva sia piu' semplice ?
Fondamentalmente e' la stessa cosa.
Ripeto che non so definire l'una piu' semplice dell'altra.
Se parli di maggiore efficienza di un ciclo rispetto alla ricorsione
siamo d'accordo, ma se parli di complessita' a livello progettuale,
sinceramente per me e' piu' semplice pensare in modo ricorsivo che in
modo sequenziale.
Tra l'altro, io applico alle liste quello che applico regolarmente
agli alberi binari, per il semplice motivo che queste strutture dati
sono definibili molto semplicemente se in maniera ricorsiva.

 O tu pensi che la soluzione ricorsiva sia piu' semplice ?
Anch'io penso che in generale la soluzione iterativa sia più semplice ed
efficiente. Ma, mentre nel caso della visita di una lista è molto facile
applicarla, non è così banale se si volesse visitare un albero.
EMG

 wrote:
[ snip ]
EMG>Anch'io penso che in generale la soluzione iterativa sia più semplice ed
EMG>efficiente. Ma, mentre nel caso della visita di una lista è molto facile
EMG>applicarla, non è così banale se si volesse visitare un albero.
Si, ma io mi riferivo al caso specifico.
Volendo restare alle liste, anche la visita in ordine inverso non ha una
semplice controparte iterativa.


semplice controparte iterativa.
Esatto, questo e' un ottimo motivo per non adottare, in questo caso
specifico, una routine iterativa, ma una ricorsiva.