《数据结构查找技术1静态查找表.ppt》由会员分享，可在线阅读，更多相关《数据结构查找技术1静态查找表.ppt（46页珍藏版）》请在三一办公上搜索。
1、第九章查 找,本章的主要内容是:,查找的基本概念（难度系数*）静态查找表（难度系数*）动态查找表（难度系数*）哈希表（难度系数*）,何谓查找表？,查找表是由同一类型的数据元素(或记录)构成的集合。,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。,查找的基本概念,对查找表经常进行的操作:,1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。,不涉及插入和删除操作的查找。涉及插入和删除操作的查找。,查找的基本概念,静态查找适用于：查找集合一经生成，便只对其进行查找，而
2、不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作；动态查找适用于：查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。,静态查找表,动态查找表,是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。,关键字,若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。,若此关键字能识别若干记录，则称之谓“次关键字”。,根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。,查找,若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录
3、在查找表中的位置；否则称“查找不成功”。查找结果给出“空记录”或“空指针”。,由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说，用另外一种结构来表示查找表。,如何进行查找？,查找的方法取决于查找表的结构。,9.1 静态查找表,9.2 动态查找树表,9.3 哈希表,主要采用顺序查找技术和折半查找技术。,主要采用二叉排序树的查找技术。,静态查找和动态查找均适用，主要采用散列技术。,查找算法的性能,查找算法时间性能通过关键码的比较次数来度量。,关键码的比较次数与哪些因素有关呢？,平均查找长度：将查找算法进
4、行的关键码的比较次数的数学期望值定义为平均查找长度，即：,ci取决于算法；pi与算法无关，取决于具体应用。如果pi是已知的，则平均查找长度只是问题规模的函数。,9.1 静 态 查 找 表,数据对象D：,数据关系R：,D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。,数据元素同属一个集合。,ADT StaticSearchTable,Create(,Destroy(,Search(ST,key);,Traverse(ST,Visit();,基本操作 P：,ADT StaticSearchTable,构造一个含n个数据元素的静态查找表ST。,Create(,
5、操作结果：,销毁表ST。,Destroy(,初始条件：操作结果：,静态查找表ST存在；,若 ST 中存在其关键字等于 key 的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。,Search(ST,key);,初始条件：操作结果：,静态查找表ST存在，key 为和查找表中元素的关键字类型相同的给定值；,按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。,Traverse(ST,Visit();,初始条件：操作结果：,静态查找表ST存在，Visit是对元素操作的应用函数；,typedef struct/数据元素存储空间基址，建表时/按实
6、际长度分配，0号单元留空 int length;/表的长度 SSTable;,假设静态查找表的顺序存储结构为,ElemType*elem;,数据元素类型的定义为:,typedef struct keyType key;/关键字域/其它属性域 ElemType;,TElemType;,一、顺序查找表,二、有序查找表,三、索引顺序表,以顺序表或线性链表表示静态查找表,一、顺序查找表,顺序查找（线性查找）,基本思想：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。,10 15 24
7、6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,例：查找key35,顺序查找（线性查找）,int SeqSearch1(int r,int n,int key)/数组r1 rn存放查找集合 i=1;while(i=n,基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。,改进的顺序查找,10 15 24 6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,例：查找key35,哨兵,35,基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在
8、查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。,改进的顺序查找,10 15 24 6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,例：查找key25,25,int SeqSearch2(int r,int n,int k)/数组r1 rn存放查找集合 r0.key=k;i=n;while(ri.key!=k)i-;return i;,改进的顺序查找,平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低。,顺序查找的缺点：,对表中记录的存储没有任何要求，顺序存储和链接存储均可；对表中记录的有序性也没有要求，无论记录是否按关键码有序均可。,顺
9、序查找的优点：算法简单而且使用面广。,定义：查找算法的平均查找长度(Average Search Length)为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值 其中:n 为表长，Pi 为查找表中第i个记录的概率，且，Ci为找到该记录时，曾和给定值比较过的关键字的个数。,分析顺序查找的时间性能,在等概率查找的情况下，顺序表查找的平均查找长度为：,对顺序表而言，Ci=n-i+1,ASL=nP1+(n-1)P2+2Pn-1+Pn,若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。,在不等概率查找的情况下，ASLss 在
10、PnPn-1P2P1时取极小值,上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。,二、有序查找表,若以有序表表示静态查找表，则查找过程可以基于“折半”进行。,折半查找,使用条件：线性表中的记录必须按关键码有序；必须采用顺序存储。,基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。,ST.elem,ST.length,例如:key=64 的查找
11、过程如下：,low,high,mid,low,mid,high,mid,low 指示查找区间的下界high 指示查找区间的上界mid=(low+high)/2,int BinSearch1(int r,int n,int k)/数组r1 rn存放查找集合 low=1;high=n;while(low rmid)low=mid+1;else return mid;return 0;,折半查找非递归算法,int BinSearch1(int r,int n,int k)/数组r1 rn存放查找集合 low=1;high=n;while(low rmid)low=mid+1;else return
12、mid;return 0;,8.2 线性表的查找技术,折半查找非递归算法,折半查找判定树,判定树：折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树，简称判定树。,先看一个具体的情况，假设：n=11,分析折半查找的平均查找长度,6,3,9,1,4,2,5,7,8,10,11,判定树,1,2,2,3,3,3,3,4,4,4,4,具有n个结点的折半查找判定树的深度为,查找成功：在表中查找任一记录的过程，即是折半查找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。,
13、查找不成功：查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数。,折半查找性能分析,三、索引顺序表的查找,以索引顺序表表示静态查找表，则查找函数可用分块查找来实现。分块查找又称索引顺序查找，这是顺序查找的一种改进方法。,索引顺序表的查找过程：,1）由索引确定记录所在区间；,2）在顺序表的某个区间内进行查找。,注意：索引可以根据查找表的特点来构造。,可见，索引顺序查找的过程也是一个“缩小区间”的查找过程。,分块查找方法描述将n个数据元素“按块有序”划分为m块（m n）。每一块中的结点不必有序，但块与块之间必须“按块有序”；即第1块中任一元
14、素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，依次类推，直至m块。分块查找操作步骤step1 先选取各块中的最大关键字构成一个索引表；step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。,分块查找,有序,索引顺序查找的平均查找长度=查找“索引”的平均查找长度+查找“顺序表”的平均查找长度,分块查找,设有n个记录的文件分为m个块，每个块均为t个记录，则n=mt。设Lb为查找索引表确定关键码所在块的平均查找长度，Lw为在块内查找关键码的平均查找长度，则分块查找的平均查找长度为：ASL=Lb+Lw 若采用顺序查找对索引表进行查找，则分块查找的平均查找长度为：,ASL=Lb+Lw=,分块查找的性能分析,小结顺序查找（重点）折半查找（重点）分块查找（了解）以及算法分析作业：完成顺序查找和折半查找算法。,
