Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Errore di segmentazione molto strano...
Forum - C/C++ - Errore di segmentazione molto strano...

Pagine: [ 1 2 ] Precedente | Prossimo
Avatar
danis486 (Normal User)
Newbie


Messaggi: 9
Iscritto: 04/03/2009

Segnala al moderatore
Postato alle 15:51
Mercoledì, 04/03/2009
Ciao a tutti,per domani mattina ho da portare al prov questo programmino ma sono due giorni con questo errore di segmentazione stupido. A furia di provare sono riuscito a far funzionare il primo algoritmo dei 4,ma gli altri 3 mi danno sempre l'errore.Vi prego aiutatemi voi perchè non riesco a capire,sono sicuro che è una cosa banalissima in quanto tutte le funzioni vanno bene e non hanno errori ne di compilazione ne di funzionamento però c'è sempre questo problema!Vi posto il codice,quello che mi interesserebbe è sapere come si risolve almeno nel bubble sort poi il resto lo faccio io altrimenti vi fo dannare XD XD Un ultimo consiglio,ho provato a creare una funzione VUOTA nominata bubble_sort con il passaggio di parametri e basta e mi da l'errore anche se dentro non c'è nulla!!!!XD XD AIUTATEMI VI PREGO :-|:-|:-|:-|:-|:-|:-|:-|
Codice sorgente - presumibilmente C/C++

  1. /*
  2. * Nome del file: main.c
  3. * Autore - Daniele Brundu Matricola:4655895
  4. * Gennaio 2009
  5. * Realizzazione per Riconoscimento 1cfu
  6. * Il programma legge da file e ordina tramite scelta dell'utente
  7. * del tipo di algoritmo una serie di valori virtualizzando il vettore ordinato
  8. */
  9.  
  10.  
  11. #include <string.h>
  12. #include <stdio.h>   //libreria per lettura da input e scrittura a video
  13.                      //(standard input-output header)
  14. #include <stdlib.h>  /* dichiara funzioni e costanti di utilità generale:
  15.                       * allocazione della memoria, controllo dei processi,
  16.                       * conversione tra tipi ecc
  17.                       */
  18.  
  19. /*SI PARTE CON LA PROTOTIPAZIONE DELLE FUNZIONI AFFICHE'
  20.  *SI POSSANO UTILIZZARE "SENZA ESSERE DEFINITE"
  21. */
  22.  
  23.  
  24. int main(void);                                              //prototipo della funzione
  25. void sequential_sort(float * V,int N,int * Perm);            //prototipo della funzione
  26. void bubble_sort(float * V,int N,int * Perm);                //prototipo della funzione
  27.  
  28. void merge_sort(float * V,int N);                            //prototipo della funzione
  29. void _mergesort(float * V,int N,float * tmp);                //prototipo della funzione
  30. void merge(float * V,int N,int Nl);                          //prototipo della funzione
  31.  
  32. void quicksort(float * V,int N);                             //prototipo della funzione
  33. int partition(float * V,int N);                              //prototipo della funzione
  34.  
  35. void swap(int * Perm,int a,int b);                         //prototipo della funzione
  36.                                                            //prototipo della funzione
  37.  
  38. void printArray(float * V, int N);                           //prototipo della funzione
  39. void printPermutatedArray(float * V, int N, int * Perm);     //prototipo della funzione
  40.  
  41. int main(void)
  42. /* apre un file testo e vi legge i valori di un vettore.
  43.    Assume che i dati nel file siano codifcati in sequenza senza
  44.    specificarne all'inizio il numero, dunque con il tracciato:
  45.    {float valore}
  46.  */
  47. {
  48.    
  49.   FILE *fhandle;     //successivamente verrà utilizzato per aprire il file e leggerlo,dichiara fhandle                  
  50.   int N;             //variabile di tipo int con nome N
  51.   float * V;        
  52.   int count;         //variabile di tipo int con nome count
  53.   float  value;      //variabile di tipo float(reale) con nome value
  54.   int * Perm;
  55.  
  56.  #define NAlgoritmi 4 //Direttiva di definizione che associa alla costante NAlgoritmi valore 2
  57.  
  58.   char nomeAlgoritmo[NAlgoritmi][18]; //definisce array bidimensionlae di grandezza 4x16 per le stringhe
  59.   strcpy(nomeAlgoritmo[0],"sequential sort"); //copia la stringa nell'indice 0
  60.   strcpy(nomeAlgoritmo[1],"bubble sort");     //copia la stringa nell'indice 1
  61.   strcpy(nomeAlgoritmo[2],"merge sort");      //copia la stringa nell'indice 2
  62.   strcpy(nomeAlgoritmo[3],"quick sort");      //copia la stringa nell'indice 3
  63.  
  64.   printf("\n vettoreN.txt");                  // stampa il nome del file
  65.  
  66.  
  67.   fhandle = fopen("vettoreN.txt", "r");        //apre il file in lettura              
  68.   N=0;                                        
  69.   while(fscanf(fhandle,"%f",&value)!=EOF){     //condizione che la lunghezza dello stream
  70.                                                //sia diversa dll'end of file
  71.     N++;                                       //incrementa N e scrive su value di appoggio
  72.   }
  73.    
  74.   printf("\n Il vettore nel file ha lunghezza : %d", N); //stampa lunghezza file
  75.   Perm=(int *)malloc(N*sizeof(int));                     //in questo modo lo alloca nello stack
  76.                                  
  77.    
  78.  
  79.   rewind(fhandle);                             //reinizializza lettura del file da capo
  80.   V=(float *)malloc(N*sizeof(float));          //malloc: abilita gestione dinamica della memoria
  81.                                                //sizeof restituisce la dimensione del tipo di dato da allocare
  82.                                                //quindi crea un buffer con dimensione 32 bits(cadauno)per N
  83.   rewind(fhandle);                             //reinizializza lettura del file da capo
  84.  
  85.  
  86.   for(count=0;count<N;count++){                    
  87.     fscanf(fhandle,"%f",&V[count]);            //legge da fhandle (file) e lo mette nella posizione [count]
  88.            
  89.   }
  90.   printf("\n Il vettore in ingresso e': ");
  91.   printArray(V,N);                             //stampa l'array
  92.   fflush(fhandle);                             //svuota fhandle
  93.   fclose(fhandle);                             //chiude la lettura
  94.  
  95.  
  96.  
  97.   //NEL PROSSIMO CICLO SELEZIONIAMO L'ALGORITMO DA USARE E CONSIDERANDO
  98.   //CHE PER UNA PERSONA E' PIU' SEMPLICE NELLA SELEZIONE PARTIRE DA 1
  99.   //E NON DA ZERO,CHIEDO DI INSERIRE I VALORI
  100.   //DA UNO A 4 MA IN REALTA' SUBITO DOPO L'INSERIMENTO
  101.   //LI SFASO DI UNO ADATTANDOLI ALL'ARRAY
  102.   //CHE PARTE DA 0!!
  103.  
  104.   count = 5;  //lo imposto a 4 per permettere al ciclo di partire(faccio questo affinchè
  105.               //se successiamente si inserisce un valore superiore riparte il ciclo fino a quando
  106.               //il valore non è compreso fra 1 e 4 che nel ciclo divente fra 0 e 3.
  107.               //E' "complesso" nella logica ma funzionale al 100% in quanto adatto all'utente!
  108.  
  109.   while(count > 4 || count < 1){
  110.               printf("\n\n Selezionare un algoritmo di ordinamento premendo :");
  111.               printf("\n 1. per utilizzare il Sequential Sort ");
  112.               printf("\n 2. per utilizzare il Bubble Sort ");
  113.               printf("\n 3. per utilizzare il Merge Sort ");
  114.               printf("\n 4. per utilizzare il Quick Sort \n");
  115.               scanf("%u",&count);
  116.                }                      //con un semplice decremento un'adattabilità maggiore all'utenza.
  117.  
  118.   printf("\n L'algoritmo selezionato e' : %s",nomeAlgoritmo[count-1]);
  119.    
  120.   //il valore algoritmo in questo momento deve essere per forza compreso fra 0 e 3 in quanto altrimenti
  121.   //il ciclo while si reinizializzerebbe.
  122.  
  123.   switch(count){                      //uso il comando switch che è più comodo in questi casi
  124.                                      
  125.      case 1:                          //se il valore è 0 passo al sequential sort
  126.        sequential_sort(V,N,Perm);
  127.        printf("\n\n il vettore ordinato con %s e':", nomeAlgoritmo[count-1]);
  128.        printPermutatedArray(V,N,Perm);//richiamo la funzione di stampa
  129.      break;                          
  130.    
  131.      case 2:                          //se il valore è 1 passo al bubble sort
  132.        bubble_sort(V,N,Perm);        
  133.        printf("\n\n il vettore ordinato con %s e':", nomeAlgoritmo[count-1]);
  134.        printPermutatedArray(V,N,Perm); //richiamo la funzione di stampa
  135.      break;                          
  136.    
  137.      case 3:                          //se il valore è 2 passo a merge sort
  138.        merge_sort(V,N);            
  139.        printf("\n\n il vettore ordinato con %s e':", nomeAlgoritmo[count-1]);
  140.        printPermutatedArray(V,N,Perm);//richiamo la funzione di stampa
  141.      break;                          
  142.      
  143.      case 4:                          //se il valore è 3 passo al quick sort(il più veloce)
  144.        quicksort(V,N);        
  145.        printf("\n\n il vettore ordinato con %s e':", nomeAlgoritmo[count-1]);
  146.        printPermutatedArray(V,N,Perm);//richiamo la funzione di stampa        
  147.      break;                          
  148.   }
  149.  
  150.   free (V);                           //libera la memoria altrimenti
  151.   free (Perm);                        
  152.  
  153.   printf("\n ");
  154.   system("PAUSE");              //comando DOS
  155.   return 0;
  156. }
  157. //cerco l'elemento con il valore più alto e lo scambio con quello dell'ultima
  158. //posizione dell'array,e così via per n-1 volte.
  159. //Invece di modificare gli elementi dell'array,costruisco un vettore di
  160. //permutazione che fornisce la sequenza attraverso la quale visitiamo il vettore
  161. //V in modo ordinato.Costo O(N).
  162.  
  163. void sequential_sort (float * V,int N,int * Perm){
  164.       int count;
  165.       int count_of_max;
  166.       int iter;
  167.       for(count = 0;count<N;count++)
  168.                 Perm[count]=count;
  169.                
  170.       for(iter=0;iter<N-1;iter++){
  171.           for(count=1,count_of_max=0;count<N-iter;count++){
  172.               if(V[Perm[count]]>V[Perm[count_of_max]]){
  173.                   count_of_max = count;
  174.               }
  175.           swap(Perm,count_of_max,N-iter-1);
  176.           }
  177.       }
  178. }
  179.  
  180. //confronta l'elemento con il suo successivo e li scambia se count<count+1
  181. void bubble_sort(float * V,int N,int * Perm){
  182.  
  183.      int count;
  184.      int iter;
  185.      int iter_without_swap;
  186.      int swap_found;
  187.      
  188.      iter=0;
  189.      iter_without_swap=0;
  190.      while(iter_without_swap == 0){
  191.       for(count=0,swap_found=0;count<N-iter-1;count++){
  192.           if(V[Perm[count]]<V[Perm[count+1]]){
  193.                swap(Perm,count,count+1);
  194.                swap_found=1;
  195.             }
  196.         }
  197.         if(swap_found==0)
  198.             iter_without_swap=1;
  199.         else iter++;
  200.      }
  201. }
  202. //duè metà del vettore vengono ordinate separatamente e poi
  203. //fuse in modo da ottenere un vettore ordinato
  204. void merge_sort(float * V,int N){
  205.      float * tmp;
  206.      tmp=(float *)malloc(N*sizeof(float));
  207.      _mergesort(V,N,tmp);
  208.      free(tmp);
  209. }
  210. //funzioe che ordina il vettore v sfruttando il vettore tmp di appoggio
  211. //e riutilizzandolo nelle diverse istanze
  212. void _mergesort(float * V,int N,float * tmp){
  213.      if(N>2){
  214.           _mergesort(V,N/2,tmp);
  215.           _mergesort(&V[N/2],N-N/2,&tmp[N/2]);
  216.           merge(V,N,N/2);
  217.      }
  218.      else{
  219.           if(V[0]<V[1]){
  220. //              _swap(V,0,1);
  221.           }
  222.      }
  223. }
  224. //funzione che fonde i due semi-vettori ordinati di V di lunghezza Nl e N-Nl
  225. void merge(float * V,int N,int Nl){
  226.      int l,r,count;
  227.      float * tmp;
  228.      tmp=(float *)malloc(Nl*sizeof(int));
  229.      for(count=0;count<Nl;count++)
  230.           tmp[count]=V[count];
  231.      
  232.      l=0;
  233.      r=0;
  234.      while(l<Nl && r<N-Nl){
  235.          if(tmp[l]<V[Nl+r]){
  236.              V[l+r]=tmp[l];
  237.              l++;
  238.          }
  239.          else{
  240.               V[l+r]=V[Nl+r];
  241.               r++;
  242.          }
  243.      }
  244.      while(l<Nl){
  245.           V[l+r]=tmp[l];
  246.           l++;
  247.      }
  248.      free(tmp);
  249. }
  250.  
  251. //considera un pivot e porta gli elementi minori a sx e i maggiori a dx.
  252. void quicksort(float * V,int N){
  253.      int q;
  254.      q=partition(V,N);
  255.      quicksort(V,q-1);
  256.      quicksort(&V[q+1],N-q-1);
  257. }
  258.  //considera il pivot e riordina i valori del vettore maggiori e minori ad esso
  259.  //e spostando il pivot in posizione tale dove alla sua sinistra risulteranno solo
  260.  //elementi minori ad esso
  261. int partition(float * V,int N){
  262.     int l;
  263.     int r;
  264.     float pivot;
  265.     pivot=V[0];
  266.     l=0;
  267.     r=N;
  268.     while(l<r)
  269.     { do { r--; } while(V[r]>pivot && r>l);
  270.        if(r!=l)
  271.        { do{ l++;} while (V[l]<=pivot && l<r);
  272. //         _swap(V,l,r);
  273.        }
  274.     }
  275. //    _swap(V,l,0);
  276.     return l+1;
  277. }
  278.    
  279.  
  280. //funzioni di swap
  281.  void swap(int * Perm,int a,int b){  //lavoro con puntatori                
  282.       int temp = Perm[a];        
  283.       Perm[a]=Perm[b];
  284.       Perm[b]=temp;
  285.  }
  286.  
  287.  
  288. //funzioni di stampa dei vettori        
  289. void printArray(float * V, int N){
  290.   int count;
  291.   for(count=0;count<N;count++)
  292.     printf("\n V[%d]=%4.2f",count,V[count]);
  293. }
  294.  
  295. void printPermutatedArray(float * V, int N, int * Perm){
  296.       int count;
  297.       for(count=0;count<N;count++)
  298.         printf("\n V[%d]=%4.2f",count,V[Perm[count]]);
  299. }


