2010-10-25 72 views
3

嗨, 我正在C中实现一个trie ...但我在insert_trie函数中出现错误。实现一个TRIE数据结构

我找不出为什么根节点没有得到更新。请帮我解决一下这个。

#include<stdio.h> 
#include<stdlib.h> 
#include<malloc.h> 

typedef struct 
{ 
    char value; 
    int level; 
    struct node *next; 
    struct node *list; 
}node; 

node *trie = NULL; 

node *init_trie() 
    { 
    node *new = (node *)malloc(sizeof(node)); 
    if(trie == NULL) 
    { 
    new->value = '$'; 
    new->next = NULL; 
    new->list = NULL; 
    new->level = 0; 
    trie = new; 
    printf("\n Finished initializing the trie with the value %c",trie->value); 
    return trie; 
    } 
    printf("\n Trie is already initialized"); 
    return trie; 
    } 

node *insert_trie(char *s) 
    { 
    node *nodepointer = trie; 
    node *new = (node *)malloc(sizeof(node)); 
    node *save = NULL; 
    int i=0; 
    while(s[i]!=NULL) 
    { 
     nodepointer = nodepointer->list; 
    while(nodepointer!=NULL) 
     { 
     if(s[i] == nodepointer->value) 
     { 
      printf("\n Found %c",nodepointer->value); 
      nodepointer = nodepointer->list; 
      i++; 
     } 
     save = nodepointer; 
     nodepointer = nodepointer->next; 
     } 
     new->value = s[i]; 
     new->next = NULL; 
     new->list = NULL; 
     printf("\n Inserting %c",new->value); 
     save->next = new;  
     i++; 
    } 

    return trie; 
    } 


int main() 
    { 

    int num; 
    char *s = (char *)malloc(sizeof(char)*10); 
    trie = init_trie(); 
    printf("\n Enter the number of words to enter into the trie "); 
    scanf("%d",&num); 
    while(num>0) 
    { 
    scanf("%s",s); 
    //printf("%s",s); 
    trie = insert_trie(s); 
    printf("\n Finished inserting the word %s into the trie \n",s); 
    num --; 
    } 
    return 0; 
    } 

由于insert_trie函数中的行nodepointer = nodepointer-> list,我得到了分段错误......为什么?

P.S:这不是家庭作业,但我想实现它。我无法找到错误。

+0

你得到了什么错误?它会发生什么? – 2010-10-25 18:01:50

+0

请看现在...我编辑了这个问题 – Flash 2010-10-25 18:08:13

回答

2

一个trie每个字符只有一个节点,并且每个字符串只执行一个malloc。你应该为每个节点调用malloc。 (另外,malloc.h是过时的。stdlib.h包含malloc自1989年的ANSI C标准)

1
node *insert_trie(char *s) 
    { 
    node *nodepointer = trie; 
    node *new = (node *)malloc(sizeof(node)); 
    node *save = NULL; 
    int i=0; 
    while(s[i]!=NULL) 
    { 
     nodepointer = nodepointer->list; 
    while(nodepointer!=NULL) 
     { 
     if(s[i] == nodepointer->value) 
     { 
      printf("\n Found %c",nodepointer->value); 
      nodepointer = nodepointer->list; // Advance pointer once OK 
      i++; 
     } 
     save = nodepointer; 
     nodepointer = nodepointer->next; // Advance pointer without checking 
     } 
     new->value = s[i]; 
     new->next = NULL; 
     new->list = NULL; 
     printf("\n Inserting %c",new->value); 
     save->next = new;  
     i++; 
    } 

    return trie; 
    } 

在if测试你提前nodepointer到nodepointer->列表。一旦if测试完成,您将nodepointer提前到nodepointer-> next,而不检查nodepointer是否来自if块中发生的升级。

2

“实现一个特里结构插入,搜索和startsWith方法 注: 你可以假设所有输入都是由小写字母A-Z”。

我已经为LeetCode上面的问题写了这个非常简单的解决方案。它已经通过了LeetCode的所有16个测试用例。我希望这将有所帮助。

//node structure 
struct TrieNode { 
    char value; 
    int count; 
    struct TrieNode * children[27]; 
}; 


static int count =0; 
/** Initialize your data structure here. */ 
//return root pointer 
struct TrieNode* trieCreate() { 
    struct TrieNode *pNode = NULL; 

    pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode)); 

    if (pNode) 
    { 
     pNode->value = '\0'; 
     pNode->count =0; 

     memset(pNode->children, 0, sizeof(pNode->children)); 

    } 
    return pNode; 


} 

/** Inserts a word into the trie. */ 
void insert(struct TrieNode* root, char* word) { 

    struct TrieNode *pCrawl = root; 
    count ++; 
    //check if the word is not empty 
    if(word){ 
    int index=0, i =0; 

    //check if the root is not empty 
    if (root){ 

    while(word[i] != '\0'){ 
     index = ((int) (word[i]) - (int)'a'); 

     if(!pCrawl->children[index]) 
     { 
      pCrawl->children[index] = trieCreate(); 
      pCrawl->children[index]->value = word[i]; 
     } 

     pCrawl = pCrawl->children[index]; 
     i++; 

    } 

     //Count !=0 tell us that this is the last node;; 
    pCrawl->count = count; 

    } 
}} 



/** Returns if the word is in the trie. */ 
bool search(struct TrieNode * root, char* word) { 

    struct TrieNode *pCrawl = root; 
    bool flag = false; 

    //check if word is NULL 
    if(!word) 
    return false; 

    //if the trie is empty 
    if(!root) 
    { 
     return false; 
    } 
    //if word is empty 
    if (*word == '\0') { 
     return true; 
    } 

    int i=0, index =0 ; 


    while (word[i] != '\0') 
    { 
    index = ((int) (word[i]) - (int)'a'); 

     //// if the node/character is not in Trie 
     if(!pCrawl->children[index]) 
     { 
      flag = false; 
      break; 
     } 

     pCrawl = pCrawl->children[index]; 
     i++; 
    } 

      //count != 0 marks node as last/leaf node 
      if(pCrawl->count != 0 && word[i] == '\0') 
      { 
       flag = true; 
      } 
     return flag; 

} 

/** Returns if there is any word in the trie 
    that starts with the given prefix. */ 
bool startsWith(struct TrieNode* root, char* prefix) { 

    struct TrieNode * pCrawl = root; 

    int i =0, index=0; 
    bool flag = false; 
    if(root){ 
    while(prefix[i] != '\0') 
    { 
     index = ((int) (prefix[i]) - (int)'a'); 

    if(pCrawl->children[index] == NULL){ 
    flag = false; 
     return flag; 
    } 
    else 
    flag = true; 

    pCrawl = pCrawl->children[index]; 
    i++; 
    } 

    } 

    return flag; 


} 

/** Deallocates memory previously allocated for the TrieNode. */ 
void trieFree(struct TrieNode* root) { 

    if(root){ 

     for(int i = 0; i <=26; i ++) 
     { 
      trieFree(root->children[i]); 
     } 
     free(root); 

    } 

} 

// Your Trie object will be instantiated and called as such: 
// struct TrieNode* node = trieCreate(); 
// insert(node, "somestring"); 
// search(node, "key"); 
// trieFree(node);