Newsgroup: it.comp.lang.c
Titolo: Lista di adiacenza :Help!

Cercando  di risolvere vari esercizi sul linguaggio c , mi sono imbattuto in
una soluzione che mi da qualche perplessità.Si tratta di un dubbio forse
stupido .
La linea di codice :
adj=(nodo*)malloc(n*sizeof(nodo));
per come la indendo io , alloca lo spazio corrispondente a n volte quello
necessario per contenere la struttura nodo, ritornando il puntatore alla
memoria allocata "castandolo" alla struttura nodo e attribuendolo a adj che
naturalmente è un puntatore a nodo.
Quindi il tutto dovrebbe potersi immaginare come un array i cui elementi
sono strutture nodo. Giusto?
Per accedere agli elementi dell' array posso usare gli indici o i puntatori
.
Se calcolo *(adj+5) dovrei accedere alla struttura nodo;poi attraverso l'
operatore "." posso accedere ai campi di nodo.
Se "buffer" è una array di 3 interi e "file"  un testo dove si trovano n
coppie di interi separati da spazio, che senso ha la porzione di codice :
for(i=0;i<n;i++)
{
fread(buffer,sizeof(int),3,file);
t=(nodo*)malloc(sizeof(*t);
t->vertice=buffer[2];
t->next =(adj+buffer[0]);
*(adj+buffer[0])=*t;
}
Non capisco le ultime 2 linee : questo codice dovrebbe servire per
implementare una lista di adiacenza, ma io avrei allocato con malloc lo
spazio per n  puntatori a nodo, li  avrei fatti puntare a Null e poi man
mano allocando lo spazio per i singoli nodi li avrei aggiunti alla lista di
adiacenza inserendoli di volta in volta nei posti opportuni.
Che ne pensate?

Che ne pensate?
Puo' servire per allocare subito tutto lo spazio che ti serve, ma poi
usarla come una lista (quindi cambiare l'ordine logico dei vari
elementi in tempo costante anziche' il tempo lineare richiesto per
cambiare la posizione di 1 elemento su 1 array).
Mi pare voglia simulare una lista usando 1 array di elementi. Il fatto
che tu possa accedere ai singoli elementi semplicemente con
"array[posizione]" e' secondario in questo caso :)
In pratica allochi subito N nodi anziche' N volte 1 nodo (e in linea
di massima risparmiando tempo, pero' devi sapere a priori quandi
allocarne).
La lista e' un concetto astratto, la posizione dei nodi su disco non
ti deve riguardare. Allocare N nodi anziche' N volte 1 nodo per la
lista non cambia nulla :)
Spero di aver capito il tuo dubbio, se no fai un replay e cerchero di
spiegare meglio :)
Mox.

 Mox.

Inizio a spiegarti in modo piu' chiaro il msg precedente.
Partiamo da queste informazioni:
<CODE target="header">
typedef struct _nodo nodo;
typedef struct _nodo * lista;
struct _nodo {
    char array[10];
    int numero;
    stuct nodo * next;
};
</CODE>
Diciamo che tu (in porzioni di codice che ora ometto) devi allocare 10
volte la struttura nodo perche' ti servono 10 nodi della lista.
<CODE>
lista L;
while(condizione) {
    lista tmp;
    /* ... */
    tmp = malloc(sizeof(nodo))
    assert(tmp);
    tmp->next = L;
    L = tmp;
}
</CODE>
Questo e' il modo classico per allocare la lista.
Ora tu puoi benissimo fare (se sai prima che ti servono 10 elementi
per es):
<CODE>
lista L;
nodo * array_nodi = malloc(10*sizeof(nodo));
assert(array_nodi);
L = array_nodi;
for (i=0; i<9; i++)
    array_nodi[i]->next = &(array_nodi[i+1]);
array_nodi[9]->next = NULL;
</CODE>
Tu hai allocato 1 array di nodi (non di puntatori a nodo). Indirizzi
tutti i campi next al successivo (questa e' solo 1 possibilita', nota
bene), l'ultimo campo next a NULL e fai puntare L al primo elemento.
Questo ti ha fatto fare 1 sola malloc anziche' N e puoi continuare ad
accedere agli elementi come fossero in una lista, seguendo i campi
next.
A questo punto ti chiederai ma a cosa puo' servirmi tutto questo?
Partiamo da:
[0|1|2|3|4|5|6|7|8|9]
E vogliamo ottenere
[0|1|3|4|5|6|7|8|9|2]
... ovvero spostare 2 in coda.
Con un array (che hai allocato per fare meno malloc oppure perche'
all'inizio del programma sapevi che ti bastavano N elementi e quindi
l'hai dichiarato in modo statico) per fare questo dovresti
implementare un algoritmo che in tempo lineare modifica cosi' l'array.
Con le liste di basta cambiare 3 puntatori (il next dell'1, il next
del 9 e il next del 2) e hai fatto, giusto?
In questa implementazione ti scordi di aver allocato 1 array (non dei
puntatori a nodo come pensavi tu, nota) e usi i nodi come componenti
di una lista.
Ci sono vari casi in cui tu preferisci allocare subito tutto lo spazio
che serve e poi usarlo come una lista perche' costa meno la gestione
se devi cambiare la posizione degli elementi.
Per quanto riguarda il codice che hai postato, non seguo bene quello
che cerca di fare, ma mi pare che voglia solo spiegarti come si
possono usare gli operatori: *  []  .  ->
in uno stesso contesto.
Es:
int array[10];
int pt = array;
array[2] == *(array+2)
pt+3 == array+3
*(pt+4) == array[4]
*(pt++) == array[1]
Sei convinto che valgano queste equivalenze? Questo era uno dei primi
esercizi fatti in laboratorio sul C, serve per dimostrarti le
differenze e le parti in comune tra stringa (o puntatore) e array.
Altra cosa, che ho gia' accennato sopra:
tipo * puntatore = malloc (N * sizeof(tipo))
assegna a un puntatore una zona di memoria continua di n posizioni e
ogni posizione e' abbastanza grande da contenere 1 oggetto di tipo
"tipo" ... equivalente a dire che assegna l'indirizzo di un array di N
oggetti di tipo "tipo".
Il cast che mettevi tu NON ci deve essere anche se non e' un errore e
comunuque il cast fatto cosi':
tipo * puntatore = (tipo*) malloc(N * sizeof(tipo))
... non vuol dire N puntatori, ma sempre e solo lo spazio per N
oggetti che poi casto (lo spazio, non i singoli oggetti) a
puntatore... cosa che serviva solo prima dello standard ISO.
Sul K&R e' ancora indicato cosi' perche' il libro e' uscito prima
dello standard, come viene espressamente detto nel libro.
Fortunatamente la lista delle correzioni da apportare al testo e'
molto breve e si trova in rete :)
Mox.

