线性表的插入和删除两种运算。
1、插入
线性表的插入运算是指在表的第 I(1≦i≦n+1 个位置上,插入一个新结点 x,
使长度为 n 的线性表
(a
1
,…a
i-1
,a
i
,…,a
n
)
变成长度为 n+1 的线性表
(a
1
,…a
i-1
,x,a
i
,…,a
n
)
算法 2.3
顺序表的插入
status ListInsert_sq ( SqList &L, int i , elemtype e) //在表中第 i 个位置插入新元素 x
{
if(i<1 || i>L.length+1) return ERROR;
if(L.length>=L.ListSize)
{
newbase=(elemtype*)realloc(L.elem,(L.listsize+Listincrement)*sizeof(elemtype));
if(!newbase) exit(overflow);
L.elem=newbase;
L.listsize+=Listincrement;
}
q=&(L.elem[i-1]); //q 为插入位置
for(p=&L.elem[L.length-1];p>=q;p--) *(p+1)=*p;
*q=e;
++L.length;
Return ok;
}
算法的复杂度。
1) 当 i=1 时,结点后移语句将循环执行 n 次,需移动表中所有结点,这是最坏情况,
2) 当 i=n+1 时,结点后移语句将不进行;这是最好情况,其时间复杂度 O(1);
3) 当 i 是一个随机数时由于插入可能在表中任何位置上进行,因此需分析算法的平均复杂度
在长度为 n 的线性表中第 i 个位置上插入一个结点,令 E
is
(n)表示移动结点的期望值(即移动的平均
次数),则在第 i 个位置上插入一个结点的移动次数为 n-i+1。故
E
is
(n)= p
i
(n-I+1)
不失一般性,假设在表中任何位置(1≦i≦n+1)上插入结点的机会是均等的,则
p
1
=p
2
=p
3
=…=p
n+1
=1/(n+1)
因此,在等概率插入的情况下,
插入:线性表的插入运算是指在表的第<<!)个位置上,插入一个新结点:
25 34 57 16 48 09 63
0 1 2 3 4 5 6 7
25 34 57 16 48 09 63
0 1 2 3 4 5 6 7
原位置的值=被覆盖
50
50
插入 x
i
50