我目前正在学习Trie数据结构。我正在寻找样本实现，其中有一部分让我感到困惑。
下面是我找到的示例代码:#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int alpha=26;
struct node{
node* child[alpha];
bool end;
int countchild;
};
node* getnode(){
node* pnode=new node;
pnode->end=false;
pnode->countchild=0;
for(int i=0;i<alpha;i++){
pnode->child[i]=NULL;
}
return pnode;
}
void insert(node* root,string key){
node* pcrawl=root;
int size=key.length();
for(int i=0;i<size;i++){
int index=key[i]-'a';
if(!pcrawl->child[index]){
pcrawl->child[index]=getnode();
}
pcrawl->countchild+=1;
pcrawl=pcrawl->child[index];
}
pcrawl->end=true;
}
现在，在insert函数中，这一行是什么意思:
int index=key[i]-'a';
我不知道为什么要特别减去"a"。我总是看到它是字符a。对不起，我听起来有点傻，但我只是不能理解。
为什么和如何工作?
可以看到，node使用了一个固定大小的指针数组:
node* child[alpha];
whereconst int alpha=26;
这意味着在每个节点上，它使用该数组中0到25之间的索引存储下一个节点。key[i]-'a'计算该索引，记住key[i]是char，即存储与字母编码对应的数值的整型。
程序的缺点
程序假定:
- 字符串参数的所有字母都是
a到z之间的小写字母 - 小写字母在编码约定中是连续的(幸运的是，这在所有主要编码中都是正确的)，编码顺序与字母顺序相对应。
不幸的是，这个程序是UB的字符串参数中有非小写字符。更安全的方法是使用
int index=tolower(key[i])-'a'; // case insensitive version
和忽略非字母字符:
if (index<0 || index>=alpha)
continue;
这里是第一个改进(上面的两个注释)，使用向量代替数组，使用成员函数代替自由函数。
下一个改进将是使用智能指针来摆脱手动内存管理，甚至可能是映射。
我不知道为什么需要减去'a'
因为每个复制这段代码的人都不知道.
你得到的是一个适用于ASCII字符"a"到"z"的树。为什么有人会在实现示例代码时添加这样一个不必要的和令人困惑的限制，这在很大程度上超出了我的理解。
如果没有这个限制，代码会更简单，更容易理解，如果它是普通的c，那么代码基本上是"带流的c"。c++中的容器应该是可迭代的，并合理地支持标准算法，等等。是的，你可以像写C一样写c++，但主要是在你不懂c++的时候才会这么做，在这种情况下，坚持用C更有意义，不要假装不是这样。编写好的C代码本身就是一种技能。我认为不存在一个简单的"过渡路径"。从C到c++:它们是不同的语言，如果你把C的习惯用法应用到c++代码中，你会写出不必要的不可理解的代码。
你找到的这段代码是另一个例子，当涉及到一些编码"挑战"的高度追求的搜索词时，盲人引导盲人。网站:/
我不知道为什么特别需要减去'a'。我总是看到它是字符'a'。
问题是映射'a' ->'z'到0 ->因此，它可以用作数组索引。尝试将'a'映射到0:
a - x = 0。
看起来X等于'a'很好。这实际上是有保证的。将b映射到1就比较棘手了。为此，我们需要一个方便的编码。ASCII可以工作，但并非总是如此，因此依赖于它可能导致未定义的行为。在ASCII中，'a'是97，'b'是98。这也可以很好地工作，因为'b' - 'a'在ASCII中是1。这将一直工作到'z'作为一个有效的映射从char到索引。这就是为什么要减去'a'。
问题是,并不是所有的系统使用ASCII,所以它不是一个便携式的解决方案。
第二个问题是合同问题。是否要求所有使用只传递一个包含char范围的字符串:'a' ->"z"?如果需要，则不需要检查。外部的任何使用都是未定义的，并且可以做任何事情。防御性编码，只执行'a'->'z'，只有在无法建立合同时才需要。这种防御契约在没有外部用户的内部类中最有用。如果这是开放API的一部分，那么可能需要警卫，但作为上下文外的片段。也许需要，也许不需要。所以尽量少写代码。