sortowanie C: wymiany wskazówek prowadzi do nieoczekiwanych wyników

Question

Na początku programowo, przydzielić pamięci dla tablicy char wskazówek:

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

Następnie użytkownik może wprowadzić do 20 słowy

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

Potem chcę posortować tę tablicę. To działa zgodnie z oczekiwaniami, jeśli mogę użyć funkcji wymiany następująco:

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]); 
    ... 
} 

Po myśli przez to, zauważyłem, że to była strata CPU, ponieważ wszystko, co musiałem zrobić, to faktycznie przekierowanie odnośniki do odpowiednich ciągów. Więc przepisał mój funkcję wymiany:

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

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

Jednak to nie będzie działać w ogóle, wyniki są bardzo niespodziewane, nie mogę zrozumieć, dlaczego (próbowałem kilka printf połączeń i etażerka) ... Mój Understanding że wskaźniki są po prostu przekierowany a więc zamieniłem, powiedzmy pamięć wygląda następująco:

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

Mój pomysł był do zmiany wskaźników zamiast tablic dla wysiłku minimum procesora (tu: wskaźnik wymiany w 100 ze wskaźnikiem w 108):

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

Próbowałem wyjaśnić to tak dokładnie, jak tylko mogłem i przykro mi, jeśli to zbyt wiele wyjaśnień. Byłbym bardzo zadowolony, gdyby ktoś mógł dać mi wgląd w to i pomóc!

pełny kod (z strcpy roboczego) można znaleźć tutaj: http://pastie.org/5361481

Answer 1

Twoja funkcja sortowania powinien wyglądać jak poniżej:

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); 
} 

Podejrzewam, że nie sprawiają, że sworzeń być char**, ale zostawił jako char*. Jeśli to zrobisz, to za każdym razem, gdy wykonasz zamianę, w rzeczywistości nie zamienisz dwóch elementów w swojej tablicy, a raczej zamienisz jeden element tablicy na zmienną lokalną. Zmienna przestawna wskazuje na inny łańcuch zamiast ostatniego elementu tablicy wskazującego inny ciąg.

Answer 2

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

To jest twój problem. Nie chcesz zamienić wskaźnika na zmienną lokalną, ale na rzeczywisty element przestawny w tablicy (który byłby args+end). working example here