M.rar_前缀树_单词出现次数_字典树 matlab

#include <stdio.h> #define MAX_NODE 1000000 typedef struct NODE { int iCount; struct NODE *pNext[26]; /* 26个孩子，26个字符 */ }NODE,*PNODE; NODE node[MAX_NODE]; int ix_node = 0; void Init(PNODE *pRoot); PNODE CreateNode(); /* 创建新结点 */ void Insert(PNODE *pRoot,char *s); /* 插入 */ int Search(PNODE *pRoot,char *s); /* 查找 */ int main() { PNODE pRoot = NULL; Init(&pRoot); char list[20]; char input[20]; while(gets(list) && list[0]) Insert(&pRoot,list); while(gets(input)) printf("%d\n",Search(&pRoot,input)); return 0; } int Search(PNODE *pRoot,char *s) { int i,k; PNODE p = *pRoot; if(!p) return 0; i = 0; while(s[i]) { k = s[i++] - 'a'; if(!p->pNext[k]) /* 没有出现过 */ return 0; p = p->pNext[k]; } return p->iCount; } void Insert(PNODE *pRoot,char *s) { PNODE p = *pRoot; int i,k; if(!p) p = *pRoot = CreateNode(); i = 0; while(s[i]) { /* 找到相应的分支 */ k = s[i++] - 'a'; if(p->pNext[k]) /* 如果此孩子非空 */ { p->pNext[k]->iCount++; } else /* 如果此孩子为空，则创建 */ { p->pNext[k] = CreateNode(); } p = p->pNext[k]; } } PNODE CreateNode() { PNODE p; int i; /* 从数组中取出根结点 */ p = &node[ix_node++]; p->iCount = 1; /* 孩子设为空 */ for(i = 0 ; i < 26 ; ++i) p->pNext[i] = NULL; return p; } void Init(PNODE *pRoot) { (*pRoot) = NULL; }