Liste in C

[-Jeko-]

Avrei bisogno di conoscere qualche buon algoritmo per utilizzare velocemente le liste in C.

Per esempio, se ho 30 strutture di queste:
struct pezzo {
unsigned int id;
struct pezzo *prev, *next;
};

struct pezzo *pezzi[30];
struct pezzo *primo_pezzo;

come posso fare a trovare velocemente un "pezzo" con id 5? Devo necessariamente cercare in tutti i "pezzi" a partire da "primo pezzo"? Oppure c'è qualche metodo più veloce?

[nico402]

Avrei bisogno di conoscere qualche buon algoritmo per utilizzare velocemente le liste in C.

Per esempio, se ho 30 strutture di queste:
struct pezzo {
unsigned int id;
struct pezzo *prev, *next;
};

struct pezzo *pezzi[30];
struct pezzo *primo_pezzo;

come posso fare a trovare velocemente un "pezzo" con id 5? Devo necessariamente cercare in tutti i "pezzi" a partire da "primo pezzo"? Oppure c'è qualche metodo più veloce?

la lista solitamente ha un solo puntatore che punta all'elemento successivo e basta..

cmq un for tipo così?

struct pezzo* elem;
for(elem=prime_elem;elem->next!=null;elem=elem->next){
               if(elem->dato==5) 
                          printf(l'ho trovato!!!);
}

se vuoi vedere a che punto della lista è basta che fai un i che si incrementa... avendo fatto poco o niente con le liste non assicuro niente però...

[The Dix]

come posso fare a trovare velocemente un "pezzo" con id 5? Devo necessariamente cercare in tutti i "pezzi" a partire da "primo pezzo"? Oppure c'è qualche metodo più veloce?

di solito per principio di lista si fa così se è una semplice lista binaria
puoi ordinarla ma dovrai sempre partire dal primo pezzo
ma dipende anche quello che vuoi fare non necessariamente devi guardare tutti i pezzi

[Lex]

Con una lista non c'è alternativa alla ricerca lineare. Se per te è fondamentale avere buone prestazioni durante le ricerche ti consiglio di usare strutture dati diverse, come gli alberi, tenendo però conto che pagherai la maggioe efficienza della ricerca con algoritmi di inserimento e cancellazione più complessi.

[morgoth90]

a proposito di questo post sarei interessato a strutture ad "albero" qualcuno può per caso indirizzarmi a qualche esempio?

[java is forever]

a proposito di questo post sarei interessato a strutture ad "albero" qualcuno può per caso indirizzarmi a qualche esempio?

Ipotizziamo di voler creare un programmino che conta le ricorrenze di ogni carattere in un testo. Questa sara' la struttura:

struct NODO {
  char character;
  int   n; 

  struct NODO *dx;
  struct NODO *sx;
};

Per costruire questo albero si fa cosi' (pseudocodice):

0. ALBERO VUOTO

1. LEGGO IL CARATTERE E LO METTO IN ROOT (INCREMENTANDO IL CONTATORE)
2. LEGGO IL CARATTERE i+1

2.1 SE VIENE PRIMA DEL CARATTERE DEL NODO VADO A SINISTRA
2.2 ALTRIMENTI VADO A DESTRA
2.3 CONTINUO COSI' FINO A  CHE NON TROVO IL CARATTERE (IN QUESTO CASO INCREMENTO IL CONTATORE) OPPURE FINO A CHE NON ARRIVO AD UN NODO TERMINALE (E LI CREO UN NUOVO NODO COL NUOVO CARATTERE)

3. TORNO A 2

In questo modo hai anche memorizzato i caratteri in ordine

spero di essermi spiegato..

[morgoth90]

si più o meno ho capito

[The Dix]

Ipotizziamo di voler creare un programmino che conta le ricorrenze di ogni carattere in un testo. Questa sara' la struttura:

struct NODO {
  char character;
  int   n; 

  struct NODO *dx;
  struct NODO *sx;
};

Per costruire questo albero si fa cosi' (pseudocodice):

0. ALBERO VUOTO

1. LEGGO IL CARATTERE E LO METTO IN ROOT (INCREMENTANDO IL CONTATORE)
2. LEGGO IL CARATTERE i+1

2.1 SE VIENE PRIMA DEL CARATTERE DEL NODO VADO A SINISTRA
2.2 ALTRIMENTI VADO A DESTRA
2.3 CONTINUO COSI' FINO A  CHE NON TROVO IL CARATTERE (IN QUESTO CASO INCREMENTO IL CONTATORE) OPPURE FINO A CHE NON ARRIVO AD UN NODO TERMINALE (E LI CREO UN NUOVO NODO COL NUOVO CARATTERE)

3. TORNO A 2

In questo modo hai anche memorizzato i caratteri in ordine

spero di essermi spiegato..

quella è la struttura ordinata per una visita binaria o simmetrica ci sono altri due metodi di visita di un albero
ma cmq quello è il metodo + usato

[java is forever]

quella è la struttura ordinata per una visita binaria o simmetrica ci sono altri due metodi di visita di un albero
ma cmq quello è il metodo + usato

Mi sembra il modo piu' facile di fare un albero

[-Jeko-]

Con una lista non c'è alternativa alla ricerca lineare. Se per te è fondamentale avere buone prestazioni durante le ricerche ti consiglio di usare strutture dati diverse, come gli alberi, tenendo però conto che pagherai la maggioe efficienza della ricerca con algoritmi di inserimento e cancellazione più complessi.

io so solo qual'è il primo e qual'è l'ultimo pezzo.
Per prestazioni migliori è meglio utilizzare alberi o liste? Per che cosa sono più indicate le liste per che cosa gli alberi?

[JavHack]

Bhe se proprio devi usare una lista nessuna ti vieta di ricercare in tutti i due "capi" della lista conteporaneamente; statisticamente hai una percentuale maggiore di successo, anche se l'algoritmo ha nel caso peggiore costo uguale

[The Dix]

Mi sembra il modo piu' facile di fare un albero

si forse è l'algoritmo + facile per eseguire poi un bilanciamento

[java is forever]

si forse è l'algoritmo + facile per eseguire poi un bilanciamento

il problema e' che se i dati da inserire sono gia' ordinati l'albero cresce solo verso destra (o verso sinistra, a seconda dell'ordinamento)... E l'algoritmo per tenerlo bilanciato "sempre e comunque" e' di un casino unico