[C] Array di puntatori ad elementi di una lista

[xglobusx]

Ho una lista di struct ordinata secondo i valori di un campo della struct.
Voglio fare un ordinamento socondo i valori assunti da un altro campo, visto che alla fine devo stampare i primi 10 elementi pensavo di fare un array di 10 puntatori alla struct e puntare i 10 elementi richiesti.
E' possibile farlo avendo già la lista ordinata (secondo l'altro campo) o bisogna farlo durante la creazione della lista?

[donato.sciarra]

che intendi con stampare i primi 10. .. . i primi 10 che trovi o i primi 10 in assoluto???

ma e' un int il campo a cui fai riferimento???

................

cmq sia ti basta scorrere la lista e riempire il vettore di puntatori a struttura. . .(si puo fare anche nel caso in cui la lista non è ordinata). . . .

. . .stampando poi cio che ti serve. . .

[xglobusx]

la struct è
char *c
int i

la lista è in ordine alfabetico secondo c.
devo stampare per esempio i 10 elementi con i minore.

[donato.sciarra]

scorri la lista con una funzione che restituisce un puntatore all'elemento cercato e assegni man mano ciò che ti restituisce ad una posizione all'interno del vettore di puntatori, controlli la posizione dell'elemento e se i e' minore del valore presente nell'ultima posizione del vettore devi inserirlo...... qui hai due casi limite:

1- la fortuna che la lista sia di al max di 10 elementi

2- il caso in cui hai piu di 10 elementi nella lista

nel secondo caso devi trovare la posizione adatta nel vettore e inserire l'elemento in modo tale da avere solo quelli che servono a te (cioe' con i minore). . .

. . .spero di essere stato chiaro se hai dubbi chiedi

[GabbOne]

Devi utilizzare un algoritmo di ordinamento per lae chiavi i .
la cosa piu semplice che si puo realizzare è costruire una funzione che ti restituisca il minimo della lista

a questo punto costruisci una funzione che ti crea un lista i cui elementi sono i primi 10 minimi della lista originale che devi ordinare. Naturalmente dovrai marcare gli elementi gia inseriti nella nuova lista per non rischiare di reimmeterli per 10 volte di seguito .Per fare questo la cosa piu semplice da fare e cancellare dalla lista originale l'elemnto che hai inserito nella lista dei minimi.Quindi se non vuoi distruggere la lista originale devi farne una copia e eseguire il tutto su questa .
Questo è un'approccio brutale al tuo problema se ne vuoi uno efficente ti consiglio nel tuo caso di utilizzare l'algoritmo Bucket Sort che come risultato finale ti darà una lista ordinata.

[donato.sciarra]

