数组计数排序分段错误

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 %d\n",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 %d\n",k);
    CountingSort(array,k,n);
    return 0;
}

我没有错误，但是当我启动我的程序时，出现分段错误。请帮助！（不要看这个机器人要我写更多的细节，但我有 none 所以我只是写了一些随机词所以我可以 post 我的问题并希望得到答案）

Answer 1

最有可能是这里的问题

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)

所以您为 C 保留了 space，最高值为 999，但在 B 中，您假设所有输入值的总和小于 100。 ..

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

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

Answer 2

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

在仔细检查循环并修复所有使用 for 循环的情况后 1..k，包括在内，而不是正确的 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]);
}

Demo.

注意：我修改了一些操作以使用C风格的复合赋值和increments/decrements，例如C[array[j]]++ 代替 C[array[j]] = C[array[j]] + 1 等

Answer 3

添加到 dasblinkenlight 的正确答案：

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

int C[1000];

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

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

where array[j] > 999 因此您将尝试越界内存访问。解决方案很简单：探测 array 的最大值并通过 malloc:

使用动态内存分配

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

注意：另一种方法是使用 calloc，这也不需要初始化循环来使 C 的所有元素等于 0，动态分配内存设置为 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]);
}

数组计数排序分段错误

array counting sort segmentation fault

c

arrays

counting-sort