分段错误和Valgrind没有在C中的Trie树上堆叠地址错误
发布时间:2020-12-16 06:59:49 所属栏目:百科 来源:网络整理
导读:我正在用C语言写一个Trie Tree,结构如下: typedef struct sNode Node;struct sNode { int word; unsigned int nsons; Node *next[26];};typedef struct { Node *root;} Trie; 但是我在这个插入函数中遇到了问题: int insert(Trie* trie,char word[]){ int
|
我正在用C语言写一个Trie Tree,结构如下:
typedef struct sNode Node;
struct sNode {
int word;
unsigned int nsons;
Node *next[26];
};
typedef struct {
Node *root;
} Trie;
但是我在这个插入函数中遇到了问题: int insert(Trie* trie,char word[]){
int i=0,posiletter,contletters=0;
char letter=word[0];
Node *newroot;
Node *newNode=NULL;
Node **copyroot;
Node *current=NULL;
Node *Nodefather=NULL;
Node verif;
if (trie->root=NULL){
newroot=malloc(sizeof(Node));
for (i=0; i<=25; i++) newroot->next[i]=NULL;
newroot->nsons=0;
newroot->word=0;
trie->root=newroot;
}
copyroot=&trie->root;
current=*copyroot;
while (word[contletters]!=' '){
posiletter=(word[contletters])-'a';
while( (current->next[posiletter])!= NULL ){ // Error in this line
Nodefather=current;
current=current->next[posiletter];
}
if ( (current->next[letter-'a']) == NULL ){
newNode=malloc(sizeof(Node));
//newNode=malloc(sizeof(Node));
for (i=0; i<=25; i++) newNode->next[i]=NULL;
newNode->nsons=0;
newNode->word=0;
Nodefather->next[letter-'a']=newNode;
Nodefather->nsons=(Nodefather->nsons)+1;
}
contletters++;
}
if (letter==' ') Nodefather->next[letter-'a']->word=1; //end of word
return 1;
}
该函数接收指向树和字符串的指针.如果Trie的根是NULL,它会创建一个节点,在此之后,它会在数组上搜索要存储的空闲(NULL)位置. 问题出在这一行: while( (current->next[posiletter])!= NULL ){ // Error in this line
它在我执行此操作时给出了Segmentation fault错误,并且在GDB上出现此错误: Program received signal SIGSEGV,Segmentation fault.
0x0804883f in insert (trie=0x804b008,word=0xbffff230 "abcdef") at trie.c:97
97 while( (current->next[posiletter])!= NULL ){ // Error in this line
并以这种方式使用Valgrind:valgrind –tool = memcheck –leak-check = full –track-originins = yes ./trie它给了我这些错误 ==3409== Invalid read of size 4 ==3409== at 0x804883F: insert (trie.c:97) ==3409== by 0x80485FD: main (triet.c:36) ==3409== Address 0x8 is not stack'd,malloc'd or (recently) free'd ==3409== ==3409== ==3409== Process terminating with default action of signal 11 (SIGSEGV) ==3409== Access not within mapped region at address 0x8 ==3409== at 0x804883F: insert (trie.c:97) ==3409== by 0x80485FD: main (triet.c:36) ==3409== If you believe this happened as a result of a stack ==3409== overflow in your program's main thread (unlikely but ==3409== possible),you can try to increase the size of the ==3409== main thread stack using the --main-stacksize= flag. ==3409== The main thread stack size used in this run was 8388608. ==3409== HEAP SUMMARY: ==3409== in use at exit: 4 bytes in 1 blocks ==3409== total heap usage: 1 allocs,0 frees,4 bytes allocated ==3409== ==3409== LEAK SUMMARY: ==3409== definitely lost: 0 bytes in 0 blocks ==3409== indirectly lost: 0 bytes in 0 blocks ==3409== possibly lost: 0 bytes in 0 blocks ==3409== still reachable: 4 bytes in 1 blocks ==3409== suppressed: 0 bytes in 0 blocks ==3409== Reachable blocks (those to which a pointer was found) are not shown. ==3409== To see them,rerun with: --leak-check=full --show-reachable=yes ==3409== ==3409== For counts of detected and suppressed errors,rerun with: -v ==3409== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 11 from 6) Segmentation fault 我非常感谢任何帮助.谢谢! ==== ====编辑 (gdb) print current $1 = (Node *) 0x0 (gdb) print current->next Isn't possible acess the memory at the address 0x8 (gdb) print current->next[posiletter] Isn't possible acess the memory at the address 0x8 (gdb) print posiletter $2 = 0 === EDIT2 === (gdb) print contletters $3 = 0 (gdb) print trie->root $4 = (Node *) 0x0 (gdb) print trie->root->next[word[0]-'a'] Isn't possible acess the memory at the address 0x8 解决方法
啊我怎么想念那个!
这是你的问题: if (trie->root=NULL) 应该 if (trie->root == NULL) 注意==. 你编写它的方式,你将root设置为NULL,其值为false,并且永远不会完成根初始化.你可以通过你的gdb为trie-> root输出0x0来解决这个问题 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
