![]() |
#2
azzbcc2016-02-18 12:16
|
http://acm.hdu.edu.cn/showproblem.php?pid=1247
这是一道字典树的模板题,小弟的AC代码如下:

#include <iostream>
#include <cstring>
#include <cstdio>
#define MAX 500007
using namespace std;
struct node
{
int e;
struct node* next[26];
};
node* root;
char str[MAX][50];
void Insert(char* s)
{
node* ptr = root;
for(;*s != '\0';s++)
{
int n = *s-'a';
if(ptr->next[n] == NULL)
ptr->next[n] = new node();
ptr = ptr->next[n];
/*看这里~~~~~
ptr = ptr->next[n];
if(ptr == NULL)
ptr = new node();
*/
}
ptr->e = 1;
}
bool find2(char* s)
{
node* ptr = root;
for(;*s != '\0';s++)
{
int n = *s-'a';
ptr = ptr->next[n];
if(ptr != NULL) {
if(ptr->e==1 && *(s+1)=='\0')
return true;
}
else
return false;
}
return false;
}
bool find1(char* s)
{
node* ptr = root;
for(;*s != '\0';s++)
{
int n = *s-'a';
ptr = ptr->next[n];
if(ptr->e==1 && find2(s+1))
return true;
}
return false;
}
int main()
{
int i = 0;
root = new node();
while(scanf("%s",str[i]) != EOF) {
Insert(str[i]);
i++;
}
for(int j = 0;j < i;j++)
if(find1(str[j]))
cout<<str[j]<<endl;
return 0;
}
我的问题是在Insert函数中的for循环体里面,有两部分代码,一部分是我现在写的(A),一部分是被我注释掉了的(B)#include <cstring>
#include <cstdio>
#define MAX 500007
using namespace std;
struct node
{
int e;
struct node* next[26];
};
node* root;
char str[MAX][50];
void Insert(char* s)
{
node* ptr = root;
for(;*s != '\0';s++)
{
int n = *s-'a';
if(ptr->next[n] == NULL)
ptr->next[n] = new node();
ptr = ptr->next[n];
/*看这里~~~~~
ptr = ptr->next[n];
if(ptr == NULL)
ptr = new node();
*/
}
ptr->e = 1;
}
bool find2(char* s)
{
node* ptr = root;
for(;*s != '\0';s++)
{
int n = *s-'a';
ptr = ptr->next[n];
if(ptr != NULL) {
if(ptr->e==1 && *(s+1)=='\0')
return true;
}
else
return false;
}
return false;
}
bool find1(char* s)
{
node* ptr = root;
for(;*s != '\0';s++)
{
int n = *s-'a';
ptr = ptr->next[n];
if(ptr->e==1 && find2(s+1))
return true;
}
return false;
}
int main()
{
int i = 0;
root = new node();
while(scanf("%s",str[i]) != EOF) {
Insert(str[i]);
i++;
}
for(int j = 0;j < i;j++)
if(find1(str[j]))
cout<<str[j]<<endl;
return 0;
}
我认为A和B的作用是相同的,但是用A提交的话就能AC而用B提交在自己电脑上测试都不过
不太理解指针一定要先判断有无然后再赋值吗?