《数据结构》课件-模块四 数据运算-查找

模块四数据运算--查找前言数据结构排序介绍排序（Sorting）是数据处理中一种很重要的运算，同时也是很常用的运算，一般数据处理工作25%的时间都在进行排序。简单地说，排序就是把一组记录（元素）按照某个域的值的递增（即由小到大）或递减（即由大到小）的次序重新排列的过程。前言前言顺序表的查找查找的基本概念折半查找和分块查找本章我们要解决的问题二叉排序树的构造和查找哈希查找前言8.1查找表基本概念数据之间的逻辑关系：一对一一对多多对多无关系8.1查找表基本概念由同一类型的数据元素（或记录）构成的集合。查找表（search

table）：查找表是一种应用灵便的数据结构，可以是线性表、树、图。学号姓名语文数学英语202201张三999798202202李四866870202203王五758066202204赵七655568202205孙九897083查找表——学生成绩信息（线性结构、可顺序可链式存储）查找表——微信用户数据集（图结构)张三李四王五赵六孙九8.1查找表基本概念1.查找特定的数据元素是否在查找表中；2.获取或读取查找表中某个数据元素的值；查找表的基本操作3.当查找失败时，将目标数据元素插入到查找表中；4.当查找成功时，将目标数据元素从查找表中删除。8.1查找表基本概念静态查找表：只做查找操作的查找表。动态查找表：在查找的过程中同时插入查找表中不存在的数据元素，或者删除已经存在的某个数据元素。决定查找操作的是关键字，只需关注记录中的关键字域，其他信息可以忽略。查找表分两大类：静态查找表、动态查找表。8.1查找表基本概念数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录）。主关键字：唯一地标识一个数据元素；否则为次关键字。关键字（key）：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。查找（searching）：8.1查找表基本概念因为查找某个数据元素依赖于该数据元素在一组数据中心所处的位置，即该组数据的组织方式，故应按照数据元素的组织方式决定采用的查找方法；（1）查找的方法关于查找，目前主要关注两方面的问题：反过来，为了提高查找方法的效率，要求数据元素采用某些特殊的组织方式。8.1查找表基本概念平均查找长度（2）查找算法的评价关于查找，目前主要关注两方面的问题：8.2静态查找表基于静态查找表主要有顺序表、有序顺序表、索引顺序表；查找法可分为顺序查找、折半查找和分块查找。8.2.1顺序查找在顺序表上查找的基本思想是：

用给定关键字与顺序表中各元素额关键字逐个比较，直到成功或失败（所有元素均不成功）。存储结构可为顺序存储结构，也可为链式存储结构。8.2.1顺序查找下面给出顺序结构有关数据类型的定义：#defineLISTSIZE100/*查找表的最大长度*/typedefstruct{ KeyTypekey;/*关键字域*/ …/*其他域*/}ElemType;typedefstruct{ ElemTyper[LISTSIZE];/*数据元素存储空间*/ intlength;/*查找表的长度*/}STable;STablest;8.2.1顺序查找顺序查找过程可以描述为：从表的一端开始扫描，逐个对记录的关键字和给定值进行比较，若两者相等，则查找成功；若扫描结束后，还没有与给定值相等的关键字，则查找失败。查找过程可用下述算法描述之（适合于表中数据无序）：intSearchSeq(STablest,KeyTypek)/*在顺序表中查找关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否则为0*/{ inti; for(i=1;i<=st.length;i++) if(st.r[i].key==k)return(i);/*查找成功*/ return(0);/*查找失败*/}8.2.1顺序查找顺序查找算法的改进：设监视哨把给定值放入表st.r[0]中，从表的尾部开始查找，逐个对记录的关键字和给定值进行比较。改进算法：intSearchSeq(STablest,KeyTypek)/*在顺序表中查找关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否则为0*/{ inti; st.r[0].key=k;/*监视哨*/ i=st.length; while(st.r[i].key!=k)i--; return(i);}8.2.1顺序查找平均查找长度：

