![](https://csdnimg.cn/release/download_crawler_static/3654184/bg5.jpg)
数据结构教程与题解
24
中 c
i
=n−i+1,但
i
未知。不失一般性,假设在表中任何合法位置(1≤i≤n+1)上插入结点
的机会是均等的,则
12 n+1
pp p 1/(n1)
,因此,在等概率插入的情况下:
n1 n1
ii
i1 i1
Mp
c
ni1 n
n1 2
也就是说,在顺序表上做插入运算,平均要移动表中一半的结点。当表长 n 较大时,
算法的效率相当低。
M 中的系数较小,但就数量级而言,它仍然是线性阶的,因此算法的
平均时间复杂度是
O(n)。
2.删除
线性表的删除运算是指将表的第
i(1≤i≤n)个结点删去,使长度为 n 的线性表(a
1
, …,
a
i−1
, a
i
, a
i+1
, …, a
n
)变为长度为 n−1 的线性表(a
1
, …, a
i−1
, a
i+1
, …, a
n
)。
和插入算法类似,在顺序表上实现删除运算也必须移动结点:先将表中位置 i+1~n 上
的结点全部前移一位以填补删除操作造成的空缺,然后表长减
1。特别地,删除位置 i=n
时无须移动结点,直接删除终端结点即可。
注意,这里结点的移动次序只能从前向后进行,即按 i+1, i+2, …, n 的次序进行。删除
过程见图
2.3。
a
1
1
前
0maxsize−1
删除
a
i−1
a
i+1
a
i
a
n−1
a
n
a
2
i−1ii−2
a
1
1
后
n−1
0maxsize−1
删除
a
i−1
a
n
空闲
空闲
n−2
…
…
a
2
i−1ii−2
a
i+1
a
i+2
……
……
图 2.3 顺序表中删除结点过程示意图
删除过程的具体算法如下:
int delete(sqlist *L,int i) { //从顺序表中删除第 i 个位置上的结点
int j;
if(L−>n==0) {cout<<”表空,不能删除!(下溢)\n”;return −1;}
if(i<1 || i>L−>n) {cout<<”非法删除位置!\n”;return 0;}
for(j=i+1;j<=L−>n;j++)
L−>data[j−2]=L−>data[j−1]; //结点前移,第 j 个结点的数组下标是 j−1
L−>n−−; //修改表长
return 1; //删除成功
}
该算法的时间分析与插入算法类似,结点的移动次数也是由表长 n 和位置 i 决定的。
删除第
i 个结点时,结点的移动次数为 c
i
=n−i。当 i=n 时结点移动次数最少,为 0 次;当 i=1
时结点移动次数最多,为 n−1 次。这两种情况下算法的时间复杂度分别是 O(1)和 O(n)。
删除算法的平均性能分析也与插入算法相似。如果在每个位置 i(1≤i≤n)上删除结
点的概率相等,则 。这样,在等概率删除的情况下:
i
p1/n
nn
ii
i1 i1
ni n1
Mpc
n2