c - 指向指针的指针段错误

Question

我创建了一个插入排序方法，它接受一个数组、它的大小和一个比较器。比较器函数是这样的:

int compare_int_ptr(void* ptr1, void* ptr2) {
  double i1 = *(double*)ptr1;
  double i2 = *(double*)ptr2;
  if(i1<i2) {
    return -1;
  }
  if(i1 == i2) {
    return 0;
  }
  return 1;
}

插入内容是这样的:

void insertion_sort(void** array, int size, CompFunction compare){
    int i,j;
    void* key;
    for(i = 1; i<size;i++){
        key = array[i];
        for(j = i-1; j>=0 && compare(array[j],key)>=0;j--){
            swap(&array[j+1],&array[j]);
        }
        array[j+1] = key;
    }
}

如果我尝试执行它，我会收到段错误错误，因此我认为我没有正确使用指针。当我进行交换时，我用 & 传递它，这是否正确？

编辑:这是我调用该方法的地方:

int main(int argc, char const *argv[]) {
    if(argc < 2) {
        printf("Usage: sortingfirstusage <file_name>\n");
        exit(EXIT_FAILURE);
      }
      double* array = load_array(argv[1]);
      insertion_sort((void**)array, 3, compare_int_ptr);
      free(array);
      return 0;

数组已正确加载，因为我在调用插入排序之前打印了所有元素并且它们已在其中。

Answer 1

您正在尝试对 double 组进行排序。 double *array 指向 n 个元素中的第一个:

array ==> [ double ]  \
          [ double ]  |
              .        > n elements
              .       |
          [ double ]  /

您正在将 array 转换为 void **:

(void **)array ==> [ void * ]  \
                   [ void * ]  |
                       .        > n elements
                       .       |
                   [ void * ]  /

不难判断前方有麻烦。 void * 不是 double。它的大小可能与 double 相同，也可能不同。它几乎肯定不会指向有效的内存位置，因此如果您取消引用它，您将调用未定义的行为，几乎肯定会导致您的程序被信号杀死。不幸的是，您的 insertion_sort 函数在调用比较函数时确实取消引用它:

        key = array[i];
        for(j = i-1; j>=0 && compare(array[j],key)>=0;j--){

array[i] 和 array[j] 都是无效的 void * 值(因为底层内存包含 doubles，而不是 void *s)。您的比较函数在此处取消引用它们:

  double i1 = *(double*)ptr1;
  double i2 = *(double*)ptr2;

ptr1 和 ptr2 包含无意义的指针值。它们不指向 double 。取消引用它们会调用未定义的行为。

<小时/>

这是 insertion_sort 的工作版本，它使用与 C 标准库中的 qsort 函数相同的函数类型和等效功能(尽管该函数的效率要低得多)比qsort):

insertion_sort.h:

#ifndef INSERTION_SORT_H_INCLUDED__
#define INSERTION_SORT_H_INCLUDED__

#include <stddef.h>

void insertion_sort(void *base, size_t nmemb, size_t size,
        int (*compar)(const void *, const void *));

#endif

insertion_sort.c:

#include <string.h>
#include "insertion_sort.h"

void insertion_sort(void *base, size_t nmemb, size_t size,
        int (*compar)(const void *, const void *))
{
    char (*b)[size] = base;
    size_t i;
    size_t j;
    int cmp;

    for (i = 1; i < nmemb; i++) {
        j = i - 1;
        /* search backwards for insertion point */
        while ((cmp = compar(b + j, b + i)) > 0 && j > 0)
            j--;
        if (cmp <= 0)
            j++;    /* went back one too far */
        if (j < i) {
            /* rotate element i to position j, j to j+1, ..., i-1 to i */
            char tmp[size];

            memcpy(&tmp[0], &b[i][0], size);
            memmove(&b[j + 1][0], &b[j][0], size * (i - j));
            memcpy(&b[j][0], &tmp[0], size);
        }
    }
}

下面是上述函数的使用示例:

ma​​in.c:

#include <stdio.h>
#include "insertion_sort.h"

int compar_double(const void *a, const void *b)
{
    double d1 = *(const double *)a;
    double d2 = *(const double *)b;

    if (d1 < d2)
        return -1;
    if (d1 > d2)
        return 1;
    return 0;
}

void print_doubles(const double *d, size_t n)
{
    size_t i;

    for (i = 0; i < n; i++)
        printf("%g\n", d[i]);
}

int main(void)
{
    double numberlist[] = { 3.0, 1.0, 5.0, -4.0, 2.0 };
    size_t len = sizeof numberlist / sizeof numberlist[0];

    printf("Unsorted:\n");
    print_doubles(numberlist, len);
    printf("\n");
    insertion_sort(numberlist, len, sizeof numberlist[0], compar_double);
    printf("Sorted:\n");
    print_doubles(numberlist, len);
    return 0;
}

这是上述程序产生的输出:

Unsorted:
3
1
5
-4
2

Sorted:
-4
1
2
3
5