、顺序擒 以顺序表或线性链表表示静态查找表 回顾顺序表的查找过程: STele 2137881992056456807513 012345678910 STLength 假设给定值e=66 要求ST.elem[i]=e,问:i=?
21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length
顺序宣线 查找过程:从表的一端开始逐个进行记录的关键字和给 定值的比较 算法描述 找64 例 012 64513192137 监视哨 比较次数 比较次数=5 查找第n个元素:1 查找第n1个元素:2 查找第1个元素:n 查找第个元素:n+1 查找失败: n+1
算法的实现 技巧ε把待查关键字key存入表头或表尾(俗称“哨兵”),这样 可以加快执行速度。 例:若将待查找的特定值key存入顺序表的首部(如0号单元),则 顺序查找的实现方案为:从后向前逐个比较! int Search Seq( ssTable ST, KeyType key )i //在顺序表ST中,查找关键字与key相同的元素;若成功,返回其位 置信息,否则返回0 STele|0小key=key/没设立哨兵,可免去查找过程中每一 步都要检测是否查找完毕。当n1000时,查找时间将减少一半。 for(i=STength; STelem i I. key!=key; --1); //不要用for(i=n;i>0;--i)或for(i=1;i<=n;i++) return i;/若到达0号单元才结柬循环,说明不成功,返回0值 (i=0)。成功时则返回找到的那个元素的位置i
int location( Sqlist L, Elem Type&e, Status(*compare)(Elem Type, Elem Type))t p L elem while( i<=Llength&& compare)(p+t,eD)i++, if (i-L length) return 1 else return o 3/location
STele 6421378819920564568075113 0 2345678910 kval= 64 STLength STelem 6021378819920564|56807513 0 2345678910 kval= 60 ST Length
21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length