Insertion int Insert( Seqlist &l, listData x, int i /insert the new element into position i if(i<o‖i> Llength‖lL. length= Listsize) return U //failure else for( int j=Llength;j>i;j--) L data[l= Ldatai -1; Ldata=x; Llength++ return1;∥ successful
▪ Insertion int Insert ( SeqList &L, ListData x, int i ) { //insert the new element into position i if (i < 0 || i > L.length || L.length == ListSize) return 0; //failure else { for ( int j = L.length; j > i; j-- ) L.data[j] = L.data[j -1]; L.data[i] = x; L.length++; return 1; //successful } }
Deletion 25 34 5750164810963 delete x 01234567 2534575048109163 The average moving number of times(AMN if it is equal probability to delete every element AMN l(n-1)nn-1 2 i=0
▪ Deletion − = − = − − − = 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 delete x 25 34 57 50 48 09 63 0 1 2 3 4 5 6 7 The average moving number of times(AMN) if it is equal probability to delete every element
Deletion routine for Seqlist int Delete( seqlist &L, listDatax //delete x int i= Find (L, x); //find x in I if(i>=0){ Llength for(intj=i;j< Llength; j++) L datai=L datai+1; return 1 //successful return o //x is not in I
▪ Deletion routine for SeqList int Delete ( SeqList &L, ListData x ) { //delete x int i = Find (L, x); //find x in l if ( i >= 0 ) { L.length -- ; for ( int j = i; j < L.length; j++ ) L.data[j] = L.data[j+1]; return 1; //successful } return 0; //x is not in l }
Application of seqList: union of set void Union( seqlist &A, seqlist &&B)i int n=Length(a) int m= Length (B); for(int i=0; i< m; i++)i intx= GetDate(B,i);在B中取元素 intk=Find(A,x);M在中查找宫 jf(k==-1) 若未到入它 iNsert (A,x, n); n++,/
Application of SeqList: union of set 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++; } } }
Intersection of set void Intersection( Seq list &A, SeqList &&B)i int n= Length(a); int m= Length(B); inti=0 while(i<n) i intx=GeDt(A,i;M在4中取一元素 intk=Find(B,x);∥在B中查宫 if(k==-1)Delete(A, i);n-1 else i++ 未到在4中删除它
▪ Intersection of set void Intersection ( SeqList &A, SeqList &B ) { int n = Length ( A ); int m = Length ( B ); int i = 0; while ( i < n ) { int x = GetData ( A, i ); //在A中取一元素 int k = Find ( B, x ); //在B中查找它 if ( k == -1 ) { Delete ( A, i ); n--; } else i++; //未找到在A中删除它 } }