Question

在顺序表中插入或删除一个数据元素,需要平均移动多少个数据元素

Answer 1

添加到第1个,移动N个；
添加到第2个,移动(N-1)个；
……
添加到第N个,移动1个；
添加到第(N+1)个,移动0个
平均：(0+1+2+……+N)/(N+1)=N/2
删除第1个,移动(N-1)个；
删除第2个,移动(N-2)个；
……
删除第N个,移动0个
平均：[0+1+……+(N-1)]/N=(N-1)/2
顺序表的结构定义:
#define
maxlen
50
//定义顺序表中元素个数最多有几个
typedef
struct{elementtype
data[maxlen];
//elementtype是元素的类型
依具体情况而定
int
listlen;
//便于时刻了解顺序表里元素的个数
}seqlist;
//顺序表的名称
不妨为seqlist
声明顺序表类型变量:
seqlist
L,L1;
如顺序表的每个结点占用len个内存单元，用location
(ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。则有如下的关系:location
(ki+1)
=
location
(ki)
+len
location
(ki)
=
location(k1)
+
(i-1)len
存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。

Answer 2

最少的是0个（插入在最后或删除最后一个）
最多的是N个（插入在最前面或删除最前面一个）
随机的位置当然是在0——N之间了，当然平均值就是（0+1+2+3+.....+(n-1)+n)/n=n/2