PM Quote
Avatar
andrea.b89 (Ex-Member)
Pro


Messaggi: 129
Iscritto: 03/03/2009

Segnala al moderatore
Postato alle 17:46
Mercoledì, 04/03/2009
Ciao ^^
Io ho analizzato il tuo codice. Il problema presente nel bubble sort e negli altri sort è che tu accedi ad un vettore, Perm, che non è inizializzato.
Nonostante tu lo crei allocando la memoria necessaria con la funzione malloc() non sistemi i valori contenuti al su interno quindi ti trovi dei valori "casuali" che eccodono i limiti del vettore.
Quindi dovresti inizializzare il vettore Perm prima di applicare gli sort proprio come fai nel selection sort.

Codice sorgente - presumibilmente Plain Text

  1. for(count = 0;count<N;count++)
  2.             Perm[count]= count;



quindi potresti mettere il codice appena illustrato prima di chiamare una delle funzioni di ordinamento, Io personalmente, per chiarezza, ti consiglio di metterle appena dopo l'allocazione del vettore.

Spero di essere stato chiaro :k:

PM Quote
Avatar
danis486 (Normal User)
Newbie


Messaggi: 9
Iscritto: 04/03/2009

Segnala al moderatore
Postato alle 18:18
Mercoledì, 04/03/2009
Perfetto...avrei bisogno di un altro paio di chiarimenti se ti è possibile...sei autorizzato a mandarmi a quel paese XD XD :heehee::heehee::heehee:
1)dovrei virtualizzare un vettore,cioè devo inserire dentro Perm gli indici di V in modo che quando devo visualizzare il vettore v ordinato seguo gli indici contenuti in Perm per poter vedere gli elementi che stanno in V ordinati.
Sto cercando di inserirli nel merge sort e nel quick sort ma poichè la ricorsione non è il mio forte penso sbaglio proprio là,ed inoltre ottengo un bel segmentation fault nel quick sort e facendo un debug mi risulta nel comando PIVOT = V[0].
Sarebbe il massimo finire entro stasera.......XD XD ti ringrazio8-|8-|8-|

