数据结构.第9章.查找.1.静态查找表ppt课件.ppt

《数据结构.第9章.查找.1.静态查找表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构DataStructures张凯计算机学院软件工程系2011年3月12日第9章查找查找的基本概念静态查找表动态查找表哈希表查找的基本概念§9.1查找的基本概念查找表：是由同一类型的具有相同可辨认特性的数据元素（或记录）构成的集合。对查找表经常进行的操作：1.查询某个“特定的”数据元素是否在查找表中；2.查询某个“特定的”数据元素的各种属性；3.在查找表中插入一个数据元素；4.删除查找表中的某个数据元素。查找表的分类§9.1查找的基本概念静态查找表动态查找表：仅作“查询”（检索）操作的查找表，只查找，不改变数据元素集内的数据元素。作“插入”和“删除

2、”操作的查找表既查找，又改变(增减)集合内的数据元素。关键字§9.1查找的基本概念在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称关键字(key)。主关键字可唯一标识一个记录的关键字。例：学号次关键字可识别若干记录的关键字。例：性别关键字§9.1查找的基本概念姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17健康……………查找§9.1查找的基本概念根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。

3、若表中存在这样的一个记录，则称查找是成功的，若表中不存在关键字等于给定值的记录，则称查找不成功。静态查找如何进行查找取决于查找表的结构，如字典，电话本平均查找长度(AverageSearchLength)§9.1查找的基本概念为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(ASL)。对于含有n个记录的表，查找成功时的平均查找长度为查找表中第i个记录的概率，且找表中关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数静态查找表顺序表的查找有序表的查找索引顺序表的查找§9.2静态查找表顺

4、序表的查找§9.2静态查找表顺序查找：从表的一端开始，逐个进行记录的关键字和给定值的比较。查找过程：找645371921135664928880750123456789101164顺序查找的算法§9.2静态查找表intSearch_seq(SSTableST[],intn,intkey){ST[0].key=key;inti=n;while(ST[i].key!=key)i--;returni;}53719211356649288807501234567891011找60找不到时，i为0&&(i>=0)顺序查找的算法§9.2静态查找表intSearch_

5、seq(SSTableST[],intn,intkey){ST[0].key=key;inti=n;while(ST[i].key!=key)i--;returni;}53719211356649288807501234567891011找60&&(i>=0)60顺序查找的算法§9.2静态查找表intSearch_seq(SSTableST[],intn,intkey){ST[0].key=key;inti=n;while(ST[i].key!=key)i--;returni;}53719211356649288807501234567891011找60

6、60监视哨监视哨作用：避免每步都去判断是否查找结束顺序查找的算法分析§9.2静态查找表对于n个数据元素的表，若给定值key与表中第i个元素的关键字相等，则需要n-i+1次关键字比较，即Ci=n-i+1。例如，当第n个元素的关键字为key时，需要进行1次比较(n-n+1=1)，又如，当第一个元素为所求时，需要进行n次比较(n-1+1=n)。因此，查找成功时，顺序查找的平均查找长度为Pi每个元素的查找概率，假设所有元素的查找概率均相等。顺序查找的算法分析§9.2静态查找表对于n个数据元素的表，若给定值key与表中第i个元素的关键字相等，则需要n-i+1次关键

7、字比较，即Ci=n-i+1。例如，当第n个元素的关键字为key时，需要进行1次比较(n-n+1=1)，又如，当第一个元素为所求时，需要进行n次比较(n-1+1=n)。因此，查找成功时，顺序查找的平均查找长度为顺序查找的算法分析§9.2静态查找表若查找失败，则算法一直遍历到Elem[0]，总共比较n+1次。5371921135664928880750123456789101160顺序查找的算法分析§9.2静态查找表查找成功时的平均查找次数为：ASL=(1+2+3+4+……+n)/n=(n+1)/2①查找不成功时的比较次数为：ASL=(n(n+1))/n=n

8、+1②则顺序查找的平均查找长度为：ASL==(①+②)/2=3(n+1)/4优点