顶序表的搜索算法 template <class e> int Seqlist<E>: Search(e x)const 在表中顺序搜索与给定值ⅹ匹配的表项,找到则 ∥/函数返回该表项是第几个元素,否则函数返回0 for(nti=0;i<=last;i++)顺序搜索 if data1==x) return 1+1;/表项序号和表项位置差1 return o ∥搜索失败
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; //搜索失败 };
顺序表的搜索(查找) last 2345↓ last dl25345716148409」aal25134|571648109 x=50 25 」34 57164809 253457164809 2534571648409 2534571648109 25|34|571514809 25|34571614809 134571648[09 2534571648109 2534571648 x=48 x=502N
顺序表的搜索（查找） x = 48 x = 50 12
顺序查找数据的时间代价(比较次数分析) ACN(Average Comparing Number) (假设表的长度为n1即n=ast+1) 搜索成功:表项查找概率p,比较次数c 平均比较次数ACN=∑P*c i=1 若搜索概率p相等,则 ACM (1+2+…+n)= 1(1+n)*n1+ 米 2 搜索不成功:数据比较次
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 data25345716480963 插入x50 last data2534575016480963…… i↑x
顺序表的插入 14
表项的插入算法 template <class e> bool seqlist<E>:: Insert (int 1, Ex)i 新元素x插入到表中第1(1≤at+2)个表项位 ∥置。 if(ast= maxSize-1) return false;∥表满 if(1<1li>lat+2) return false;∥参数i不合理 for (int j=last;j>=1-1; j-=) 依次后移 data[j+1]=datall data[i-l]=x;/插入(第i表项在data[i-1]处) last++ return true; /插入成功
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; //插入成功 };