7.3 Binary Search 1. Ordered Lists 二分查找/搜索 (折半查找/搜索) DEFINITION An ordered list is a list in which each entry contains 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 modification to an ordered list Methods insert and replace must fail when they would otherwise disturb the order of a list
7.3 Binary Search 1. Ordered Lists DEFINITION An ordered list is a list in which each entry contains 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 modification to an ordered list. ◆Methods insert and replace must fail when they would otherwise disturb the order of a list. 二分查找/搜索 (折半查找/搜索)
We implement an ordered list as a class derived from a contiguous List. In this derived class we shall override the method insert and replace with now implementations. 覆盖父类的插入方法 typedef Key record ∠用条件 class Ordered_list: public List<Records i public: Ordered listo; Error_code insert(const Record &data) Error_ code insert(int position, const Record &data Error_ code replace (int position, const Record &data); ;
◆We implement an ordered list as a class derived from a contiguous List. In this derived class, we shall override the methods insert and replace with new implementations. 重载的插入方法 typedef Key Record; class Ordered_list: public List<Record> { public: Ordered_list( ); Error_code insert(const Record &data); Error_code insert(int position, const Record &data); Error_code replace(int position, const Record &data); }; 该查找方法的 应用条件 覆盖父类的插入方法
Error code Ordered list: insert(const Record &data) ∥按要插入的 data. key值插入到合适的位置,以保持有序 for(int i=0; i<size & data > entry[; i++); return List<Record>: :insert(i, data); 带两个参数的重载父类的插入方法,请看Pg280 Note: The overridden method replaces a method of the base class by one with a matching name and parameter list. The overloaded method matches in name but has a different parameter list
Error_code Ordered_list::insert(const Record &data) { // 按要插入的data.key值插入到合适的位置，以保持有序 for(int i=0; i<size() && data >= entry[i]; i++); return List<Record>::insert(i, data); } 带两个参数的重载父类的插入方法，请看 Pg.280 Note: The overridden method replaces a method of the base class by one with a matching name and parameter list. The overloaded method matches in name but has a different parameter list