顺序表插入的时间代价(移动次数) 在表中第i个位置插入,从 datai-到 data last成块后移 移动n1-(1)+1=n计项(假设表的长度为n,即n=last+1) 平均数据移动次数MN( Average Moving Number)在各表项插入概率相等时为 AMN ∑(n-+1)=,(m+…+1+0) n+1 n+1 1m(n+1)n (n+1)22 在插入时有n+1个插入位置,平均移动m/2项
平均数据移动次数AMN（Average Moving Number）在各表项插入概率相等时为 顺序表插入的时间代价（移动次数） 在插入时有n+1个插入位置，平均移动n/2项 在表中第 i 个位置插入，从data[i-1] 到data [last] 成块后移， 移动n-1-(i-1)+1 = n-i+1项 (假设表的长度为n,即n = last + 1) 2 2 ( 1) ( 1) 1 ( 1 0) 1 1 ( 1) 1 1 = 1 1 n n n n n n n i n n i = + + = + + + + − + = + + = AMN 16
顺序表的表项删除 last data25345716|480963 ●。●。● 删除x16 last data2534|57480963 ↑
顺序表的表项删除 17
表项的删除算法 template <class e> bool seqlist<E> Remove (int i, E& x)i ∥表中删除第i(1ast+1)个表项,通过引用型 ∥参数ⅹ返回被删元素。 if (last=-1)return false; 表空 if(1<1i>lat+l) return false;/参数i合理 x=data1-1I for(intj=j;j<=last;j+)∥依次前移,填补 datalj-1]=data last return true
18 表项的删除算法 template <class E> bool SeqList<E>::Remove (int i, E& x) { //从表中删除第 i (1≤i≤last+1) 个表项，通过引用型 //参数 x 返回被删元素。 if (last == -1) return false; //表空 if (i < 1 || i > last+1) return false;//参数i不合理 x = data[i-1]; for (int j = i; j <= last; j++) //依次前移，填补 data[j-1] = data[j]; last--; return true; };
顺序表表项删除的时间代价(移动次数) 删除第i个表项,需将第计1项到第ls汁+项全部前移,需前 移的项数为m-(计+1)+1=ni(假设表的长度为n,即n=last+1) 平均数据移动次数AMN( Average Moving Number)在n个表项删除概率相等时为 AMN=∑(n- l(n-1)nn-1 2 在删除时有n个删除位置,平均移动(n-1)/2项
平均数据移动次数AMN（Average Moving Number）在n个表项删除概率相等时为 顺序表表项删除的时间代价(移动次数) 在删除时有n个删除位置，平均移动(n-1)/2项 删除第 i 个表项，需将第 i+1 项到第 last+1项全部前移，需前 移的项数为 n-(i+1)+1 = n-i (假设表的长度为n,即n = last + 1) = − = − − = n i n n n n n i n 1 2 1 2 1 ( 1) ( ) 1 AMN = 19
顺序表的应用:顺序表实现集合的“并”运算 void Union( seqlist<ints la, Seqlistsint &lB i int n=LA Length(; int m=LB Length(; int xo for( inti=l; i<=m; i++i LB. getDat(ix);M在LB中取一元素 intk= LA Search(x);M在LA中搜索它 if (k==0 /若未找到插入它 in++; LAInsert(n, x);)
顺序表的应用： void Union ( SeqList<int> & LA, SeqList<int> & LB ) { int n = LA.Length ( ); int m = LB.Length ( ); int x; for ( int i = 1; i <= m; i++ ) { LB.getData(i, x); //在LB中取一元素 int k = LA.Search (x); //在LA中搜索它 if ( k == 0 ) //若未找到插入它 {n++; LA.Insert (n, x);} } } 用顺序表实现集合的“并”运算 20