本文主要是介绍hdu 题目2072 单词数 （字典树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
单词数
Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 6 Accepted Submission(s) : 2
Problem Description
lily的好朋友xiaoou333最近很空，他想了一件没有什么意义的事情，就是统计一篇文章里不同单词的总数。下面你的任务是帮助xiaoou333解决这个问题。
Input
有多组数据，每组一行，每组就是一篇小文章。每篇小文章都是由小写字母和空格组成，没有标点符号，遇到#时表示输入结束。
Output
每组只输出一个整数，其单独成行，该整数代表一篇文章里不同单词的总数。
Sample Input
you are my friend #
Sample Output
4
1、简单的字典树，添加单词到字典树时判断单词是不是新单词（单词最后字母的flag 是不是 0 ），若是则NUM++；
2、输出num即可
分离单词时注意考虑全面！！（因为没考虑完WA了好多次）
要除去单词前面多余的空格后才能接收单词，，，还有 全是空格的情况，应该输出0
#define N 1000005
#include<stdio.h>
#include<string.h>
#include<stdlib.h>typedef struct Tire
{Tire * child[26];bool flag;
}Tire;Tire * root;
int num;
void insert(char * s)
{Tire *p,*q=root;for(int i=0;i<strlen(s);i++) {if(q->child[s[i]-'a']) q = q->child[s[i]-'a'];else{p = (Tire *)malloc(sizeof(Tire));p->flag=0;for(int j=0;j<26;j++) p->child[j]=NULL;q->child[s[i]-'a'] = p;q = p;}}if(!q->flag) num++; //新单词q->flag = 1;
}int main()
{ char s[N],s1[1005];while(gets(s) && s[0]!='#' ){ root = (Tire *)malloc(sizeof(Tire));for(int i=0;i<26;i++) root->child[i]=NULL;num=0;for(int j=0;j<strlen(s);j++){while(s[j++]==' ') ; j--;if(j==strlen(s)) break;int k=0;while(s[j]!=' ' && j<strlen(s)) s1[k++]=s[j++];s1[k] = '\0';insert(s1);}printf("%d\n",num);}return 0;
}
STL 将每个单词存入 set <string > sentence;; 最后直接输出元素个数即可，，，，
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <set>using namespace std;int main()
{char s[1000005],s1[1005];while(gets(s) && s[0]!='#' ){ set <string> sentence;for(int j=0;j<strlen(s);j++){while(s[j++]==' ') ; j--; /除去多余的空格if(j==strlen(s)) break;int k=0;while(s[j]!=' ' && j<strlen(s)) s1[k++]=s[j++]; //接收每个单词s1[k] = '\0';sentence.insert(s1);}printf("%d\n",sentence.size());}return 0;
}
这篇关于hdu 题目2072 单词数 （字典树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
