📄 6.6.2.htm
字号:
<html>
<head>
<title>编译原理</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<link type="text/css" rel="stylesheet" href="../css/specification.css">
</head>
<body>
<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.6.0b.htm'"></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.6.3.htm'"></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>6.6.2 线性表(linear list)</b></font>
<table><tr><td>    </td>
<td class="content">
<P>
我们首先要介绍的符号表是线性符号表。符号表的表项的建立与查寻虽然是两个相互独立的操作，但是它们是密切关联的，它们都取决于符号表的结构方式。如6.6.1节所讨论的符号表的数据结构，即按出现的先后顺序把每一个表项作为一个记录填人表中，那么可以说，使用记录的线性表是实现符号表的数据结构的最简单的方法，记录的线性表如图6.27所示。
</p>
</td></tr></table>
<br>
<table align=center border=0 cellspacing=0 cellpadding=0 width="40%">
<tr>
<td align=right valign=bottom width="50%">available  ---><br><br></td>
<td align=left width="50%">
<table border="0" cellspacing="0" cellpadding="4" align=center style="border-left:#000000 1px double;border-top:#000000 1px double;border-bottom:#000000 0px double;border-right:#000000 1px double;">
<tr>
<td align=center style="border-bottom:#000000 1px double">
id<sub>1</sub><br>- - - - - - -<br>info<sub>1</sub>
</td>
</tr>
<tr>
<td align=center style="border-bottom:#000000 1px double">
id<sub>2</sub><br>- - - - - - -<br>info<sub>2</sub>
</td>
</tr>
<tr>
<td align=center style="border-bottom:#000000 1px double">
<br>...<br><br>
</td>
</tr>
<tr>
<td align=center style="border-bottom:#000000 1px double">
id<sub>n</sub><br>- - - - - - -<br>info<sub>n</sub>
</td>
</tr>
<tr>
<td><br><br></td>
</tr>
</table>
</td>
</tr>
</table>
<br><br><p align=center><b>图6.27</b>  记录的线性表</p><br>
<table><tr><td>    </td>
<td class="content">
<P>
我们使用一个数组或等价的几个数组来存放名字及与其有关的信息。新的名字和有关信息将顺序加入到数组元素中去。数组元素的当前位置由指针available标记，指出下一个符号表表项将要存放的位置。名字的检索是从表的前端到始端进行的。如图6.27所示，当名字的位置被找到时，其有关信息紧随其后。在查找某个名字时，如果我们已到达数组的开始位置而没有找到所要的名字，即出现一个错误——所期待的名字不在表中。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
如果符号表包含着n个名字，在插入一个新名字时，我们必须查看整个符号表以确定这个名字是否已在符号表中，为此所需的工作量与n成正比。另一方面，为查寻关于某个名字的数据平均需要检索n/2个名字，这样，一次查寻所需的工作量也是与n成正比的。于是，由于插入和查寻所需的时间都与n成正比，所以在表中。插入n个名字和在n个名字上进行e次查找所需的总的时间最多为cn(n＋e），其中c是一个常数用来表示一组机器指令的操作的时间。在一个中型的源程序中，通常譬如可能有n=100，e=1000。如果n和e都增大10倍的话，那么总的花费就将增大100倍。人们常常把插入n个名字和进行e次查找所需的总的时间作为评价符号表的重要基础。
</p>
</td></tr></table>
<br>
<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.6.0b.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.6.3.htm'"></img></td>
</tr>
</table>
</BODY>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -