第2章至第7章中已经介绍了各种线性或非线性的数据结构

第9章查找第2章至第7章中已经介绍了各种线性或非线性的数据结构，在这一章将讨论另一种在实际应用中大量使用的数据结构——查找表。查找表(SearchTable)是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。对查找表经常进行的操作有：(1)查询某个“特定的”数据元素是否在查找表中；(2)检索某个“特定的”数据元素的各种属性；(3)在查找表中插入一个数据元素；(4)从查找表中删去某个数据元素。若对查找表只作前两种统称为“查找”的操作，则称此类查找表为静态查找表(StaticSearchTable)。若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类表为动态查找表(DynamicSearchTable)。所谓“查找”即为在一个含有众多的数据元素(或记录)的查找表中找出某个“特定的”数据元素(或记录)。关键字(Key)是数据元素(或记录)中某个数据项的值，用它可以标识(识别)一个数据元素(或记录)。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字(PrimaryKey)(对不同的记录，其主关键字均不同)。反之，称用以识别若干记录的关键字为次关键字(SecondaryKey)。当数据元素只有一个数据项时，其关键字即为该数据元素的值。查找(Searching)根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。如何进行查找?显然，在一个结构中查找某个数据元素的过程依赖于这个数据元素在结构中所处的地位。因此，对表进行查找的方法取决于表中数据元素依何种关系(这个关系是人为地加上的)组织在一起的。[例如]，查电号码时，由于电话号码簿是按用户(集体或个人)的名称(或姓名)分类且依笔划顺序编排，则查找的方法就是先顺序查找待查用户的所属类别，然后在此类中顺序查找，直到找到该用户的电话号码为止。[又如]，查阅英文单词时，由于字典是按单词的字母在字母表中的次序编排的，因此查找时不需要从字典中第一个单词比较起，而只要根据待查单词中每个字母在字母表中的位置查到该单词。同样，在计算机中进行查找的方法也随数据结构不同而不同。正如前所述，本章讨论的查找表是一种非常灵便的数据结构。但也正是由于表中数据元素之间仅存在着“同属一个集合”的松散关系，给查找带来不便。为此，需在数据元素之间人为地加上一些关系，以便按某种规则进行查找，即以另一种数据结构来表示查找表。本章将分别就静态查找表和动态查找表两种抽象数据类型讨论其表示和操作实现的方法。9.1静态查找表9.2动态查找表9.3哈希表9.1静态查找表（学时）抽象数据类型静态查找表的定义为：ADTStaticSearchTable{数据对象D：具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：Create(&ST，n)；操作结果：构造一个含n个数据元素的静态查找表ST。Destroy(&ST)；初始条件：静态查找表ST存在。操作结果：销毁表ST。Search(ST，key)；初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中位置，否则为“空”。Traverse(ST，visit())；初始条件：静态查找表ST存在，visit是对元素操作的应用函数。操作结果：按某种次序对ST的每个元素调用函数visit()一次且仅一次，一旦visit()失败，则操作失败。}ADTStaticSearchTable静态查找表可以有不同的表示方法，在不同的表示方法中，实现查找操作的方法也不同。9.1.1顺序表的查找以顺序表或线性链表表示静态查找表，则Search函数可用顺序查找来实现。本节中只讨论它在顺序存储结构模块中的实现，在线性链表模块中实现的情况类似。//————静态查找表的顺序存储结构———typdefstruct{ElemType*elem;//数据元素存储空间基址intlength;//建表时按实际长度分配，0号单元留空表长度}SSTable；下面讨论顺序查找的实现。顺序查找(SequentialSearch)的查找过程为：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。此查找过程可用算法9.1描述之。intSearch_Seq(SSTableST，KeyTypekey){//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。ST.elem[0].key=key;//0号单元作为监视哨for(i=ST.length;!EQ(ST.elem[i].key,key);--i);//从后往前找returni；//找不到时，i为0}//Search_Seq算法9.1分析顺序查找演示过程参见（板书走程序）】。查找操作的性能分析:衡量一个算法好坏的量度有三条：时间复杂度(衡量算法执行的时间量级)；空间复杂度(衡量算法的数据结构所占存储以及大量的附加存储)；算法的其它性能。对于查找算法来说，通常只需要一个或几个辅助空间。又，查找算法中的基本操作是“将记录的关键字和给定值进行比较”，因此，通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量查找算法好坏的依据。定义：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(AverageSearchLength)。对于含有n个记录的表，查找成功时的平均查找长度为(9-1)9.1.2有序表的查找以有序表表示静态查找表时，Search函数可用折半查找来实现。折半查找(BinarySearch)的查找过程是：先确定待查记录所在的范围(区间)，然后逐步缩小范围直到找到或找不到该记录为止。[例如]：已知如下11个数据元素的有序表(关键字即为数据元素的值)：现要查找关键字为21和85的数据元素。其中：Pi为查找表中第i个记录的概率，且；Ci为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数。显然，Ci随查找过程不同而不同。假设n=ST.length，则顺序查找的平均查找长度为ASL=nPl+(n-1)P2+…+2Pn-1+Pn(9-2)假设每个记录的查找概率相等，即Pi=1/n，则在等概率情况下顺序查找的平均查找长度为有时，表中各个记录的查找概率并不相等。[例如]：将全校学生的病历档案建立一张表存放在计算机中，则体弱多病同学的病历记录的查找概率必定高于健康同学的病历记录。由于式(9—2)中的ASL在Pn≥Pn-1≥…≥P2≥P1时达到极小值。因此，对记录的查找概率不等的查找表若能预先得知每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由小至大重新排列，以便提高查找效率。然而，在一般情况下，记录的查找概率预先无法测定。为了提高查找效率，我们可以在每个记录中附设一个访问频度域，并使顺序表中的记录始终保持按访问频度非递减有序的次序排列，使得查找概率大的记录在查找过程中不断往后移，以便在以后的逐次查找中减少比较次数。或者在每次查找之后都将刚查找到的记录直接移至表尾。顺序查找和我们后面将要讨论到的其它查找算法相比，其缺点是平均查找长度较大，特别是当n很大时，查找效率较低。然而，它有很大的优点是：算法简单且适应面广。假设指针low和high分别指示待查元素所在范围的下界和上界，指针mid指示区间的中间位置，即mid=(low+high)／2。在此例中，low和high的初值分别为1和11，即[1，11]为待查范围。先看给定值key=21的查找过程：ST.elem[mid].key与给定值key相比较，因为ST.elem[mid].keykey，说明待查元素若存在，必在区间[low，mid-1]的范围内，则令指针high指向第mid-1个元素，重新求得mid=(1+5)／2=3仍以ST.elem[mid].key和key相比，因为ST.elem[mid].keykey，说明待查元素若存在，必在[mid+1，high]范围内，则令指针low指向第mid+1个元素，求得mid的新值为4，比较ST.elem[mid].key和key，因为相等，则查找成功，所查元素在表中序号等于指针mid的值。再看key=85的查找过程。此时因为下界low上界high，则说明表中没有关键字等于key的元素，查找不成功。折半查找算法如下：intSearch_Bin(SSTableST，KeyTypekey){//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。low=1;high=ST.lenqth；//置区间初值while(low=high){mid=(low+high)/2ifEQ(key,ST.elem[mid].key)returnmid;//找到待查元素elseifLT(key,ST.elem.[mid].key)high=mid-1;//继续在前半区间进行查找elselow=mid+1;//继续在后半区间进行查找}return0;//顺序表中不存在待查元素}//Search_Bin9.1.3静态树表的查找上一小节对有序表的查找性能的讨论是在“等概率”的前提下进行的，即当有序表中各记录的查找概率相等时，按图9.2所示判定树描述的查找过程来进行折半查找，其性能最优。如果有序表中各记录的查找概率不等，情况又如何呢?先看一个具体例子。假设有序表中含5个记录，并且已知各记录的查找概率不等，分别为p1=0.1，p2=0.2，p3=0.1，p4=0.4和p5=0.2。则按式(9-1)的定义，对此有序表进行折半查找，查折半查找的性能分析:先看上述11个元素的表的具体例子。从上述查找过程可知：找到第⑥个元素仅需比较1次；找到第③和第⑨个元素需比较2次；找到第①、④、⑦和⑩个元素需比较3次；找到第②、⑤、⑧…需比较4次。这个查找过程可用图9.2所示的二叉树来描述。树中每个结点表示表中一个记录，结点中的值为该记录在表中的位置，通常称这个描述查找过程的二叉树为判定树，从判定树上可见，查找21的过程恰好是走了一条从根到结点④的路径，和给定值进行比较的关键字个数为该路径上的结点数或结点④在判定树上的层次数。图9.2描述查找过程的判定树折半查找的平均查找长度是多少呢?为讨论方便起见，假定有序表的长度，n=2k-1(反之，k=log2(n+1))，则描述折半查找的判定树是深度为k的满二叉树。树中层次为1的结点有1个，层次为2的结点有2个，…，层次为k的结点有2k-1个。假设表中每个记录的查找概率相等(Pi=1/n)，则查找成功时折半查找的平均查找长度对任意的n，当n较大(n50)时，可有下列近似结果ASL=log2(n+1)-1(9—6)可见，折半查找的效率比顺序查找高，但折半查找只能适用于有序表，且限于顺序存储结构(对线性链表无法进行折半查找)。以有序表表示静态查找表时，进行查找的方法除折半查找之外，还有斐波那契查找和插值查找。找成功时的平均查找长度为：5∑PiCi=0.1*2+0.2*3+0.1*1+0.4*2+0.2*3=2.3i=1但是，如果在查找时令给定值先和第4个记录的关键字进行比较，比较不相等时再继续在左子序列或右子序列中进行折半查找，则查找成功时的平均查找长度为：5∑PiCi=0.1*3+0.2*2+0.1*3+0.4*1+0.2*2=