英语词典的维护和识别 题集P168，课本P249 问题描述：

Presentation on theme: "英语词典的维护和识别 题集P168，课本P249 问题描述："— Presentation transcript:

1 英语词典的维护和识别 题集P168，课本P249 问题描述： Trie树通常作为一种索引树，这种结构对于大小变化很大的关键字特别有用。利用Trie树实现一个英语单词辅助记忆系统，完成相应的建表个查表程序。

2 【基本要求】 不限定Trie树的层次，每个叶子结点只含一个关键字，采用单字符逐层分割的策略。实现Trie树的插入、删除和查询的算法，查询可以有两种方式：查询一个完整的单词或者查询以几个字母开头的单词。 【测试数据】 自行设定。 【实现提示】 以实习三中已实现的串类型或C语言中提供的长度不限的串类型表示关键字，叶子结点内应包括英语单词。 【选作内容】 限定Trie树的层次，每个叶子结点可以包含多个关键字。

3 Trie树的定义 Trie树是一棵度 m ≥ 2 的树，它的每一层分支不是靠整个关键码的值来确定，而是由关键码的一个分量来确定。 如下图所示Trie树，关键码由英文字母组成。它包括两类结点：元素结点和分支结点。元素结点包含整个key数据；分支结点有27个指针，其中有一个空白字符‘b’，用来终结关键码；其它用来标识‘a’, ‘b’,..., ‘z’等26个英文字母。 在第0层，所有的关键码根据它们第0位字符, 被划分到互不相交的27个类中。 因此，root→brch.link[i] 指向一棵子Trie树，该子Trie树上所包含的所有关键码都是以第 i 个英文字母开头。 若某一关键码第 j 位字母在英文字母表中顺序为 i ( i = 0, 1, ?, 26 ), 则它在Trie树的第 j 层分支结点中从第 i 个指针向下找第 j+1 位字母所在结点。当一棵子Trie树上只有一个关键码时，就由一个元素结点来代替。在这个结点中包含有关键码，以及其它相关的信息，如对应数据对象的存放地址等。

4

5 Trie树的三个基本性质： 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串 。 每个节点的所有子节点包含的字符都不相同。

6 例子： 这是一个Trie结构的例子： 在这个Trie结构中，保存了t、to、te、tea、ten、i、in、inn这8个字符串，仅占用8个字节（不包括指针占用的空间）。

7 void Insert(string str, Word *info) //插入
在Trie树上的插入和删除： void Insert(string str, Word *info) //插入     {         int len = str.length();         Node *p = root;         for (int i = 0; i < len; i++)         {             p->cnt++;             int now = str[i] - 'a';             if (NULL == p->next[now])                 p->next[now] = new Node();             p = p->next[now];         }         p->cnt++;         p->info = info;     }

8 void DeleteSubtree(Node *p) //删除    
{         for (int i = 0; i < MAX_SIGMER; i++)             if (NULL != p->next[i])                 DeleteSubtree(p->next[i]);         delete p;     }     ~Trie()     {         DeleteSubtree(root);     }

9 stack<Node*> q; Node *p = root; int len = str.length();
  bool Delete(string str) { stack<Node*> q; Node *p = root; int len = str.length(); //find the node, or exit the function for (int i = 0; i < len; i++) int now = str[i] - 'a'; if (NULL == p->next[now]) return false; q.push(p); p = p->next[now]; } if (p->info==NULL) delete p->info; p->info = NULL; //delete the node which is needn't while (!q.empty()) p = q.top(); q.pop(); p->cnt--; if (0 >= p->cnt) delete p; return true;

10 Word* Find(string str)//搜索
{ Node *p = root; int len = str.length(); for (int i = 0; i < len; i++) int now = str[i] - 'a'; if (NULL == p->next[now]) return NULL; p = p->next[now]; } return p->info;

11 算法的特色： 在程序中用了析构， 作用相当于free， 把不用的数组或指针释放， 节省空间。

12 谢谢观赏