// Definition of a Key class class Keyt public. // Add any constructors and methods for key data. private. // Add declaration of key data members here l Declare overloaded comparison operators for keys. bool operator==(const Key &x, const Key &y bool operator >(const Key &x, const Key &y bool operator<(const Key &x, const Key &y bool operator >=(const Key &x, const Key &y bool operator <=(const Key &x, const Key &y) bool operator !=(const Key &x, const Key &y); Definition of a record class: class recordi public. Key Keyo; / implicit conversion from Record to Key. l Add any constructors and methods for record objects. private: // Add data components 西川大学计算机(软件)学院
四川大学 计算机(软件)学院 // Definition of a Key class: class Key{ public: // Add any constructors and methods for key data. private: // Add declaration of key data members here. }; // Declare overloaded comparison operators for keys. bool operator ==(const Key &x, const Key &y); bool operator > (const Key &x, const Key &y); bool operator < (const Key &x, const Key &y); bool operator >=(const Key &x, const Key &y); bool operator <=(const Key &x, const Key &y); bool operator !=(const Key &x, const Key &y); // Definition of a Record class: class Record{ public: Key Key(); // implicit conversion from Record to Key. // Add any constructors and methods for Record objects. private: // Add data components. };
Sequential Search and Analysis Begin at one end of the list and scan down it until the desired key s found or the other end is reached: Error code sequential search(const list<Record> &the list, const Key &target, int &position) Post: If an entry in the list has key equal to target, then return success and the output parameter position locates such an entry within the list *t otherwise return not present and position becomes invalid. int s= the list size for(position=0; position <s; position++) Record data the list. retrieve(position, data); if(data==target) return success; return not present; 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 Sequential Search and Analysis Begin at one end of the list and scan down it until the desired key is found or the other end is reached: Error_code sequential_search(const List<Record> &the_list, const Key &target, int &position) /* Post: If an entry in the_list has key equal to target, then return success and the output parameter position locates such an entry within the list. Otherwise return not_present and position becomes invalid. */ { int s = the_list.size(); for (position = 0; position < s; position++) { Record data; the_list.retrieve(position, data); if (data == target) return success; } return not_present; }
折半查找 上述顺序查找表的查找算法简单 但平均查找长度较大,特别不 适用于表长较大的查找表 若以有序表表示静态查找表, 则查找过程可以基于“折半”进行 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不 适用于表长较大的查找表 折半查找 若以有序表表示静态查找表， 则查找过程可以基于“折半”进行
基于有序顺序表的折半搜索 设n个对象存放在一个有序顺序表中 并按其关键码从小到大排好了序 折半搜索时,先求位于搜索区间正中的 对象的下标md,用其关键码与给定值 x比较 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 基于有序顺序表的折半搜索 ◼ 设n个对象存放在一个有序顺序表中， 并按其关键码从小到大排好了序 ◼ 折半搜索时, 先求位于搜索区间正中的 对象的下标mid，用其关键码与给定值 x比较
1. Element mid. key=x搜索成功 2 ement mid). key>x把搜索区间缩小 到表的前半部分,继续折半搜索 3 ElementI mid. key<x把搜索区间缩小 到表的后半部分,继续折半搜索 如果搜索区间已缩小到一个对象,仍 未找到想要搜索的对象,则搜索失败 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 1.Element[mid].key==x 搜索成功 2.Element[mid].key>x 把搜索区间缩小 到表的前半部分，继续折半搜索 3.Element[mid].key<x 把搜索区间缩小 到表的后半部分，继续折半搜索 ◼ 如果搜索区间已缩小到一个对象，仍 未找到想要搜索的对象，则搜索失败