数据结构学习之路----------线性表顺序存储结构插入和删除节点平均移动次数

时间:2022-09-01 21:42:02

假设线性表的长度为n。

首先来说线性表顺序存储的插入问题:

线性表元素有n个,那么插入位置有n+1个。

数据结构学习之路----------线性表顺序存储结构插入和删除节点平均移动次数

插入第一个位置需要移动n个,第二个需要移动n-1个,第三个需要移动n-2个。以此类推,总共移动次数为n+(n-1)+(n-2)+...+2+1+0=(n+1)*n/2。

共有n+1个插入位置,所以平均需要移动次数为n/2 次。

接下来说说线性表顺序存储的删除问题:

线性表有n个元素,所以删除位置数肯定是n个。

删除第一个要移动n-1个,删除第二个要移动n-2个,第三个要n-3个。总共移动次数为(n-1)+(n-2)+...+2+1+0=n*(n-1)/2。

共有n个删除位置,所以平均移动次数为(n-1)/2次。