顺序表的搜索算法 template <class E> int SeqList<E>::Search(E x)const{ /在表中顺序搜索与给定值X匹配的表项，找到则 川函数返回该表项是第几个元素，否则函数返回0 for (int i=0;i<=last;i++) /顺序搜索 if data[i]x return+l;/表项序号和表项位置差l return 0; /搜索失败 ; 11
11 顺序表的搜索算法 template <class E> int SeqList<E>::Search(E & x) const { //在表中顺序搜索与给定值 x 匹配的表项，找到则 //函数返回该表项是第几个元素，否则函数返回0 for (int i = 0; i <= last; i++) //顺序搜索 if ( data[i] == x ) return i+1; //表项序号和表项位置差1 return 0; //搜索失败 };
顺序表的搜索（查找) 012345↓ast 01 234512ast data 253457164809 data253457164809 48tN x=50: 25 34 57 16 48 09 25 34 57 16 48 09 25 3457 16 48 09 253457 16 4809 25 34 5716 48 09 25 345716 4809 25 34 5716 48 09 25 3457 16 48 09 2为 25345716 4809 2为 x=48 x=50 12
顺序表的搜索（查找） x = 48 x = 50 12
顺序查找数据的时间代价（比较次数分析) ACN(Average Comparing Number) (假设表的长度为n,即n=last+1) 搜索成功：表项的查找概率p,,比较次数c 平均比较次数ACN= ∑p: C i=1 若搜索概率p,相等，则 ACN (1+2+·+n) 三 n i=1 n 1 (1+n) *n 二 米 2 2 搜索不成功：数据t比较n次 13
2 1 2 1 (1 ) (1 2 ) 1 1 = 1 n n n n n n i n ACN n i + = + = = + + + = = 顺序查找数据的时间代价（比较次数分析） 搜索成功：表项i的查找概率pi，比较次数ci 若搜索概率pi 相等，则 平均比较次数 搜索不成功：数据比较n次 ACN(Average Comparing Number) (假设表的长度为n,即n = last + 1) 13 = n i i i ACN p * c 1 =
顺序表的插入 last 0 1 2 34 56/7 data 25 34 5716 48 09 63 ●年●●● 插入x 50 last 0 12 3八 45 b 7 data 25 34 57 50 16 48 09 63 年中年。。平 i↑z 14
顺序表的插入 14
表项的插入算法 template <class E> bool SeqList<E>:Insert (int i,E x) /将新元素x插入到表中第i(l≤i≤last什2)个表项位 /置。 if (last ==maxSize-1)return false; /表满 if(i<1‖i>last+2)return false;/参数i不合理 for (int j last;j>=i-1;j--) /依次后移 data[j+1]data[j]; data[i-1]=x; /插入（第i表项在data[i-l]处） last++; return true; /插入成功 15
15 表项的插入算法 template <class E> bool SeqList<E>::Insert (int i, E x) { //将新元素x插入到表中第i (1≤i≤last+2) 个表项位 //置。 if (last == maxSize-1) return false; //表满 if (i < 1 || i > last+2) return false; //参数i不合理 for (int j = last; j >= i-1; j--) //依次后移 data[j+1] = data[j]; data[i-1] = x; //插入(第 i 表项在data[i-1]处) last++; return true; //插入成功 };