在编译器设计中，列表和自组织列表是什么？

列表

• 从概念上讲，用线性记录列表实现符号表的数据结构是最简单和容易实现的，如下所示：

• 它可以使用单个数组来存储名称及其关联的信息。新名称按遇到的顺序插入到列表中。它可以从数组的开头到指针 AVAILABLE（指示数组空部分的开头）标记的位置检索我们搜索的名称的相关数据。
• 当放置名称时，可以在接下来的单词中找到关联的数据。如果我们在没有识别名称的情况下到达 available，则可能会出现使用未定义名称的错误。
• 如果插入 n 个名称和 m 个查询，则总工作量为 c(n+m)，其中 c 是表示新机器操作所需时间的常数。如果插入 n 个名称和 m 个查询，则总工作量为 c(n+m)，其中 c 是表示新机器操作所需时间的常数。

关于列表数据结构的一些事实

• 添加新名称所需的工作量与 n 成正比，其中符号表包含 n 个名称。
• 在列表中搜索名称的成本与 n/2 成正比。
• 要插入 n 个名称和 m 个查询，总工作量为

                     cn (n + m)               其中 c 为常数

优点

• 它用于最小化空间需求。
• 易于理解和实现。

缺点

• 它用于顺序访问
• 需要完成的工作量很大。

自组织列表

以牺牲少量额外空间为代价，可以使用一个技巧来节省大量搜索符号表的时间。它可以向每个记录添加一个 LINK 字段，我们按 LINK 指示的顺序搜索列表。下图显示了一个包含四个名称的符号表的示例。

FIRST 指示链接列表中第一个记录的位置，每个 LINK 字段表示列表中的下一个记录。当引用名称或首次创建其记录时，可以通过移动指针将该名称的记录移动到列表的开头。

这种方法用于减少列表组织中的搜索时间。一个特殊的属性链接被添加到名称信息中，允许列表具有动态特性，此特性有助于最大限度地减少空间浪费，并在一定程度上促进可重用性。

第一个指针指向符号表的开头。

如果名称按以下顺序排列：

3 → 1 → 4 → 2

如果需要特定记录，则需要将记录移动到列表的开头。

假设我们需要 4，那么新的连接将是：

4 → 3 → 1 → 2

优点

• 它可以提高搜索效率。
• 它可以在一定程度上提高可重用性。

缺点

• 维护如此多的链接和连接可能很困难。
• 它需要额外的空间。

Ginni

更新于：2021年11月8日

浏览量 1K+

启动您的职业生涯

通过完成课程获得认证

开始