| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
用字典树写的,不知道哪里有问题?求大佬帮助
//数字树 - 字典树
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
bool findsolve = false;
struct trie
{
bool isEnd;//标记结束
int cnt;//标记数量
trie * next[10];//标记下一个结点
trie()
{
isEnd = false;
cnt = 0;
for(int i = 0 ; i < 10; i++)
next[i] = NULL;
}
};
trie * root = new trie;
void Insert(char * s)
{
int len = strlen(s);
// cout << len << endl;
trie *p = root, *nw;
for(int i = 6 ; i >= 0 ; i--)
{
if(p->next[s[i]-'0'] == NULL)
{
nw = new trie;
p->next[s[i]-'0'] = nw;
}
p = p->next[s[i]-'0'];
}
p->isEnd = true;
p->cnt++;
}
void del(trie * root)
{
trie*p = root;
if(root == NULL)
return;
for(int i = 0 ; i < 10 ; i++)
{
if(p->next[i] != NULL)
{
del(p->next[i]);
}
}
delete root;
return;
}
bool Search(char *s)
{
trie *p = root;
int len = strlen(s);
for(int i = 0; i < len ; i++)
{
if(p->next[s[i]-'0'] == NULL)
return false;
p = p->next[s[i]-'0'];
}
if(p->isEnd == true)
return true;
return 0;
}
//test:ok
int trans(char *s)
{
int x = 0;
int len = strlen(s);
for(int i = 0 ; i < len ; i++)
{
if(s[i] == '-')
continue;
x *= 10;
if(s[i] >= 'A' && s[i] <= 'Y')
x += (s[i]-'A'-(s[i]>'Q'))/3+2;
else if(s[i] >= '0' && s[i] <= '9')
x += s[i]-'0';
}
return x;
}
void dfs(trie* p,int m,char phone[9])
{
if(p->isEnd == true)
{
if(p->cnt > 1)
{
for(int i = 1; i <= 7 ; i++)
{
if(i == 4)
printf("-");
printf("%c",phone[i]);
}
printf(" %d\n",p->cnt);
findsolve = true;
}
return ;
}
for(int i = 0 ; i < 10 ; i++)
{
if(p->next[i] != NULL)
{
phone[m+1] = (char)(i+'0');
dfs(p->next[i],m+1,phone);
}
}
return ;
}
int main()
{
char phone[100];
freopen("in.txt","r",stdin);
// cin.sync_with_stdio(false);
int n, num;
// cin >> n;
scanf("%d",&n);
char ch[100];
for(int i = 0 ; i < n; i++)
{
scanf("%s",ch);
num = trans(ch);
//test:ok
char ans[100];
int j = 0;
if(num == 0)
{
for(int i = 0 ; i <= 6; i++)
{
ans[i] = '0';
}
ans[7] = '\0';
Insert(ans);
}
else
{
while(num)
{
int a = num % 10;
ans[j++] = (char)(a+'0');
num /= 10;
}
ans[j] = '\0';
Insert(ans);//插入树中
}
}
dfs(root,0,phone);
if(!findsolve)
printf("No duplicates.\n");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator