实施TRIE数据结构

Hii，我在C中实现了一个trie …但我在insert_trie函数中遇到错误。

我无法弄清楚为什么根节点没有得到更新。 请帮我解决一下这个。

#include #include #include 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函数中的line nodepointer = nodepointer-> list，我得到了一个分段错误…为什么????

PS：这不是家庭作业。但我正在努力实现它。 我只是找不到错误。

Answer 1

“使用insert，search和startsWith方法实现trie。注意：您可以假设所有输入都由小写字母az组成。”

我已经从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); 

Answer 2

trie每个字符保存一个节点，并且每个字符串只执行一个malloc 。 您应该为每个节点调用malloc 。 （另外， malloc.h已经过时了。从1989年的ANSI C标准开始， stdlib.h包含malloc 。）

Answer 3

 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-> list。 if测试完成后，将nodepointer提前到nodepointer-> next，而不检查nodepointer是否为if块中发生的进程的NULL。