Trie 实现：使用 Int 与 Char

Question

我目前正尝试在 C 中实现一个 trie，以便进行拼写检查（字典取自加载到 trie 结构中的文本文件）。

这是我当前的节点结构（取自https://www.cs.bu.edu/teaching/c/tree/trie/）：

typedef struct trieNodeTag 
{
    char key;
    struct trieNodeTag *next, *children;
} trieNodeT;

key 是要加载到内存中的每个单词的字母。

我的问题如下：使用 int 类型作为 key 对内存/速度有影响吗？ char直接当int处理吗？

谢谢！

Answer 1

int 的行为是否与 char 不同也取决于平台。类型 int 可能是机器字，更容易寻址；但是，char 的内存大小可能更小。

Answer 2

由于 char 后跟两个指针，struct 将得到 padded 给 next 和 children 一个合适的对齐。假设 int 的大小小于或等于系统上指针的大小，声明 key 和 int 不会改变 struct 的内存要求.

就速度而言，您很可能看不出两种方式有太大差异。一个好的实用方法是选择最适合您的程序逻辑的类型，并且仅当分析表明它会产生很大差异时才将其更改为不同的类型。

Answer 3

My question is the following: does that make a difference in memory / speed to use a type int for key ?

如果您将其 key 成员的类型从 char 修改为 [=，struct trieNodeTag 的大小很可能（但不确定）会保持不变13=]，因为编译器很可能会布置该结构，以便指针 next 从结构开头的偏移量是四个字节的倍数。如果您想确定，请将 sizeof() 运算符应用于结构的每个版本，并比较结果。结果在某种程度上取决于您使用的 C 实现。

Is a char treated directly as an int ?

在大多数表达式的计算中，char 类型的操作数在被操作之前被提升为 int。这很便宜，甚至可能是免费的，但是不，char 不会被直接视为 int。

总的来说，如果代码与键入 int 或 char 的密钥同样正确，那么您应该会发现两者之间的性能差异很小或没有。

不过，我认为您提出了错误的问题。 int 和 char 类型之一很可能更自然地适合成员 key 的预期使用。我猜那是 char，但无论是哪个，都应该使用它。努力编写有意义且能正常工作的代码。为任务使用适当的算法，但在衡量你的表现并发现它缺乏之前，不要担心精细的性能细节。

Trie 实现：使用 Int 与 Char

Trie Implementation: using Int vs Char

c

struct

design-patterns

trie