-
Notifications
You must be signed in to change notification settings - Fork 0
/
trietree.c
140 lines (134 loc) · 3.31 KB
/
trietree.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#pragma once
#pragma execution_character_set("UTF-8")
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "trietree.h"
//initialize a node in trie-tree
void trienode_initialize(TRIENODE* pnode, uchar key)
{
if(pnode == NULL)
return;
pnode->keyword = key;
pnode->numchild = 0;
pnode->stat = STAT_NONWORD;
pnode->childptr = NULL;
pnode->capacity = 0;
}
//insert a word into the Trie tree
int trietree_insert(TRIETREE* ptree, const uchar* chars)
{
unsigned char i;
int pos;
TRIENODE* pnode = NULL;
if(ptree==NULL || chars==NULL)
return 0;
//a new word begining
if(ptree[*chars] == NULL)
{
ptree[*chars] = (TRIENODE*)malloc(sizeof(TRIENODE));
trienode_initialize(ptree[*chars], *chars);
}
pnode = ptree[*chars];
while(*(++chars))
{
pos = 0;
while(pos<(pnode->numchild) && (pnode->childptr[pos].keyword)<*chars)
++pos;
//insert a node
if((pos>=pnode->numchild) || ((pnode->childptr[pos].keyword)>*chars))
{
//lack of memory
if(pnode->numchild >= pnode->capacity)
{
TRIENODE* ptr = (TRIENODE*)realloc(pnode->childptr, sizeof(TRIENODE)*(pnode->capacity+INCR_STEP));
if(ptr==NULL)
{
fprintf(stderr, "Error reallocating memory\n");
return 0;
}
pnode->childptr = ptr;
pnode->capacity += INCR_STEP;
}
// insert ahead
for(i=pnode->numchild; i>pos; --i)
pnode->childptr[i] = pnode->childptr[i-1];
//initialize the node newly inserted
trienode_initialize(pnode->childptr+pos, *chars);
pnode->numchild += 1;
}
//get the node directly and walk down
pnode = pnode->childptr+pos;
}
if(pnode->stat == STAT_NONWORD)
{
pnode->stat = STAT_WORD;//the node is the end of a word
return 1;
}
return 0;//the word already exists,failed to insert
}
////find a word in the tree and returns the corresponding node with binary search
//TRIENODE* trietree_find(const TRIETREE* ptree, const uchar* chars)
//{
// TRIENODE* pnode;
// int pos;
// if(ptree==NULL || chars==NULL)
// return NULL;
//
// pnode = (TRIENODE*)ptree[*(chars)];
// if(pnode == NULL)
// return NULL;
//
// while(*(++chars))
// {
// //binary search
// pos=binary_search(pnode->childptr, pnode->numchild, *chars);
// if(pos<0)
// return NULL;
// pnode = pnode->childptr+pos;
// }
// if( pnode->stat == STAT_WORD)
// return pnode;
// return NULL;
//}
//match a string(bytes oriented) in the dictionary as much as possible
int trietree_match_prefix(const TRIETREE* ptable, const uchar* chars)
{
TRIENODE* pnode;
int depth=0, pos, match_lenth=0;
if(ptable==NULL || chars==NULL)
return 0;
pnode = ptable[*(chars+depth)];//get the root of trie-tree
if(pnode == NULL)//the first byte doesn't match
return 0;
while(*(chars+(++depth)))
{
if(pnode->stat == STAT_WORD)//match a word
match_lenth = depth;
pos = binary_search(pnode->childptr, pnode->numchild, *(chars+depth));
if(pos < 0)//the given byte doesn't exist
return match_lenth;
pnode = pnode->childptr+pos;
}
if(pnode->stat == STAT_WORD)//match a word
match_lenth = depth;
return match_lenth;
}
int binary_search(const TRIENODE* a, int num, uchar val)
{
int low=0, high=num-1, mid;
if(a == NULL)
return -1;
while(low <= high)
{
mid = (low+high)/2;
if(a[mid].keyword > val)
high = mid-1;
else if(a[mid].keyword < val)
low = mid+1;
else
return mid;
}
return -1;
}