为什么堆排序的 C 实现会出现分段错误？

Question

我尝试在 gcc 和turboc 中执行此代码。在 GCC 中，它在运行时给出了分段错误错误，而在 Turbo 中，它在运行时再次给出了空指针分配错误。

我尝试追踪它，但我看不出问题出在哪里。

#include<stdio.h>

int heapsize;

void heapify(int a[],int i)
{
    int l=2*i,r=2*i+1,largest,temp;
    if(l<=heapsize && a[l]>a[i])
        largest=l;
    else
        largest=i;
    if(r<=heapsize && a[r]>a[largest])
        largest=r;
    if(largest!=i)
    {
        temp=a[i];
        a[i]=a[largest];
        a[largest]=temp;
        heapify(a,largest);
    }
}

void buildheap(int a[],int length)
{
    int i;  
    heapsize=length;    
    for(i=length/2;i>=0;i--)
        heapify(a,i);
}

void heapsort(int a[],int length)
{
    int i,temp; 
    buildheap(a,length);
    for(i=length-1;i>=1;i++)
    {
        temp=a[0];
        a[0]=a[i];
        a[i]=temp;
        heapsize--;         
        heapify(a,0);   
    }
}

void main()
{
    int a[20],i,length;
    printf("ENTER THE SIZE OF YOUR ARRAY:");
    scanf("%d",&length);
    printf("ENTER THE ARRAY ELEMENTS: \n");
    for(i=0;i<length;i++)
        scanf("%d",&a[i]);
    heapsort(a,length);
    printf("THE SORTED ARRAY IS:");
    for(i=0;i<length;i++)
        printf("%d /t",a[i]);
}

注意：我使用 CLRS 中给出的堆排序算法对此进行了编码。

编辑：这是我给出的输入和我得到的错误。

chaitanya@chaitanya-laptop:~/Desktop/My prog$ ./a.out
输入阵列的大小：5
输入数组元素：
9
5
8
7
6
分段错误

编辑：显然是 i++ 而不是 i-- 的愚蠢错误导致了问题。但现在似乎存在逻辑错误，因为程序没有给出排序后的数组作为输出。

输入阵列的大小：5
输入数组元素：
2
4
3
1
9
排序后的数组为：3013077 4 1 9 2

Answer 1

下面的 for 循环永远不会终止。索引不断增加导致数组越界，这就是您收到上述错误的原因。

for(i=length-1;i>=1;i++)
{
    temp=a[0];
    a[0]=a[i];
    a[i]=temp;
    heapsize--;         
    heapify(a,0);   
}

更新：你的 heapify() 不正确..试试这个

if(l<heapsize && a[l]>a[i])
    largest=l;
else
    largest=i;
if(r<heapsize && a[r]>a[largest])
    largest=r;

Answer 2

在 heapsort 函数中，您应该在 for 循环中使用 i-- 而不是 i++。

Answer 3

• 如果用户输入的 length 大于 20，您肯定会溢出 a
• heapsort 函数永远不会终止，因为 i不断增长。增长。您应该使用 i-- 来代替。
• 最后的 printf 输出 /t，而不是制表符。将其更改为 \t

这些至少应该让您克服段错误，尽管排序看起来仍然不正确。