删除值为x的元素时需要比较元素和移动元素的总次数为

  1. 在一个长度为n的线性表中,删除值为x的元素时需要比较元素和移动元素的总次数为( )。
    A.(n+1)/2 B.n/2
    C.n D.n+1
    解析:假设长度为n的线性表中只有一个值为x的元素,则从第一个元素起到找到值为x(假设为第i个元素)比较i次,删除i后,第i+1个元素到第n个元素都要移动,移动n-(i+1)+1即n-i次,故比较元素和移动元素的总次数为n次。注:以上答案是针对线性表中只有一个值为x的元素
    问一下那个移动n-(i+1)+1怎么来的

假设有10个元素,你删除第3个,那么从第4个到第10个元素都要向前移动一个位置。因此总共需要移动的元素个数是10-3个,也就是n-i

因为i+1到第n个元素都要移动,要计算移动多少次
n-(i+1)的意思是最后的第n个元素到第i+1个元素相隔了几个元素
也就是第i+1个元素后面还排了多少元素
比如n-(i+1)=k,那么意思就是第i+1个元素后面还有k个
移动的时候这k个元素都要移动,但这k个元素是指从第i+1后面到n要移动k个元素,不包括第i+1个元素
所以后面要加上第i+1个元素往前移动的一次
所以是移动了n-(i+1)+1次
化简后是n-1次

例如如,数组为 123456789 10
n为10,i为5,i+1为6
删除5后,数组就变成了1234 6789 10
n-(i+1)就是10-6=4
可得6后面还有4个元素
往前移动的次数就是7 8 9 10这四个元素移动
但没有包括6的移动
所以要把6的移动加上
所以就是n-(i+1)+1