DATA STRUCTURES 插入的主要思想: (1)检查插入操作要求的有关参数的合理性; (2)将顺序表最后位置加1 (3)将第逐第n-1个表项依次往后移动一个位 置 (4)把新的表项插入在顺序表的第个位置 Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 插入的主要思想： （1）检查插入操作要求的有关参数的合理性； （2）将顺序表最后位置加1 （3）将第i至第n-1个表项依次往后移动一个位 置； （4）把新的表项插入在顺序表的第i个位置
DATA STRUCTURES template <class Type> int Seqlist<Type>:: Insert type &x, int i 在表中第个位置插入新元素x f(i0‖>last+l‖!at== Max size-1) return 09 /插入不成功 else last++ for(int j=last;j>i;1-) datal 1「;三1 ata datai=x return l /插入成功 Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES template <class Type> int SeqList<Type>::Insert ( Type & x, int i ){ //在表中第 i 个位置插入新元素 x if ( i < 0 || i > last+1 || last == MaxSize-1 ) return 0; //插入不成功 else { last++; for ( int j = last; j > i; j-- ) data[j] = data[j -1]; data[i] = x; return 1; //插入成功 } }
DATA STRUCTURES 插入算法分析(移动的元素个数) 最好:0 最坏:n 平均: AM=、1又 ∑ (n-i)=—(n+…+1+0 n+17 n+1 1n(n+1)n (n+1)2 2 =O(n) Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 插入算法分析(移动的元素个数) ➢最好： ➢最坏： ➢平均： 2 2 ( 1) ( 1) 1 ( 1 0) 1 1 ( ) 1 1 = 0 n n n n n n n i n AMN n i = + + = + + + + − = + = 0 n *O(n)
DATA STRUCTURES 删除: int Remove(Type&x) last datal25345716480963… 删除x16 last data253457480963 ↑℃ Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES ◼删除： int Remove ( Type & x )
DATA STRUCTURES 删除的主要思想: (1)在顺序表中查找x,如果x在表中不存在 则不能删除 (2)如果x在表中存在,设x在顺序表中的 位置为i (3)将顺序表的最后位置减1; (4把顺序表中原来第计+1至第n-1个表项依 次向前移动一个表项位置 Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 删除的主要思想： (1) 在顺序表中查找x,如果x在表中不存在， 则不能删除； (2)如果x在表中存在，设x在顺序表中的 位置为i; (3) 将顺序表的最后位置减1； (4)把顺序表中原来第i+1至第n-1个表项依 次向前移动一个表项位置