Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Quicksort ordinamento stringhe
Forum - C/C++ - Quicksort ordinamento stringhe

Avatar
Misciu87 (Normal User)
Pro


Messaggi: 68
Iscritto: 01/07/2008

Segnala al moderatore
Postato alle 11:58
Martedì, 01/07/2008
Ciao a tutti,devo un set di stringhe prese in input da un file e restituirle ordinate in un file di output, la prima parte del codice(funzioni exchange,partition e sortlist servono per l'ordinamento le altre funzioni per il caricamento delle stringhe e quelle funzionano) il mio problema e nella funzione partition in quanto questo codice funziona con gli interi ma non con i char perche' nei confronti con <> per i char è diverso dovrei usare strcmp ma non riesco a farlo funzionare, qualcuno può aiutarmi a sistemare i confronti con la strcmp? grazie mille


Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <string.h>
  5.  
  6. void exchange(char **list, int i, int j)
  7. {
  8.         char *tmp=list[i];
  9.         list[i]=list[j];
  10.         list[j]=tmp;
  11. }
  12.  
  13. int partition(char **list, int p, int r)
  14. {
  15.         int i=p, j=r, x, v;
  16.         char *pivot;
  17.  
  18.         x=rand()%(r-p+1)+p;
  19.         exchange(list,x,p);
  20.         pivot=list[p];
  21.        
  22.         while(p<r)
  23.     {
  24.                
  25.         while(j>p && strcmp(list[j],pivot)<0) j--;
  26.                 while(i<r && strcmp(list[j], pivot)>=0) i++;
  27.                 if(i<j)
  28.           exchange(list,i,j);
  29.         }
  30.         exchange(list,p,j);    
  31. }
  32.  
  33. char **sortlist (char **list, int p, int r)
  34. {
  35.     int q,i;
  36.         if(p<r)
  37.     {
  38.                 q=partition(list,p,r);
  39.                 sortlist(list,p,q-1);
  40.                 sortlist(list,q+1,r);
  41.         }
  42.         return list;
  43. }
  44.  
  45. void readsize(char *inputlist, int *length, int *size)
  46. {
  47.         FILE *in=fopen("inputlist.txt","r");
  48.         int i=0,j=0;
  49.         char tmp;
  50.  
  51.         while(fscanf(in,"%c",&tmp)!=EOF && tmp!='\n') j++;
  52.         rewind(in);
  53.         while(fscanf(in,"%*s\n")!=EOF) i++;
  54.         (*length)=i; (*size)=j;
  55.         fclose(in);
  56. }
  57.  
  58. char *readline(FILE *in,int size)
  59. {
  60.         char *line=(char *)malloc(size*sizeof(char)), tmp;
  61.         int i=0;
  62.  
  63.         while(i<size && fscanf(in,"%c",&line[i])!=EOF) i++;
  64.         fscanf(in,"%c",&tmp);
  65.         if(tmp!='\n')
  66.     {
  67.                 printf("Error: malformed file\n");
  68.                 return NULL;
  69.         }
  70.  
  71.         return line;
  72. }
  73.  
  74. char **loadlist(char *inputlist, int *length, int *size)
  75. {
  76.         int i;
  77.         char **list;
  78.         FILE *in=fopen("inputlist.txt","r");
  79.        
  80.         readsize(inputlist,length,size);
  81.  
  82.         list=(char **)malloc((*length)*sizeof(char *));
  83.  
  84.         for(i=0; i<(*length); i++)
  85.                 list[i]=readline(in,(*size));
  86.                
  87.         fclose(in);
  88.  
  89.         return list;
  90. }
  91. void printlist(char *outputlist, char **list, int length)
  92. {
  93.         int i;
  94.         FILE *out=fopen("outputlist.txt","w");
  95.        
  96.         for(i=0; i<length; i++)
  97.                 printf(out,"%s\n",list[i]);
  98.         fprintf(out,"\n");
  99.         fclose(out);
  100. }
  101. int main(int argc, const char *argv[]) {
  102.  
  103.     char **list;       
  104.         int length,size;
  105.         time_t start, end;
  106.  
  107.         if(argc!=3)
  108.     {
  109.                 printf("Usage: stringsort <input list> <output list>\n");
  110.                 return 1;
  111.         }
  112.  
  113.         list=loadlist((char *)argv[1],&length,&size);
  114.         start=clock();
  115.  
  116.         list=sortlist(list,length,size);
  117.         end=clock();
  118.                
  119.         printf("%g\n",(int)(end-start)/(int)CLOCKS_PER_SEC);
  120.         printlist((char *)argv[2],list,length);
  121.  
  122.         return 0;
  123.        
  124. }


Ultima modifica effettuata da Misciu87 il 01/07/2008 alle 12:00
PM Quote
Avatar
asdasd (Normal User)
Newbie


Messaggi: 8
Iscritto: 01/05/2008

Segnala al moderatore
Postato alle 18:54
Martedì, 01/07/2008
Non vorrei dire una cavolata, ma secondo me sbagli  nell'utilizzare quel char **list;

Essendo un puntatore di puntatore non penso puoi accedergli così list[x]

Correggetemi se sbaglio...

PM Quote
Avatar
Misciu87 (Normal User)
Pro


Messaggi: 68
Iscritto: 01/07/2008

Segnala al moderatore
Postato alle 19:38
Martedì, 01/07/2008
No parche io ho un pezzo di codice che era di base e sono le funzioni main, readsize, readline e loadlist, in più le altre funzioni(exchenge,partition e sortlist) vanno bene ma funzionano per gli interi e non per i char, io devo modificarlo opportunamente in modo che confronti i char!

PM Quote
Avatar
gantonio (Normal User)
Guru^2


Messaggi: 1532
Iscritto: 09/09/2007

Segnala al moderatore
Postato alle 22:56
Martedì, 01/07/2008
La funzione partition deve restituire un valore ... correggila ...

PM Quote
Avatar
Misciu87 (Normal User)
Pro


Messaggi: 68
Iscritto: 01/07/2008

Segnala al moderatore
Postato alle 1:51
Mercoledì, 02/07/2008
ok l'ho modificato cosi però non funziona lo stesso..
Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <string.h>
  5.  
  6.  
  7.  
  8. void readsize(char *inputlist, int *length, int *size) {
  9.         FILE *in=fopen("inputlist.txt","r");
  10.         int i=0,j=0;
  11.         char tmp;
  12.  
  13.         while(fscanf(in,"%c",&tmp)!=EOF && tmp!='\n') j++;
  14.         rewind(in);
  15.         while(fscanf(in,"%*s\n")!=EOF) i++;
  16.         (*length)=i; (*size)=j;
  17.         fclose(in);
  18. }
  19.  
  20. char *readline(FILE *in,int size) {
  21.         char *line=(char *)malloc(size*sizeof(char)), tmp;
  22.         int i=0;
  23.  
  24.         while(i<size && fscanf(in,"%c",&line[i])!=EOF) i++;
  25.         fscanf(in,"%c",&tmp);
  26.         if(tmp!='\n')
  27.     {
  28.                 printf("Error: malformed file\n");
  29.                 return NULL;
  30.         }
  31.  
  32.         return line;
  33. }
  34.  
  35. char **loadlist(char *inputlist, int *length, int *size) {
  36.         int i;
  37.         char **list;
  38.         FILE *in=fopen("inputlist.txt","r");
  39.        
  40.         readsize(inputlist,length,size);
  41.  
  42.         list=(char **)malloc((*length)*sizeof(char *));
  43.  
  44.         for(i=0; i<(*length); i++)
  45.                 list[i]=readline(in,(*size));
  46.                
  47.         fclose(in);
  48.  
  49.         return list;
  50. }
  51. void exchange(char **list, int i, int j) {
  52.         char *tmp=list[i];
  53.         list[i]=list[j];
  54.         list[j]=tmp;
  55. }
  56.  
  57. char partition(char **list, int p, int r) {
  58.         int i=p, j=r, x, v;
  59.         char *pivot;
  60.  
  61.         x=rand()%(r-p+1)+p;
  62.         exchange(list,x,p);
  63.         pivot=list[p];
  64.        
  65.         while(p<r)
  66.     {
  67.                
  68.         while(j>p && strcmp(list[j],pivot)<0)
  69.           j--;
  70.                 while(i<r && strcmp(list[j], pivot)>=0) i++;
  71.                 if(i<j)
  72.           exchange(list,i,j);
  73.         }
  74.         exchange(list,p,j);
  75.         return q;
  76.        
  77. }
  78. char **sortlist (char **list, int p, int r) {
  79.        
  80.      char q,
  81.      int i;
  82.        
  83.         if(p<r)
  84.     {
  85.        
  86.                 q=partition(list,p,r);
  87.                
  88.                 sortlist(list,p,q-1);
  89.                 sortlist(list,q+1,r);
  90.         }
  91.         return list;
  92. }
  93. void printlist(char *outputlist, char **list, int length)
  94. {
  95.         int i;
  96.         FILE *out=fopen("outputlist.txt","w");
  97.        
  98.         for(i=0; i<length; i++)
  99.                 fprintf(out,"%s\n",list[i]);
  100.         fprintf(out,"\n");
  101.         fclose(out);
  102. }
  103. int main(int argc, const char *argv[]) {
  104.  
  105.     char **list;       
  106.         int length,size;
  107.         time_t start, end;
  108.  
  109.         if(argc!=3)
  110.     {
  111.                 printf("Usage: stringsort <input list> <output list>\n");
  112.                 return 1;
  113.         }
  114.  
  115.         list=loadlist((char *)argv[1],&length,&size);
  116.         start=clock();
  117.  
  118.         list=sortlist(list,length,size);
  119.         end=clock();
  120.                
  121.         printf("%g\n",(int)(end-start)/(int)CLOCKS_PER_SEC);
  122.         printlist((char *)argv[2],list,length);
  123.  
  124.         return 0;
  125.        
  126. }


PM Quote
Avatar
gantonio (Normal User)
Guru^2


Messaggi: 1532
Iscritto: 09/09/2007

Segnala al moderatore
Postato alle 15:30
Giovedì, 10/07/2008
Hai aggiunto una

return q;

ma q non esiste nella funzione ... se aggiungi istruzioni a caso, non ti funzionera' mai ...

E non e' solo quello il problema ...

PM Quote
Avatar
Misciu87 (Normal User)
Pro


Messaggi: 68
Iscritto: 01/07/2008

Segnala al moderatore
Postato alle 16:55
Mercoledì, 16/07/2008
Gia risolto da sola!

PM Quote
Avatar
gantonio (Normal User)
Guru^2


Messaggi: 1532
Iscritto: 09/09/2007

Segnala al moderatore
Postato alle 17:25
Mercoledì, 16/07/2008
Testo quotato

Postato originariamente da Misciu87:

Gia risolto da sola!



Bene! Mi fa piacere ...

PM Quote