ordinamento lista di strutture C

[burohkr]

Sono alle prime armi con la programmazione ed ho il seguente problema:
ho creato una lista di elementi tipo strutture che contiene un intero long in un suo campo........indipendentemente dagli elementi inseriti (dinamicamente) voglio ordinare crescentem o decresc in base ai valori long negli elementi ( ho un pò di problemi a lavorare con puntatori e perciò ad esempio leggendo come funziona il mergesort sugli array non riesco a capire come utilizzarlo nel mio caso). DIMENTOICAVO, POSSIBILMENTE DEVE ESSERE UNA FUNZIONE RICORSIVA AD ORDINARE.......grazie ciao a tutti

[Icedguardian]

Lista monodirezionale o bidirezionale?
Cmq non credo tu possa utilizzare il merge (a meno di modifiche pesanti), io punterei sull'insertion-sort (semplice anche se non efficacissimo).

Ciao

[cionci]

Si può lavorare in due modi....

Metti di avere una lista di questo tipo:

D -> A -> C -> B

da ordinare alfabeticamente...

Il primo modo è di cambiare i puntatori all'interno degli elementi della lista estraendo un elemento e posizionandolo dove ci interessa...
Metto da parte A...
Modifico il puntatore di D e lo faccio puntare a C...

C -> D -> B

Ora prendo a A lo faccio puntare a C...

A -> C -> D -> B

