编译器设计中的列表和自组织列表是什么？
列表
在线性记录列表中实现符号表的数据结构在概念上是最简单和容易的，如下所示 -
它可以使用单独的数组来存储名称及其相关信息。新名称按照遇到的顺序插入到列表中。它可以检索我们搜索的名称的数据，从数组的开头一直到指针 AVAILABLE 标记的位置，该指针指示数组空部分的开头。
放置名称后，可以在接下来的单词中发现相关数据。如果我们在没有识别名称的情况下到达可用，则使用未定义的名称可能会出错。
它可以插入n个名字，m查询总工作量是c(n+m)，其中c是常数，表示新机器所需的时间operations.It可以插入n个名字，m查询总工作量是c(n+m)，其中c是常数代表新机器操作所需的时间。
关于列表数据结构的一些事实
添加新名称所需的工作与 n 成正比，其中符号表包含 n 个名称。
在列表中搜索名称的成本与 n/2 成正比。
要插入 n 个姓名和 m 个查询，总工作量为
cn (n + m) 其中 c 是常数
优势
它用于最小的空间要求。
它易于理解和实施。
坏处
它用于顺序访问
需要完成的工作量很大。
自组织列表
以一点额外空间为代价，它可以使用一个技巧来节省搜索符号表所花费的大部分时间。它可以为每条记录添加一个 LINK 字段，我们按照 LINK 指示的顺序搜索列表。图中显示了四个名称符号表的示例。
首先，给出链表上第一条记录的位置，每个 LINK 字段表示链表上的下一条记录。当一个名字被引用或它的记录被第一次创建时，它可以通过移动指针将该名字的记录移动到列表的前面。
这种方法用于减少列表组织中的搜索时间。在名称信息中添加了一个特殊的属性链接，允许列表中的动态特性，这个特性有助于最大限度地减少空间的浪费，也在一定程度上促进了可重用性。
第一个指针指向符号表的开始。
如果我们按以下顺序命名。
3 → 1 → 4 → 2
如果我们需要特定的记录，我们需要将记录移动到列表的前面。
假设我们需要 4 个，那么新的连接将是
4 → 3 → 1 → 2
优势
它可以提高搜索效率。
它可以在一定程度上促进可重用性。
坏处
维护如此多的链接和连接可能很困难。
它可以有额外的空间需求。
以上是 编译器设计中的列表和自组织列表是什么？ 的全部内容， 来源链接： utcz.com/z/363460.html
