本文使用 Google Docs 编辑，以网页形式发布。最新版本请看以下链接：
http://docs.google.com/View?id=df4r7psc_973ccmbxncnPOJ Problem 1002 Solved!
这个题目的解题思路与上次写的英文单词自动补全、纠错很相似。先将电话号码用有根树的形式保存，每个节点表示一个号码，从根到叶节点就是一个完整的号码。记录每个叶子节点的出现在次数，若大于2，就表示有重复的号码了。
POJ平台对输出的要求十分严格，一点差别都不能有。比如今天遇到的是多输出了一个 '\0'，这是个不可见字符，测试根本看不出问题。
因为有根树的代码大量借鉴了之前写的，所以这次基本上没有遇到什么大问题，只是有些细节上，出现了些低级错误（如 == 写成了 =，函数参数列表中 , 写成了 ;）。
下面是代码：
1 #include <string.h>
2 #include <stdlib.h>
3 #include <stdio.h>
4 #include <ctype.h>
5
6 #define NUM_OF_CHILD 10
7
8 typedef struct NumberNode
9 {
10 char number;
11 struct NumberNode *child[NUM_OF_CHILD]; // 0 ~ 9
12 struct NumberNode *parent;
13
14 long counter; // number of occurence
15 } NUMBER;
16
17 // function decleration ===================================
18 NUMBER *build_tree ();
19 // for build_tree() -------------------------------
20 void parse_input (char input[], char entry[]);
21 NUMBER *init_root ();
22 NUMBER *add_entry (NUMBER *root, char *entry);
23 NUMBER *add_node (NUMBER *cur_node, char c);
24 NUMBER *has_child (NUMBER *cur_node, char c);
25
26 void leaf_walk (NUMBER *root);
27 // for leaf_walk()
28 int has_no_child (NUMBER *cur_node);
29 void print_entry (NUMBER *leaf);
30
31 // @func: build_tree
32 // 从输入字符串建立有根树
33 // @return 返回有根树的根节点
34 NUMBER *build_tree ()
35 {
36 int num_of_input;
37 scanf ("%d", &num_of_input);
38
39 char input[100];
40 char entry[8];
41 // TODO: build root
42 NUMBER *root = init_root();
43
44 int i;
45 for (i=0; i<num_of_input; ++i)
46 {
47 scanf ("%s", input);
48 // procee *input* to number format
49 parse_input (input, entry);
50
51 // TODO: add this entry to root
52 add_entry (root, entry);
53 }
54
55 return root;
56 }
57
58 // @func init_root
59 // 申请根节点内存，初始化根节点
60 // @return 返回指向根节点的指针
61 NUMBER *init_root ()
62 {
63 NUMBER *root = (NUMBER *) malloc (sizeof (NUMBER));
64 root->number = '\0';
65 int i;
66 for (i=0; i<NUM_OF_CHILD; ++i)
67 root->child[i] = NULL;
68 root->parent = NULL;
69 root->counter = 0;
70
71 return root;
72 }
73
74 // @func parse_input
75 // parse string *input* to 7 digits and then store them in *entry*
76 // @param input: unformat string
77 // @param entry: storage for the 7 digits
78 const char A2iTable[26] =
79 {'2','2','2', '3','3','3', '4','4','4', '5','5','5', '6','6','6',
80 '7','7','7','7', '8','8','8', '9','9','9','9'};
81 void parse_input (char input[], char entry[])
82 {
83 size_t length = strlen (input);
84 int i, j, index;
85 for (i=0, j=0; i<length; ++i)
86 {
87 if (isdigit(input[i]))
88 {
89 entry[j++] = input[i];
90 }
91 else if (input[i] == '-')
92 continue;
93 else if (isupper(input[i]) && input[i]!='Q' && input[i]!='Z')
94 {
95 index = (int)input[i] % (int)('A');
96 entry[j++] = A2iTable[index];
97 }
98 }
99 entry[j] = '\0';
100
101 // debug: exam entry
102 // printf ("%s\n", entry);
103
104 }
105
106
107 // @func add_entry
108 // 往 root 加电话号码条目 entry
109 // @para root 树的根节点
110 // @para entry 待加入单词
111 // @return 返回树的根节点
112 NUMBER *add_entry (NUMBER *root, char *entry)
113 {
114 NUMBER *cur_node = root;
115
116 int i;
117 for (i=0; i<strlen(entry); ++i)
118 cur_node = add_node (cur_node, *(entry+i));
119
120 return root;
121 }
122
123 // @func add_node
124 // 往当前节点 cur_node 添加 c 节点
125 // @para cur_node 当前节点
126 // @para c 要添加的节点字母
127 // @return 返回新节点
128 NUMBER *add_node (NUMBER *cur_node, char c)
129 {
130 NUMBER *child = has_child (cur_node, c);
131 // if *c* already exist
132 if (child)
133 {
134 ++ child->counter;
135 return child;
136 }
137 // otherwise, create a new node
138 child = (NUMBER *) malloc (sizeof (NUMBER));
139 child->number = c;
140 child->counter = 1;
141 // maintain the tree
142 cur_node->child[c-'0'] = child;
143 child->parent = cur_node;
144 int i;
145 for (i=0; i<NUM_OF_CHILD; ++i)
146 {
147 child->child[i] = NULL;
148 }
149
150 return child;
151 }
152
153 // @func has_child
154 // 判断节点 cur_node 是否拥有一级子节点 c
155 // @para cur_node
156 // @para c 字节点字母
157 // @return 如果有则返回该子节点，无则返回 NULL
158 NUMBER *has_child (NUMBER *cur_node, char c)
159 {
160 if (!cur_node)
161 return NULL;
162 return cur_node->child[c-'0'];
163 }
164
165 int has_no_child (NUMBER *cur_node)
166 {
167 int i;
168 for (i=0; i<NUM_OF_CHILD; ++i)
169 if (cur_node->child[i])
170 return 0;
171 return 1;
172 }
173
174 int flag_no_duplicte = 1;
175 int hyphen_counter = 0;
176 void print_entry (NUMBER *leaf)
177 {
178 if (leaf->parent && leaf->parent->parent)
179 {
180 print_entry (leaf->parent);
181 }
182 printf ("%c", leaf->number);
183 if (2 == hyphen_counter++)
184 printf ("-");
185 }
186
187 void leaf_walk (NUMBER *root)
188 {
189 if (!root)
190 return;
191 if (has_no_child (root) && (root->counter > 1))
192 {
193 print_entry (root);
194 printf (" %ld\n", root->counter);
195 hyphen_counter = 0;
196 flag_no_duplicte = 0;
197 return;
198 }
199 int i;
200 for (i=0; i<NUM_OF_CHILD; ++i)
201 leaf_walk (root->child[i]);
202 }
203
204 int main (int argc, char **argv)
205 {
206 NUMBER *root = build_tree ();
207
208 leaf_walk(root);
209 if (flag_no_duplicte)
210 printf ("No duplicates.\n");
211 return 0;
212 }