1.3 线性表及顺序存储结构 
考点6 线性表的定义 
　　线性表是n(n≥0)个元素构成的有限序列(a1，a2，…，an)。表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表是一个空表，或可以表示为 
(a1，a2，…，an) 
　　其中ai(i=1，2，…，n)是属于数据对象的元素，通常也称其为线性表中的一个结点。 
　　其中，每个元素可以简单到是一个字母或是一个数据，也可能是比较复杂的由多个数据项组成的。在复杂的线性表中，由若干数据项组成的数据元素称为记录(record)，而由多个记录构成的线性表又称为文件(file)。在非空表中的每个数据元素都有一个确定的位置，如a1是第一个元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。非空线性表有如下一些结构特征： 
  (1)有且只有一个根结点a1，它无前件； 
  (2)有且只有一个终端结点an，它无后件； 
  (3)除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时称为空表。 
考点7 线性表的顺序存储结构 
　　线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。 
　　线性表的顺序存储结构具备如下两个基本特征： 
 　(l)线性表中的所有元素所占的存储空间是连续的；  
   (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 
　　假设线性表的每个元素需要占用k个存储单元，并以所占的存储位置ADR(ai+1)和第i个数据元素的存储位置ADR(ai)之间满足下列关系： 
　　ADR(ai+1)=ADR(ai)+k 
　　线性表第i个元素ai的存储位置为 
　　ADR(ai)=ADR(a1)+(i-1)×k 
　　式中ADR(ai)是线性表的第一个数据元素a，的存储位置，通常称做线性表的起始位置或基址。 
　　线性表的这种表示称做线性表的顺序存储结构或顺序映像，这种存储结构的线性表为顺序表。表中每一个元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比例的常数。如图1-4所示。由此只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。 

考点8 顺序表的插入运算 
　　线性表的插入运算是指在表的第i(1≤i≤n+l)个位置上，插入一个新结点x，使长度为n的线性表 
　　(a1，…，ai-1，ai，…，an) 
　　变成长度为n+1的线性表 
                            (a1，…，ai-1，x，ai，…，an) 
　　现在分析算法的复杂度。这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环结点后移语句上，该语句的执行次数(即移动结点的次数)是n-i+1。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。 
　　当i=n+1时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O(1)； 
　　当i=1时，结点后移语句，将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O(n)。 
　　由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度。 
    在长度为n的线性表中第i个位置上插入一个结点，令Eis ( n )表示移动结点的期望值(即移动的平均次数)，则在第i个位置上插入一个结点的移动次数为n-i+1。故 
不失一般性，假设在表中任何位置(1≤i≤n+1)上插入结点的机会是均等的，则 
                             p1=p2=p3=…=pn+1=1/(n+1) 
    因此，在等概率插入的情况下， 
    也就是说，在顺序表上做插入运算，平均要移动表上一半的结点。当表长n较大时，算法的效率相当低。虽然Eis ( n )中n的的系数较小，但就数量级而言，它仍然是线性级的。因此算法的平均时间复杂度为O(n)。