questo è il quick sort modificato per il vettore Perm da sostituire a quello del codice precedente

Codice sorgente - presumibilmente C#

  1. void quicksort(float * V,int N,int * Perm){
  2.      int q;
  3.      q=partition(V,N,Perm);
  4.      quicksort(V,q-1,Perm);
  5.      quicksort(&V[q+1],N-q-1,Perm);
  6. }
  7.  //considera il pivot e riordina i valori del vettore maggiori e minori ad esso
  8.  //e spostando il pivot in posizione tale dove alla sua sinistra risulteranno solo
  9.  //elementi minori ad esso
  10. int partition(float * V,int N,int * Perm){
  11.     int l;
  12.     int r;
  13.     float pivot;
  14.     l=0;
  15.     pivot=V[0];
  16.     r=N;
  17.     while(l<r)
  18.     { do { r--; } while(V[r]>pivot && r>l);
  19.        if(r!=l)
  20.        { do{ l++;} while (V[l]<=pivot && l<r);
  21.          swap(Perm,l,r);
  22.        }
  23.     }
  24.     swap(Perm,l,0);
  25.     return l+1;
  26. }



questo il merge sort modificato:
Codice sorgente - presumibilmente C++

  1. void merge_sort(float * V,int N,int * Perm){
  2.      float * tmp;
  3.      tmp=(float *)malloc(N*sizeof(float));
  4.      _mergesort(V,N,tmp,Perm);
  5.      free(tmp);
  6. }
  7.  
  8. //funzione che ordina il vettore v sfruttando il vettore tmp di appoggio
  9. //e riutilizzandolo nelle diverse istanze
  10. void _mergesort(float * V,int N,float * tmp,int * Perm){
  11.      if(N>2){
  12.           _mergesort(V,N/2,tmp,Perm);
  13.           _mergesort(&V[N/2],N-N/2,&tmp[N/2],Perm);
  14.           merge(V,N,N/2,Perm);
  15.      }
  16.      else{
  17.           if(V[0]>V[1]){
  18.               swap(Perm,0,1);
  19.           }
  20.      }
  21. }
  22.  
  23. //funzione che fonde i due semi-vettori ordinati di V di lunghezza Nl e N-Nl
  24. void merge(float * V,int N,int Nl,int * Perm){
  25.      int l,r,count;
  26.      float * tmp;
  27.      tmp=(float *)malloc(Nl*sizeof(int));
  28.      for(count=0;count<Nl;count++)
  29.           tmp[count]=V[count];
  30.      
  31.      l=0;
  32.      r=0;
  33.      
  34.      while(l<Nl && r<N-Nl){
  35.          if(tmp[l]<V[Nl+r]){
  36.     //         V[l+r]=tmp[l];
  37.                Perm[l+r]= l;
  38.              l++;
  39.          }
  40.          else{
  41.      //         V[l+r]=V[Nl+r];
  42.                 Perm[l+r]=Nl+r;
  43.               r++;
  44.              
  45.          }
  46.      }
  47.      while(l<Nl){
  48.    //       V[l+r]=tmp[l];
  49.                Perm[l+r]=l;
  50.           l++;
  51.          
  52.      }
  53.      free(tmp);
  54. }


