顺序表插入的时间代价（移动次数) 在表中第i个位置插入，从data[i-1到data [last]成块后移 移动n-1-(i-1)+1=n-i计1项（假设表的长度为n,即n=last+1) 平均数据移动次数AMN(Average Moving Number)在各表项插入概率相等时为 1 n+1 AMN m+a-i+1)=n+++1+0) n+1 i=1 1 (n+l) n (n+1) 2 在插入时有n+1个插入位置，平均移动n/2项 16
平均数据移动次数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 0 1 23 45 6/ data 25 34 57 16 48 09 63 删除x16 last 0 1 2 3 4 56 data 25 34 57 48 09 63 龙tz 17
顺序表的表项删除 17
表项的删除算法 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+l)return false;/参数i不合理 x data[i-1]; for (int j=i;j<=last;j++) /依次前移，填补 data[j-1]dataj]; last--; return true; }; 18
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项到第lst+1项全部前移，需前 移的项数为n-(i计1)+1=n-i (假设表的长度为n,即n=last+1) 平均数据移动次数AMN(Average Moving Number)在n个表项删除概率相等时为 AMN-1I-)= 1(n-1)n n-1 i=1 2 2 在删除时有n个删除位置，平均移动(n-1)/2项 19
平均数据移动次数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 SegList<int>LA, SegList<int>LB) int n LA.Length () int m LB.Length () int x; for (inti=1;i<=m;i++){ LB.getData(i,x);/在LB中取一元素 intk=LA.Search(x);/在LA中搜索它 if(k==0) 若未找到插入它 in++;LA.Insert (n,x); 20
顺序表的应用： 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