数据结构与程序设计(王丽苹)18searching

《数据结构与程序设计(王丽苹)18searching》由会员分享，可在线阅读，更多相关《数据结构与程序设计(王丽苹)18searching（38页珍藏版）》请在装配图网上搜索。

1、5/5/2021 数 据 结 构 与 程 序 设 计 1 数 据 结 构 与 程 序 设 计 (18) 王 丽 苹 5/5/2021 数 据 结 构 与 程 序 设 计 2 Chapter 7 SEARCHINGn Information retrieval is one of the important applications of computers.n We are given a list of records, where each record is associated with one piece of information, which we shall call a k

2、ey(关 键 字 ). (BOOK P269 FIGURE 7.1) n 本 章 讨 论 顺 序 存 储 列 表 的 查 找操 作 ， 链 接 存 储 在 第 10章 讨 论 。 5/5/2021 数 据 结 构 与 程 序 设 计 3 Chapter 7 SEARCHINGn We are given one key, called the target, and are asked to search the list to find the record(s) (if any) whose key is the same as the target.n We often ask how

3、times one key is compared with another during a search. This gives us a good measure of the total amount of work that the algorithm will do. 5/5/2021 数 据 结 构 与 程 序 设 计 4 Chapter 7 SEARCHINGn The searching problem falls naturally into two cases.n Internal searching（ 内 部 查 找 ） means that all the recor

4、ds are kept in high-speed memory. n In external searching（ 外 部 查 找 ） , most of the records are kept in disk files. n We study only internal searching. 5/5/2021 数 据 结 构 与 程 序 设 计 5 Implementation of Key Classn class Key n int key;n public:n Key (int x = 0);n int the_key( ) const;n ; n bool operator =