查找成功时的平均查找长度为：查找算法查找失败查找长度为：为n+1优点：算法简单，且对表的结构无任何要求。缺点：平均查找长度较大，查找效率低，不适用于数据元素数目比较多的查找表。如果查找表中的记录按关键字有序，则可以采用一种高效率的查找方法——折半查找，也称二分查找。8.2.2二分查找（折半查找）二分查找法：设表中的人元素按关键字递增有序，首先将待查值和表中间位置上的元素关键字进行比较，若相等，则查找成功；若待查值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到找到或者查找范围为空而查不到为止。二分查找的过程实际上是先确定待查元素所在的区域，然后逐步缩小区域，直到查找成功或失败为止。二分查找只适用于以顺序存储结构组织的有序表。8.2.2二分查找（有序顺序表）查找的过程：例如：key=64的查找过程如下low指示查找区间的下界high指示查找区间的上界mid=(low+high)/2lowhighmidlow

mid

high

mid8.2.2二分查找——查找性能有序表：（5,12,18,20,35,50,64,72,80,88,95）上述查找过程可用图(a)的二叉树表示。若树中每个结点表示一个记录，结点中的值为该记录在表中的位置，通常这个描述查找过程的二叉树为判定树，如图(b)所示。(a)描述折半查找的二叉树(b)描述折半查找的判定树8.2.2二分查找——查找性能有序表：（5,12,18,20,35,50,64,72,80,88,95）(a)描述折半查找的二叉树(b)描述折半查找的判定树查找20的过程？二分查找在查找成功时进行比较的次数最多不超过树的深度。8.2.2二分查找——查找性能二分查找ASL：对于上例，从判定树上可知：

ASLsucc=(1+2+2+3+3+3+3+4+4+4+4)=3从该例可看出，二分查找成功的平均查找长度与序列中的具体元素无关，只取决于序列中元素的数目。intBinSearch(STablest,KeyTypekey)

/*在有序表st中折半查找其关键字等于key的元素，若找到，则函数值为该元素在表中的位置*/{ intlow,high,mid; low=1;high=st.length; /*置区间初值*/ while(low<=high) { mid=(low+high)/2; /*折半*/ if(key==st.r[mid].key) return(mid); /*找到待查元素*/ else if(key<st.r[mid].key) high=mid-1;/*继续在前半区间进行查找*/ else low=mid+1;/*继续在后半区间进行查找*/ }return(0);}二分查找的算法如下：8.2.2二分查找——查找性能二分查找的优点是比较次数少，查找速度快，但只能对顺序存储的有序表进行查找。它适用于一经建立就很少变动而又经常需进行查找的有序表。8.2.3分块查找分块查找又称索引顺序查找，它是顺序查找的一种改进方法。该方法除要求原表外，还要求建立一个索引表，将关键字分块，块内可无序，但块间有序。将每块的最大关键字值组成索引表，每个索引指向本快的第一关键字。图8.2索引顺序表示例（有序）8.2.3分块查找分块查找过程如下：第一步，将待查关键字K与索引表中的关键字进行比较，以确定待查记录所在的块。具体可用顺序查找法或折半查找法进行。第二步，用顺序查找法，在相应的块内查找关键字为K的记录。查找关键字K=37过程？（有序）8.2.3分块查找——查找性能分块查找ASL：分块查找的平均查找长度由两部分构成，即查找索引表时的平均查找长度LB以及在相应的块内进行顺序查找的平均查找长度LW，即

ASLbs=LB+LW假定将长度为n的表分成b块，且每块含s个数据元素，则b=n/s。又假定表中每个元素的查找概率相等，则每个索引项的查找概率为1/b，块中每个元素的查找概率为1/s。若用顺序查找法确定待查元素所在块，则有：8.2.3分块查找分块查找性能介于顺序查找和折半查找之间，它适合于对关键字“分块有序”的查找表进行查找操作。三种查找方法比较（静态查找表）8.3二叉排序树（动态查找表）1.二叉排序树的定义二叉排序树又称为二叉查找树，它是一种特殊的二叉树，其定义为：

二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；②若它的右子树非空，则右子树上所有结点的值均大于或等于根结点的值；③它的左、右子树也分别是二叉排序树。8.3二叉排序树中序遍历，可得到序列：06，15，39，58，67，76，80，88，97二叉排序树的重要性质：中序遍历一棵二叉排序树时可以得到一个递增有序序列。图8.3二叉排序树示例8.3二叉排序树2.二叉排序树的查找过程对二叉排序树进行查找的过程类似于在折半查找判定树上所进行的查找过程，其不同之处为：折半查找的判定树是静态的，二叉排序树是动态的。在二叉排序树中进行查找的过程为：

