插入到每个位置的概率相等的情况下，平均移动次 数是/2，有些情况下插入到每个位置的概率不一 定相等，怎麽算？假设插入到第一个位置的概率是 112,其余位置是1/2n,所需移动元素次数的期望 值（平均值)（用到概率中的数学期望概念)： B-21-jw六n-1h) n+l n+l i=1 i=2
◼ 插入到每个位置的概率相等的情况下，平均移动次 数是n/2，有些情况下插入到每个位置的概率不一 定相等，怎麽算？假设插入到第一个位置的概率是 1/2，其余位置是1/2n，所需移动元素次数的期望 值（平均值）（用到概率中的数学期望概念）：
2、删除线性表的第个数据元素 ao ao ao a a a a2 az a 1 ag a; a3 a4 a4 a4 as as as a6 n as a6
i a0 a1 a2 a6 a5 a4 a3 i i n n n a0 a1 a2 a5 a4 a3 a6 a0 a1 a2 a5 a4 a3 x a6 2、 删除线性表的第i个数据元素
分析删除线性表的第个数据元素所需移动元素次数 ■答：从第+1个数据元素到第n个都需向上移动，共 需移动n-i次 每一个位置上的数据元素都有可能被删除，平均移动 次数是多少？ 答：删除第一个数据元素需要n-1次，第二个数据元 素需要n-2次，第三个位置上n-3次，依次类推，第n 个位置上0次，平均移动次数为： ■[(n-1)+(n-2)+.+1]n=(n-1)/2,即： n-l n(n-1) 平均次数 2 =n-1 n n 2
◼ 分析删除线性表的第i个数据元素所需移动元素次数 ◼ 答：从第 i+1个数据元素到第n 个都需向上移动，共 需移动n- i次 ◼ 每一个位置上的数据元素都有可能被删除，平均移动 次数是多少？ ◼ 答：删除第一个数据元素需要n-1次，第二个数据元 素需要n-2次，第三个位置上n-3次，依次类推，第n 个位置上0次，平均移动次数为： ◼ [（n-1）+（n-2）+.+1]/n=（n-1）/2 , 即： 2 n -1 n 2 n(n -1) n j n-1 j 1 = = = 平均次数 =
■删除每个数据元素的概率相等的情况下即pi=1n,平 均移动次数是(-1)2，有些情况下删除每个数据 元素概率不一定相等，怎麽算？假设删除第一个数据 元素概率是112，其余位置是-可所需移动元素次数的 期望值（平均值）（用到概率中的数学期望概念）： R-2P4a-=分×a-*z 1,×∑(m-i0 i=1 i=2
◼ 删除每个数据元素的概率相等的情况下即pi=1/n，平 均移动次数是（n-1）/2，有些情况下删除每个数据 元素概率不一定相等，怎麽算？假设删除第一个数据 元素概率是1/2，其余位置是 所需移动元素次数的 期望值（平均值）（用到概率中的数学期望概念）： 2(n 1) 1 −
2.2.3源码实现 一、几点说明： ■1、定义线性表接口IListDS<T> interface IListDS<T> { int Count();//求长度 void Clear();/清空操作 boolean IsEmpty();//判断线性表是否为空 void Append(T item));//附加操作 void Insert(T item,inti);//插入操作 T Delete(inti);//删除操作 T GetE1em(inti);//取表元 int Locate(T value);/按值查找
2.2.3源码实现 ◼ 一、 几点说明： ◼ 1、定义线性表接口IListDS<T> interface IListDS<T> { int Count(); //求长度 void Clear(); //清空操作 boolean IsEmpty();//判断线性表是否为空 void Append(T item);//附加操作 void Insert(T item, int i);//插入操作 T Delete(int i); //删除操作 T GetElem(int i); //取表元 int Locate(T value);//按值查找 }