e' quasi la stessa cosa ma sottolineo il fatto che non e' necessario creare una copia della lista e un altra dove immagazzinare i valori della copia(tagliati nell'originale). . .si risolve molto piu semplicemente tramite un vettore di puntatori con n posti disponibili !

A mio parere c'e solo uno spreco di memoria con la creazione di una lista parallela piu una di supporto. . .

[GabbOne]

La lista di copia si puo risparmiare "nella mia soluzione" mettendo un campo in piu nella struttura ad esempio
struct ...
{
..
..
int marcatore=0;
}

poi quando nella lista originale estrai il minimo consideri anche la variabile marcatore se è impostata a 0 è un (possibile )minimo valido (imposti il marcatore ad 1) altrimenti continui la ricerca del minimo.

Poi si puo utilizzare un vettore come dice donato ,dipende solo da cosa si vuole in iscita dal programma ,un lista , un vettore o solo stampare i primi 10 ,in quest'ultimo caso non ti serve ne un vettore ne una lista , ad ogni minimo trovato lo si stampa.

P.S.
Donato il tuo algoritmo sinceramente non l'ho capito molto bene ad esempio

Scorri la lista con una funzione che restituisce un puntatore all'elemento cercato

Qualè l'elemento cercato?
Poi mi sembra che nel passo 2 vuoi dire che ad ogni elemento trovato devi riordianre il vettore per cosi prendere i primi 10 valori piu piccoli della lista originale?

[donato.sciarra]

pensandoci bene e' possibile scrivere tuttto in un unica funzione che scorre la lista cercando cio che c serve e se necessario riempiendo il vettore . . . .

. . .conviene inserire nella struttura un altro parametro di controllo ! (che chiamo con originalita int controllo inizializzandoli tutti a 0 con la funzione void init_controllo)

/*si ipotizza di aver dichiarato [b]a livello globale[/b] il puntatore di testa della lista! ! 

lista e' il tipo di dato della struttura che rappresenta il nodo

lista *vett[9]; e' il vettore di dieci elementi da riempire con i puntatori alla lista;*/

/*struttura usata*/
struct nodo{
        int i;
        int controllo;
        char *c;
        struct nodo *next;
}
typedef struct nodo lista;

/*la seguente funzione va lanciata esattamente prima di lanciare la funzione riempi*/
void init_controllo(void){
    lista *temp;
    temp=testa;
    while(temp){
        temp->controllo=0;
        temp=temp->next;
    }
}

/*riempi restituisce il numero di parametri inseriti nel vettore dalla lista*/
int riempi(void){
      int da_cercare;
      int i=0;/*indice del vettore da riempire*/
      int trovato=1;
      lista *cursore, *temp;/*puntatori per scorrere la lista*/
      cursore=testa;
      /*scandisco la lista trovando l'elemento piu piccolo*/
      da_cercare=testa->i;
      while(cursore){
         if(cursore->i < da_cercare){
             da_cercare=cursore->i;
             temp=cursore;/*memorizzo il puntatore al nodo con la variabile i piu piccola*/
         }
         cursore=cursore->next;
      }
      /*a questo punto ho il valore piu piccolo rappresentato da da_cercare e puntato da temp*/
      /*dato che e' il piu piccolo lo inserisco nel vettore dichiarato globalmente sempre che la lista non sia vuota*/
      if(temp){
         temp->controllo=1;/*in questo modo nn sarà piu il piu piccolo*/
         vett[i]=temp;
         i++;
         /*faccio un ciclo per trovare gli altri 9 piu piccoli*/
        while(i<10){
          cursore=testa;
          da_cercare=testa->i;
          trovato=0;
          while(cursore){
               if((cursore->i < da_cercare)&&(cursore->controllo==0)){
                  da_cercare=cursore->i;
                  temp=cursore;
                  trovato=1;
                  }
                 cursore=cursore->next; /*continuo a scorrere la lista*/ 
                }/*fine while*/
                /*temp mi da il valore piu piccolo diverso da quello precedentemente inserito*/
                if(trovato){
                  vett[i]=temp;
                  temp->controllo=1;
                  i++;
               }
               else break;
         }/*fine while*/
       return (i);
      }/*fine if*/

       else return 0;/*lista vuota*/
} 

questa puo essere una possibile soluzione che non ho testato, molto probabilmente ci sono degli obbrobbi . . .

fatemi sapere

[GabbOne]

Ad occhi non sono riuscito a terminare la compilazione .Comunqu per una maggiore leggibilità io la seconda funzione l'avrei scritta così

/*
Supponendo che il puntatore alla testa della lista (headList).Per la funzione minimo supponiamo che gli interi da                                                                                                                                                                cercare siano ad esempio >0 per avere   cosi un codice di errore                                                                         di ritorno (-1) nel caso in cui non ci sono piu minimi da estrarre dalla lista
*/

int minimo(void)
{
      min=-1;/*
      tmp=headList;
      while(tmp!=NULL)
      {
           if((tmp->i < min)&&(tmp->marcatore!=1))
           {
                   min=i;
                   aux=tmp;
           }
      }
      aux->marcatore=1;
      return min;
}

int main()
{
   int A[10];  
   init_Controllo(); 
   for(i=0;i<10;i++)
          A[i]=minimo();
   return 1;
}

A questo punto le prove le possiamo lasciare a xglobusx

[xglobusx]

domani o sabato lo finisco, oggi si fa altro.