if(llength>=Listsize) printf( overflow) exit(overflow) for(=1.length-1;j>=l-1; j-) I. dataLj+1=ldatal 1. data[l-1]F=X length++
⚫ 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) 不失一般性,假设在表中任何位置(1sisn+1) 上插入结点的机会是均等的,则 p=p2=p3=…=pn+1=1(n+1) 因此,在等概率插入的情况下, E(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较大时,算法的效 率相当低。虽然Ea(m)中n的的系数较小,但就 数量级而言,它仍然是线性阶的。因此算法的 平均时间复杂度为O(n) 2、删除 线性表的删除运算是指将表的第 i(1ⅰn)结点删除,使长度为n的线性表: a a ai, a 变成长度为n-1的线性表 a1 a 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(sqlist L, int D) Int f(<1‖ I>llength) printf(" position error") return error for(=i; j<=1.length-1; j++) 1. datalj-1]F=1. datal] 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--; }