DATA STRUCTURES template <class Type> int Seqlist< Type>:: Remove( Type &x) 在表中删除已有元素x int i= Find(x) ∥在表中搜索x f(i>=0){ last -- or(In it=i; j<=last; j ++) datal]=datal +1; return 1 成功删除 return u ∥表中没有x Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES template <class Type> int SeqList<Type>::Remove ( Type & x ) { //在表中删除已有元素x int i = Find (x); //在表中搜索 x if ( i >= 0 ) { last-- ; for ( int j = i; j <= last; j++ ) data[j] = data[j+1]; return 1; //成功删除 } return 0; //表中没有 x }
DATA STRUCTURES 删除算法分析(移动的元素个数) 最好:0 最坏:n1 平均: AM Is ∑(n-i-1) l(n-1)nn-1 i=0 n 2 *O(n Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 删除算法分析（移动的元素个数） ➢最好： ➢最坏： ➢平均： − = − = − − − = 1 0 2 1 2 1 ( 1) ( 1) 1 = n i n n n n n i n AMN 0 n-1 *O(n)
DATA STRUCTURES 顺序表的应用:集合的“并”和“交”运篁 template <class type> void Union( seqlist<type>& la, Seglist< type>& lB)i int n=LA Length o; int m=LB Length(; for( inti=l; i-m; i++ Type x=LBGe(1);M在LB中取一元素 intk=LA,Find(x);/在LA中搜索它 f(k==-1) /若未找到插入它 (LA Insert(n+l, x); n++; Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES template <class Type> void Union ( SeqList<Type> & LA, SeqList<Type> & LB ) { int n = LA.Length ( ); int m = LB.Length ( ); for ( int i = 1; i <= m; i++ ) { Type x = LB.Get(i); //在LB中取一元素 int k = LA.Find (x); //在LA中搜索它 if ( k == -1 ) //若未找到插入它 { LA.Insert (n+1, x); n++; } } } 顺序表的应用：集合的“并”和“交”运算 ？
DATA STRUCTURES template <class Type> void Intersection( Seqlist<Type>& la, Seg list< type>& lB i int n=LALength(; int m=-LB Length(; int i=0; while(i<n Type x= LA. Get(1);在L4中取一元素 ntk=LB.Fd(x);在LB中搜索它 if (k==-1LA Remove(i;n-i else i+ 未找到在L4中删除它 } Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES template <class Type> void Intersection ( SeqList<Type> & LA, SeqList<Type> & LB ) { int n = LA.Length ( ); int m = LB.Length ( ); int i = 0; while ( i < n ) { Type x = LA.Get (i); //在LA中取一元素 int k = LB.Find (x); //在LB中搜索它 if ( k == -1 ) { LA.Remove (i); n--; } else i++; //未找到在LA中删除它 } }
DATA STRUCTURES 顺序表: 优点:存储利用率高,存取速度快 插入和删除操作时? 插入:AMN=n/2 删除:AMN=(n1)/2 Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 顺序表： 插入和删除操作时？ 插入：AMN=n/2 删除：AMN=(n-1)/2 优点：存储利用率高，存取速度快