Ошибка выполнения с кодом выхода 6 на онлайн-судье

Я делаю свою домашнюю работу по c ++ на онлайн-судье. Есть m строк длиной n. Мне нужно найти минимальное выражение новой строки, а затем вставить его в дерево три. Для каждой строки мне нужно вернуть «номер позиции» первой идентичной строки.

Ниже приведен мой код:

#include <cstdio>
using namespace std;

struct trie_node
{
trie_node * firstSon;
trie_node * nextBro;
char value;
bool isKey;
int firstPos;
trie_node(char value):firstSon(NULL), nextBro(NULL), value(value), isKey(false), firstPos(-1){}
};

class trie_Tree
{
public:
trie_Tree();
int searchStr(char* desStr, int len, int selfPos);

private:
trie_node* searchChar(trie_node* fatherNode, char desChar);
trie_node* root;
};

trie_Tree::trie_Tree()
{
root = new trie_node('0');
}

int trie_Tree::searchStr(char * desStr, int len, int selfPos)
{
trie_node* fatherNode = root;
for (int i=0; i<len; i++)
{
fatherNode = searchChar(fatherNode, desStr[i]);
}
if (!fatherNode->isKey)
{
fatherNode->isKey=true;
fatherNode->firstPos=selfPos;
}
return fatherNode->firstPos;
}

trie_node* trie_Tree::searchChar(trie_node* fatherNode, char desChar)
{
if (fatherNode->firstSon==NULL)
{
fatherNode->firstSon = new trie_node(desChar);
return fatherNode->firstSon;
}

trie_node* travNode = fatherNode->firstSon;
while (travNode->nextBro!=NULL)
{
if (travNode->value==desChar) return travNode;
travNode=travNode->nextBro;
}

if (travNode->value==desChar) return travNode;
else
{
travNode->nextBro = new trie_node(desChar);
return travNode->nextBro;
}
}

char* getMinPre(char *s, int _size)
{
int min=0, trav=1;
while (trav<_size && min<_size)
{
int i;
for (i=0; i<_size; i++)
{
if (s[(min+i)%_size]<s[(trav+i)%_size])
{
trav=trav+i+1;
break;
}
else if (s[(min+i)%_size]>s[(trav+i)%_size])
{
min=trav;
trav=trav+1;
break;
}
}
if (i==_size) break;
}

char * result=new char[_size];
for (int i=0; i<_size; i++)
{
result[i]=s[(min+i)%_size];
}
return result;
}

int main()
{
int m, n, result=0;
scanf("%d %d", &m, &n);

trie_Tree tt=trie_Tree();

char* s=new char[n+1];
for (int i=0; i<m; i++)
{
scanf("%s", s);
s=getMinPre(s, n);
result = tt.searchStr(s, n, i);
printf("%d\n", result);
}
delete[] s;

return 0;
}

Я скомпилировал свой код с VS и g ++ и много раз запускал программу для тестирования. Это сработало отлично.

Но когда система онлайн-судей вернула ошибку времени выполнения (код выхода 6).

Я погуглил «код выхода 6». Он поднимается самой программой, например, сделав системный вызов abort (). Это может быть вызвано new а также delete операция. Но я все еще не могу отладить свой код.

Кто-нибудь может мне помочь?

0

Решение

Это много кода, но кое-что посмотреть:

  1. Внутри вашей основной функции вы выделяете s: char* s=new char[n+1];,
  2. Вы передаете s в char* getMinPre(char *s, int _size),
  3. getMinPre выделяет другой буфер и возвращает его, перезаписывая s: s=getMinPre(s, n); (утечка памяти начальной s буфер).

Это потенциально часто происходит в цикле основной функции, поэтому у вас может не хватить памяти. (getMinPre выделение и перезапись указателя на выделенный буфер).

Поскольку это онлайн-платформа для судей, я бы рекомендовал создавать экстремальные тестовые примеры (минимум, максимум элементов, тонны итераций) и запускать их локально.

Также: добавьте некоторую отладочную информацию. Вы даже можете заключить их в капсулу #ifdef так что вам не придется их удалять.

0

Другие решения

В вашем trie_Tree конструктор, вы используете new выделить динамическую память, но я не нахожу вас delete этот объект где угодно. Точно так же в searchCharВы выделяете много дочерних узлов, но никогда не удаляете их. Также в getMinPre, Все они приведут к утечке памяти. Единственная память, которую вы освободили, это result в main(),

В C ++ динамическое управление памятью является действительно сложной темой и подвержено ошибкам, каждый раз, когда вы выделяете некоторую память с newнужно иметь ввиду освободить их от delete где-то. Как и в C, каждый раз, когда вы используете malloc(), тебе нужно free(),

Есть много библиотек, которые вы можете использовать вместо управления памятью самостоятельно. Для связанного списка, вы можете рассмотреть std::vector в заголовке<vector>,

Кстати, я думаю, что этот код выглядит С с классом, не C ++.

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector