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，因此產生的排序順序將是不正確的（甚至是可預見的）。