p->is_tail = TRUE; // 标记当前串已是结尾
// 判断插入串是否是某个串的前缀←判断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->is_tail)
{
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()
{
int T = 0; // 测试用例编号
char line[MAX_NODE_COUNT]; // 输入的一行
trie_tree_t *trie_tree = trie_tree_create();
BOOLEAN islegal = TRUE;
while (scanf("%s", line) != EOF)
{
if (strcmp(line, "9") == 0)
{
if (islegal)
{
printf("Set %d is immediately decodable\n", ++T);
dfs_travel(trie_tree->root);
}
else
{
printf("Set %d is not immediately decodable\n", ++T);
dfs_travel(trie_tree->root);
}
trie_tree_clear(trie_tree);
islegal = TRUE;
}
else
{
if (islegal)
islegal = trie_tree_insert(trie_tree, line);
}
}
trie_tree_destroy(trie_tree);
return 0;
}
稍微改变一下：
/**字典树——检测01编码是否具有前缀性
*Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的
*使得查询单词就是查字典一样。插入和删除跟查询有关。
*/
#include
#include
#include
#define CHAR_COUNT 2/** 字符的种类，也即单个节点的子树的最大个数，这里是01编码 */
#define MAX_CODE_LEN 10/** 编码的最大长度. */
/** 字典树的最大节点个数.每个 code 不超过 10bit，因此最大节点个数为 2^11-1*/
#define MAX_NODE_COUNT ((1<<(MAX_CODE_LEN+1))-1)
typedef enum {FALSE,TRUE} BOOLEAN;
/** 字典树的节点，包含CHAR_COUNT个指针和一个布尔值 */
typedef struct trie_node_t
{
struct trie_node_t* next[CHAR_COUNT];
int count; /** 标记当前字符是否位于某个串的尾部 */
/** 这里要特别注意，当is_tail为真且next数组里的指针全部为空时，当前结点才是叶节点 */
} trie_node_t;
/** 字典树. */
typedef struct trie_tree_t
{
trie_node_t *root; /** 树的根节点 */
int size; /** 树中实际出现的节点数 */
/**开一个大数组，加快速度，否则要给每一个结点malloc CHAR_COUNT个空间 */
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_insert(trie_tree_t *tree, char *word)
{
int i;
BOOLEAN ok=TRUE;
trie_node_t *p = tree->root;
while (*word)
{
int curword = *word - '0';
if (p->next[curword] == NULL)
p->next[curword] = &(tree->nodes[tree->size++]);//代替一次malloc
p = p->next[curword];
if (p->count!=0) ok=FALSE; // 某个串是插入串的前缀
word++; // 指针下移
}