《第九章静态查找表优秀课件.ppt》由会员分享，可在线阅读，更多相关《第九章静态查找表优秀课件.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第九章静态查找表第1页，本讲稿共38页何谓查找表何谓查找表？查找表是由同一类型同一类型的数据元素(或记录)构成的集合集合。由于“集合”中的数据元素之间存在着松松散散的关系，因此查找表是一种应用灵便的结构。第2页，本讲稿共38页对查找表经常进行的对查找表经常进行的操作操作:1）查查询询某个“特特定定的的”数据元素是是否否在在查查找找表表中中；2）检索检索某个“特定的特定的”数据元素的各种属性各种属性；3）在查找表中插入插入一个（不存在的）数据元素；4）从查找表中删删去去某个（已经存在的）数据元素。第3页，本讲稿共38页仅作查询查询和检索检索操作的查找表。静态查找表静态查找表有时在查询之后，还需要
2、将“查询”结果为“不在查找表中”的数据元素插入插入到查找表中；或者，从查找表中删除删除其“查询”结果为“在查找表中”的数据元素。动态查找表动态查找表查找表可分为两类查找表可分为两类:第4页，本讲稿共38页是数据元素（或记录）中某个数据项数据项的值，用以标识标识（识别）一个数据元素（或记录）。关键字关键字 若此关键字可以识别唯一唯一的一个记录，则称之谓“主关键字主关键字”。若此关键字能识别若干若干记录，则称之谓“次关键字次关键字”。第5页，本讲稿共38页查找（搜索查找（搜索、Search)n n 所谓所谓所谓所谓查找查找，就是，就是在数据集合中寻找满足某种条在数据集合中寻找满足某种条 件的数据对
3、象。件的数据对象。件的数据对象。件的数据对象。n n 查找的结果通常有两种可能：查找的结果通常有两种可能：u u 查找成功查找成功查找成功查找成功，即找到满足条件的数据对象。这时，即找到满足条件的数据对象。这时，作为结果，可报告该对象在结构中的位置，还可作为结果，可报告该对象在结构中的位置，还可进一步给出该对象中的具体信息进一步给出该对象中的具体信息。u u 查找不成功查找不成功，或搜索失败。作为结果，也应或搜索失败。作为结果，也应 报报告一些信息，如失败标志、失败位置等。告一些信息，如失败标志、失败位置等。通常称用于搜索的数据集合为通常称用于搜索的数据集合为查找表查找表，它是由，它是由，它是
4、由，它是由同一数同一数同一数同一数据类型的对象据类型的对象据类型的对象据类型的对象(或记录或记录或记录或记录)组成。组成。第6页，本讲稿共38页 由于查找表中的数据元素之间不存在明显的由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。组织规律，因此不便于查找。为了提高查找的效率，为了提高查找的效率，需要在查找表中需要在查找表中的元素之间的元素之间人为地人为地 附加某种确定的关系附加某种确定的关系，换，换句话说，句话说，用另外一种结构来表示查找表用另外一种结构来表示查找表。如何进行查找？如何进行查找？查找的方法取决于查找表的结构。查找的方法取决于查找表的结构。第7页，本讲稿共38页
5、衡量一个搜索算法的时间效率的标准是：衡量一个搜索算法的时间效率的标准是：在在搜搜索索过过程程中中关关键键码码的的平平均均比比较较次次数数，这这个个标标准准也也称称为为平平均均搜搜索索长长度度ASLASL(Average Average Search Search LengthLength)，通通常常它它是是搜搜索索结结构构中中对对象象总总数数 n n 或或文文件件结结构构中中物物理理块块总总数数 n n 的的函数。函数。另另外外衡衡量量一一个个搜搜索索算算法法还还要要考考虑虑算算法法所所需需要的存储量和算法的复杂性等问题。要的存储量和算法的复杂性等问题。第8页，本讲稿共38页9.1 静态查找表
6、静态查找表9.2 动态查找树表动态查找树表9.3 哈希表哈希表第9页，本讲稿共38页9.1 静静 态态 查查 找找 表表第10页，本讲稿共38页数据对象数据对象D：数据关系数据关系R：D是具有相同特性的数据元素的集合。每个数每个数据元素含有类型相同的据元素含有类型相同的关键字关键字，可唯一标识数据元素。数据元素同属一个集合。ADT StaticSearchTable 第11页，本讲稿共38页 Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit();基本操作基本操作 P：ADT StaticSearchTable第12页，本讲稿
7、共38页构造一个含n个数据元素的静态查找表ST。Create(&ST,n);操作结果：第13页，本讲稿共38页销毁表ST。Destroy(&ST);初始条件：操作结果：静态查找表ST存在；第14页，本讲稿共38页若 ST 中存在其关键字等于 key 的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。Search(ST,key);初始条件：操作结果：静态查找表ST存在，key 为和查找表中元素的关键字类型相同的给定值；第15页，本讲稿共38页按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。Traverse(ST,Visit();初始条
8、件：操作结果：静态查找表ST存在，Visit是对元素操作的应用函数；第16页，本讲稿共38页typedef struct /数据元素存储空间基址，建表时 /按实际长度分配，0号单元留空 int length;/表的长度 SSTable;假设静态查找表静态查找表的顺序存储结构顺序存储结构为ElemType*elem;第17页，本讲稿共38页数据元素类型的定义为数据元素类型的定义为:typedef struct keyType key;/关键字域 /其它属性域 ElemType;,TElemType;第18页，本讲稿共38页一、顺序查找表一、顺序查找表二、有序查找表二、有序查找表三、索引顺序表三、
9、索引顺序表第19页，本讲稿共38页 以顺序表或线性链表表示静态查找表一、顺序查找表顺序查找表第20页，本讲稿共38页顺序查找顺序查找(Sequential Search)所所谓谓顺顺序序查查找找，又又称称线线性性查查找找，主主要要用用于于在在线线性结构中进行查找。性结构中进行查找。设设若若表表中中有有 n n 个个对对象象，则则顺顺序序查查找找从从表表的的一一端端开开始始，顺顺序序用用各各对对象象的的关关键键码码与与给给定定值值x x进进行行比比较较，直直到到找找到到与与其其值值相相等等的的对对象象，则则查查找找成功，给出该对象在表中的位置。成功，给出该对象在表中的位置。若若整整个个表表都都已
10、已检检测测完完仍仍未未找找到到关关键键码码与与x x相相等等的对象，则查找失败。给出失败信息。的对象，则查找失败。给出失败信息。第21页，本讲稿共38页ST.elem回顾顺序表的查找过程：回顾顺序表的查找过程：假设给定值 e=64,要求 ST.elemk=e,问:k=?kk第22页，本讲稿共38页int location(SqList L,ElemType&e,Status(*compare)(ElemType,ElemType)p=L.elem;for(k=1;k=L.length&!(*compare)(*p+,e);k+);if(k=0;-i);第25页，本讲稿共38页 所查找的记录的序
11、号所查找的记录的序号 关键字需比较次数关键字需比较次数 n n-1 n-2 2 1 1 2 3 n-1 n 平均比较次数平均比较次数（1+2+3+n-1+n）/n=（n+1）/2查找算法的查找算法的平均查找长度平均查找长度(Average Search Length)约为表长的一半。约为表长的一半。第26页，本讲稿共38页 上述顺序查找表的查找算法简单，但平均查找长度较大，即查找效率太低,特别不适用于表长较大的查找表。二、有序查找表二、有序查找表 若以有序表有序表表示静态查找表，则查找过程可以基于“折半折半”进行。第27页，本讲稿共38页基于有序顺序表的折半搜索基于有序顺序表的折半搜索设设n
12、n个个对对象象存存放放在在一一个个有有序序顺顺序序表表中中，并并按按其其关关键键字字从从小小到到大排好了序。大排好了序。采采用用折折半半查查找找时时，先先求求位位于于查查找找区区间间正正中中的的对对象象的的下下标标midmid，用其关键码与给定值用其关键码与给定值x x比较比较:ElemElem midmid.KeyKey=x x，查找成功；，查找成功；ElemElem midmid.KeyKey x x，把把查查找找区区间间缩缩小小到到表表的的前前半半部分部分，再继续进行折半查找；，再继续进行折半查找；ElemElem midmid.KeyKey x x，把把查查找找区区间间缩缩小小到到表表
13、的的后后半半部分部分，再继续进行折半查找。，再继续进行折半查找。每每比比较较一一次次，查查找找区区间间缩缩小小一一半半。如如果果查查找找区区间间已已缩缩小小到一个对象，仍未找到想要查找的对象，则查找失败。到一个对象，仍未找到想要查找的对象，则查找失败。第28页，本讲稿共38页ST.elemST.length例如例如:key=64 的查找过程如下：lowhighmidlow mid high midlow 指示查找区间的下界high 指示查找区间的上界mid=(low+high)/2通过比较ST.elemmid.key与key的大小来逐步缩小查找范围第29页，本讲稿共38页搜索成功的例子搜索成功
14、的例子 搜索失搜索失败的例子的例子第30页，本讲稿共38页int Search_Bin(SSTable ST,KeyType key)low=1;high=ST.length;/置区间初值置区间初值 while(low 50时，可得近似结果 折半查找的效率比顺序查找高，但折半查找折半查找的效率比顺序查找高，但折半查找只适用于有序表，且限于顺序存储结构（只适用于有序表，且限于顺序存储结构（为为什么线性链表无法实施折半查找？什么线性链表无法实施折半查找？）第34页，本讲稿共38页索引顺序表的查找索引顺序表的查找查找方法：分块查找（索引顺序查找）查找方法：分块查找（索引顺序查找）索引表的建立：索引表
15、的建立：分块有序原则：第二个子表的所有记录的关键字均大分块有序原则：第二个子表的所有记录的关键字均大于第一个字表中的最大关键字，于第一个字表中的最大关键字，依此类推。，依此类推。22 48 861713索引表索引表该子表内的该子表内的最大关键字最大关键字该子表在表中该子表在表中的起始地址的起始地址221213 8 9 20 334244382448605874498653关键字项关键字项 指针项指针项第35页，本讲稿共38页索引顺序表的查找过程：索引顺序表的查找过程：1）由索引确定记录所在块（子表）；2）在顺序表的某个块内进行顺序查找。注意：索引可以根据查找表的特点来构造。注意：索引可以根据查
16、找表的特点来构造。可见，索引顺序查找索引顺序查找的过程也是一个“缩小区间缩小区间”的查找过程。第36页，本讲稿共38页索引顺序查找的平均查找长度索引顺序查找的平均查找长度=查找查找“索引索引”的平均查找长度的平均查找长度 +查找查找“顺序表顺序表”的平均查找长度的平均查找长度因因为索引表中的索引表中的 索引索引项是按关是按关键字有序排字有序排列的，因此可用列的，因此可用顺序序查找，也可用折半找，也可用折半查找；找；而而块（子表）中的（子表）中的记录是任意排列的，只能是任意排列的，只能用用顺序序查找的方法。找的方法。第37页，本讲稿共38页作业作业给定定11个数据元素的有序表（个数据元素的有序表（2 2，3 3，10，15，25，28，29，30，35，40），采用），采用折半折半查找，画出其判定找，画出其判定树，试问若若查找找给定定值为20的元素，将依次与表的元素，将依次与表中哪些元素比中哪些元素比较？若若查找找给定定值为20的元素，将依次与表的元素，将依次与表中哪些元素比中哪些元素比较？第38页，本讲稿共38页