p->count++; // 标记当前串已是结尾
// 判断插入串是否是某个串的前缀←判断p是否叶子结点←判断p包含的所有指针是否都为空
for (i = 0; i < CHAR_COUNT; i++)
if (p->next[i] != NULL)
ok=FALSE;
return ok;
}
/** DFS Trie树.
*注意：相同字符串只输出一次
*/
void dfs_travel(trie_node_t *root)
{
static char word[MAX_CODE_LEN + 1]; /* 中间结果 */
static int pos; /* 当前位置 */
int i;
if (root->count)
{
word[pos] = '\0';
printf("%s\n", word);
}
for (i = 0; i < CHAR_COUNT; i++) /* 扩展 */
{
if (root->next[i])
{
word[pos++] = i+'0';
dfs_travel(root->next[i]);
pos--; /* 返回上一层时恢复位置 */
}
}
}
int main()
{
char line[MAX_NODE_COUNT]; // 输入的一行
trie_tree_t *trie_tree = trie_tree_create();
while (scanf("%s", line) != EOF)
{
if (strcmp(line, "9") == 0)
{
dfs_travel(trie_tree->root);
trie_tree_clear(trie_tree);
}
else
{
trie_tree_insert(trie_tree, line);
}
}
trie_tree_destroy(trie_tree);
return 0;
}
Trie树之统计词频问题
/**字典树——统计词频
*进一步考虑添加删除函数，优化空间，强化查询
*http://www.cnblogs.com/cherish_yimi/archive/2009/10/12/1581666.html
*/
#include
#include
#include
typedef enum{FALSE,TRUE}BOOLEAN;
#define MAXN 1000 /** no more than 10,000 species，会 MLE，因此减一个 0 */
#define CHAR_COUNT 128 /** ASCII 编码范围 */
#define MAX_WORD_LEN 30 /** 编码的最大长度. */
#define MAX_NODE_COUNT (MAXN * MAX_WORD_LEN + 1) /** 字典树的最大节点个数. */
/** 字典树的节点 */
typedef struct trie_node_t
{
struct trie_node_t* next[CHAR_COUNT];
int count; /** 该单词出现的次数 ，count>0则表示这是一个单词的词尾*/
} trie_node_t;
/** 字典树. */
typedef struct trie_tree_t
{
trie_node_t *root; /** 树的根节点 */
int size; /** 树中实际出现的节点数 */
trie_node_t nodes[MAX_NODE_COUNT]; /* 开一个大数组，加快速度 */
} trie_tree_t;
/** 创建. */
trie_tree_t* trie_tree_create(void)
{
trie_tree_t *tree = (trie_tree_t*)malloc(sizeof(trie_tree_t));
tree->root = &(tree->nodes[0]);
memset(tree->nodes, 0, sizeof(tree->nodes));
tree->size = 1;
return tree;
}
/** 销毁. */
void trie_tree_destroy(trie_tree_t *tree)
{
free(tree);
tree = NULL;
}
/** 将当前字典树中的所有节点信息清空 */
void trie_tree_clear(trie_tree_t *tree)
{
memset(tree->nodes, 0, sizeof(tree->nodes));
tree->size = 1; // 清空时一定要注意这一步!
}
/** 在当前树中查询 word 字符串 */
BOOLEAN trie_tree_query(trie_tree_t *tree, char *word)
{
trie_node_t *p = tree->root;
while (*word)
{
if (p->next[*word] == NULL)
return FALSE;
p = p->next[*word];
word++; // 指针下移
}
if(!p->count)
return FALSE;
return TRUE;
}
/** 在当前树中插入 word 字符串
*/
//返回word之前是否已经在树中
BOOLEAN trie_tree_insert(trie_tree_t *tree, char *word)
{
trie_node_t *p = tree->root;
while (*word)
{
if (p->next[*word] == NULL)
{
p->next[*word] = &(tree->nodes[tree->size++]);
}
p = p->next[*word];
word++; // 指针下移
}
// if(!p->count)
// return FALSE;
p->count++;
// return TRUE;
}
int n = 0; // 输入的行数
/** DFS Trie树. */
void dfs_travel(trie_node_t *root)
{
static char word[MAX_WORD_LEN + 1]; /* 中间结果 */
static int pos; /* 当前位置 */
int i;
if (root->count) /* 如果 count 不为 0，则肯定找到了一个单词 */
{
word[pos] = '\0';
printf("%s %0.4f\n", word, ((float)root->count * 100) / n);
}