由于插入可能在表中任何位置上进行,因此 需分析算法的平均复杂度 在长度为n的线性表中第i位置上插入一个 结点,令E(n)表示移动结点的期望值(即移动 的平均次数),则在第i位置上插入一个结点 的移动次数为n-+1。故 E(n)=p(n-+1) 不失一般性,假设在表中任何位置(1至in+1) 上插入结点的机会是均等的,则 p=p2=p3=.pn+1=1/(n+1) 因此,在等概率插入的情况下, E(n)=(n-H+1/(n+1)=n/2
由于插入可能在表中任何位置上进行，因此 需分析算法的平均复杂度 在长度为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) 删除 线性表的删除运算是指将表的第 1in)结点删除,使长度为n的线性表: a a-1 ,a;,a 变成长度为n-1的线性表 a a i-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 )
算法思想 ①进行合法性检查,I是否满足1<=I<=n; ②判线性表是否已空, LIength=0 ③将第I+1至第n个元素逐一向前移一个位置; ④将表的长度减1。 Void deletelist(sqlist L, int D nt if(I<1‖> L length) i printf( position error); return ERROR J for(=1;<=Llength-1;j++) I. datalj-1]F=Ldatal L. length--;)
算法思想： ① 进行合法性检查，I是否满足1<=I<=n； ② 判线性表是否已空， L.length=0； ③ 将第I+1至第n个元素逐一向前移一个位置； ④ 将表的长度减1。 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--;}
该算法的时间分析与插入算法相似,结点的移 动次数也是由表长n和位置诀决定 若Ⅰ-n,则由于循环变量的初值大于终值 移语句将不执行,无需移动结点; 若I=1,则前移语句将循环执行n-1次,需移 动表中除开始结点外的所有结点。这两种情况 下算法的时间复杂度分别为O(1)和On) 删除算法的平均性能分析与插入算法相似。 在长度为n的线性表中删除一个结点,令Ede(n) 表示所需移动结点的平均次数,删除表中第i 结点的移动次数为n-i,故 Ede(n= pi(n-D 式中,pi凄表示删除表中第个结点的概率。在等
• 该算法的时间分析与插入算法相似，结点的移 动次数也是由表长n和位置i决定。 • 若I=n，则由于循环变量的初值大于终值，前 移语句将不执行，无需移动结点； • 若I=1，则前移语句将循环执行n-1次，需移 动表中除开始结点外的所有结点。这两种情况 下算法的时间复杂度分别为O(1)和O(n)。 • 删除算法的平均性能分析与插入算法相似。 在长度为n的线性表中删除一个结点，令Ede(n) 表示所需移动结点的平均次数，删除表中第i个 结点的移动次数为n-i，故 Ede(n)= pi(n-I) • 式中，pi表示删除表中第i个结点的概率。在等