如何制作字典？ [英] how to make a dictionary ?

问题描述

请帮助我.....





我想用C语言创建一本字典..

就像我搜索'Ab'一样，那么这些单词就会显示出来，这是从'Ab'开始的....

Please Help Me.....


I want to create a dictionary In C language..
like if I search 'Ab', then those words will display, which is starts from 'Ab'....

推荐答案

有很多可能方法。我会考虑构建一个树，其中每个叶子和分支对应一个字符。即G。如果你有狗，甜甜圈和天字，你的树看起来像这样：

There are many possible ways. I'd consider building a tree where each leaf and branch corresponds to one character. e. g. if you have the words "dog", "donut" and "day", your tree would look something like this:

    [d]
    / \
  [a] [o]
  /   / \
[y] [n] [g]
    /
  [u]
  /
[t]

您需要考虑如何为节点设置数据结构：显然每个节点最多可以有26个孩子（假设您只是使用az，没有数字，没有特殊字符或重音），你不知何故需要标记那些实际单词的节点，即使它们分支成更多的单词（例如do是一个有效单词但分为dog和donut ）：



当你想要打印以do开头的有效单词列表时，你只需要将树遍历到叶子[d] - [o]然后遍历所有孩子。



请注意，此解决方案可能比解决方案1更复杂，并且向字典添加单词可能会更慢这个解决方案但如果做得好，查找一系列单词可能会非常快。

You'll need to consider how to set up the data structure for the nodes: obviously each can have up to 26 children (assuming you're just using a-z, no numbers, no special characters or accents), and you somehow need to mark those nodes that are actual words even tough they branch into more words (e. g. "do" is a valid word but branches into "dog" and "donut"):

When you want to print a list of valid words starting with "do", then you only need to traverse the tree to the leaf [d]-[o] and then traverse all children.

Note that this solution may be more complex to implement than solution 1, and adding a word to the dictionary may be slower with this solution. but looking up a range of words can be very fast if done right.

您可能会模仿纸质词典的完成方式：按字母顺序存储字符串。

然后你可以执行二进制搜索，以便找到满足用户输入的字符串范围的第一个和最后一个项目。

C ++ libraries（如果你可以使用这样的编程语言）可以帮助你。

You might mimic how the paper dictionaries are done: storing your strings in alphabetic order.
Then you could perform a binary search in order to find the first and last items of the string range satisfying the user input.
C++ libraries (if you can use such programming language) would help you.

看一下google sparsehashmap的内存使用情况，使用densehashmap来提高性能。如果词典元素有限，推荐使用densehashmap。

have a look on google sparsehashmap for memory usage, densehashmap for performance. if the dictionary elements is limited, recommend densehashmap.

这篇关于如何制作字典？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！