2012-11-11 11 views
7

All'inizio del programma, che allocare memoria per un array di char-puntatori:Marchio C: scambio puntatori porta a risultati inattesi

char **buffer = calloc(20, sizeof(char *));

Poi l'utente può inserire fino a 20 parole:

buffer[i] = calloc(40, sizeof(char)); 
fgets(buffer[i], 40, stdin)` 

Successivamente, desidero ordinare questo array. Esso funziona come previsto se uso la mia funzione di swap come segue:

void swap(char *args1, char *args2) { 
    char tmp[40]; 
    strcpy(tmp, args1); 
    strcpy(args1, args2); 
    strcpy(args2, tmp); 
} 

void sort(char **args, int count) { 
    ... 
    swap(args[i], args[j]); 
    ... 
} 

Dopo averci pensato attraverso questo, ho notato che si trattava di uno spreco di CPU dato che tutto quello che dovevo fare era in realtà reindirizzando i puntatori ai corrispondenti stringhe. Così ho riscritto la mia funzione di swap:

void swap(char **args1, char **args2) { 
    char *tmp = *args1; 
    *args1 = *args2; 
    *args2 = tmp; 
} 

void sort(char **args, int count) { 
    ... 
    swap(&args[i], &args[j]); 
    ... 
} 

Tuttavia, questo non funziona affatto, i risultati sono estremamente inaspettato, non riesco a capire perché (ho provato diverse chiamate printf e quant'altro) ... La mia comprensione era che i puntatori sono solo reindirizzati e quindi scambiati, diciamo la memoria è simile al seguente:

(begin of char**): 
100: *160 
108: *200 
116: *240 
124: *280 
... 
(begin of char*): 
160: Hello!\0 
200: World!\0 
... 

la mia idea era quella di modificare i puntatori al posto degli array per il minimo sforzo CPU (qui: puntatore di swap in 100 con puntatore in 108):

(begin of char**): 
100: *200 
108: *160 
116: *240 
124: *280 
... 
(begin of char*): 
160: Hello!\0 
200: World!\0 
... 

Ho cercato di spiegarlo nel modo più approfondito possibile e mi dispiace se è una spiegazione eccessiva. Sarei molto contento se qualcuno potesse darmi un'idea di questo e aiutare!

Il codice completo (con la strcpy di lavoro) può essere trovato qui: http://pastie.org/5361481

+0

E il codice completo per quello non funzionante? –

+0

Il codice non funzionante è solo con il metodo di sostituzione sostituito e chiama: http://pastie.org/5361515 – Danyel

+1

Prova a passare attraverso il codice, riga per riga, con un debugger (per un piccolo insieme di input, ovviamente). –

risposta

5

tua funzione di ordinamento dovrebbe finire per assomigliare a questo:

void sort(char ** args, const int start, const int end) { 
     char **pivot = &args[end]; 
     int i = start-1, j = start; 
     while(j < end) { 
       int cmp = strcmp(*pivot, args[j]); 
       if(cmp > 0) 
         swap(&args[++i], &args[j]); 
       j++; 
     } 
     swap(&args[++i], pivot); 
     if(start + 1 < i) 
       sort(args, start, i - 1); 
     if(end - 1 > i) 
       sort(args, i + 1, end); 
} 

ho il sospetto che non hai fatto il perno essere un char**, ma lo ha lasciato come char*. Se lo fai, allora ogni volta che fai lo swap, in realtà non stai scambiando due elementi nel tuo array, ma scambiando un elemento dell'array con una variabile locale. La variabile pivot finisce per puntare a una stringa diversa anziché all'ultimo membro dell'array che punta a una stringa diversa.

+0

Questo ha risolto il problema ma non capisco perché devo fare il pivot un 'char **' invece di un 'char *' – Danyel

+0

@Danyel: ho cercato di spiegarlo meglio. Fammi sapere se non è ancora chiaro. –

+0

Ohh, penso di averlo capito. :) Sì, ha senso, ma devo ripensarlo perché dopo aver pensato così tanto la testa inizia a dolere. : D – Danyel

3
char *pivot = args[end]; 
... 
    swap(&args[++i], &pivot); 

Questo è il vostro problema. Non si desidera scambiare il puntatore con la variabile locale, ma con l'effettivo elemento pivot dell'array (che sarebbe args+end). working example here

+0

Grazie, anche qualcun altro l'ha risolto. Questo era esattamente il problema! :) – Danyel