我在为我的编译器课程做一个SymbolTable的程序...我遇到了一个pos的问题...为什么我们首先要用它呢？TIA<3
void insert(char *symbol, char *type)
{
int pos = cHash(symbol);
if (block[pos] == NULL)
{
block[pos] = new SymbolInfo();
block[pos]->symbol = symbol;
block[pos]->type = type;
block[pos]->next = NULL;
}
else
{
SymbolInfo *newNode = new SymbolInfo();
newNode->symbol = symbol;
newNode->type = type;
// pointer swap
SymbolInfo *nextNode = block[pos];
block[pos] = newNode;
newNode->next = nextNode;
}
}
这里的代码实现了所谓的链式哈希表。我们维护一个链表数组，并使用函数cHash将每个符号分配给其中一个链表。
这样存放东西的好处是速度快。如果我们把所有东西都放入一个单链表中，那么查找东西的平均成本是O(n)，其中n是列表中的条目数，因为平均来说，我们至少要查找列表中的一半条目。但是，通过拥有多个链表（例如，其中的b个），并或多或少随机地在它们之间分配项目，我们将查找的平均成本降低到O(1+N/b)，如果b与N大致相同的数量级，则查找速度要快得多。