Search

2022-12-05

查找表 Set/Collections

. 同一类型的数据元素/记录的集合

. 简称表

关键字 key

. 数据元素/记录中某个数据项的值，用来标识一个数据元素/记录

. 可以是唯一的，也可以是不唯一的，相应的，可以分为主关键字、次关键字

查找 Search

. 根据给定值在查找表中确定一个关键字和给定值相等的数据元素或记录

如果存在，查找成功，给出相应的信息，如位置、值

如果不存在，查找失败，给出空记录或空指针

静态查找和动态查找 Static vs Dynamic

. 如果查找过程中，同时执行修改如删除、插入等操作，称为动态查找，否则为静态查找

. 一个精心设计的系统一定是动态的，以便更好的服务用户

[] 图书检索

[] 社交APP新闻查询

[] 购物APP品搜索：黄桃罐头、莲花清瘟胶囊...

平均查找长度 ASL

. Average Search Length

. 为了确定查找结果，需要和给定值比较的关键字个数的期望

. 用来衡量Evaluate查找算法的性能

主要分类Classification

1. 线性表的查找

2. 树表的查找

3. 散列表的查找

总结Summary

去哪里找Where？找什么What？怎么找How？结果如何Evaluate？

如果在查找的同时对表执行修改操作，则称相应的表为静态查找表。(×)

适用于折半查找的表的存储方式及元素排列要求为（D）。

A. 链接方式存储，元素无序

B. 链接方式存储，元素有序

C. 顺序方式存储，元素无序

D. 顺序方式存储，元素有序

对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（C）。

A. (n-1)/2

B. n/2

C. (n+1)/2

D. n