if(llength>=Listsize) printf(" overflow); exit(overflow) forG=llength-1; ]>=1-1; j--) I. dataLj+1=l datal 1. data[ l-1=X Ilength++
⚫ if(l.length>=ListSize) ⚫ printf(“overflow”); ⚫ exit(overflow); ⚫ for(j=l.length-1;j>=I-1;j--) ⚫ l.data[j+1]=l.data[j]; ⚫ l.data[I-1]=x; ⚫ l.length++; ⚫ }
现在分析算法的复杂度。 这里的问题规模是表的长度,设它的 值为。该算法的时间主要化费在循环的 结点后移语句上,该语句的执行次数 (即移动结点的次数)是。由此可看出, 所需移动结点的次数不仅依赖于表的长 度,而且还与插入位置有关。 。当时,由于循环变量的终值大于初值, 结点后移语句将不进行;这是最好情况, 其时间复杂度O(1) 当=1时,结点后移语句将循环执行n次, 需移动表中所有结点,这是最坏情况
⚫ 现在分析算法的复杂度。 ⚫ 这里的问题规模是表的长度，设它的 值为。该算法的时间主要化费在循环的 结点后移语句上，该语句的执行次数 （即移动结点的次数）是。由此可看出， 所需移动结点的次数不仅依赖于表的长 度，而且还与插入位置有关。 ⚫ 当时，由于循环变量的终值大于初值， 结点后移语句将不进行；这是最好情况， 其时间复杂度O（1）； ⚫ 当=1时，结点后移语句将循环执行n次， 需移动表中所有结点，这是最坏情况
其时间复杂度为O(n) 由于插入可能在表中任何位置上进行,因 此需分析算法的平均复杂度 在长度为n的线性表中第个位置上插入一 个结点,令E(n)表示移动结点的期望值(即移 动的平均次数),则在第个位置上插入 点的移动次数为n-+1。故 Es(n)p(n-1+1) 不失一般性,假设在表中任何位置(1sisn+1) 上插入结点的机会是均等的,则 p=p2=p3=…=pn+1=1/n+1 因此,在等概率插入的情况下, Es(n)=(n-+1)/(n+1)=n/2
⚫ 其时间复杂度为O（n）。 ⚫ 由于插入可能在表中任何位置上进行，因 此需分析算法的平均复杂度 在长度为n的线性表中第i个位置上插入一 个结点，令Eis(n)表示移动结点的期望值（即移 动的平均次数），则在第i个位置上插入一个结 点的移动次数为n-I+1。故 Eis(n)= pi (n-I+1) 不失一般性，假设在表中任何位置(1≦i≦n+1) 上插入结点的机会是均等的，则 p1=p2=p3=…=p n+1=1/(n+1) 因此，在等概率插入的情况下， Eis(n)= (n-I+1)/(n+1)=n/2
也就是说,在顺序表上做插入运算,平均要移 动表上一半结点。当表长n较大时,算法的效 率相当低。虽然E(n)中n的的系数较小,但就 数量级而言,它仍然是线性阶的。因此算法的 平均时间复杂度为O(n) 2、删除 线性表的删除运算是指将表的第 (1in)结点删除,使长度为n的线性表: (a ai1, ai, a 变成长度为n-1的线性表 a a 1 a
也就是说，在顺序表上做插入运算，平均要移 动表上一半结点。当表长 n较大时，算法的效 率相当低。虽然Eis(n)中n的的系数较小，但就 数量级而言，它仍然是线性阶的。因此算法的 平均时间复杂度为O(n)。 2、删除 线性表的删除运算是指将表的第 i(1≦i≦n)结点删除，使长度为n的线性表： (a1，…a i-1，ai，a i+1…，an ) 变成长度为n-1的线性表 (a1，…a i-1，a i+1，…，an )
Void deleteList(Ssqlist* L, int D) f(<1‖ I>llength) printf(" Position error") return error for(j=i;j<=llength-1; j++) I data[j-1=l data[iI; 1. length-
Void deleteList(Sqlist*L，int I) { int j; if(I<1 || I>l.length) printf(“Position error”); return ERROR for(j=i;j<=l.length-1;j++) l.data[j-1]=l.data[j]; l.length--; }