blocks|key|1672322|text|您可以将所有单词放入trie中，然后在处理完整个文件后计算单词数。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1672323|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Trie^0|A|4|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

You can put all of the words into a <a href="http://en.wikipedia.org/wiki/Trie" rel="nofollow noreferrer">trie</a> and then count the number of words after you have processed the whole file.

blocks|key|926195|text|二进制搜索树可以很好地处理字符串。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|926196|如果你不关心单词的排序，你可以只使用哈希表。|926197|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Binary Search Trees work fine for strings.

If you don't care about having the words in sorted order, you can just use a hash table.

blocks|key|2813997|text|我将单词放在一个链表中，并对其进行线性搜索。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2813998|如果要检查单词W是否存在，你要检查整个列表，那么它肯定很长。O(n%5E2)，其中n是列表的大小。|2813999|最简单的方法可能是使用散列。它很容易实现(与一些树结构不同)，即使是C语言也应该有一些库。你会得到O(n)复杂度。|2814000|编辑一些C哈希表实现|offset|length|style|BOLD|2814001|http://en.wikipedia.org/wiki/Hash_table#Independent_packages|2814002|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|0|0|2|0|0|1O|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|V|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|W|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|X|8|@$H|Y|I|Z|J|K]]|9|@]|A|$]]|$1|L|3|M|5|6|7|10|8|@]|9|@$H|11|I|12|1|13]]|A|$]]|$1|N|3|-4|5|6|7|14|8|@]|9|@]|A|$]]]|O|$P|$5|Q|R|S|A|$T|M]]]]

I'm puting the words in a linked list and just making a linear search into it. 
If to check whether word W is present, you go through the whole list, then it's surely long. O(n^2), where n is size of the list.

Simplest way is probably having a hash. It's easy to implement yourself (unlike some tree structures) and even C should have some libraries for that. You'll get O(n) complexity.

edit Some C hashtable implementations 
<a href="http://en.wikipedia.org/wiki/Hash_table#Independent_packages" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Hash_table#Independent_packages</a>

blocks|key|926242|text|如果您使用的是UNIX系统，那么您可以使用bsearch()或hsearch()系列函数来代替线性搜索。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|926243|entityMap^0|L|9|V|9|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|M|8|@]|D|@]|E|$]]]|G|$]]

If you're on a UNIX system, then you could use the <code>bsearch()</code> or <code>hsearch()</code> family of functions instead of a linear search.

blocks|key|4222849|text|算法的第一个升级可能是对列表进行排序，因此，您的线性搜索可能会更快(您只能搜索到比您的元素大的一个元素)，但这仍然是一个天真的解决方案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4222850|最好的方法是二进制搜索树，更好的是前缀树(或trie，已经在其他答案中提到)。|4222851|在K&R的“C编程语言”中，你可以找到你想要的东西的确切例子。“自动引用的数据结构”(6.5)的第一个例子是用于计算字符串中每个单词的出现次数的二进制搜索树。(你不需要计算:P)|4222852|其结构类似于：|4222853|struct+tnode+{
++++++++char+*word;
++++++++struct+tnode+*left;
++++++++struct+tnode+*right;
};|code-block|syntax|javascript|4222854|在这本书中，你可以看到你想要做的事情的整个例子。|4222855|二进制搜索树可以很好地处理任何可以接受订单的数据结构，并且比列表中的线性搜索更好。|4222856|对不起，我的英语很差，如果我说错了，请纠正我，我对C+:p很不了解。|4222857|编辑：我不能给其他答案添加评论，但是我读到了来自OP的评论：“列表没有排序，所以我不能使用二进制搜索”。在链表上使用二进制搜索是无稽之谈。为什么？当对随机元素的访问速度很快时，对分搜索是有效的，比如在数组中。在双向链表中，最差的访问将是n/2。但是，您可以在列表中放置许多指针(访问关键元素)，但这是一个糟糕的解决方案。|offset|length|style|BOLD|4222858|entityMap^0|0|0|0|0|0|0|0|0|0|3|0^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|11|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|12|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|13|8|@]|9|@]|A|$]]|$1|H|3|I|5|J|7|14|8|@]|9|@]|A|$K|L]]|$1|M|3|N|5|6|7|15|8|@]|9|@]|A|$]]|$1|O|3|P|5|6|7|16|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|17|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|18|8|@$U|19|V|1A|W|X]]|9|@]|A|$]]|$1|Y|3|-4|5|6|7|1B|8|@]|9|@]|A|$]]]|Z|$]]

The first upgrade to your algorithm could be having the list sorted, so, your lineal search could be faster (you only search until you find one element greater than yours), but this is still a naive solution.

Best approaches are Binary Search Trees and even better, a prefix tree (or trie, already mentioned in other answer).