5、 (const Key 5/5/2021 数 据 结 构 与 程 序 设 计 6 Implementation of Key Classn Key:Key(int x)n key=x;n n int Key:the_key() constn return key;n n bool operator = (const Key n 5/5/2021 数 据 结 构 与 程 序 设 计 7 Implementation of Record Classn class Recordn public:n operator Key( ); / implicit conversion from Record

6、to Key .n Record(int x=0, int y=0);n private:n int key; n int other;n ; 5/5/2021 数 据 结 构 与 程 序 设 计 8 Implementation of Record Classn Record:Record(int x, int y)n key=x;n other=y;n n Record:operator Key( )n Key tmp(key); n return tmp；n 5/5/2021 数 据 结 构 与 程 序 设 计 9 Test Mainn void main()n Key target(5

7、);n Record myrecord(5,9);n if (target=myrecord) coutyesendl;n else coutnoendl;n n 调 用 operator Key( )构 造 临 时 Key tmp,采 用 void operator = (const Key 主 要完 成 从 Recorder对 象 到 Key对 象 的 自 动 转换 。 可 以 用 其 他 方 法 完 成 该 功 能 。n Use constructor to conversion from Record to Key . 5/5/2021 数 据 结 构 与 程 序 设 计 12 Imp

8、lementation of Key Classn class Key n int key;n public:n Key (int x = 0);n Key (const Record n int the_key( ) const;n ; n bool operator = (const Key 5/5/2021 数 据 结 构 与 程 序 设 计 13 Implementation of Key Classn Key:Key(int x)n key=x;n n Key:Key(const Record n n int Key:the_key() constn return key;n n b

9、ool operator = (const Key n 5/5/2021 数 据 结 构 与 程 序 设 计 14 Implementation of Record Classn class Recordn public:n Record(int x=0, int y=0);n int the_key() const;n private:n int key;n int other; n ; 5/5/2021 数 据 结 构 与 程 序 设 计 15 Implementation of Record Classn Record:Record(int x, int y)n key=x;n othe

10、r=y;n n int Record:the_key() constn return key; n 5/5/2021 数 据 结 构 与 程 序 设 计 16 Test Mainn void main()n Key target(5);n Record myrecord(5,9);n if (target=myrecord) coutyesendl;n else coutnoendl;n n 调 用 Key(const Record n for (position = 0; position s; position+) n Record data;n the_list.retrieve(pos

11、ition, data);n if (target = data) return success;n n return not_present;n 5/5/2021 数 据 结 构 与 程 序 设 计 19 AnalysisBOOK P273n The number of comparisons of keys done in sequential search of a list of length n is:n Unsuccessful search: n comparisons.n Successful search, best case: 1 comparison.n Successf

12、ul search, worst case: n comparisons. n Successful search, average case: (n + 1)/ 2 comparisons. 5/5/2021 数 据 结 构 与 程 序 设 计 20 Binary SearchSequential search is easy to write and efficient for short lists, but a disaster for long ones.One of the best methods for a list with keys in order is binary s

13、earch.首 先 讨 论 如 何 构 建 一 个 有 序 的 列 表 。然 后 讨 论 针 对 顺 序 列 表 的 二 分 查 找 。 5/5/2021 数 据 结 构 与 程 序 设 计 21 Ordered Listsn 有 序 列 表 的 定 义 ：n DEFINITION n 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 th

14、e key of entry i is less than or equal to the key of entry j . 5/5/2021 数 据 结 构 与 程 序 设 计 22 Ordered Listsn class Ordered_list: public Listn public:n Error_code insert(const Record n Error_code insert(int position, const Record n Error_code replace(int position, const Record n ; 5/5/2021 数 据 结 构 与 程

15、 序 设 计 23 Ordered Listsn Error_code Ordered_list : insert(const Record n int position;n for (position = 0; position s; position+) n Record list_data; n retrieve(position, list_data);n if (data list_data) break; /book p279 wrongn n return List : insert(position, data);n /调 用 父 类 的 方 法 。n 5/5/2021 数 据

16、 结 构 与 程 序 设 计 25 Ordered Listsn Error_code Ordered_list : insert(int position, const Record n if (data list_data)n return fail;n n if (position list_data)n return fail;n n return List : insert(position, data);n 5/5/2021 数 据 结 构 与 程 序 设 计 27 Ordered Listsn Error_code Ordered_list : replace(int posit

17、ion, const Record n Record list_data;n if (position 0) n retrieve(position - 1, list_data); n if (data list_data)n return fail;n n if (position list_data)n return fail;n n entryposition = data;n return success;n 5/5/2021 数 据 结 构 与 程 序 设 计 28 Ordered Listsn class Recordn public:n Record();n Record(in

18、t x, int y=0);n int the_key() const;n private:n int key;n int other; n ;n bool operator (const Record n bool operator (const Record n ostream n n bool operator (const Record n n ostream n outputendl; n return output;n 5/5/2021 数 据 结 构 与 程 序 设 计 31 Ordered Lists-Mainn template n void print(List_entry

19、 n n void main() n Ordered_list mylist;n for(int i=0;i5;i+)mylist.insert(Record(i*2);n mylist.insert(Record(3);n mylist.insert(0,Record(30);n coutYour list have mylist.size() elements:endl;n mylist.traverse(print); 5/5/2021 数 据 结 构 与 程 序 设 计 32 Resultn Your list have 6 elements:n 0n 2n 3n 4n 6 n 8 5

20、/5/2021 数 据 结 构 与 程 序 设 计 33 Ordered Lists-Mainn mylist.remove(0, Record(i);n coutAfter remove(0):endl;n mylist.traverse(print); 5/5/2021 数 据 结 构 与 程 序 设 计 34 Resultn After remove(0):n 2n 3n 4n 6n 8 5/5/2021 数 据 结 构 与 程 序 设 计 35 Ordered Lists-Mainn mylist.replace(0, Record(-1);n coutAfter replace(0,

21、 Record(-1):endl;n mylist.traverse(print);n 5/5/2021 数 据 结 构 与 程 序 设 计 36 Resultn After replace(0, Record(-1):n -1n 3n 4n 6n 8 5/5/2021 数 据 结 构 与 程 序 设 计 37 Ordered Lists-Main目 录 Ordered_list下 例 程 5/5/2021 数 据 结 构 与 程 序 设 计 38 课 后 阅 读n 关 于 顺 序 查 找 的 效 率 测 试 。n 课 后 阅 读 P274 3.testingn 理 解 函 数 test_search/统 计 查 找 成 功 和 查找 不 成 功 时 的 比 较 次 数 。