C语言 在堆中搜索元素后删除元素时出现分段错误

Question

下面的代码在堆中线性搜索元素 x 后从堆中删除该元素

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MaxSize 100001
struct minheap {
    long int a[MaxSize];
    int end;
};
void minHeapify(struct minheap *h, int i) {
    int largest;
    long int temp;
    int l=2*i+1;
    int r=2*i+2;
    largest=i;
    if(l<=(h->end) && (h->a[l])<(h->a[i]))
       largest=l;
    if(r<=(h->end) && (h->a[r])<(h->a[largest]))
       largest=r;
    if(largest!=i) {
       temp=h->a[i];
       h->a[i]=h->a[largest];
       h->a[largest]=temp;
       minHeapify(h,largest);
    }
}

int main() {
    long int x,i=0,temp=0;
    int N;
    int type;
    scanf("%d",&N);
    struct minheap h;
    h.end=-1;
    while(N--) {
        scanf("%d",&type);
        if(type==1) {
              scanf("%ld",&x);
              h.end=h.end+1;
              h.a[h.end]=x;
              i=h.end;
              while(i>0 && h.a[(i-1)/2]>h.a[i]) { //fix minheap on insertion
                  temp = h.a[(i-1)/2];
                  h.a[(i-1)/2]=h.a[i];
                  h.a[i]=temp;
                  i=(i-1)/2;
              }
        }
        else if(type==2) {
              scanf("%ld",&x);
              for(i=0;i<=h.end;i++) {
                  if(x == h.a[i])
                    break;
              }
              h.a[i]=h.a[h.end];
              h.end=h.end-1;
              if(i!=(h.end+1))
              minHeapify(&h,i);
        }
        else if(type==3) {
        printf("%ldn",h.a[0]);
        }
    }
 return 0;
}

但是下面的测试用例给出的分段错误为：

Program terminated with signal SIGSEGV, Segmentation fault.
#0  main () at solution.c:59
59                    if(x == h.a[i])
#0  main () at solution.c:59

完整的测试用例可以在此链接中找到：

https://hr-testcases-us-east-1.s3.amazonaws.com/15379/input04.txt?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1547134261&Signature=D%2B39%2BHr%2F4lRFV%2BetxFwnGWm1iac%3D&response-content-type=text%2Fplain

为什么会出现这种分段错误？

Answer 1

给定错误消息，

> Program terminated with signal SIGSEGV, Segmentation fault.
> #0  main () at solution.c:59 59                    if(x == h.a[i])
> #0  main () at solution.c:59

。表达式中i的值：if(x == h.a[i]) 可能超出范围。这会导致未定义的行为，在某些情况下似乎有效，而其他情况下则可能导致分段错误。

查看此行以获取可能的解决方案：

for(i=0;i<=h.a[h.end];i++)

调用此表达式时a.end的值是多少？

这里还可能存在问题：

while(i>0 && h.a[(i-1)/2]>h.a[i])

其中表达式：(i-1)/2是整数除法，将跳过值。

Answer 2

我在删除项目的代码中看到一些问题：

          for(i=0;i<=h.end;i++) {
              if(x == h.a[i])
                break;
          }
          h.a[i]=h.a[h.end];
          h.end=h.end-1;
          if(i!=(h.end+1))
          minHeapify(&h,i);

首先，如果未找到具有您输入的值的项目，您将遇到麻烦，因为i > h.end .您最终要么索引数组的末尾，要么删除最后一项。

更重要的是，您没有处理替换它的项目小于父项的情况。例如，考虑以下堆：

        1
    6       2
  7   8   3

如果删除值为 7 的节点，则值 3 将替换它：

        1
    6       2
  3   8

这不是一个有效的堆。您必须在堆中向上移动 3 才能创建：

        1
    3       2
  6   8

这里的关键是，如果要替换的项目与堆中的最后一个项目位于不同的子树中，则替换节点可能会小于被替换节点的父节点。

所以你的代码必须这样做：

h.a[i] = h.a[h.end];
h.end = h.end-1;
// here you have to:
// if (h.a[i] < parentOf(h.a[i]))
//    move it up the heap
// else
//    minHeapify(&h, i);