C比较排序比较时分段错误

Question

我只是最近开始在C编程，我遇到了一些比较排序算法的麻烦。我将发布下面的代码，但基本上我有三个独立的比较函数，可以帮助对一个unsigned int数组进行排序。

第一个比较函数按升序排序，第二个按降序排序，第三个是根据int的二进制表示中1的个数进行排序 - 这是这三个中最后一个给出的结果我的分段错误。

想法？

#include <stdlib.h> 
#include <stdio.h> 
#include <stdint.h> 
#include <sys/types.h> 
#include <time.h> 
#include <unistd.h> 

/* ASIZE is the size of the array to sort (number of 32-bit integers) */ 
#define ASIZE 100 
/* NFCNS is the number of different sort functions defined in the comp array */ 
#define NFCNS 3 

/* defines the type compare_fcn to be a pointer to a function that takes two 
* constant void pointers and returns an integer. */ 
typedef int (*compare_fcn)(const void *, const void *); 

/* randomly permute the elements in an array of size 32-bit integers. 
* Permutation is done in place. */ 
void shuffle(uint32_t *a, int size) { 
    int i = 0; /* Scratch */ 

    /* Seed the random number generator with the current time. Since time(2) 
    * returns a time_t, the code casts it properly. */ 
    srandom((unsigned int) time(NULL)); 

    /* Permute the elements */ 
    for (i = 0; i<size; i++) { 
    int j = random() % size; 
    int k = random() % size; 
    int tmp = 0; 

    if (j == k) continue; 
    tmp = a[j]; 
    a[j] = a[k]; 
    a[k] = tmp; 
    } 
} 

/* Print the 32-bit array (of size integers) to stdout. Print the integers as 
* 3-digit, zero-padded integers, 10 integers to a line. */ 
void dump_array(uint32_t *a, int size) { 
    int i = 0; /* Scratch */ 

    for (i = 0; i < size; i++) { 
    if (i % 10 == 0) printf("\n"); 
    printf("%03d ", a[i]); 
    } 
    if ((size -1) % 10 != 0) printf("\n"); 
} 

/* 
* qsort comparison functions compare the data pointed to by two pointers. In 
* this program, the data is always interpreted as 32-bit, unsgned integers 
* (uint32_t's). Comparison functions need to cast the pointers into the right 
* type and carry out the comparison. The return value is <0 if the first data 
* should appear before the second, >0 if the first should appear after the 
* second, and 0 if there is no preference. 
*/ 

/* 
* Compare the elements pointed to b a and b to each other as 32-bit integers. 
*/ 
int compare_ab(const void *a, const void *b) { 
    const uint32_t *aa = (const uint32_t *) a; 
    const uint32_t *bb = (const uint32_t *) b; 
    return *aa - *bb; 
} 


int reverse_compare_ab(const void*a, const void *b){ 
    const uint32_t *aa = (const uint32_t *) a; 
    const uint32_t *bb = (const uint32_t *) b; 
    return *bb - *aa; 
} 

int compare_by_ones(const void*a, const void*b){ 
    const uint32_t *aa = (const uint32_t *) a; 
    const uint32_t *bb = (const uint32_t *) b; 

    int count1 = 0; 
    int count2 = 0; 

    for(int i = 0; i < 32; i++) 
    { 
     uint32_t temp1 = (uint32_t) *aa >> i; 
     uint32_t one = 0x01; 
     temp1 = temp1 & one; 
     if(temp1 == one) count1++; 

     uint32_t temp2 = (uint32_t) *bb >> i; 
     temp2 = temp2 & one; 
     if(temp2 == one) count2++; 
    } 

    return -(count2 > count1); 
} 

/* Definition of the array to sort */ 
uint32_t a[ASIZE]; 

/* Definition of the array of comparison functions */ 
compare_fcn comp[NFCNS]; 

/* 
* Main driver program. Initialize an array with the integers from 0-ASIZE, 
* permute it, and sort it with different comparisons. Print the initial 
* array, the permuted array, and each sort to stdout. 
*/ 
int main(int argc, char **argv) { 
    int i = 0;  /* Scratch */ 

    /* Initialize array and functions */ 
    for (i = 0 ; i < ASIZE; i++) 
    a[i] = i; 

    /* Initialize function table */ 
    comp[0] = compare_ab; 

    comp[1] = reverse_compare_ab; 

    dump_array(a, ASIZE); 

    /* Permute */ 
    shuffle(a, ASIZE); 
    dump_array(a, ASIZE); 

    /* Sorts */ 
    for (i=0; i < NFCNS; i++) { 
    qsort(a, ASIZE, sizeof(uint32_t), comp[i]); 
    dump_array(a, ASIZE); 
    } 
}  

Answer 1

正如其他评论者已经说过，您的代码至少有2个错误。

更明显的错误是，你没有初始化comp阵列的所有成员，所以这个循环：

for (i=0; i < NFCNS; i++) { 
    qsort(a, ASIZE, sizeof(uint32_t), comp[i]); 
    dump_array(a, ASIZE); 
} 

在其最后一次迭代访问comp[2]，这仍然是NULL。通过NULL指针调用函数是分段错误的直接原因。

不太明显的错误是，你compare_by_onesqsort比较返回0或-1，但从来没有1，因此产生的排序顺序将是不正确的（甚至是可预见的）。