Esercizio: quicksort applicato a stringhe

di Anonimizzato16393 il
7 risposte
/
Anonimizzato16393
Utente anonimizzato
Come dal titolo devo creare un programma che utilizzi la procedura del quicksort per ordinare un array bidimensionale di stringhe.

il codice che ho creato è questo:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void swap (char **a,int i, int j) {
  char temp[1001];
  strcpy(temp,a[i]);
  strcpy(a[i],a[j]);
  strcpy(a[j],temp);
}
int distribuzione(char **a, int sx, int px, int dx) {
  int i; int j; char x[1001];
  if (px != dx){
   swap (a,px,dx);
  }
   strcpy(x,a[dx]);
   i=sx-1;
  for(j=sx;j<dx;j++){
      if ((strcmp(a[j],x)==0) || ((strcmp(a[j],x)<0)))
     {
      i=i+1;
      swap(a,i,j);
    }
  }
  i++;
  swap(a,i,dx);
  return i;
}

void quicksort( char **a, int sx, int dx ) {
  int perno,pivot;
  if( sx < dx ) {
    pivot =sx + rand() % (dx-sx+1);
    perno = distribuzione(a, sx, pivot, dx);
    quicksort(a, sx, perno-1);
    quicksort(a, perno+1, dx);
  }
}

void legge(char **a, int len) {
  int i;
  scanf("%d",&len);
  a = malloc(len*sizeof(char*));
  for(i=0;i<len;i++){
	a[i]=malloc(101*sizeof(char));
	  scanf("%s",a[i]);
  }
}

int main() {
  int i, n;
  char **A;
  legge(A,n);
  quicksort(A, 0, n);
  for(i=0;i<n;i++){
    printf("%s\n", A[i]);
  }
  return 0;
}
solo che non mi da nessun risultato alla fine dell'esecuzione...qualcuno sa come aiutarmi?

7 Risposte

  • Super Famoso
    Iscritto da
    nov, 2011
    Messaggi
    21917
    Intanto per acquisire i dati nell'array, devi passare gli argomenti per puntatore, altrimenti non potrai modificarli e quindi non avrai i valori corretti nel main. Dunque dovrà essere
    
  legge(&A, &n);
    e di conseguenza la funzione legge dovrà essere
    
void legge(char ***a, int *len) {
  int i;
  scanf("%d",len);
  (*a) = (char **)malloc((*len)*sizeof(char*));
  for(i=0;i<(*len);i++){
   (*a)[i]=(char *)malloc(101*sizeof(char));
   scanf("%s",(*a)[i]);
  }
}
    In secondo luogo, la chiamata alla funzione di ordinamento dovrà prevedere n-1 elementi, ovvero
    
  quicksort(A, 0, n-1);
  • /
    Anonimizzato16393
    Utente anonimizzato
    Funziona grazie

    ma non capisco questo che hai scritto:
    void legge(char ***a, int *len) {
  int i;
  scanf("%d",len);
  (*a) = (char **)malloc((*len)*sizeof(char*));
  for(i=0;i<(*len);i++){
   (*a)[i]=(char *)malloc(101*sizeof(char));
   scanf("%s",(*a)[i]);
  }
}
    perchè a ha 3 asterischi se è un array bidimensionale? e sopratutto perchè "len" deve essere un puntatore? cioè in altri es che ho fatto io tutto questo non lo facevo eppure funzionavano...

    sono alle prime armi capiscimi se ho ancora questi dubbi
  • Super Famoso
    Iscritto da
    nov, 2011
    Messaggi
    21917
    perchè a ha 3 asterischi se è un array bidimensionale?
    Perché ti ho detto che il puntatore doppio A che c'è nel main deve essere passato per puntatore se lo devi usare come argomento. E quindi un puntatore doppio passato per puntatore diventa un puntatore triplo.
    perchè "len" deve essere un puntatore?
    Per lo stesso motivo di prima ... len sta nel main, ti domando : come lo modifichi in una funzione se non lo passi per puntatore?
  • /
    Anonimizzato16393
    Utente anonimizzato
    Di solito io metto solo la variabile...
  • Super Famoso
    Iscritto da
    nov, 2011
    Messaggi
    21917
    Cioè? Con quale codice?
  • /
    Anonimizzato16393
    Utente anonimizzato
    Ahhhh ho capito mi sono confuso io...io intendevo tipo:
    #include <stdio.h>
#include <malloc.h>
int somma (int *a, int n) {
	int som=0;
	int i;
	for (i=0;i<n;i++) {
		som=som+a[i];
	}
return som;
}

int main() {
	int *a;
	int n,i,p;
	scanf("%d",&n);
	a=malloc(n*sizeof(int));
	for (i=0;i<n;i++) {
		scanf("%d",&a[i]);
	}
	p=somma(a,n);
	printf ("%d",p);
return 0;
}
    solo che qui "n" lo inizializzo prima della chiamata ricorsiva...giusto?
  • Super Famoso
    Iscritto da
    nov, 2011
    Messaggi
    21917
    1) Quella funzione non è ricorsiva

    2) Il fatto non è che la variabile è inizializzata ma che l'argomento non è usato per restituire un risultato
Devi accedere o registrarti per scrivere nel forum
7 risposte