插入 234567 25345716480963 插入x50 234 2534575016480963 顺序表插入时,平均数据移动次数AMN在各表项 插入概率相等时 AMN ∑(n-i)=—(n+…+1+0) n+1 +1) (n+1) 2
▪ 插入 2 2 ( 1) ( 1) 1 ( 1 0) 0 1 1 ( ) 1 1 = n n n n n n i n n i n = + + = + + + = + − = + AMN 25 34 57 16 48 09 63 0 1 2 3 4 5 6 7 插入 x 50 25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7 50 i 顺序表插入时，平均数据移动次数AMN在各表项 插入概率相等时
顺序表的插入 int Insert Seqlist &l, listData x, inti)t /在表中第i个位置插入新元素x if(i<0‖|i> Llength‖ Llength= Listsize) return O /插入不成功 ese for(int j=Llength;j>i;j-) L data=x: Llength++,. L data[jl=Ldatai -1 return1;/插入成功
▪ 顺序表的插入 int Insert ( SeqList &L, ListData x, int i ) { //在表中第 i 个位置插入新元素 x if (i < 0 || i > L.length || L.length == ListSize) return 0; //插入不成功 else { for ( int j = L.length; j > i; j-- ) L.data[j] = L.data[j -1]; L.data[i] = x; L.length++; return 1; //插入成功 } }
删除 2534575016480963 删除x/ 0123 4″5″6 7 25345750480963 顺序表删除平均数据移动次数AMN在各表项 删除概率相等时 AMN l(-1)nn-1 2
▪ 删除 − = − = − − − = 1 0 2 1 2 1 ( 1) ( 1) 1 = n i n n n n n i n AMN 25 34 57 50 16 48 09 63 16 删除 x 25 34 57 50 48 09 63 0 1 2 3 4 5 6 7 顺序表删除平均数据移动次数AMN在各表项 删除概率相等时
顺序表的删除 int Delete( Seqlist &l, listDatax)t /在表中删除已有元素x inti=Find(L,x);M在表中查找x if(i>=0){ L.length--; for(int j=i;j< Llength; j++) L data[jl=Ldatai+1; return 1 ∥F功删除 return 0; 表中没有x
▪ 顺序表的删除 int Delete ( SeqList &L, ListData x ) { //在表中删除已有元素 x int i = Find (L, x); //在表中查找 x if ( i >= 0 ) { L.length -- ; for ( int j = i; j < L.length; j++ ) L.data[j] = L.data[j+1]; return 1; //成功删除 } return 0; //表中没有 x }
顺序表的应用集合的“并”运算 void Union( Seqlist &a, seqlist &B)i int n=Length(A) int m= Length (B ) for (int i=0; i< m; i++)t intx= GetData(B,i);M在B中取一元素 intk=Find(A,x);M在A中查找它 if(k==-1) 若未找到插入它 iNsert(A,x,n); n++;)
顺序表的应用:集合的“并”运算 void Union ( SeqList &A, SeqList &B ) { int n = Length ( A ); int m = Length ( B ); for ( int i = 0; i < m; i++ ) { int x = GetData ( B, i ); //在B中取一元素 int k = Find (A, x); //在A中查找它 if ( k == -1 ) //若未找到插入它 { Insert ( A, x, n ); n++; } } }