Я делаю свою домашнюю работу по 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
операция. Но я все еще не могу отладить свой код.
Кто-нибудь может мне помочь?
Это много кода, но кое-что посмотреть:
s
: char* s=new char[n+1];
, s
в char* getMinPre(char *s, int _size)
, getMinPre
выделяет другой буфер и возвращает его, перезаписывая s
: s=getMinPre(s, n);
(утечка памяти начальной s
буфер).Это потенциально часто происходит в цикле основной функции, поэтому у вас может не хватить памяти. (getMinPre
выделение и перезапись указателя на выделенный буфер).
Поскольку это онлайн-платформа для судей, я бы рекомендовал создавать экстремальные тестовые примеры (минимум, максимум элементов, тонны итераций) и запускать их локально.
Также: добавьте некоторую отладочную информацию. Вы даже можете заключить их в капсулу #ifdef
так что вам не придется их удалять.
В вашем trie_Tree
конструктор, вы используете new
выделить динамическую память, но я не нахожу вас delete
этот объект где угодно. Точно так же в searchChar
Вы выделяете много дочерних узлов, но никогда не удаляете их. Также в getMinPre
, Все они приведут к утечке памяти. Единственная память, которую вы освободили, это result
в main()
,
В C ++ динамическое управление памятью является действительно сложной темой и подвержено ошибкам, каждый раз, когда вы выделяете некоторую память с new
нужно иметь ввиду освободить их от delete
где-то. Как и в C, каждый раз, когда вы используете malloc()
, тебе нужно free()
,
Есть много библиотек, которые вы можете использовать вместо управления памятью самостоятельно. Для связанного списка, вы можете рассмотреть std::vector
в заголовке<vector>
,
Кстати, я думаю, что этот код выглядит С с классом, не C ++.