为何程序执行到case2、n=20时出现free(): invalid pointer错误？

我编写了一个程序，用于生成不同属性、不同大小的数组，对其进行冒泡排序（bubble-sort），统计比较次数和交换次数，并打印每种序列、每种大小的结果。程序能正常打印到“case 2, n = 20”的结果，之后就会因free(): invalid pointer错误终止。我原本以为是生成序列函数内的内存分配有误，但该函数内的检查并未触发，说明并非这个原因。

原代码 #

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

void generate_sequences (int **a, int n, int var)
{
    *a = (int*) malloc (n * sizeof(int));
    if (*a == NULL) {
        printf("memalloc fail\n");
        exit(1);
    }
    switch (var)
    {
        case 1:
            for (int i = 0; i < n; i++)
                (*a)[i] = i + 1;
            break;
        case 2:
            for (int i = 0, j = n; i < n, j >= 0; i++, j--)
                (*a)[i] = j;
            break;
        case 3:
            for (int i = 0, j = n; i < n, j >= 0; i++, j--)
                (*a)[i] = (i%2 == 0)? i + 1 : j;
            break;
        case 4:
            srand(time(NULL));
            for (int i = 0; i < n; i++)
                (*a)[i] = 1 + rand() % n;
            break;
        default:
            printf("invalid var\n");
            return;
    }
}

int compares = 0;
int swaps = 0;

bool compare (int x, int y)
{
    compares++;
    return x >= y;
}

void swap (int *x, int *y)
{
    swaps++;
    *x ^= *y;
    *y ^= *x;
    *x ^= *y;
}


void bubble_sort (int *a, int n)
{
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - i - 1; j++)
            if (compare(a[j], a[j + 1])) 
                swap(&a[j], &a[j + 1]);
}

int arith_mean (int *a, int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += a[i];
    sum /= n;
    return sum;
}

int main()
{
    int sizes[] = {10, 20, 50, 100};
    int *comps_num = calloc(4, sizeof(int));
    int *swaps_num = calloc(4, sizeof(int));
    int *a;
    for (int j = 1; j <= 4; j++)
    {
        printf("-------- case %d --------\n", j);
        for (int i = 0; i < 4; i++)
        {
            generate_sequences (&a, sizes[i], j);
            bubble_sort (a, sizes[i]);
            comps_num[i] = compares;
            swaps_num[i] = swaps;
            printf("n = %d:\n", sizes[i]);
            printf("comparisons = %d\n", compares);
            printf("swaps = %d\n", swaps);
            compares = 0;
            swaps = 0;
            free(a);
        }
        printf("average comps = %d\n", arith_mean(comps_num, 4));
        printf("average swaps = %d\n", arith_mean(swaps_num, 4));
    }
    free(comps_num);
    free(swaps_num);
    return 0;
}

问题根源 #

1. 数组越界写入：case 2和case 3的for循环使用了逗号表达式i < n, j >= 0，逗号表达式的结果取最后一个表达式的值，导致循环会持续到j >= 0。以n=20为例，i会遍历到20（数组下标仅到19），此时写入(*a)[i]会破坏malloc分配的内存块元数据，后续free时触发无效指针错误。
2. swap函数潜在风险：用异或实现交换时，若x和y指向同一地址（虽冒泡排序中不会出现，但属于不良实现）会导致值被清零。
3. srand调用时机错误：case 4中每次生成随机数组都调用srand(time(NULL))，若循环执行过快，会因时间戳重复生成相同随机序列。

修复方案 #

1. 修正循环条件：将case 2、case 3的循环条件改为i < n，确保只遍历数组的有效下标：

   // case 2修正后
   case 2:
       for (int i = 0, j = n; i < n; i++, j--)
           (*a)[i] = j;
       break;
   // case 3修正后
   case 3:
       for (int i = 0, j = n; i < n; i++, j--)
           (*a)[i] = (i%2 == 0)? i + 1 : j;
       break;
   

2. 改进swap函数：用临时变量替代异或，避免潜在问题：

   void swap (int *x, int *y)
   {
       swaps++;
       int temp = *x;
       *x = *y;
       *y = temp;
   }
   

3. 调整srand位置：在main函数开头仅调用一次srand(time(NULL))，移除case 4中的srand调用。

内容的提问来源于stack exchange，提问作者noko