C语言堆排序代码中length变量莫名被修改的问题求助

问题描述 #

编写C语言堆排序代码时遇到异常：未通过指针或引用操作length变量，也未将其声明为const，但它会莫名变为3，而它本应是10。

代码片段 #

#include<stdio.h>
#include<windows.h>

void HeapAdjust(int *a,int s,int length);
void swap(int *a,int m,int n);

int main(){
    int a[] = {99,19,2,98,103,3,9,20,78,201,88,9,23,46,77,59,67,69,75,38};

    /* 
      bug here 👇
    */
    int length = sizeof(a)/sizeof(a[0]);

    for(int i=length/2;i>=0;i--)
    {
        HeapAdjust(a,i,length);
    }

    for(int i=length;i>0;i--)
    {
        swap(a,0,i-1);
        HeapAdjust(a,0,i-2);
    }

    /* Show the result of Heap_sort */
    for(int i=0;i<length;i++)
    {
        printf("%d ",a[i]);
    }
    system("pause");
}

void HeapAdjust(int *a,int s,int length)
{
    int temp = a[s];
    for(int j=s*2;j<=length;j*=2)
    {
        if(j<length&&a[j+1]>a[j])
            j++;
        if(temp>=a[j])
            break;
        a[s] = a[j];
        s = j;
    }
    a[s] = temp;
}

void swap(int *a,int m,int n)
{
    int temp = a[m];
    a[m] = a[n];
    a[n] = temp;
}

问题原因 #

核心问题是数组越界访问覆盖了栈上的length变量内存：

1. 堆索引逻辑错误：当下标从0开始时，左孩子索引应为2*s+1，右孩子为2*s+2，但代码中用了j=s*2，直接导致索引超出数组有效范围。
2. 循环条件加剧越界：j<=length会让j达到数组元素个数（比如20），而数组最大有效索引是length-1（19），此时访问a[j]就是读写数组外的内存。
3. 内存布局影响：length变量在栈上的位置紧邻数组a，越界写入的内容直接覆盖了length的内存值，导致它被莫名修改为3。

修复方案 #

1. 修正堆调整的索引与循环逻辑 #

修改HeapAdjust函数的索引计算和边界判断，避免越界：

void HeapAdjust(int *a,int s,int length)
{
    int temp = a[s];
    // 左孩子索引修正为2*s+1，循环条件改为j<length
    for(int j=2*s+1;j<length;j=2*j+1)
    {
        // 右孩子存在且更大时，指向右孩子
        if(j+1<length&&a[j+1]>a[j])
            j++;
        if(temp>=a[j])
            break;
        a[s] = a[j];
        s = j;
    }
    a[s] = temp;
}

2. 修正主函数的堆调整调用参数 #

第二个循环中，HeapAdjust的第三个参数应改为i-1，确保堆的范围正确：

for(int i=length;i>0;i--)
{
    swap(a,0,i-1);
    // 参数修正为i-1，避免遗漏元素
    HeapAdjust(a,0,i-1);
}

3. 修正初始堆构建的循环起始值 #

初始堆构建应从最后一个非叶子节点开始，即length/2 -1：

// 起始值修正为length/2 -1，覆盖所有非叶子节点
for(int i=length/2 -1;i>=0;i--)
{
    HeapAdjust(a,i,length);
}

验证说明 #

修复后，堆排序逻辑完全正确，不会再出现数组越界，length变量的内存也不会被意外覆盖，能正常输出排序后的结果。

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