这一题其实是水题,简单的一道字典树问题,但是在实现的过程中发现了如下问题:
1.对指针的用法太随意,一直以为是指针引用以及全局和局部的区别,但后来发现不是。
2.初期思想是正确的,但是没考虑清楚,有些细节问题(见代码指示下)
3.我的思想是这样,初期建立一个根节点,然后每次输入一个单词,就插入根树当中,如果在建立的过程中发现已经有单词结束或者在已存在的节点中发现自己当前单词已经结束,则说明存在前缀现象。
4.关于字典树的用法有很多,这道题是最简单的一些用法,高级灵活的用法后面会遇到,不管怎样都是基础知识的结合,同时注意与后缀数组,后缀树联系。下面是这道题具体代码:
01.
/*
02.
* 163.cpp
03.
*
04.
* Created on: 2013年8月11日
05.
* Author: panzhizhou
06.
*/
07.
#include<iostream>
08.
#include<string.h>
09.
#include<stdio.h>
10.
using
namespace
std;
11.
typedef
struct
Treenode{
12.
bool
flag;
//单词是否结束标记
13.
Treenode *next[10];
14.
char
data;
15.
}Treenode;
16.
Treenode *root;
//全局变量
17.
Treenode *newtree(){
18.
Treenode *tree=
new
Treenode;
19.
tree->flag=
false
;
20.
for
(
int
i=0;i<10;i++){
21.
//t->next[i]=new Treenode;
22.
tree->next[i]=NULL;
23.
// tree->data=-1; //作为开始字符
24.
}
25.
return
tree;
26.
}
27.
int
create(
char
s[]){
28.
// Treenode *t=temp;
29.
Treenode *t=root;
30.
int
len=
strlen
(s);
31.
for
(
int
i=0;i<len;i++){
32.
if
(t->next[s[i]-
'0'
]==NULL){
33.
t->next[s[i]-
'0'
]=newtree();
34.
t->next[s[i]-
'0'
]->data=s[i];
35.
t=t->next[s[i]-
'0'
];
36.
if
(i==len-1) t->flag=
true
;
37.
}
38.
39.
else
40.
{
41.
//已经有过的了
42.
if
(t->next[s[i]-
'0'
]->flag==
true
||i==len-1){
//如果长的单词先出现,则短的单词到这里若结束了,则也是有前缀现象
43.
return
1;
44.
}
45.
t=t->next[s[i]-
'0'
];
46.
}
47.
}
48.
return
0;
49.
//t->flag=true; //单词结束标志,flag=true
50.
}
51.
void
print(Treenode *&temp){
52.
Treenode *t=temp;
53.
for
(
int
i=0;i<10;i++){
54.
if
(t->next[i]!=NULL){
55.
while
(t->next[i]!=NULL){
56.
cout<<t->next[i]->data<<
" flag: "
<<t->next[i]->flag<<
","
;
57.
t=t->next[i];
58.
}
59.
}
60.
t=temp;
61.
62.
}
63.
}
64.
int
main()
65.
{
66.
// freopen("3.txt","r",stdin);
67.
// freopen("3_out.txt","w",stdout);
68.
int
ncase;
69.
bool
result;
70.
cin>>ncase;
71.
while
(ncase--){
72.
int
n;
73.
result=
false
;
74.
cin>>n;
75.
root=newtree();
//创建头节点
76.
for
(
int
i=0;i<n;i++){
77.
char
s1[11];
78.
scanf
(
"%s"
,s1);
79.
if
(!result&&create(s1))
80.
{
81.
result=
true
;
82.
}
83.
// temp=root;
84.
}
85.
86.
//print(root);
87.
if
(result==
true
){
88.
//有前缀存在,NO
89.
cout<<
"NO"
<<endl;
90.
}
91.
else
92.
{
93.
cout<<
"YES"
<<endl;
94.
}
95.
}
96.
//system("pause");
97.
return
0;
98.
}