C中排序算法的錯誤（基數排序的變異）

Question

我在學習C，我在網上閱讀了一些排序算法。 我試圖做出自己的排序算法，它看起來有點像基數排序。 Radix sort on Wikipedia。以下是我的排序算法的程序。

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

/* prints all elements of an array of n length */ 
void printArray(int *arr, int n){ 
    if (n < 0){ 
    return; 
    } else if (n == 0){ 
    printf("()\n"); 
    } else { 
    int i; 
    printf("(%d", arr[0]); 
    for(i=1; i<n; i++){ 
     printf(", %d", arr[i]); 
    } 
    printf(")\n"); 
    } 
} 

/* safe replacement for malloc. */ 
void *safeMalloc(int size) { 
    void *ptr = malloc(size); 
    if (ptr == NULL) { 
    printf("\nError: memory allocation failed....abort\n"); 
    printf("\nNot enough space for %d int numbers\n", size); 
    exit(-1); 
    } 
    return ptr; 
} 

/* safe replacement for realloc. */ 
int *resizeArray(int *arr, int newSize){ 
    int *ptr = realloc(arr, newSize*sizeof(int)); 
    if (ptr == NULL) { 
    printf("\nError: memory allocation failed....abort\n"); 
    exit(-1); 
    } 
    return ptr; 
} 

/* check if array is sorted */ 
void checkArray(int length, int *a){ 
    int i; 
    for(i=0; i<length-i; i++){ 
    if (a[i] > a[i+1]){ 
     printArray(a, length); 
     printf("Error in: %d\n", i); 
     return; 
    } 
    } 
} 

/*/////////////////////////////////////////////////// 
* /////////////// SORTING ALGORITHM //////////////// 
* ////////////////////////////////////////////////*/ 
void sort(int length, int a[], int digits){ 
    /* base case */ 
    if ((length <= 1) || (digits == 0)){ 
    return; 
    } 
    /* recursive case */ 
    /* declare variables */ 
    int i, j, digit, idx = 0, sum = 0; 
    int *copy[10], lengthCopy[10]; 
    for(i=0; i<10; i++){ 
    lengthCopy[i] = 0; 
    copy[i] = safeMalloc(sizeof(int)); 
    } 
    for(i=0; i<length; i++){ 
    /* get the n'th digit. Example: a[i]=12345 and digits=100 --> digit=3 */ 
    digit = (a[i]/digits)%10; 

    lengthCopy[digit]++; 
    if (lengthCopy[digit] > 1){ 
     resizeArray(copy[digit], lengthCopy[digit]); 
    } 
    copy[digit][lengthCopy[digit]-1] = i; 
    } 
    /* Get the values */ 
    for(i=0; i<10; i++){ 
    for(j=0; j<lengthCopy[i]; j++){ 
     copy[i][j] = a[copy[i][j]]; 
    } 
    } 
    /* fill in the elements of copy in the original array */ 
    for(i=0; i<10; i++){ 
    for(j=0; j<lengthCopy[i]; j++){ 
     a[idx] = copy[i][j]; 
     idx++; 
    } 
    /* copy[i] is no longer necessary, so free it */ 
    free(copy[i]); 
    } 

    for(i=0; i<10; i++){ 
    /* call recursive function */ 
    sort(lengthCopy[i], &a[sum], digits/10); 
    sum += lengthCopy[i]; 
    } 
} 

int getMax(int length, int a[]){ 
    int i, max = 1; 
    for(i=0; i<length; i++){ 
    while(a[i] > max*10){ 
     max *= 10; 
    } 
    } 
    return max; 
} 

int main(int argc, char *argv[]){ 
    int i, *a, length=20; 
    a = safeMalloc(length*sizeof(int)); 
    for(i=0; i<length; i++){ 
    a[i] = rand()%100; 
    } 
    sort(length, a, getMax(length, a)); 
    checkArray(length, a); 
    printArray(a, length); 
    free(a); 
    return 0; 
} 

現在，非常奇怪的事情時，我嘗試了我的計劃是，當我在主函數有發生分段錯誤：INT長度= 1000，但如果我輸入了：INT長度= 20 ;

我不知道這個錯誤來自哪裏。有人能幫我嗎？

由於提前，

帕特里克

附：對不起，我的英語，這不是我第一次languague;）

Answer 1

由於魯本斯的建議，使用Valgrind的帶你直接到錯誤：

==7369== Invalid write of size 4 
==7369== at 0x400991: sort (/tmp/t.c:77) 
==7369== by 0x400BF2: main (/tmp/t.c:118) 
==7369== Address 0x4de46e4 is 0 bytes after a block of size 4 free'd 
==7369== at 0x402FD9E: realloc (valgrind/coregrind/m_replacemalloc/vg_replace_malloc.c:661) 
==7369== by 0x4007AA: resizeArray (/tmp/t.c:33) 
==7369== by 0x40096A: sort (/tmp/t.c:75) 
==7369== by 0x400BF2: main (/tmp/t.c:118) 

你realloc後，不能您訪問舊陣列，你必須使用新的數組。由於某種原因，您的resizeArray函數返回新數組;忽略該返回值是一個錯誤。

現在，儘管存在這個錯誤，但您的程序仍然「有效」，但只是偶然。堆腐敗臭蟲就這樣討厭。