IT评测·应用市场-qidao123.com

标题: 数据结构（Trie树（字典树）） [打印本页]
作者: 天空闲话    时间: 2024-6-23 12:21
标题: 数据结构（Trie树（字典树））
        今天没有例题，只是分享一个字典树的模板，之后我计划学一下AC自动机和网络流有关的内容，这两个似乎都挺难的，作为AC自动机的前置内容，就提前分享一下Trie树的学习心得。
        字典树，名字里有个字典，那么他和字典有什么关系呢？
        我们回想一下我们是怎么查字典的（这里就拿查英语单词举例子，毕竟英语烂，比赛都要靠字典续命，中字字典好久没用过了），我们会先找到首字母的区域，而后在这个区域内依次找接下来的字母，那么你就已经能够相识Trie树的构造了。
        Trie树就像一部字典一样，从根节点的叶子节点，一条链构成一个或几个完备的单词（注意是一个或几个，比如像busy,bus,在busy串里会有bus的包罗），那么该如何实现呢？
        我们必要一些数组来存储并维护，ch数组，存储的是叶子信息，cnt数组存储的是完备的单词在文本中出现的次数，s是读取文本信息，但是众所周知，字母是有顺序的，ch数组如果存储的是字母信息，怎么将信息通报下去呢？
        谁说ch肯定要存字母信息了。先来看看我是怎么初始化的吧：
  1. char s[N];
  2. int ch[N][26], cnt[N], idx;
复制代码
        26？怎么这么眼熟，这里我们接纳的是将字母映射为索引的方法，通过记录索引来反映我们这一位是什么字母，a对应0，b对应1······所以我们引入了idx来标记我们当前字母的位次。
        当树为空或者说当前首字母并未出如今根下时，我们要开一个新根去存储当前单词链，同理，当我们有首字母但是没有找到想要的接下去字母时，我们就从断点长出一条新的链，是不是就是我们查字典的方法？
        代码如下：
  1. void insert(char *s)
  2. {
  3.         int p = 0;
  4.         for(int i = 0; s[i]; i ++)
  5.         {
  6.                 int j = s[i] - 'a';
  7.                 if(!ch[p][j])
  8.                         ch[p][j] = ++ idx;
  9.                 p = ch[p][j];
  10.         }
  11.         cnt[p] ++;
  12. }
复制代码
        但是注意到了末尾的cnt++操纵，上面我们说到要存储单词出现的个数，cnt就是为此而生的，当我们完备记录下一个单词后，在末尾字母处记录下次数，就算出现busy和bus这样的环境也不会相互影响。
        以上是存储的内容，查询其实也是如此，就像查字典一样，从根到尾。如果找不到某一个字母，就表明它就没有出现过。
        代码如下：
  1. void query(char *s)
  2. {
  3.         int p = 0;
  4.         for(int i = 0; s[i]; i ++)
  5.         {
  6.                 int j = s[i] - 'a';
  7.                 if(!ch[p][j])
  8.                         return 0;
  9.                 p = ch[p][j];
  10.         }
  11.         return cnt[p];
  12. }
复制代码
        之后要学一下AC自动机和网络流，虽然学长说这些都是金牌题，但是我感觉还是要逼本身一下的，毕竟技能树先多点点>_<.

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/) Powered by Discuz! X3.4