索引顺序查找 1)由索引确定记录所在区间 2)在顺序表的某个区间内进行查找 可见 索引顺序查找的过程也是一个 缩小区间”的查找过程 注意:索引可以根据查找表的特点来构造 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 索引顺序查找 1）由索引确定记录所在区间 2）在顺序表的某个区间内进行查找 注意：索引可以根据查找表的特点来构造 可见: 索引顺序查找的过程也是一个 “缩小区间”的查找过程
索引顺序查找的平均查找长度= 查找“索引”的平均查找长度 +查找“顺序表”的平均查找长度 对于按顺序索引表的平均查找长度 ASL=G+S)+ 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 索引顺序查找的平均查找长度 = 查找“索引”的平均查找长度 + 查找“顺序表”的平均查找长度 对于按顺序索引表的平均查找长度: ( ) 1 2 1 = + s + s n ASL
Ordered lists DEFINITION An ordered list is a list in which each entry con tains a key, such that the keys are in order. That is, if entry i comes before entry j in the list, then the key of entry i is less than or equal to the key of entry j All List operations except insert and replace apply without mod ification to an ordered list a Methods insert and replace must fail when they would other- wise disturb the order of a list a We implement an ordered list as a class derived from a con- tiguous List. In this derived class, we shall override the meth ods insert and replace with new implementations 四川大学计算机(软件)学院
四川大学 计算机(软件)学院
class Ordered_list: public List< Record>t Ordered_list( Error-code insert(const Record &data); Error-code insert(int position, const Record &data Error-code replace(int position, const Record &data 四川大学计算机(软件)学院
四川大学 计算机(软件)学院
Overloaded Insertion We also overload the method insert so that it can be used with a single parameter. The position is automatically determined so as to keep the resulting list ordered: Error-code Ordered-list: insert(const Record &data Post: f the Ordered_list is not full. the function succeeds. The record data is inserted into the ist, following the last entry of the list with a strictly lesser key(or in the first list position if no list element has a lesser key) Else: the function fails with the diagnostic Error-code overflow. * int s= size(; int position; for(position=0; position s; position++)t Record list_data: retrieve(position, list_data if (data > list_data)break; return List< Record>: insert(position, data);
四川大学 计算机(软件)学院