Le tue informazioni mi sono state molto utili per capire il casting , e di
questo di sono estremamente debitore.
Tuttavia , nonostante la mia buona volontà non riesco affatto a capire come
lavori il codice da me riportato.
Nell'ipotesi che tu mi voglia ancora aiutare ti allego la parte completa di
codice a me incomprensibile .
Il file "nomefile "  richiamato all' interno di  "Caricamento_lista_stanze"
è così fatto:
5 2 1 3 2 5 5 7 4 3 1 4
//definizioni di variabili
typedef struct node{int vertice;node* next;}nodo;
nodo *t,*z,*s;
nodo *adj;//puntatore alla lista di adiacenza rappresentante il grafo
int numerostanze,stanzadipartenza;
int *val;//vettore ad una lista delle stanze gia' visitate
nodo *percorso;//lista delle stanze visitate in un ciclo chiuso
//--------------------------------------------------------------------------
---
//la funzione seguente carica da file il numero e la disposizione delle
stanze
//ed inoltre inizializza e riempie la lista di adiacenza che servira' per
//rappresentare il grafo orientato associato alle aperture fra le stanze
void Caricamento_lista_stanze(char *nomefile)
{
int buffer[3];
FILE *fileambienti;
z=(nodo*)malloc(sizeof*z);
z->next=z;
percorso=z;
if((fileambienti=fopen(nomefile,"r"))!=NULL)
 {
 int i;
 fread(buffer,sizeof(int),2,fileambienti);
 if(!ferror(fileambienti))
  {
  numerostanze=buffer[0];
  stanzadipartenza=buffer[1];
  adj=(nodo*)malloc(numerostanze*sizeof(nodo));
  for(i=0;i<numerostanze;i++)
   *(adj+i)=*z;                    ?????????????????????????
  for(i=1;i<=numerostanze;i++)
   {
   fread(buffer,sizeof(int),3,fileambienti);
   if(!ferror(fileambienti))
    {
    t=(nodo*)malloc(sizeof*t);
    t->vertice=buffer[2];
    t->next=(adj+buffer[0]);    ??????????????????????????
    *(adj+buffer[0])=*t;        ?????????????????????
    }
   else Errore_nel_file();
   }
  }
 else Errore_nel_file();
 }
else Errore_nel_file();
}
I passaggi che non capisco li ho segnati con ????????????????????
E poi cosa significa  sizeof*t ?

E poi cosa significa  sizeof*t ?
sizeof(*t) sifnifica l'occupazione di memoria dell'oggetto puntato da
t. Se t era un struct nodo * allora *t e' una struct nodo :)
Ho gia' visto usare il sizeof() senza parentesi e parrebbe funzionare,
ma non so se e' un puro caso (come le fflush() su stdin) o un refuso
preansi).
Scusa, sara' colpa delle macchine di Turing che ho studiato per tutto
il pomeriggio, ma non riesco a seguire il codice.
Mi pare voglia rappresentare un grafo attraverso le liste di
adiacenza, quindi una cosa del tipo:
+---+                      ;
| 0 | --> 1 --> 3 --> /    ; significa che da 0 arrivi a 1 e a 3
+---+                      ; 
| 1 | --> 2 ---> 3 --> /   ; significa che da 1 arrivi a 2 e a 3
+---+                      ;
| 2 | --> 3 --> /          ; significa che da 2 arrivi a 3
+---+                      ;
| 3 | --> 2 --> 4 --> /    ; significa che da 3 arrivi a 2 e a 4
+---+                      ;
| 4 | --> /                ; significa che da 4 non arrivi da nessuna parte
+---+                      ;
Non capisco esattamente cosa voglia fare, per questo in genere si
mettono i commenti nel codice o un commento dettagliato sulle funzioni
:)
Se tra qualche giorno riesco a estrarre le intenzioni dell'autore
posto qualcosa, se no spero qualcuno abbia 1 un'intuizione al posto
mio.
La cosa piu' difficile dal codice e' estrarre le intenzioni del
programmatore. Ogni trutto, ogni scorciatoia del C mediamente
diminuisce la comprensione e aumenta la potenza. Piu' ne metti piu'
commenti devi mettere per compensare in genere.
Se sai darmi informazioni esatte su cosa devi ottenere posta e vediamo
di capirci qualcosa :)
Mox.

 ha scritto nel messaggio
news:95XlO7z4rOkLDZ...@4ax.com...
