[C] Problema di Segmentation Fault

[DiegoDrizzt1989]

Ciao a tutti, sono nuovo del forum, mi sono inscritto dopo aver provato e riprovato a risolvere un problema di segmentation fault di un piccolo programma in C.
Premetto che non è molto tempo che inserisco i puntatori nei codici C e l'approccio iniziale chiaramente non è dei migliori!!!
Comunque il programma riceve un array di dimensioni "dim" (dim viene inserita da tastiera).
La procedura "leggi" asseggna ai valori dell'array un numero randomico tra 1000 e -1000.
Successivamente la procedura distribuzione provvede a separare i numeri pari da quelli dispari, in pratica dopo la procedura nell'array saranno verranno prima tutti i numeri pari e successivamente tutti quelli dispari.
Infine tratto l'array come se fosse composto da due segmenti, il primo che comprende tutti i numeri pari e il secondo tutti quelli dispari, ordino entrambi i segmenti con una procedura di "QuickSort" anch'essa definita dentro il codice, senza utilizzare la "qsort" della libreria standard.

Compilo sotto linux con:

# gcc -o QSortPD.exe QSortPD.c

Quando vado ad eseguire il codice compilato con:

# ./QSortPD.exe

Mi chiede la dimensione dell'array, mi genera i valori randomici stampandomeli a video e successivamente viene il simpatico

segmentation fault

LISTATO

• #include<stdio.h>
  #include<stdlib.h>
  
  #define RANGE 1000
  
  void scambia(int *a, int *b)
  {
  int tmp= *a;
  *a = *b;
  *b = tmp;
  }
  
  int distribuzione(int A[], int sx, int px, int dx)
  {
  int i, j;
  if(px != sx)
  scambia(&A[sx], &A[px]);
  
  px=sx;
  
  for(i=sx, j=sx+1; j<dx; j++)
  if(A[j]<A[px])
  scambia(&A[++i],&A[j]);
  
  if(px != i)
  scambia(&A[px], &A[i]);
  
  return i;
  }
  
  void QuickSort (int A[], int sx, int dx)
  {
  int perno, pivot;
  if(sx<dx)
  {
  pivot = random()%(dx-sx+1);
  perno = distribuzione(A, sx, pivot, dx);
  
  QuickSort (A,sx,perno-1);
  QuickSort (A,sx,perno+1);
  }
  }
  
  void disposizione(int A[], int dim)
  {
  int i=0, j=dim;
  while(i != j)
  {
  if(A[i] % 2 != 0)
  {
  scambia(&A[i], &A[j]);
  j--;
  }
  else i++;
  }
  }
  
  int leggi(int **A, int *dim)
  {
  int i;
  
  printf("Quanti lementi deve contenere l'array?\n");
  scanf("%d", dim);
  if(*dim<=0) return 1;
  
  *A = (int*)malloc(sizeof(int)*(*dim));
  if(*A==NULL) return 1;
  
  for(i=0; i<*dim; i++)
  {
  *((*A)+i)= (random()%((RANGE*2)+1)-RANGE);
  printf("%d - %d\n", i, ((**A)+i));
  }
  return 0;
  }
  
  int main()
  {
  int i, cx=0, *A, dim;
  
  srand(time (NULL));
  
  leggi(&A, &dim);
  disposizione(A, dim);
  
  while((A[cx]%2)==0)
  cx++;
  
  QuickSort(A, 0, cx);
  QuickSort(A, cx+1, dim);
  
  return 0;
  }

[oregon]

A parte il fatto che hai usato la funzione random invece di rand, ma non ho avuto alcun problema in esecuzione ...

Sai come riprodurre l'errore (o la riga in cui si verifica)?

[YuYevon]

Beh esiste anche la funzione random(), anche se non capisco perché non usare rand()...

Comunque oregon sei sicuro di non avere problemi con l'esecuzione? Io anche ho un segmentation fault e mi pare pure ovvio considerando che queste due righe:

QuickSort (A,sx,perno-1);
QuickSort (A,sx,perno+1);

sono concettualmente sbagliate: una volta partizionato l'array, la sua parte sinistra va da sx a perno, mentre la sua parte destra va da perno + 1 a dx... quindi dovrebbe essere

QuickSort (A, sx, perno);
QuickSort (A, perno+1, dx);

inoltre:

1) queste due righe

int i=0, j=dim;

e

QuickSort(A, cx , dim);

vanno corrette rispettivamente con

int i=0, j=dim - 1;

e

QuickSort(A, cx , dim - 1);

perché dobbiamo considerare il fatto che l'indice di spiazzamento massimo per un array (in C) è pari al suo size meno 1...

