C - 数组计数排序分段错误

Question

您好，我正在尝试使用计数排序对从文件中读取的数字进行排序。 这是我的代码：

    void CountingSort(int array[], int k, int n)
{
    int i, j;
    int B[100], C[1000];
    for (i = 0; i <= k; i++)
    {
        C[i] = 0;
    }
    for (j = 1; j <= n; j++)
    {
        C[array[j]] = C[array[j]] + 1;
    }
    for (i = 1; i <= k; i++)
    {
        C[i] = C[i] + C[i-1];
    }
    for (j = 1; j <= n; j++)
    {
        B[C[array[j]]] = array[j];
        C[array[j]] = C[array[j]] - 1;
    }
    printf("The Sorted array is : ");
    for (i = 1; i <= n; i++)
    {
        printf("%d ", B[i]);
    }
}

void max(int array[],int *k,int n){
    int i;
    printf("n je %dn",n);
    for (i = 0; i < n; i++)
    {
        if (array[i] > *k) {
            *k = array[i];
        }
    }
}
int main(int brArg,char *arg[])
{
    FILE *ulaz;
    ulaz = fopen(arg[1], "r");
    int array[100];
    int i=0,j,k=0,n,x,z;

    while(fscanf(ulaz, "%d", &array[i])!=EOF)i++;
    fclose(ulaz);
    n=i;
    max(array,&k,n);
    printf("Max je %dn",k);
    CountingSort(array,k,n);
    return 0;
}

我没有错误，

但是当我启动程序时，我收到分段错误错误。 请帮忙！（不要阅读这个机器人要求我写更多细节，但我没有，所以我只是写一些随机单词，这样我就可以发布我的问题并希望得到答案）

Answer 1

问题是计数排序的实现不正确：它使用数组，就好像它们是从 1 开始的，而在 C 中它们是从零开始的。

在仔细检查循环并修复使用1..k、包含for循环而不是正确0..k-1的所有情况后，代码开始正常工作：

int i, j;
int B[100], C[1000];
for (i = 0; i <= k; i++){
     C[i] = 0;
}
for (j = 0; j < n; j++){
     C[array[j]]++;
}
for (i = 1; i <= k; i++){
     C[i] += C[i-1];
}
for (j = 0; j < n; j++) {
  B[--C[array[j]]] = array[j];
}
printf("The Sorted array is : ");
for (i = 0; i < n; i++) {
   printf("%d ", B[i]);
}

演示。

注意：我修改了一些操作以使用 C 样式的复合赋值和递增/递减，例如 C[array[j]]++代替C[array[j]] = C[array[j]] + 1等。

Answer 2

问题很可能在这里

int B[100], C[1000]; // C has space for numbers up to 999
...
for (i = 1; i <= k; i++)
    C[i] = C[i] + C[i-1]; // adding up till C[k] == sum(array)
for (j = 0; j < n; j++)
    B[C[array[j]]] = array[j]; // B has space up to 99, but C[k] is sum(array)

因此，您为最高值 999 的 C 保留空间，但在B中，您假设所有输入值的总和小于 100...

问题的解决方案是首先探测输入数组并获取所有输入值的最大值和总和（如果范围可能为负值，则为最小值）并相应地分配空间

编辑：你可能的意思是j < n而不是j <= n

Answer 3

补充达斯布林肯莱特的准确答案：

您的输入数据是否保证在[0, 999]范围内？如果不是，很明显，分段错误可能并且将会发生。假设 array 的最大值为 1000。 C声明为

int C[1000];

这意味着 C 的有效索引是0, 1, 2, ... 999 。但是，在某些时候，您将拥有以下内容：

C[array[j]] = ... /* whatever */

array[j] > 999，您将尝试越界内存访问。解决方案很简单：探测array的最大值，并通过malloc使用动态内存分配：

/* assuming k is the maximum value */
int * C = malloc((k + 1) * sizeof(int));

注意：另一种选择，也可以消除初始化循环使C的所有元素等于 0 的需要，即使用 calloc ，动态分配设置为 0 的内存。

// allocate C with elements set to 0
int * C = calloc(k + 1, sizeof(int);

另一个重要因素是运行索引的范围：您似乎忘记了 C 中的数组是从 0 开始索引的。要遍历长度K数组，您需要执行以下操作：

for (i = 0; i < K; ++i)
{ 
    processArray(array[i]); 
}

而不是

for (i = 1; i <= K; ++i)
{
    processArray(array[i]);
}