（7）交换线性表中序号i和序号j的元素swap（i，j）//交换data[i]和data[j]public void swap(int i,int j)E tmp=data[i];data[i]=data[j]; data[j]=tmp;16/58
public void swap(int i,int j) //交换data[i]和data[j] { E tmp=data[i]; data[i]=data[j]; data[j]=tmp; } 16/58
（8）在线性表中插入e作为第i个元素Insert（i，e）//在线性表中序号i位置插入元素epublic void Insert(int i, E e)/参数错误抛出异常{if(i<oi>size)thrownewIllegalArgumentException（"插入：位置i不在有效范围内"）；//满时倍增容量if(size==capacity)updatecapacity(2*size);//将data[i]及后面元素后移一个位置for (int j=size; j>i; j--)data[j]=data[j-1];//插入元素edata[i]=e;//顺序表长度增1size++;7Vaiai+1an-1UUU从an-1元素开始移动起17/58
public void Insert(int i, E e) //在线性表中序号i位置插入元素e { if (i<0 || i>size) //参数错误抛出异常 throw new IllegalArgumentException("插入:位置i不在有效范围内"); if (size==capacity) //满时倍增容量 updatecapacity(2*size); for (int j=size; j>i; j-) //将data[i]及后面元素后移一个位置 data[j]=data[j-1]; data[i]=e; //插入元素e size++; //顺序表长度增1 } a0 a1 . ai ai+1 . an-1 . 从an-1元素开始移动起 17/58
public void Insert(int i,E e)//在线性表中序号i位置插入元素e{ if (i<o ll i>size)//参数错误抛出异常thrownewIllegalArgumentException（"插入：位置i不在有效范围内"）；//满时倍增容量if(size==capacity)updatecapacity(2*size);//将data[il及后面元素后移一个位置for (int j=size; j>i; j--)data[j]=data[j-1];1/插入元素edata[i]=e;//顺序表长度增1size++;7调用updatecapacity多少次？18/58
调用updatecapacity多少次？ public void Insert(int i, E e) //在线性表中序号i位置插入元素e { if (i<0 || i>size) //参数错误抛出异常 throw new IllegalArgumentException("插入:位置i不在有效范围内"); if (size==capacity) //满时倍增容量 updatecapacity(2*size); for (int j=size; j>i; j-) //将data[i]及后面元素后移一个位置 data[j]=data[j-1]; data[i]=e; //插入元素e size++; //顺序表长度增1 } 18/58
1主要时间花在元素移动上。有效插入位置的取值是0～n，共有n+1个位置可以插入元素：当=0时，移动次数为n，达到最大值。当n时，移动次数为0，达到最小值。其他情况，需要移动data[i..n-1]的元素，移动次数为（n-1)-i+1=n-i。Pi=所需移动元素的平均次数为：n+1n1n(n + 1)nPinXn122n+1n+i=0=0插入算法的平均时间复杂度为o（n）。19/58
主要时间花在元素移动上。有效插入位置i的取值是0～n，共有n+1个位置可 以插入元素： 当i=0时，移动次数为n，达到最大值。 当i=n时，移动次数为0，达到最小值。 其他情况，需要移动data[i.n-1]的元素，移动次数为(n-1)-i+1=n-i。 a0 a1 . ai ai+1 . an-1 . 所需移动元素的平均次数为： 插入算法的平均时间复杂度为O(n)。 19/58
说明扩容运算updatecapacity()在size+1次插入中仅仅调用一次其平摊时间为01)，上述算法时间分析中可以忽略它。28/58
扩容运算updatecapacity()在size+1次插入中仅仅调用一次， 其平摊时间为O(1)，上述算法时间分析中可以忽略它。 说明 20/58