Ошибка сегментации при удалении элемента после поиска в куче - PullRequest
Новая
       23

Ошибка сегментации при удалении элемента после поиска в куче

0 голосов
/ 10 января 2019

Следующий код удаляет элемент 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("%ld\n",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 & Истекает = 1547134261 & Подпись = D% 2B39% 2BHr% 2F4lRFV% 2BetxFwnGWm1iac% 3D & реакция-контент- тип = текст% 2Fplain

Почему происходит ошибка сегментации?

Ответы [ 2 ]

0 голосов
/ 11 января 2019

Я вижу несколько проблем в вашем коде для удаления элемента: 

          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);
0 голосов
/ 10 января 2019

Учитывая сообщение об ошибке, 

> 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 является целочисленным делением и будет пропускать значения.

...