符号表(Symbol Tables)

时间:2024-07-30 14:32:56

小时候我们都翻过词典,现在接触过电脑的人大多数都会用文字处理软件(例如微软的word,附带拼写检查)。拼写检查本身也是一个词典,只不过容量比较小。现实生活中有许多词典的应用:

拼写检查

数据库管理应用中的数据词典

装载机,汇编器,便一起产生的符号表

网络公司的路由表(DNS域名解析)

在计算机科学中,提到抽象数据类型时,我们通常用术语符号表来代替词典。

什么是符号表?

通过上面的讨论,我们可以将符号表定义为一个数据结构,这个数据结构与一个关键字相对应。他支持一下操作:

搜索某个特定名称,检查是否在表中

获取这个名称的属性

修改这个名称的属性

插入一个新的名称及其属性

删除一个名称及其属性

总的来说符号表只支持三种操作:搜索,散列,删除。

例子:DNS域名解析,假设这里面的关键字是URL(网址),相应的值是IP地址。

插入特定的URL和相应的IP地址

给定URL,找到相应的IP地址

Key [Website] Value [IP Address]
www.abc.com 128.112.136.11
www.def.com 128.112.128.15
www.ghi.com 130.132.143.21
www.klm.com 128.103.060.55
www.studyalgorithms.com 104.28.31.39

符号表的实现参考符号表实现(Symbol Table Implementations)