8.1 ADT 符号表

  • 「符号表 symbol table」 是计算机科学领域中,把字典作为抽象数据型时,通常使用术语「符号表」,定义为名字-属性对 (name-attribute pairs) 的集合。名称和属性的特征随着应用的不同而变化。例如,在分类词汇表中,名字是一个单词,而属性是该词的同义词表。
  • 「ADT 符号表」 SymbolTable 是一个名字-属性对的集合,其中名称是唯一的。
class SymbolTable
{
    SymbolTable Create(int max_size) {
        // 创建一个空符号表,其最大容量是 max_size
    }
    bool IsIn(SymbolTable symtab, Name name) {
        if (name 在 symtab 中) return true;
        else return false;
    }
    Attribute Find(SymbolTable symtab, Name name) {
        if (name 在 symtab 中) return 相关属性
        else return 空属性
    }
    SymbolTable Insert(SymbolTable symtab, Name name, Attribute attr) {
        if (name 在 symtab 中) 用 attr 替换当前属性
        else 把名字-属性对插入 (name, attr) 到符号表 symtab
    }
    SymbolTable Delete(SymbolTable symtab, Name name) {
        if (name 不在 symtab 中) return
        else 从符号表 symtab 中删除名字-属性对 (name, attr)
    }
}
  • 「散列 hashing」 一种使查找、插入和删除操作具有良好期望性能的技术。
  • 将符号表的存储方式用查找树来表示时,查找时依赖于标识符,而散列依赖 「散列函数 hashing function」
  • 散列分为:「静态散列 static hashing」「动态散列 dynamic hashing」

results matching ""

    No results matching ""