E questa è una iterazione (attenzione non ho specificato il tipo di algoritmo, diciamo che vale per tutto l'insieme di algoritmi che non fanno scambi fra elementi)...

Quelli che fanno scambi si posso adattare scambiando le informazioni di ogni elemento (non va bene l'assegnazione normale perchè i puntatori non vanno scambiati)...

D -> A -> C -> B

TMP = A
A = D
D = TMP

A -> D -> C -> B

Un semplice algoritmo ricorsivo è quello che scambia un elemento con il successivo se si verifica una certa condizione:

struct st {
   int info;
   st *next;
};

....

st *ordina(st *primo)
{
   struct st *secondo;
   struct st *tmp; //per il primo metodo
   //int tmp; //per il secondo metodo
   //condizioni di arresto
   if(!primo)
      return NULL;
   if(!primo->next)
      return primo;

   //condizione normale
   secondo = ordina(primo->next); //ricorsione

   if(secondo->info > primo->info) //condizione di scambio
   {
      //con il primo metodo   
      tmp = secondo->next;
      secondo->next = primo;
      primo->next = secondo
      return secondo;
      //con il secondo metodo
      /*
      tmp = secondo->info;
      secondo->info = primo->info;
      primo->info = tmp;
      */
   }
   return primo;
}

[cionci]

Mi ero scordato un pezzettino e avevo sbagliato qualcosa

struct st {
   int info;
   st *next;
};

....

int ciclo(st **primo)
{
   int scambio = 0;
   struct st *secondo;
   struct st *tmp; //per il primo metodo
   //int tmp; //per il secondo metodo
   //condizioni di arresto
   if(!*primo)
      return 0;
   if(!*primo->next)
      return 0;

   //condizione normale
   secondo = *primo->next;

   if(secondo->info > *primo->info) //condizione di scambio
   {
      //con il primo metodo   
      tmp = secondo->next;
      secondo->next = *primo;
      *primo->next = tmp;
      //devo scambiare anche questi valori per far sì che torni
      tmp = *primo;
      secondo = tmp;
      *primo = secondo;

      //con il secondo metodo
      /*
      tmp = secondo->info;
      secondo->info = *primo->info;
      *primo->info = tmp;
      */

      scambio = 1;
   }
   return scambio + ciclo(&secondo);
}

void ordina(st **testa)
{
   //fino a quando viene fatto almeno uno scambio cicla
   while(ciclo(testa));
}

Se questa volta non ho fatto errori questo dovrebbe funzionare e dovrebbe anche essere veloce...

[burohkr]

Mi sembra che possa andar bene, ma dimmi una cosa..... E' normale che non riesco a ragionare in C? Mi si ingarbuglia il cervello e anche se c'è una strada corta per arrivare ad una soluzione, prendo quella lunga!!
Per te è stato difficile?

[cionci]

Bisogna un po' prenderci la mano... Non ti preoccupare...ci vuole un po' di tempo... Ti ci trovi un po' male soprattutto se già conosci linguaggi di altissimo livello come VB o Java...
Non ti posso dire come mi ci sono trovato io perchè è il primo linguaggio che ho imparato...ed il primo ha per forza una curva di apprendimento più lunga...

[burohkr]

credo che ci sia un errore: quando all'interno della funzione ciclo che restituisce un valore di tipo INT fai : return secondo......il quale è un puntatore. Non è detto che c'ho preso ma se così fosse potresti darle una corretta? Ti volevo chiedere anche un ' altra cosa: dove posso guardare su internet per trovare algoritmi o esercizi svolti, utili per farmi imparare?

[cionci]

Scusa...mi era rimasto dal codice che avevo scritto sopra...

[cionci]

Ho fatto un altro errore... Sai, non avendolo provato certe cose si vedono male... Coretto...

[cionci]

Per esercizi...dovresti fare una ricerca... Di solito si trovano le dispense di qualche corso universitario con esercizi svolti...

[cionci]

Ad esempio:

http://www.elet.polimi.it/upload/fugini/linguaggio_C_esempi.doc
http://www.dia.uniroma3.it/~torlone/calcolatori/Esercizi.pdf

E molti altri... Sono i primi che ho trovato cercando su Google "esercizi liste linguaggio C"...

[burohkr]

perché usi come argomento della funzione ciclo, un puntatore ad un puntatore? Lo attaccata al mio programma cambiando le cose che mi sembravano giuste, ma non senza dubbi.

es: io dopo aver definito la strurrura col nome lista ho fatto:

typedef struct lista LISTONE;
typedef struct LISTONE *LINK;/* per il puntatore alla strurrura */

quindi come argomento di ciclo ho passato (LINK testa) dove testa è il puntatore al primo elemento della lista. Così che nel resto della funzione
al posto di *primo ho usato testa...... E' GIUSTO QUELLO CHE HO FATTO.....mi dà un errore terribile in esecuzione: errore di accesso illegittimo al segmento o qualcosa del genere, insomma quando si tratta di accessi illegittimi non è un bel segno.....

[cionci]

Gli passo un puntatore ad un puntatore perchè in caso venga cambiato il valore di *primo questo cambiamento si riflette anche sul puntatore usato per la chiamata...

Lunedì mi ci metto e lo compilo...

[cionci]

Ecco qua:

#include <stdio.h>
#include <stdlib.h>

struct st { 
   int info; 
   struct st *next; 
}; 


int ciclo2(struct st *primo) 
{ 
   int scambio = 0; 
   struct st *secondo; 
   int tmp;
   //condizioni di arresto 
   if(!primo) 
      return 0; 
   if(!primo->next) 
      return 0; 

   //condizione normale 
   secondo = primo->next; 

   if(secondo->info > primo->info) //condizione di scambio 
   { 
      tmp = secondo->info; 
      secondo->info = primo->info; 
      primo->info = tmp; 
	  scambio = 1;
   } 
   return scambio + ciclo2(secondo); 
} 


int ciclo1(struct st **primo) 
{ 
   int scambio = 0; 
   struct st *secondo; 
   struct st *tmp; //per il primo metodo 
   //condizioni di arresto 
   if(!*primo) 
      return 0; 
   if(!(*primo)->next) 
      return 0; 

   //condizione normale 
   secondo = (*primo)->next; 

   if(secondo->info > (*primo)->info) //condizione di scambio 
   { 
      //con il primo metodo    
      tmp = secondo->next; 
      secondo->next = *primo; 
      (*primo)->next = tmp; 
      //devo scambiare anche questi valori per far sì che il valore modificato di primo
     //venga cambiato anche nel chiamante
      tmp = *primo; 
      *primo = secondo; 
      secondo = tmp; 

      scambio = 1; 
   } 
   scambio += ciclo1(&secondo);
   (*primo)->next = secondo; //se eventualmente secondo è cambiato lo aggiorno
   return scambio; 
} 

void ordina(struct st **testa) 
{ 
   //fino a quando viene fatto almeno uno scambio cicla 
   while(ciclo1(testa)); 
}

void inserisci(struct st **testa, int info)
{
   struct st *tmp;
   tmp = (struct st *)malloc(sizeof(struct st));
   tmp->next = NULL;
   if(!*testa)
     *testa = tmp;
   else
   {
      tmp->next = *testa;
      *testa = tmp;
   }
   (*testa)->info = info;
}

void stampa(struct st *t)
{
   if(!t)
      return;
   printf("%d\n", t->info);
   stampa(t->next);
}

int main()
{
   struct st *testa = NULL;
   inserisci(&testa, 4);
   inserisci(&testa, 10);
   inserisci(&testa, 1);
   inserisci(&testa, 0);
   inserisci(&testa, 10);
   inserisci(&testa, 1);
   inserisci(&testa, 0);
   inserisci(&testa, 10);
   inserisci(&testa, 1);
   inserisci(&testa, 0);
   inserisci(&testa, 5);
 
   ordina(&testa);
   
   stampa(testa);  
   
   return 0;
}

[burohkr]

Il tuo algoritmo è perfetto ma non riesco a far funzionare il mio programmino d'apprendimento.

devo leggere un file di input (esempio: un txt creato con il block note dove ho inserito: il nome di un programma televisivo, separato da questo il codice che lo identifica, e ancora più avanti l'odiens.

ES, per una righa ho:

canale5 ch5 1000000

e a seguire ho altre righe con altri canali........

Devo leggere questi dati, metterli in una lista e dire quali sono i due canali più visti (per questo cercavo di ordinare la lista)

ECCO IL MIO CODICE: ti prego di dirmi tutti gli errori e perché li ho fatti...... ti ringrazio.

#include <stdio.h>
#include <stdlib.h>

#ifndef NULL
  #define NULL 0
#endif

/* dichiarazione della lista semplice*/
struct lista{
       int spettatori;
       char programma;
       char codice;
       struct lista *prossimo;
};
typedef  struct lista LISTONE;
typedef LISTONE **LINK;
struct lista *testa = NULL; /*puntatore alla testa della lista*/
/*dichiarazione del puntatore al file da aprire*/
FILE *fp;          

void add_to_list(FILE *disco,LINK first);
int ciclo(LINK first);  
void ordina(LINK first); 
int main()
{
 /*dichiaro alcune variabili locali alla funzione main*/
 int number;
 char buffer[20];
 int count;
 int scelta;
 printf("inserire il nome del file da aprire con estensione:   ");
 gets(buffer);
 
 
    
 printf("inserire il numero di righe da leggere:   ");
 scanf("%d", &number);
 
   if (number == 0)
   exit(0);
  else 
    {
     /*apertura del file */
     if ((fp = fopen(buffer, "r")) == NULL )
          {
          fprintf(stderr,"errore nell apertura del file");
          exit(0);
          }       
     for (count = 0 ; count < number ; count++)
     	add_to_list(fp, &testa);
        
    }
fclose(fp); 
/* ora creo un menu per scegliere diverse operazioni da fare*/

 ordina(&testa);
 
 printf("Il canale piu visto è :  %s con %d spettatori",testa->programma,testa->spettatori);
 
   return 0;
}
/* codice delle funzioni */
void add_to_list(FILE *disco,LINK first)
{
 struct lista *nuovo = NULL;
 struct lista *temp = NULL;
 struct lista *preced = NULL;
 
 /*alloca la memoria in modo dinamico*/
 nuovo = (struct lista *)malloc(sizeof(LISTONE));
      if (!nuovo)
      {
       fprintf(stderr,"errore nell/' allocazione della memoria");
       exit(0);
      }
     /*legge la prima riga del file aperto */
  fscanf(disco,"%s %s %ld", &nuovo->programma,&nuovo->codice,&nuovo->spettatori);
    
     if ((*first) == NULL)
        /* aggiungo il primo elemento */         
        {
         *first = nuovo;
         nuovo->prossimo = NULL;
        }
      else
        {
         preced  = *first;
         temp =preced->prossimo;
             while (temp != NULL)
              {
               temp = temp->prossimo;
               preced = preced->prossimo;
              }
         temp = nuovo;
         temp->prossimo = NULL;  
        }
 }

int ciclo(LINK first)  
{ 
   int scambio = 0; 
   struct lista *secondo = NULL; 
   struct lista *tmp = NULL; //per il primo metodo 
   //int tmp; //per il secondo metodo 
   //condizioni di arresto 
   if(!*first) 
      return 0; 
   if(!(*first)->prossimo) 
      return 0; 

   //condizione normale 
   secondo = (*first)->prossimo; 

   if((secondo->spettatori) > ((*first)->spettatori)) //condizione di scambio 
   { 
      //con il primo metodo    
      tmp = secondo->prossimo; 
      secondo->prossimo = *first; 
      (*first)->prossimo = tmp; 
      //devo scambiare anche questi valori per far sì che torni 
      tmp = *first; 
      secondo = tmp; 
      *first = secondo;
       

      //con il secondo metodo 
      /* 
      tmp = secondo->info; 
      secondo->info = *primo->info; 
      *primo->info = tmp; 
      */ 

      scambio = 1; 
   } 
   
   scambio += ciclo(&secondo); 
   (*first)->prossimo = secondo;
   return scambio;
} 

void ordina(LINK first) 
{ 
   //fino a quando viene fatto almeno uno scambio cicla 
   while(ciclo(first)); 

}

[/code][/u]

[cionci]

Magari se mi dai anche un file di prova...

[cionci]

Ecco qua:

#include <stdio.h> 
#include <stdlib.h> 

#ifndef NULL 
  #define NULL 0 
#endif 

/* dichiarazione della lista semplice*/ 
struct lista{ 
       int spettatori; 
       char programma[100]; 
       char codice[5]; 
       struct lista *prossimo; 
}; 
typedef  struct lista LISTONE; 
typedef LISTONE **LINK; 
struct lista *testa = NULL; /*puntatore alla testa della lista*/ 
/*dichiarazione del puntatore al file da aprire*/ 
FILE *fp;          

void add_to_list(FILE *disco,LINK first); 
int ciclo(LINK first);  
void ordina(LINK first); 
int main() 
{ 
 /*dichiaro alcune variabili locali alla funzione main*/ 
 int number; 
 char buffer[20]; 
 int count; 
 int scelta; 
 printf("inserire il nome del file da aprire con estensione:   "); 
 gets(buffer); 
  
  
    
 printf("inserire il numero di righe da leggere:   "); 
 scanf("%d", &number); 
  
   if (number == 0) 
   exit(0); 
  else 
    { 
     /*apertura del file */ 
     if ((fp = fopen(buffer, "r")) == NULL ) 
          { 
          fprintf(stderr,"errore nell apertura del file"); 
          exit(0); 
          }        
     for (count = 0 ; count < number ; count++) 
        add_to_list(fp, &testa); 
        
    } 
fclose(fp); 
/* ora creo un menu per scegliere diverse operazioni da fare*/ 

 ordina(&testa); 
  
 printf("Il canale piu visto è :  %s con %d spettatori",testa->programma,testa->spettatori); 

   return 0; 
} 
/* codice delle funzioni */ 
void add_to_list(FILE *disco,LINK first) 
{ 
 struct lista *nuovo = NULL; 
 struct lista *temp = NULL; 
 struct lista *preced = NULL; 
  
 /*alloca la memoria in modo dinamico*/ 
 nuovo = (struct lista *)malloc(sizeof(LISTONE)); 
      if (!nuovo) 
      { 
       fprintf(stderr,"errore nell/' allocazione della memoria"); 
       exit(0); 
      } 
     /*legge la prima riga del file aperto */ 
  fscanf(disco,"%s %s %ld", &nuovo->programma,&nuovo->codice,&nuovo->spettatori); 
    
     if ((*first) == NULL) 
        /* aggiungo il primo elemento */          
        { 
         *first = nuovo; 
         nuovo->prossimo = NULL; 
        } 
      else 
        { 
         nuovo->prossimo = *first;
         *first = nuovo;
        } 
 } 

int ciclo(LINK first)  
{ 
   int scambio = 0; 
   struct lista *secondo = NULL; 
   struct lista *tmp = NULL; //per il primo metodo 
   //int tmp; //per il secondo metodo 
   //condizioni di arresto 
   if(!*first) 
      return 0; 
   if(!(*first)->prossimo) 
      return 0; 

   //condizione normale 
   secondo = (*first)->prossimo; 

   if((secondo->spettatori) > ((*first)->spettatori)) //condizione di scambio 
   { 
      //con il primo metodo    
      tmp = secondo->prossimo; 
      secondo->prossimo = *first; 
      (*first)->prossimo = tmp; 
      //devo scambiare anche questi valori per far sì che torni 
      tmp = *first; 
      *first = secondo; 
      secondo = tmp;         

      //con il secondo metodo 
      /* 
      tmp = secondo->info; 
      secondo->info = *primo->info; 
      *primo->info = tmp; 
      */ 

      scambio = 1; 
   } 
    
   scambio += ciclo(&secondo); 
   (*first)->prossimo = secondo; 
   return scambio; 
} 

void ordina(LINK first) 
{ 
   //fino a quando viene fatto almeno uno scambio cicla 
   while(ciclo(first)); 

}

C'erano diversi errori a giro...

La struttura deve essere composta da stringhe...mentre tu avevi emsso solo un char...
Era sbagliato l'inserimento... Ci ho messo un inserimento in testa...
Ti mancava na modifica sul codice della funzione ciclo che avevo fatto l'ultima volta...

[burohkr]

adesso lo provo, cmq il file di prova te lo puoi creare, è un .txt con la struttura che ti ho detto sopra......mi sei stato di molto aiuto, ciao

[cionci]

Me lo sono già fatto