主题：[原创]一道ACM的题目
lihui068
[专家分：50] 发布于 2006-03-16 21:04:00
写一个程序，统计输入中每个单词的出现次数，并按照出现次数的顺序打印单词。在每个单词前打印出现次数
这是一道ACM的题目，应该怎么做 谁可以给个算法！
回复列表 （共10个回复）
沙发
xgxa1 [专家分：80] 发布于 2006-03-28 22:56:00
用二叉树对输入的单词进行统计。
每个节点为一个char类型的指针以及一个int变量用来做计数器（用来存储单词出现的次数），指针要开的空间跟据读入的单词长度进行确定。
每次读入一个单词，当它与节点单词相同时，该节点计数器增一，相比更大时递归进入左节点，相比更小时递归进入右节点。
最后对处理输出。
板凳
1Player [专家分：20] 发布于 2006-03-30 12:17:00
搞一个链表，读一个单词往链表里相应的地方计数+1，最后给链表排序输出，完毕。
3 楼
清影2002 [专家分：0] 发布于 2006-04-05 09:08:00
我感觉还是用链表比较的直接，好理解
4 楼
if007 [专家分：650] 发布于 2006-04-11 21:07:00
此题链表效益较低哦,那个二叉树的还不错,不过还是不够高效,因为例如abc,abcd,abce,比例次数多了,而且极占空间.
建议,设树根为0根.而有二十四个子结点.依次每个根点为a,b,c,d,...
每次只读入一个单词的里一个字母,读一个对应进入一个子节点.若无字母可读时,则该节点计数加一.(这样可避免前面的子串重复比较,且对大数据而言空间量少很多,输出的时侯可用一个数组来保存访问过的节点,'进'则保存,'退'则数组同样退一个字母.)
5 楼
if007 [专家分：650] 发布于 2006-04-11 21:11:00
顺便说句,这题可能是为解密用的吧,哈哈,通常解密的才需求单词出现的频率
6 楼
euc [专家分：4310] 发布于 2006-04-15 18:08:00
hash比较快，但比较难编。
7 楼
bricks [专家分：20] 发布于 2006-05-05 17:18:00
用二分搜索就可以了。简单题！！！
8 楼
yigerengudu [专家分：200] 发布于 2006-08-15 17:40:00
有个比较简单的方法:
开个数组a[128];存放128个ACSII码.
读入字串时,直接对相应的a[i], (i为对应字符的ACSII码) 加1,
最后进行排序就OK了
9 楼
vcacm [专家分：1500] 发布于 2007-04-02 20:07:00
线性规划!
10 楼
liulibo133 [专家分：170] 发布于 2007-05-16 15:42:00
这题看数据规模，数据规模不大的时候怎么做都可以的。但是数据规模大的时候，链表的效率显然不行了，平衡二叉树是不错的。另外还有一种直接的方法，读入所有单词，然后排序，这样重复出现的单词会连续出现，然后一次从头到尾的线性扫描统计每个单词的频度，记录下来，再对频度排序后输出就行了。排序算法使用快速排序，时间复杂度为O(nlog n)，对于10000000以内的数据规模，这样的方法都应该可以在1秒内解决。
我来回复
您所在位置：