作者热门文章
- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我正在用 C 语言编写一个 Trie 树,其中包含以下结构:
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]!='\0'){
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=='\0') 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-origins=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
===编辑2===要求的其他值:
(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
来弄明白
关于c - C 中的 Trie 树上的段错误和 Valgrind 未堆叠地址错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10474459/
我是一名优秀的程序员,十分优秀!