数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学不同数据结构在编译器设计中的作用是什么？
在编译过程中，每次遇到标识符时都会搜索符号表。如果找到新的名称或关于现有名称的新信息，则会添加数据。因此，在设计符号表结构时，需要一种能够有效地插入新条目并识别表中现有条目的方案。
数据结构中使用了四种符号表，如下所示：
- 列表- 为符号实现数据结构的最简单明了的方法是线性记录列表，如图所示。
它可以使用单个数组或多个等效数组来保存名称及其相关数据。新名称按遇到的顺序插入列表中。可以从数组的开头搜索到指针AVAILABLE标记的位置（表示数组空闲部分的开头）来检索关于某个名称的数据。
自组织列表- 通过增加少量额外空间，我们可以使用一个技巧来节省大量搜索符号表的时间。它可以为每个记录添加一个LINK字段，我们按照LINK指示的顺序搜索列表。当引用名称或第一次创建其记录时，可以通过移动指针将该名称的记录移动到列表的前面。
搜索树- 符号表组织的更有效方法是为每个记录插入两个链接字段LEFT和RIGHT。我们使用这些字段将记录链接到二叉搜索树中。
这棵树具有这样的特性：通过遵循LEFT(i)链接，然后遵循任何链接序列，从NAME(i)访问的所有名称NAME(j)都将按字母顺序（符号上，NAME(j) < NAME(i)）在NAME(i)之前。
二叉搜索树算法
- 最初，Ptr将指向树的根。
- 当Ptr ≠ NULL时
- 如果NAME = NAME(Ptr)
- 则返回true
- 否则如果NAME < NAME(Ptr) 则
- Ptr = LEFT(Ptr)
- 否则 Ptr = RIGHT(Ptr)
- 循环结束
哈希表- 哈希表包含K个从0到K-1的条目。这些条目是指向符号表的指针，指向符号表的名称。我们可以使用哈希函数'h'来判断“Name”是否在符号表中，使得h(Name)的结果是0到K-1之间的整数。可以通过position = h(Name)来搜索任何名称。
更新于：2021年11月8日
3K+浏览量
广告