■2.2.2顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性 表的一些操作，如线性表的构造、第个元 素的访问。 注意：C语言中的数组下标从“0”开始，因 此，若L是Sglist类型的顺序表，则表中第i 个元素是l.data[i-1]。 以下主要讨论线性表的插入和删除两 种运算。 1、插入 线性表的插入运算是指在表的第 i(1≤isn+1个位置上，插入一个新结点x
2.2.2 顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性 表的一些操作，如线性表的构造、第i个元 素的访问。 注意：C语言中的数组下标从“0”开始，因 此，若L是Sqlist类型的顺序表，则表中第i 个元素是l.data[i-1]。 以下主要讨论线性表的插入和删除两 种运算。 1、插入 线性表的插入运算是指在表的第 i(1≦i≦n+1个位置上，插入一个新结点x
使长度为n的线性表 (an,.ai1,a,.an) 变成长度为n+1的线性表 (a1,.ai-1,X,aj,.an)
使长度为n的线性表 (a1，.a i-1，ai，.，an ) 变成长度为n+1的线性表 (a1，.a i-1，x，ai，.，an )
1.[初值] 获取线性表L,插入位置i,插入元素e 2.[检查参数] 若（插入位置超出线性表长度范围）则输出错误 3.[检查空间] 若（线性表空间不足） 则 分配新空间 若（分配成功） 则修改线性表的容量 否则输出溢出错误 4.[插入元素] 将插入位置以及其后的L中的元素全部后移一格 将元素e插入位置i 线性表长度增加1 5.[算法结束]
1.[初值] 获取线性表L，插入位置i，插入元素e 2.[检查参数] 若 （插入位置超出线性表长度范围） 则 输出错误 3.[检查空间] 若 （线性表空间不足） 则 分配新空间 若 （分配成功） 则 修改线性表的容量 否则 输出溢出错误 4.[插入元素] 将插入位置i以及其后的L中的元素全部后移一格 将元素e插入位置i 线性表长度增加1 5.[算法结束]
■现在分析算法的复杂度。 这里的问题规模是表的长度，设它的值为。 该算法的时间主要花费在循环的结点后移 语句上，该语句的执行次数（即移动结点 的次数)是n-+1。由此可看出，所需移动 结点的次数不仅依赖于表的长度，而且还 与插入位置有关。 ■ 当i=n+1时，由于循环变量的终值大于初值， 结点后移语句将不进行：这是最好情况， 其时间复杂度0(1)； 当i=1时，结点后移语句将循环执行n次，需 移动表中所有结点，这是最坏情况
现在分析算法的复杂度。 这里的问题规模是表的长度，设它的值为n。 该算法的时间主要花费在循环的结点后移 语句上，该语句的执行次数（即移动结点 的次数）是n-i+1。由此可看出，所需移动 结点的次数不仅依赖于表的长度，而且还 与插入位置有关。 当i=n+1时，由于循环变量的终值大于初值， 结点后移语句将不进行；这是最好情况， 其时间复杂度O（1）； 当i=1时，结点后移语句将循环执行n次，需 移动表中所有结点，这是最坏情况
■其时间复杂度为O(n) 由于插入可能在表中任何位置上进行，因此需分析算 法的平均复杂度 在长度为的线性表中第i个位置上插入一个结点，令 Es()表示移动结点的期望值（即移动的平均次数），则 在第i个位置上插入一个结点的移动次数为-i+1。故 不失一般性，假设在表中任何位置(1sn+1)上插入结点 的机会是均等的，则 P1=p2=p3=.=pt1=1/(n+1) 因此，在等概率插入的情况下
其时间复杂度为O（n）。 由于插入可能在表中任何位置上进行，因此需分析算 法的平均复杂度 在长度为n的线性表中第i个位置上插入一个结点，令 Eis(n)表示移动结点的期望值（即移动的平均次数），则 在第i个位置上插入一个结点的移动次数为n-i+1。故 不失一般性，假设在表中任何位置(1≦i≦n+1)上插入结点 的机会是均等的，则 p1=p2=p3=.=p n+1=1/(n+1) 因此，在等概率插入的情况下， + = = − + 1 1 ( ) ( 1) n i i s i E n p n i 2 ( 1) 1 1 ( ) 1 1 n n i n E n n i i s − + = + = + =