PM Quote
Avatar
andrea.b89 (Ex-Member)
Pro


Messaggi: 129
Iscritto: 03/03/2009

Segnala al moderatore
Postato alle 18:39
Mercoledì, 04/03/2009
Farò il possibile ^^
Comunque secondo me il merge sort non è proprio il massimo, ma proverò a sistemartelo.
Eventualmente ti indico anche come lo farei io, ma poi spetterà a te decider ^^

PM Quote
Avatar
danis486 (Normal User)
Newbie


Messaggi: 9
Iscritto: 04/03/2009

Segnala al moderatore
Postato alle 18:44
Mercoledì, 04/03/2009
ti prego,il bello è che il prof nel libro ha inserito i primi due con la virtualizzazione e gli altri due (merge e quick senza),girando su internet a quanto pare sono io l'unico coglione che deve fare una cosa del genere e perdere una serata per un misero credito!Questa è l'università italiana...(stendiamo un velo pietoso).
Se riesci a modificarli fai pure basta che funzionino dopodichè una pizza come minimo!XD
Io ci sto provando da stamattina ma secondo me lavoro male con la ricorsione...e quindi esce tutto sballato.:hail::hail::hail::hail::hail::hail::hail:

PM Quote
Avatar
andrea.b89 (Ex-Member)
Pro


