加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

分段错误和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来解决这个问题

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读