线性表是一种最简单、最容易的符号表构造方法，它按名字的出现顺序填写各个表项，可以用多个一维数组来存放名字及其相关信息。当要了解某一名字的有关信息，只需从符号表的第一项开始顺序查找即可。线性表的结构如图7-5所示，其中，指示器available总是指向下一个可用的空白表项。
图7-5 线性表
线性表中每一项的先后顺序是按先来先填的原则安排的，编译程序不做任何整理次序的工作。对于显式说明的程序设计语言来说，是根据名字在说明部分出现的先后顺序依次填入符号表的末尾；对于隐式说明的程序设计语言来说，是根据名字首次引用的先后顺序填入表中的。应当注意的是，当把一个新说明的名字填入符号表时，需要从符号表的首项开始顺序查找，如果一直查到available还未找到该名字，则说明该名字不在表中，此时可将它填进available所指的位置，然后使available指向下一个空白项；否则，说明表中已经存在该名字，则要报告重名错误。(www.xing528.com)
对于一张含n项的线性表而言，查找一个表项平均需要做n/2次的比较操作，显然效率很低。然而，由于线性表具有结构简单、节省存储空间等优点，因此，线性表依然受到很多编译程序设计者的青睐。
线性表的查找效率在一定程度上可以提高。例如，给每个表项增加一个指示器，通过这些指示器把所有的项按最新最近访问原则构造成一条链，从而使得在任何时候该链的第1个元素所指的项是最新最近被访问过的项，而第2个元素所指的项是次新次近被访问过的项，如此类推下去。每次查表时都按这条链所指的顺序进行，一旦查到就即刻改造这条链，使链头指向刚刚查到的那个项；并且，每当填入新项时，总让链头指向该最新项。于是，将含有这种链的线性表称作自适应线性表。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