Messaggi: 129
Iscritto: 03/03/2009

Segnala al moderatore
Postato alle 18:49
Mercoledì, 04/03/2009
ah..come di capisco sono pure io all'università XD ma almeno il mio prof di algoritmi, il corso che sto frequentando in questo trimestre, è bravo ^^
in più ho appena fatto tutti gli algoritmi di ordinamento, dal quicksort, al mergesort ecc...
quindi dovrei riuscire a sistemarteli ^^

PM Quote
Avatar
danis486 (Normal User)
Newbie


Messaggi: 9
Iscritto: 04/03/2009

Segnala al moderatore
Postato alle 18:54
Mercoledì, 04/03/2009
mi raccomando con quella storia della virtualizzazione.Praticamente il vettore V l'algoritmo non lo deve modificare,semplicemente deve inserire in Perm l'indice degli elementi in ordine.
Per esempio,se V ha come terzo elemento il più piccolo,dentro Perm[0] ci metto 2 (perchè si parte da 0). Era per spiegarmi meglio...spero riusciate ad aiutarmi...altrimenti domani darò buca al prof che è la seconda volta che mi rimanda a casa per queste cose giusto perchè tanto esami da dare ce ne sono un paio XD XD!!!!:d:d:d:d:d

PM Quote
Avatar
andrea.b89 (Ex-Member)
Pro


Messaggi: 129
Iscritto: 03/03/2009

Segnala al moderatore
Postato alle 18:58
Mercoledì, 04/03/2009
sisi tranquillo avevo capito ^^

PM Quote
Avatar
danis486 (Normal User)
Newbie


Messaggi: 9
Iscritto: 04/03/2009

Segnala al moderatore
Postato alle 19:00
Mercoledì, 04/03/2009
madonna se stai a firenze e mi risolvi il problema ti offro una pizza...:D:D:D:rotfl::rotfl::rotfl:

PM Quote
Pagine: [ 1 2 ] Precedente | Prossimo