0

我正在尝试在 C 中使用来自 Numerical Recipes (NR) 的 indexx() 算法，并发现了一个非常奇怪的错误。

（NR 在此处公开：http ://www2.units.it/ipl/students_area/imm2/files/Numerical_Recipes.pdf第 338 页，第 8.4 节）

该函数应输出与输入浮点数组的元素相对应的索引数组，从低到高排序。

下面是一个最小的工作示例，显示该算法似乎忽略了前两个元素。输出数组的前两个元素始终为 0，后跟数组的长度（本例中为 9）。其余元素似乎已正确排序。

哦，我试图在 NR 论坛上提问，但我的帐户已等待很长时间才能激活...提前非常感谢！

[编辑数组名称]

#include "nr_c/nr.h"

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


int main()
{
    float unsorted[9] = {4., 5., 2., 6., 3., 8., 1., 9., 7.};
    long unsigned int sort[9];

    printf("Unsorted input array:\n");
    for (int i=0; i<9; i++) {
        printf("%.1f  ", unsorted[i]);
    }
    printf("\n\n");

    indexx(9, unsorted, sort);

    printf("Indexx output array:\n");
    for (int i=0; i<9; i++) {
        printf("%d    ", sort[i]);
    }
    printf("\n\n");

    printf("Should-be-sorted array:\n");
    for (int i=0; i<9; i++) {
        printf("%.1f  ", unsorted[sort[i]]);
    }
    printf("\n\n");

    return 0;
}

输出：

Unsorted input array:
4.0  5.0  2.0  6.0  3.0  8.0  1.0  9.0  7.0  

Indexx output array:
0    9    6    2    4    1    3    8    5    

Should-be-sorted array:
4.0  0.0  1.0  2.0  3.0  5.0  6.0  7.0  8.0
4

1 回答 1

1

Numerical Recipes C 代码使用从 1 开始的索引。（因为它的 FORTRAN 起源，第一个版本是用 FORTRAN 编写的，fortran 对数组和矩阵使用基于 1 的索引。C 版本可能基于...的输出f2c）在问题的原始代码中，indexx()函数忽略unsorted[]和 sort[]数组的第一个元素。另外：它访问数组的最后一个元素之外的一个（导致 UB）因此，索引数组中存在 0 和 9。（最初0的其实是未初始化的内存，但没有被indexx()函数触及）

如果我的假设是正确的，那么以下应该有效：

#include "nr_c/nr.h"

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


int main()
{
    float unsorted[9] = {4., 5., 2., 6., 3., 8., 1., 9., 7.};
    long unsigned int sort[9];

    printf("Unsorted input array:\n");
    for (int i=0; i<9; i++) {
        printf("%.1f  ", unsorted[i]);
    }
    printf("\n\n");

    indexx(9, unsorted-1, sort-1); // <<-- HERE

    printf("Indexx output array:\n");
    for (int i=0; i<9; i++) {
        printf("%d    ", sort[i]);
    }
    printf("\n\n");

    printf("Should-be-sorted array:\n");
    for (int i=0; i<9; i++) {
        printf("%.1f  ", unsorted[sort[i]-1]); // <<-- AND HERE
    }
    printf("\n\n");

    return 0;
}

该numerical recipes in C代码假定基于 1 的索引：一个 N 大小的数组具有索引1..N。这样做是为了不让数学家感到困惑。（结果，整整一代程序员都被搞糊涂了）分配函数是对 的包装器malloc()，它通过返回指向-1已分配空间的第 th 个成员的指针来作弊。对于float向量，这可能类似于：

#include <stdlib.h>

float * float_vector(unsigned size)
{
float * array;
array = calloc( size, sizeof *array);
if (!array) return NULL;
return array -1;
}
于 2017-01-05T18:05:48.963 回答