Phân loại trong C: trao đổi con trỏ dẫn đến kết quả bất ngờ

Question

Vào đầu programm, tôi phân bổ bộ nhớ cho một mảng của char-con trỏ:

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

Sau đó, người dùng có thể nhập lên đến 20 chữ:

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

Sau đó tôi muốn sắp xếp mảng này. Nó hoạt động như mong đợi nếu tôi sử dụng chức năng trao đổi của tôi như sau:

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

Sau khi suy nghĩ qua chuyện này, tôi nhận thấy rằng đây là một sự lãng phí CPU vì tất cả tôi phải làm đã thực sự chuyển hướng các con trỏ đến chuỗi tương ứng. Vì vậy, tôi viết lại chức năng trao đổi của tôi:

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

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

Tuy nhiên, điều này sẽ không làm việc ở tất cả, kết quả rất bất ngờ, tôi không thể hiểu tại sao (Tôi đã thử một số cuộc gọi printf và không có điều gì) ... hiểu biết của tôi là rằng các con trỏ chỉ là chuyển hướng và do đó hoán đổi, giả sử bộ nhớ trông như thế này:

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

ý tưởng của tôi là để thay đổi con trỏ thay vì các mảng cho nỗ lực CPU tối thiểu (đây: con trỏ swap trong 100 với con trỏ ở 108):

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

Tôi đã cố gắng giải thích điều này kỹ càng nhất có thể và tôi xin lỗi nếu có quá nhiều lời giải thích. Tôi sẽ vui mừng nhất nếu ai đó có thể cho tôi cái nhìn sâu sắc về điều này và giúp đỡ!

Mã đầy đủ (với strcpy làm việc) có thể được tìm thấy ở đây: http://pastie.org/5361481

Answer 1

chức năng sắp xếp của bạn nên kết thúc lên trông như thế này:

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

Tôi nghi ngờ rằng bạn đã không làm cho các trục là char**, nhưng để lại dưới dạng char*. Nếu bạn làm điều đó, sau đó bất cứ khi nào bạn thực hiện trao đổi, bạn không thực sự trao đổi hai phần tử trong mảng của bạn, mà thay vào đó trao đổi một phần tử của mảng với một biến cục bộ. Biến pivot kết thúc bằng cách trỏ đến một chuỗi khác thay vì thành viên mảng cuối cùng trỏ đến một chuỗi khác.

Answer 2

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

Đây là vấn đề của bạn. Bạn không muốn trao đổi con trỏ với biến cục bộ của bạn, nhưng với phần tử trục thực tế trong mảng (có thể là args+end). working example here