面试题

hightman

原帖由 weiwolves 于 2005-11-19 00:14 发表
　　前天面试遇了个题，现在还没个好方法，请高手指点。
　　给定一个文件，计算并输出文件中不同单词的个数，以及单词出现的行号码。

简单一点, 还是用结构体线性链表来实现吧(也可以考虑改成二叉树,加快查找),  碰到一个单词就从头检索一次该词是否已存在;
是否已换行; ... 然后将计数++, 如果有新行, 加到 ->lines 的数组中 (通过 realloc() 重新分配更大内存,也可以一次性多预约几个)

typedef struct word_count WC;

struct word_count
{
  char word[256];  // 单词不会变态超过 256字符吧
int num;  // 单词个数
int linenum; // 总共有几行中出现该单词
int *lines; // 用于存放各行的行号, 动态分配
WC *next; //
};

mingyanguo

hash保存已经出现的单词，每个单词保存已经出现的行号（链表/数组/结合），每个遇到的单词先到hash中查找，没找到就加入，然后加入当前行号。
暂时就想到这些，不过感觉文件大的话可以连个数据库比较干净利落。

leethium

main()写的比较随便；假定只求每个word第一次出现的行号。（小改一下，求所有行号业可以）

请大家题提意见。

fangshi

如果是C++的话可以使用map这个标准模板
typedef map<string,int,less< string > > mmap;
string 为单词，int为行号

sunlan

原帖由 weiwolves 于 2005-11-19 00:14 发表
　　前天面试遇了个题，现在还没个好方法，请高手指点。
　　给定一个文件，计算并输出文件中不同单词的个数，以及单词出现的行号码。

以前读书的时候记得写过这样的程序。实现的思想是这样的：
1。建立一个单词链表。
2。每次从文件中读一行，记录行号
3。从行数据里依次读单词
4。在单词链表中查找该单词，如已存在，在单词计数上加1，记录出现行号；如无，在单词链表中新增一个项。

链表主要元素有：单词、出现次数、出现行号（也以链表形式设计）

leethium

std::map的[]是O(log(n))，跟二叉树实现好像差不多吧？感觉还是hash好一点，就算结果要排序也只要另设一个数组存每个节点的地址，再qsort()。

[ 本帖最后由 leethium 于 2005-11-21 09:42 编辑 ]

soul_of_moon

原帖由 大司南 于 2005-11-19 10:37 发表
我的思路是读空格和tab,同一行的只要单词后面含有空格和tab就把计数+1,直到独到r.
比如:
hello come here

单词换行好像有点问题。应该还要判断'-'