首先将给定值和根结点的关键字进行比较，若相等，则查找成功；否则，依据给定值小于或大于根结点的关键字，继续在左子树或右子树中进行查找，直到查找成功或者左子树或右子树为空，后者说明查找不成功。二叉排序树的特性：通过和根结点关键字的比较可将继续查找的范围缩小到某一棵子树中。8.3二叉排序树查找关键字

Key=50,35,90,9550308020908540358832二叉排序树505050304035505080908.3二叉排序树二叉排序树的查找算法如下：BTreeNode*SearchBST(BTreeNode*bt,KeyTypekey)/*在根指针bt所指二叉排序树中，查找关键字等于key的元素，若查找成功，则返回指向该元素的指针，否则返回空指针*/{ if(!bt) returnNULL; else if(bt->key==key)returnbt; /*查找成功*/ if(key<bt->key) returnSearchBST(bt->lchild,key); /*在左子树查找*/ returnSearchBST(bt->rchild,key); /*在右子树查找*/}8.3二叉排序树3.二叉排序树的插入和生成已知一个关键字值为key的结点s，若将其插入到二叉排序树中，只要保证插入后仍符合二叉排序树的定义即可。插入过程可描述如下：①若二叉排序树是空树，则key成为二叉排序树的根。②若二叉排序树是非空树，则将key与二叉排序树的根进行比较，如果key等于根结点的值，则停止插入；如果key小于根结点的值，则将key插入左子树；否则则将key插入右子树。二叉排序树的插入算法如下：viodInsertBST(BTreeNode**bt,KeyTypekey)

/*若在二叉排序树中不存在关键字等于key的元素，插入该元素*/{ BTreeNode*s; if(*bt==NULL)/*递归结束条件*/ { s=(BSTree)malloc(sizeof(BSTNode)); s->key=key; s->lchild=NULL;s->rchild=NULL; *bt=s; } elseif(key<(*bt)->key) InsertBST(&((*bt)->lchild),key);/*将s插入左子树*/ else if(key>(*bt)->key) InsertBST(&((*bt)->rchild),key);/*将s插入右子树*/}8.3二叉排序树构造二叉排序树的算法如下所示：voidCreateBST(BTreeNode**bt) /*从键盘输入元素值，建立相应二叉排序树*/{ KeyTypekey; *bt=NULL; scanf(″%d″,&key); while(key!=ENDKEY)/*ENDKEY为自定义常数，作为结束标识*/ { InsertBST(bt,key); scanf(″%d″,&key); }}有一关键字序列：56，26，67，12，37，98，按上述算法建立二叉排序树的过程:8.3二叉排序树如果输入顺序为：26，67，12，37，56，98，(原顺序：56，26，67，12，37，98)则构造的二叉排序树如下所示。对于同样的元素，如果输入顺序不同，构造的二叉排序树形状不同。8.3二叉排序树4.二叉排序树的删除在二叉排序树中删除一个结点，不能将以该结点为根的子树全部删除，只能删除该结点并使得二叉树依然满足二叉排序树的性质。在二叉排序树中删除一个结点可分三种情况讨论：（1）

被删除的结点是叶子；（2）

被删除的结点只有左子树或者只有右子树；（3）

被删除的结点既有左子树，也有右子树。（1）

被删除的结点是叶子结点50308090854035203288被删关键字=88其双亲结点中相应指针域的值改为“空”f->lchild=NULL;free(p);/*f为被删除的结点p的双亲*/20被删关键字=80其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。f->rchild=p->lchild或f->rchild=p->rchild；free(p);40（2）