2)

pivot = random() % (dx - sx + 1);

a parte che ti consiglio di usare la funzione rand(), quella riga dovrebbe essere

pivot = sx + rand() % (dx - sx + 1);

visto che l'intenzione è di generare un numero a caso tra sx e dx.

Apportando queste modifiche il programma non dovrebbe crashare più, ma in ogni caso l'output non è quello che ci si aspetta... ti consiglio di rivedere l'implementazione dell'algoritmo quicksort, tra l'altro quella mi sembra un po' contorta...

(PS: includi l'header time.h)

[oregon]

Ho solamente compilato ed eseguito ... non avendo rilevato alcun segmentation error (su Windows ...) non ho controllato il codice ...

Comunque YuYevon, ha perfettamente ragione ...

[DiegoDrizzt1989]

Ok grazie di tutto! in effetti ho fatto degli errori abbastanza stupidi, pensavo dipendesse dai puntatori e mi sono concentrato soprattutto su quelli, quando la cosa che era implementata male era il quick stesso, in ogni modo ora sembra che vada.
Il quick sort apparte i problemi segnalati da YuYevon (non pochi ma di distrazione) funziona, ho modificato soltanto sostituito due pezzi ma niente di che:

nella funzione distribuzione:
for(i=sx, j=sx+1; j<dx; j++)
con
for(i=sx, j=sx+1; j<= dx; j++)

e nella funzione QuickSort:
if(A[j] < A[px])
con
if(A[j] <=A[px])

Ho eliminato la funzione "leggi" implementandola nel main, perché mi dava alcuni problemi.

Per quanto riguarda la random(), la utilizzo al posto della rand() per il semplice fatto che all'università (primo anno di informatica) utilizzano random() invece che rand(), non so bene quale sia la differenza ma in fondo fanno la stessa cosa per quanto ho potutto vedere...

Grazie dell'aiuto, comunque il codice ora sembra andare:

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

#define RANGE 1000

void scambia(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}


int distribuzione(int A[], int sx, int px, int dx)
{
int i, j;
if(px != sx)
   scambia(&A[sx], &A[px]);
px=sx;
for(i=sx, j=sx+1; j<=dx; j++)
   if(A[j]<=A[px])
     {
      i++;
      scambia(&A[i],&A[j]);
    }
if(px != i)
   scambia(&A[px], &A[i]);
return i;
}


void QuickSort (int A[], int sx, int dx)
{
int perno, pivot;
if(sx<dx)
   {
   pivot =sx+random()%(dx-sx+1);
   perno = distribuzione(A, sx, pivot, dx);

   QuickSort (A,sx,perno-1);
   QuickSort (A,perno+1,dx);
   }
}


void disposizione(int A[], int dim)
{
int i=0, j=dim-1;
while(i != j)
   {
   if(A[i] % 2 != 0)
      {
      scambia(&A[i], &A[j]);
      j--;
      }
   else i++;
   }
}


int main()
{
int i, cx=0, *A, dim;
srand(time (NULL));

printf("Quanti elmenti deve contenere l'array?\n");
scanf("%d", &dim);
if(dim<=0) return 1;

A = (int*)malloc(sizeof(int)*dim);  
if(A==NULL) return 1;

for(i=0; i<dim; i++)
   {
   *(A+i)= (random()%((RANGE*2)+1)-RANGE);
   printf("%d - %d\n",  i, A[i]);
   }

disposizione(A, dim);
while((A[cx]%2)==0)
   cx++;
QuickSort(A, 0, cx-1);
QuickSort(A, cx, dim-1);
printf("Stampa degli elementi ordinati secondo specifiche\n");
for(i=0; i<dim;i++)
printf("%d - %d\n", i, A[i]);
return 0;
}

[mondobimbi]

Originariamente inviato da DiegoDrizzt1989

...
Compilo sotto linux con:

# gcc -o QSortPD.exe QSortPD.c

Quando vado ad eseguire il codice compilato con:

# ./QSortPD.exe

è bruttissimo ed inutile chiamare gil eseguibili linux con l'estensione .exe . In linux qualsiasiasi file può essere marcato come eseguibile con il comando

$chmod u+x nome_file

che rende il file appunto eseguibile per l'utente.

Vedo poi che lo esegui come root, anche questo sconsigliabile, prendi la abitudine a lavorare sempre come utente.

Inoltre gli eseguibili normalmente vanno inseriti nella directory $(HOME)/bin, quindi compila con

$ gcc -o $(HOME)/bin/QSortPD QSortPD.c

ed esegui con

$QSortPD

Infine inizia ad utilizzare il makefile che nel tuo caso potrebbe essere

CC=gcc

APPNAME=QSortPD

CFLAGS=
INCLUDE=

main=$(HOME)/../QSortPD.c

SRCFILES=$(main)

$(APPNAME) : $(SRCFILES) 
	   $(CC) $(CFLAGS) $(INCLUDE) $(SRCFILES) -o $(HOME)/bin/$(APPNAME)

ciao
sergio

[DiegoDrizzt1989]

Grazie delle dritte sulla compilazione nel mondo Linux, mondobimbi, in effetti non è da molto che utilizzo il pinguino per provare a fare qualche programmetto, anche io facevo parte dell'enorma casta di persone che usano Win (ogni tanto ammetto di usarlo ancora) prima di avvicinarmi all' open source...

Vabbè comunque gli esercizi per l'università non li considero proprio come programmi, ma rimangono semplici esercizi da tenere a portata di mano sulla "Scrivania", se creo qualche eseguibile che mi serve veramente allora lo inserisco nella home/bin/

Mi sarà utile cominciare ad utilizzare il makefile, in effetti non avevo ancora provato ;-)
Grazie ancora!

