實現一個TRIE數據結構

Question

嗨， 我正在C中實現一個trie ...但我在insert_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：這不是家庭作業，但我想實現它。我無法找到錯誤。

Answer 1

一個trie每個字符只有一個節點，並且每個字符串只執行一個malloc。你應該爲每個節點調用malloc。 （另外，malloc.h是過時的。stdlib.h包含malloc自1989年的ANSI C標準）

Answer 2

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塊中發生的升級。

Answer 3

「實現一個特里結構插入，搜索和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);