全国计算机二级公共基础知识考试重点(四)

全国计算机二级公共基础知识考试重点(四)

顺序表的删除运算

在顺序在存储结构的线性表中删除一个元素。

注意：找到删除的数据元素后，从该元素位置开始，将后面的元素一一向前移动，在移动完成后，线性表的长度减1

(1)删除运算的逻辑描述

线性表的删除运算是指将表的第i(1≤i≤n)个结点删去，使长度为n的线性表

(a1，…，ai-1，ai，ai+1，…，an)

变成长度为n-1的线性表

(a1，…，ai-1，ai+1，…，an)

注意：

当要删除元素的位置i不在表长范围(即i<1或i>L->length)时，为非法位置，不能做正常的删除操作

(2)顺序表删除操作过程

在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。若i=n，则只要简单地删除终端结点，无须移动结点;若1≤i≤n-1，则必须将表中位置i+1，i+2，…，n的结点，依次前移到位置i，i+1，…，n-1上，以填补删除操作造成的空缺。其删除过程【参见动画演示】

(3)具体算法描述

void DeleteList(SeqList *L,int i)

{//从L所指的顺序表中删除第i个结点ai

int j;

if(i<1||i>L->length)

Error("position error"); //非法位置

for(j=i;j<=L->length-1;j++)

L->data[j-1]=L->data[j]; //结点前移

L->length--; //表长减小

}

(4)算法分析

①结点的移动次数由表长n和位置i决定：

i=n时，结点的移动次数为0，即为0(1)

i=1时，结点的移动次数为n-1，算法时间复杂度分别是0(n)

②移动结点的平均次数EDE(n)

其中：

删除表中第i个位置结点的移动次数为n-i

pi表示删除表中第i个位置上结点的概率。不失一般性，假设在表中任何合法位置(1≤i≤n)上的删除结点的机会是均等的，则

p1=p2=…=pn=1/n

因此，在等概率插入的情况下，

顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是0(n)。

以上就是“全国计算机二级公共基础知识考试重点(四)”相关内容，小伙伴们快来了解一下吧，大家可“ 免费预约短信提醒”届时环球网校会及时为大家推送2020年全国计算机二级考试信息提醒，确保大家顺利考试!环球网校友情提示：在备战计算机二级考试中，环球网校特地为您准备了计算机二级复习资料，如有需要请点击文章下方“免费下载>>>计算机二级考试资料”下载学习。