[YuYevon]

Originariamente inviato da DiegoDrizzt1989
anche io facevo parte dell'enorma casta di persone che usano Win (ogni tanto ammetto di usarlo ancora)

Non è che sia una colpa usare Windows eh... si può preferire un sistema operativo all'altro per un'infinità di motivi, ma non c'è certamente di che "vergognarsi" ad usare l'uno piuttosto che l'altro, non è una colpa che bisogna "ammettere"... in generale l'ideale sarebbe diventare almeno buon utenti di ogni sistema, e magari profondi conoscitori di alcuni di essi (detto da chi comunque preferisce *n?x da un po' di tempo).

Originariamente inviato da DiegoDrizzt1989
Vabbè comunque gli esercizi per l'università non li considero proprio come programmi, ma rimangono semplici esercizi da tenere a portata di mano sulla "Scrivania", se creo qualche eseguibile che mi serve veramente allora lo inserisco nella home/bin/

Mi sarà utile cominciare ad utilizzare il makefile, in effetti non avevo ancora provato ;-)
Grazie ancora!

Effettivamente, con tutto il rispetto per mondobimbi, non vedo l'utilità di ricorrere ad un makefile per un programma costituito da un solo file sorgente, che non richiede particolari opzioni o tempo per la compilazione. Imparare a utilizzare i makefile può essere utile, in ogni caso...

In quanto a questo

è bruttissimo ed inutile chiamare gil eseguibili linux con l'estensione .exe . In linux qualsiasiasi file può essere marcato come eseguibile con il comando

$chmod u+x nome_file

che rende il file appunto eseguibile per l'utente.

concordo pienamente! In *n?x "tutto è file", anche i programmi. Ti basta avere i permessi di esecuzione su di essi e puoi avviarli tranquillamente a prescindere dall'estensione che hanno.

Condivido anche il consiglio di lavorare sempre come utente semplice quando non sono necessari i privilegi di root (e del resto chiunque sarebbe d'accordo).

[mondobimbi]

Originariamente inviato da YuYevon
...
non vedo l'utilità di ricorrere ad un makefile per un programma costituito da un solo file sorgente, che non richiede particolari opzioni ...

qualsiasi programma di una certa utilità, per quanto striminzito, avrà bisogno di sapere dove sono i file include, di richiamare librerie e per lo meno di essere compilato con le opzioni di debugging e senza, i filemake rendono la vita più semplice e prima si impara ad usarli meglio ci si troverà in futuro

ciao
sergio

[DiegoDrizzt1989]

Infatti nn ho dubbi sulla validità di tutti questi consigli, sono soltanto alle prime armi e per questo mi mancano diversi strumenti, ad esempio non saprei nemmeno come compilare programmi da utente semplice, a dire il vero credevo che non cambiasse niente, per quale motivo sarebbe così importante abituarsi a compilare come utente normale invece che come root? e soprattutto come faccio a passare da root ad utente semplice e viceversa?
Quando ho preso in mano linux, circa un mese e mezzo fa mi sono messo a "smanettare" sul terminale e vedere i comandi principali, ma la strada è sempre lunga :-)

Ah! approposito, come utilizzo il comando chmod u+x nome_file, ho provato a compilare una sorgente c in un file (senza estenzione questa volta, in effetti è squallido dare un estenzione .exe su linux)

gcc -o prova prova.c

e poi che faccio?

chmod u+x prova

non cambia niente... pur dandogli i permessi per eseguirlo come programma, non parte se non come facevo rpima cio con:

./prova