проблема переполнения стека в программе - PullRequest
Новая
       15

проблема переполнения стека в программе

2 голосов
/ 03 апреля 2010

Так что в настоящее время я получаю странное исключение переполнения стека, когда я пытаюсь запустить эту программу, которая читает числа из списка в текстовом файле и вставляет их в двоичное дерево поиска. Странная вещь в том, что когда программа работает, когда у меня есть список из 4095 номеров в случайном порядке. Однако, когда у меня есть список из 4095 номеров в возрастающем порядке (таким образом, он создает линейное дерево поиска), он выдает сообщение о переполнении стека. Проблема не в статической переменной count, потому что даже когда я удалил ее и установил t = new BinaryNode (x, 1), он все равно дал исключение переполнения стека. Я попытался отладить его, и он сломался на if (t == NULL){ t = new BinaryNode(x,count); Вот функция вставки. 

BinaryNode *BinarySearchTree::insert(int x, BinaryNode *t) {
 static long count=0;
 count++;

 if (t == NULL){ 
  t = new BinaryNode(x,count);
  count=0;
 }
 else if (x < t->key){
  t->left = insert(x, t->left);
 }
 else if (x > t->key){
  t->right = insert(x, t->right);
 }
 else
  throw DuplicateItem();
 return t;
}

Ответы [ 2 ]

1 голос
/ 03 апреля 2010

На языке, подобном C ++, вы не можете использовать рекурсивные алгоритмы на высоких деревьях, потому что каждый вызов функции использует дополнительное пространство в ограниченном стеке. Вы должны либо изменить свой алгоритм (использовать итерацию, а не рекурсию) или использовать сбалансированную структуру двоичного дерева.

Если у вас ограниченный вход (как, по-видимому, и в этом случае), вы можете уменьшить нагрузку на стек, либо увеличив его (как предлагает Андреас), либо поместив в стек меньше данных. Кажется, что insert является функцией-членом класса BinarySearchTree, даже если она не ссылается ни на какие другие члены класса. Если вы сделаете insert статическим методом (или обычной функцией, не входящей в класс), ему не придется помещать указатель this в стек для каждого вызова функции, и вы сможете получить больше итераций до того, как перелив.

0 голосов
/ 03 апреля 2010

Вы можете увеличить размер стека. В зависимости от того, с каким компилятором вы работаете, это делается по-разному. Например, в Visual Studio размер стека можно установить с помощью параметра командной строки: 

/F stacksize
...