TBDW - Binarne Drzewa Wyszukiwawcze

Question

Hej, pracuję aktualnie nad zadaniem TBDW - Binarne Drzewa Wyszukiwawcze na Spoju. I nie mogę nigdzie znaleźć błędu w kodzie(SIGSEGV). Mój kod - https://ideone.com/AeZqYv. Jeśli widzicie jakieś dodatkowe błędy związane z zadaniem również proszę o podpowiedzi. Będę wdzięczny za każdą pomoc. Pozdrawiam ;)

Answer 1

wejście powodujące sigabrt: double free

wejście powodujące sigsev

Tutaj masz generator testów którym znalazłem te testy:

// wstawienie elementu x do drzewa (I x) (1 <= x <= 10000),
// usunięcie elementu x z drzewa (D x),
// wyszukiwanie elementu x w drzewie (S x),
// znajdowanie najmniejszego (X 0) oraz największego (X 1) elementu w drzewie,
// znajdowanie następnika elementu x (N x) oraz poprzednika elementu x (P x),
// przeglądanie wierzchołków drzewa trzema sposobami (inorder: R 0, preorder: R
// 1, postorder: R 2).

#include <iostream>
#include <stdlib.h>
using namespace std;

inline int rnd(int first, int last) { return rand() % (last - first) + first; }

int main(int argc, char **argv) {
  srand(time(0) + (argc > 1 ? stoi(argv[1]) : 0));
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int z = rnd(1, 10);
  std::cout << z << '\n';
  while (z--) {
    int insts = rnd(1, 256);
    std::cout << insts << '\n';
    while (insts--) {
      int inst = rnd(0, 6);
      std::cout << "IDSXNR"[inst] << ' '
                << (inst == 5 ? rnd(0, 3) : inst == 3 ? rnd(0, 2) : rnd(0, 100))
                << '\n';
    }
  }

  return 0;
}

 

Comments

Bardzo dziękuję za odpowiedź, mam jeszcze pytanie, w jaki sposób sprawdziłeś że te dane generują właśnie taki błąd? Oraz czy istnieje możliwość sprawdzenia w której linijce została zarezerwowana niezwolniona pamięć?

---

Napisałem skrypt w bashu który testował twój program na testach wygenerowanych przez generator, jak twój program się wywalił to dostałem informację na ekran co to za błąd.

Jeżeli chodzi o problemy związane z pamięcią to jest dużo opcji radzenia sobie z nimi. Możesz skompilować program z symbolami do debugowania (opcja g2 w gcc i clang, nie wiem jak w msvc) i użyć gdb lub innego ulubionego debuggera. Również możesz sobie popatrzeć na AddressSanitizer oraz valgrind.

---

Dzięki wielkie, znalazłem błąd w kodzie który powodował te błędy. Natomiast po poprawce mam nowy problem - a mianowicie na spoju wyskakuje mi błąd SIGXFSZ. Na razie jestem na etapie poszukiwania testu który ten błąd generuje. Poprawiony kod.