被删除的结点只有左子树或者只有右子树50302090853588408032被删关键字=50以其前驱替代之，然后再删除该前驱结点（3）被删除的结点既有左子树，也有右子树（方法一）503080209085358840324040被删结点前驱结点（中序序列）（3）被删除的结点既有左子树，也有右子树（方法二）首先找到p结点在二叉排序树的中序遍历序列中的直接前驱s结点(无右子树)，然后将p的左子树改为f的左子树，而将p的右子树改为s的右子树：结果如图(b)所示。8.3二叉排序树5.二叉排序树的查找性能分析在二叉排序树上进行查找，若查找成功，则是从根结点出发走了一条从根到待查结点的路径；若查找不成功，则是从根结点出发走了一条从根结点到叶子结点的路径。在二叉排序树中查找到一个记录时，其比较次数不超过树的深度。输入序列为（56，26，67，12，37，98）建立二叉排序树例如下图：输入序列（12，26，37，56，67，98）建立二叉排序树例如右图：二叉排序树的平均查找长度ASL与二叉排序树的形态有关。(a)图：(b)图：8.3二叉排序树5.二叉排序树的查找性能分析二叉排序树查找的平均比较次数取决于二叉树的深度。就平均性能而言，二叉排序树与折半查找的查找性能相差不大，并且在二叉排序树上进行插入和删除十分方便，无需移动大量结点。经常做插入、删除、查找运算的表，宜采用二叉排序树结构。8.4哈希表的查找前面讨论查找方法中，表示查找表各种结构的共同特点是：记录在表中的位置和它的关键字之间不存在一个确定的关系，查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。而散列查找(又称为哈希查找)的思想与前面四种方法完全不同。8.4.1什么是哈希表（散列表）理想情况是希望不经过任何比较，一次存取便能获得所查记录，即哈希函数在关键字和地址之间建立一一对应关系。因此散列查找方法是用关键字进行计算元素存储位置的查找方法。其基本思想是：在数据元素的关键字k和数据元素的存储位置addr之间建立一个对应关系H，使得addr=H(k)，H称为哈希函数。按这个思想在一块连续的内存空间中建立的表为散列表(也称哈希表)。8.4.1什么是哈希表（散列表）当关键字集合很大时，关键字值不同的元素可能会得到相同的地址，即k1≠k2，但H(k1)=H(k2)，这种现象称为冲突。

k1,k2称为同义词。由于散列函数是一个压缩映象，不可能完全避免冲突；遇到冲突怎么解决？哈希表的构造及查找主要包括以下两方面的内容：①如何构造哈希函数；②如何处理冲突。8.4.2哈希函数的构造方法一个好的哈希函数能将给定的数据集合均匀地散列到地址区间（哈希表）中。构造哈希函数常用的六种方法：若是非数字关键字，则需先对其进行数字化处理。除留余数法：设定散列函数为:H(key)=keyMODp其中，

p≤m(表长)并且p应为不大于m的素数（质数）(4)叠加法(5)除留余数法(6)伪随机数法(1)直接定址法(2)数字分析法(3)平方取中法8.4.3处理冲突的方法通过构造性能良好的哈希函数可以减少冲突，但一般不可能完全避免冲突。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应一致。下面以创建哈希表为例说明解决冲突的两种方法。（1）开放定址法（2）链地址法开放定址法也称再散列法，其基本思想是：当关键字key的哈希地址addr=H(key)出现冲突时，去探测未存储数据的存储单元，将关键字存在空的存储单元。这种方法利用下列公式计算求得下一个地址：

Hi=(H(key)+di)%m其中，H(key)为哈希函数；m为表长，di称为增量序列。1.开放定址法增量序列的取值方式不同，相应的再散列方式也就不同。主要有以下三种：（1）线性探测再散列（2）二次探测再散列（3）伪随机探测再散列Hi=(H(key)+di)%m1）

线性探测再散列

di=c

i

最简单的情况c=12）

二次探测再散列

di=12,-12,22,-22,…k2,-k2(k≤m/2),3）

伪随机探测再散列

di

是一组伪随机数列或者

di=i×H2(key)(又称双散列函数探测)1.开放定址法对增量di

有三种取法：设定哈希函数H(key)=keyMOD11(表长=11)若采用线性探测再散列处理冲突

(求ASL)

Hi=(H(key)+di)%m例如:关键字集合{19,01,23,14,55,68,11,82,36}190123145568190123146811823655118236比较次数：11

2

1

36

2

51比较次数：112

1

21

3

1

2ASL=22/9ASL=14/9若采用二次探测再散列处理冲突(求ASL)

链地址法的基本思想是：将所有关键字是同义词的元素连接成一条线性链表，并将其链头存在相应的哈希地址所指的存储单元中。链地址法用于经常进行插入和删除的情况。

例如，一组关键字(19,01,23,14,55,68,11,82,36)，哈希表长为11，哈希函数为：H(key)=