n插入 23 56 25345716480963 插入X50 234567 2534|571501648109|63 顺序表插入时,平均数据移动次数AMN在各表项 插入概率相等时 AMN n (n+…+1+0) n+1 n+1 1n(n+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( Seq list &l, listData x, int i)& /在表中第i个位置插入新元素x if(i<0‖i>L. length Llengt Listsize) return o /插入不成功 else for(int j=Llength;j>i;j--) Ldata jl= ldatai -1] Ldata=X; Llength++ 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// 234″5′6″7 25345750480963 顺序表删除平均数据移动次数AMN在各表项 删除概率相等时 AMN (n-i-1) (n-1)nn-1 2 i=0
▪ 删除 − = − = − − − = 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, listData x& /在表中删除已有元素x inti=Find(L,x);M在表中查找x if(i>=0){ Llength for(intj=i;j<Length; j++) Ldata=Ldata[j+1 return 1 成功删除 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++) intx= GetData(B,i);在B中取一元素 intk=Find(A,x);M在A中查找它 f(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++; } } }