存储字典的数据结构

• 下载源码 - 789 B

引言

摘自 Steven S. Skiena 的《算法设计手册》: 抽象数据类型“字典”是计算机科学中最重要的结构之一。已经提出了几十种不同的数据结构来实现字典，包括哈希表、跳跃列表和平衡/非平衡二叉搜索树——因此选择正确的一种可能很棘手。根据应用程序的不同，它也是一个会显著影响性能的决定。在实践中，避免使用坏的数据结构比确定可用的最佳选项更重要。

本文解释了一种可以用于在内存中存储字典（单词及其定义）的数据结构。

背景

这里应用了一个非常基础的数据结构“树”。

Using the Code

代码由 CharacterNode 类组成，该类存储一个 char 值，以及对其他 26 个 CharacterNode 的引用。选择 26 作为引用数量的原因是，此代码目前仅限于存储 26 个英文字母。

如图所示，CharacterNode 的根对象指向 'a' 和 'f'。与字符 'a' 和 'f' 对应的节点进一步指向其他字母，这些字母又遵循相同的规则。描述 CharacterNode 类的代码片段如下：

class CharacterNode
{
    char c;
    CharacterNode next[]=new CharacterNode[26];
    CharacterNode()
    {
        c='a';
        for(int i=0;i<26;i++)
        {
            next[i]=null;
        }    
    }
    //..rest of the class definition
}

根（参见图）始终保存字符 'a'（图中未显示）。这是因为它​​是形成的第一个对象（如下所示），并且任何对象始终将 'a' 作为初始字符（请参见上面的构造函数）。

public class CharacterNodeTree
{
    public static void main(String args[]) throws IOException
    {
        CharacterNode root=new CharacterNode();
        //..rest of the code  

insert() 例程描述了如何将字符存储在字典中。

void insert(char ch)
{
    this.c=ch;
}

main() 中的 insert() 例程以以下方式调用：

CharacterNode temp=null;
String str=null;

System.out.print("Enter the string to insert:");
BufferedReader br1=new BufferedReader(new InputStreamReader(System.in));
str=br1.readLine();
root.next[str.charAt(0)-97]=new CharacterNode();
temp=root.next[str.charAt(0)-97];
for(int i=0;i<str.length();i++)
{
    temp.insert(str.charAt(i),i);
    try
    {
        temp.next[str.charAt(i+1)-97]=new CharacterNode();
        temp=temp.next[str.charAt(i+1)-97];
    }
    catch(StringIndexOutOfBoundsException e) {}
}

因此，一个简单的计算允许从 string 中插入一个字母。此计算只不过是字母在字母序列中的位置（例如 'a' 为 0，'b' 为 1，'z' 为 25 等）。因此，可以插入 string 中的其他字母，因此可以插入整个 string 。

find() 例程描述了如何从字典中检索完整的 string 。

boolean find(String str)
{
    CharacterNode temp=this;
    for(int i=0;i<str.length();i++)
    {
        if(temp.next[str.charAt(i)-97]==null)
        {
            return false;
        }
        else
        {
            temp=temp.next[str.charAt(i)-97];
            continue;
        }
    }
    return true;
}

main() 中的 find() 例程以以下方式调用：

System.out.print("Enter the string to find:");
BufferedReader br2=new BufferedReader(new InputStreamReader(System.in));
str=br2.readLine();
if(root.find(str)==true)
{
    System.out.println("FOUND");
}

同样，一个简单的计算允许检索一个 string （甚至其中的一部分）。

关注点

查看图表，可以进一步修改代码：

1. 可以将一个布尔值添加到 CharacterNode 类定义中，以指示特定字符是否以有意义的单词结尾。例如，在图中，所有叶子都以有意义的单词结尾（并且由于代码的结构，必须结尾）（'aleak'、'alert'、'all'、'food'、'foot' 是图中显示已添加的单词）。但是，'ale' 是一个不以叶子结尾但仍然是一个有意义的单词，并显示已添加。因此，叶子（'k'、't'、'l'、'd'、't'）和非叶子节点（'e'）必须具有 true 的布尔值。
2. 更容易找到具有特殊属性的单词，例如以特定字符开头或以特定字符结尾（考虑直接引用叶子的链接！），或具有固定长度（因为所有具有相同长度的单词都出现在同一级别，并且应该不难编写所有这些单词之间的链接！）。
3. 一个递归例程（最好使用堆栈）可以提供一种按字典顺序检索所有单词的方法。

历史

• 2009 年 4 月 25 日：初始帖子
• 2009 年 4 月 26 日：上传源代码