令E(m表示在长度为n的线性表中插入一个元素所需移动 元素的期望值(即移动元素的平均次数),则 E Is ∑P 其中,P表示在表中第个位置上插入一个元素的概率:m是 在表中第个位置上插入一个元素时所需移动元素的次数,那 么m;=n-+1。不失一般性,假设在表中任何有效位置(1≤ ≤n+1)上插入元素的机会是均等的,即p1p2=…pn+=, 因此,在等概率插入的情况下有: ∑(m-i+1) n IS
令Eis(n)表示在长度为n的线性表中插入一个元素所需移动 元素的期望值（即移动元素的平均次数），则 i n 1 i 1 Eis pi m + = = 其中，pi表示在表中第i个位置上插入一个元素的概率；mi是 在表中第i个位置上插入一个元素时所需移动元素的次数，那 么mi = n-i+1。不失一般性，假设在表中任何有效位置（1 i n+1）上插入元素的机会是均等的，即 p1=p2=…=pn+1= ， 因此，在等概率插入的情况下有： + = = + − + = n 1 i 1 n 1 1 2 n (n i 1) is E
即,在顺序表上做插入运算平均要移动表中的一半 元素,当表长n较大时,算法的效率相当低,其平均 时间复杂度是on) 有时需要使得顺序表是有序的,即不指定插入位置, 按元素值从小到大插入
即，在顺序表上做插入运算平均要移动表中的一半 元素，当表长n较大时，算法的效率相当低，其平均 时间复杂度是O(n)。 有时需要使得顺序表是有序的，即不指定插入位置， 按元素值从小到大插入
2.删除 线性表的删除运算是指将表的第i(1≤isn)个元 素删去,使长度为n的线性表: a 125i-15ii+1:n 变成长度为n-1的线性表 aaa 29 1-131+13"n
线性表的删除运算是指将表的第i（1 i n）个元 素删去，使长度为n的线性表： （a1 ,a2 ,…,ai-1 ,ai ,ai+1 ,…,an） 变成长度为n-1的线性表： （a1 ,a2 ,…,ai-1 ,ai+1 ,…,an） ⒉ 删除
分析: 和插入运算类似,在顺序表上实现删除运 算也必须移动元素,才能反映出元素间逻辑 关系的变化。若i==n,则只要简单地删除 终端元素,不需移动元素;若1≤i≤n-1则 必须将表中位置1,+2,,n的元素依次前 移到位置i,许1,…,n-1上,以填补删除操作 造成的空缺
和插入运算类似，在顺序表上实现删除运 算也必须移动元素，才能反映出元素间逻辑 关系的变化。若i == n，则只要简单地删除 终端元素，不需移动元素；若1 i n -1则 必须将表中位置i+1,i+2,…,n上的元素依次前 移到位置i ,i+1 , …, n-1上，以填补删除操作 造成的空缺。 分析：
bool DeleteNode(sqlist &L, int i, int &e) ∥删除L的第个元素,被删元素值存入引用参数e; ∥若正常完成删除返回true,否则返回 false。 i int j; bool r= false;∥/预置标志 if(i|j> L Size)∥非法删除位置 cout < ERROR:invalid i !!n else∥/正常删除 e=L。elem[i-1];∥被删数据元素值放入e for(j=i;jL.Size;j+)∥数据元素依次前移 L elem[-1]=L elenD; L.Size-;∥表长减1
bool DeleteNode(sqList &L , int i , int &e) // 删除L的第i个元素，被删元素值存入引用参数e ； // 若正常完成删除返回true，否则返回false。 { int j ; bool r = false; // 预置标志 if(i<1 || i>L.Size) // 非法删除位置 cout << " ERROR:invalid i !!\n"; else // 正常删除 { e=L.elem[i-1]; // 被删数据元素值放入e for(j=i; j<L.Size; j++) // 数据元素依次前移 L.elem[j-1]=L.elem[j]; L.Size --; // 表长减1