In "The C Programming Language" From K&amp;R you have the exact example of what you are looking for.
The first example of "autoreferenced data structs" (6.5) is a binary search tree used for counting the ocurrences of every word in a string. (You don't need to count :P)

the structure is something like this:

<pre><code>struct tnode {
 char *word;
 struct tnode *left;
 struct tnode *right;
};
</code></pre>

In the book you can see the whole example of what you want to do.

Binary Search Trees works good with any tipe of data structure that can accept an order, and will be better than a lineal search in a list. 

Sorry for my poor english, and correct me if i was wrong with something I've said, Im very noob with C :p

EDIT: I can't add comments to other answers, but I have read a coment from OP saying "The list isn't sorted so I can't use binary search". It is nonsense to use binary search on a linked list. ¿Why? Binary Search is efficient when the access to a random element is fast, like in an array. In a double linked list, your worst access will be n/2.. However, you can put a lot of pointers in the list (accesing to key elements), but it is a bad solution..

blocks|key|4222909|text|如果你需要一些简单易得的东西，那么man+tsearch就是简单的二叉搜索树。但这是普通的二叉树，不是平衡的。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|4222910|根据唯一字的数量，也可以选择普通的C数组%2B+realloc()+%2B+qsort()+%2B+bsearch()。这就是我在普通的可移植C中需要比线性搜索更快的简单搜索时使用的。(否则，如果可能的话，我选择C%2B%2B和std：：map/std：：set)。|4222911|更高级的选项通常是特定于平台的(例如Linux上的glib+)。|4222912|另外，另一个非常容易实现的结构是hash。对于字符串来说效率较低，但非常容易实现。通过将内存投入到问题中，可以非常迅速地使其达到惊人的速度。|4222913|entityMap|0|LINK|mutability|MUTABLE|url|http://linux.die.net/man/3/tsearch|1|http://linux.die.net/man/3/qsort|2|http://linux.die.net/man/3/bsearch|3|http://en.wikipedia.org/wiki/Hash_table^0|H|B|H|B|0|0|Y|7|1|18|9|2|0|0|G|4|3|0^^$0|@$1|2|3|4|5|6|7|Z|8|@$9|10|A|11|B|C]]|D|@$9|12|A|13|1|14]]|E|$]]|$1|F|3|G|5|6|7|15|8|@]|D|@$9|16|A|17|1|18]|$9|19|A|1A|1|1B]]|E|$]]|$1|H|3|I|5|6|7|1C|8|@]|D|@]|E|$]]|$1|J|3|K|5|6|7|1D|8|@]|D|@$9|1E|A|1F|1|1G]]|E|$]]|$1|L|3|-4|5|6|7|1H|8|@]|D|@]|E|$]]]|M|$N|$5|O|P|Q|E|$R|S]]|T|$5|O|P|Q|E|$R|U]]|V|$5|O|P|Q|E|$R|W]]|X|$5|O|P|Q|E|$R|Y]]]]

If you need something simple and easily available then <a href="http://linux.die.net/man/3/tsearch" rel="nofollow noreferrer"><code>man tsearch</code></a> for simple binary search tree. But this is plain binary search tree, not balanced.

Depending on number of unique words, plain C array + realloc() + <a href="http://linux.die.net/man/3/qsort" rel="nofollow noreferrer">qsort()</a> + <a href="http://linux.die.net/man/3/bsearch" rel="nofollow noreferrer">bsearch()</a> might be an option too. That's what I use when I need no-frills faster-than-linear search in plain portable C. (Otherwise, if possible, I opt for C++ and std::map/std::set.)

More advanced options are often platforms specific (e.g. glib on Linux).

P.S. Another very easy to implement structure is a <a href="http://en.wikipedia.org/wiki/Hash_table" rel="nofollow noreferrer">hash</a>. Less efficient for strings but very easy to implement. Can be very quickly made blazing fast by throwing memory at the problem.

blocks|key|1672449|text|你在计算文件中唯一单词的数量？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1672450|为什么不构造一个简单的哈希表呢？这样，对于列表中的每个单词，将其添加到哈希表中。任何重复项都将被丢弃，因为它们已经在哈希表中-最后，您可以只计算数据结构中元素的数量(通过存储计数器并在每次添加到表中时递增它)。|1672451|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

You're counting the number of unique words in the file?

Why don't your construct a simple hash table? This way, for each word in your list, add it into the hash table. Any duplicates will be discarded since they would already be in the hash table - and finally, you can just count the number of elements in the data structure (by storing a counter and incrementing it each time you add to the table).

I'm using a naive approach to this problem, I'm putting the words in a linked list and just making a linear search into it. But it's taking too much time in large files.

I was thinking in use a Binary Search Tree but I don't know if it works good with strings. Also heard of Skip Lists, didn't really learn it yet.

And also I have to use the C language...

Counting unique words in a file? Good Linear Search alternative?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我使用了一种简单的方法来解决这个问题，我将单词放在一个链表中，然后对其进行线性搜索。但它在大文件中占用了太多时间。我在考虑使用二进制搜索树，但我不知道它是否适用于字符串。我也听说过跳过列表，但还没有真正学会它。而且我还必须使用C语言。

问是否计算文件中的唯一字？好的线性搜索替代方案吗？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问是否计算文件中的唯一字？好的线性搜索替代方案吗？EN