《查找与排序优秀PPT.ppt》由会员分享，可在线阅读，更多相关《查找与排序优秀PPT.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、查找与排序1你现在浏览的是第一页，共27页天津大学2/27本章内容（树形结构）查找查找排序排序你现在浏览的是第二页，共27页天津大学3/271.查找查找你现在浏览的是第三页，共27页天津大学4/27查找的基本概念 查找查找：在数据元素集合：在数据元素集合(查找表查找表)中查找关键字与给定中查找关键字与给定值相等的数据元素。值相等的数据元素。关键字关键字：数据元素中的一个或多个数据项值，它可以惟：数据元素中的一个或多个数据项值，它可以惟一标识一个数据元素。一标识一个数据元素。平均查找长度平均查找长度(ASLASL)：式中，式中，n n为查找表的长度；为查找表的长度；p pi i为查找第为查找第i
2、 i个元素的概率，在个元素的概率，在等概率情况下等概率情况下p pi i等于等于1/n1/n；C Ci i为找到第为找到第i i个元素时的比较个元素时的比较次数次数你现在浏览的是第四页，共27页天津大学5/27顺序查找 基本思想基本思想：用给定值依次与线性表中每个元素的：用给定值依次与线性表中每个元素的关键字进行比较。如果某个元素的关键字与给定值关键字进行比较。如果某个元素的关键字与给定值相同，则查找成功；如果找遍全表也没有发现满足相同，则查找成功；如果找遍全表也没有发现满足条件的元素，则查找失败。条件的元素，则查找失败。要求要求：查找表必须采用线性表。查找表必须采用线性表。平均查找长度平均查
3、找长度 评价评价：在用顺序查找方法完成查找时，每进行一次：在用顺序查找方法完成查找时，每进行一次成功查找需要的平均比较次数约为表长度的一半，因成功查找需要的平均比较次数约为表长度的一半，因此，它的效率较低。适用于在查找表较小的情况下进此，它的效率较低。适用于在查找表较小的情况下进行查找。行查找。你现在浏览的是第五页，共27页天津大学6/27二分查找要求要求：u查找表必须采用线性表；查找表必须采用线性表；u必须以顺序方式存储线性表；必须以顺序方式存储线性表；u线性表中所有数据元素必须按照关键字有序排列线性表中所有数据元素必须按照关键字有序排列 基本思想基本思想：将给定值与处于顺序表：将给定值与处
4、于顺序表“中间位置中间位置”上上的元素的关键字进行比较，若相等则查找成功，若的元素的关键字进行比较，若相等则查找成功，若给定值大于关键字则在表的后半部分继续进行二分给定值大于关键字则在表的后半部分继续进行二分查找，否则在表的前半部分继续进行二分查找。如查找，否则在表的前半部分继续进行二分查找。如此进行下去直至找到满足条件的元素，或当前查找此进行下去直至找到满足条件的元素，或当前查找区为空，此时查找失败。区为空，此时查找失败。你现在浏览的是第六页，共27页天津大学7/27优点优点：u查找效率高查找效率高u平均查找长度平均查找长度缺点缺点：u查找前要将表中元素按关键字有序排列查找前要将表中元素按关
5、键字有序排列u只适用于线性表的顺序存储。适用于那种一经建只适用于线性表的顺序存储。适用于那种一经建立就很少改动而又经常需要查找的线性表。立就很少改动而又经常需要查找的线性表。你现在浏览的是第七页，共27页天津大学8/27分块查找要求要求：u查找表必须采用线性表；查找表必须采用线性表；u待查找的线性表分成若干块。在每一块内，元素的待查找的线性表分成若干块。在每一块内，元素的存放是任意的，但在块与块之间元素的存放是有序存放是任意的，但在块与块之间元素的存放是有序的，即前一块中任意一个元素的关键字值都必须小的，即前一块中任意一个元素的关键字值都必须小于（或大于）后一块中所有元素的关键字值；于（或大于
6、）后一块中所有元素的关键字值；u建立一个索引表，索引表中的每个索引项对应于一块。建立一个索引表，索引表中的每个索引项对应于一块。一个索引项至少应含有两部分信息：一是对应块中最一个索引项至少应含有两部分信息：一是对应块中最大的关键字值；二是指向对应块中第一个元素的指针大的关键字值；二是指向对应块中第一个元素的指针你现在浏览的是第八页，共27页天津大学9/27 基本思想基本思想：首先在索引表中查找，确定出要查找的：首先在索引表中查找，确定出要查找的元素应该在哪一块中；然后在已确定的那一块内进元素应该在哪一块中；然后在已确定的那一块内进行顺序查找。行顺序查找。你现在浏览的是第九页，共27页天津大学1
7、027 优点优点：块内元素是任意存放的，插入或删除运算不：块内元素是任意存放的，插入或删除运算不会造成元素的大量移动。会造成元素的大量移动。缺点缺点：u增加了存放索引表的辅助空间及初始时对线性表分增加了存放索引表的辅助空间及初始时对线性表分块排序的运算块排序的运算u大量的插入和删除运算可能会导致各块中元素的数大量的插入和删除运算可能会导致各块中元素的数目很不均匀，这会降低查找速度目很不均匀，这会降低查找速度你现在浏览的是第十页，共27页天津大学1127二叉排序树查找o基本思想基本思想n当二叉排序树不为空时，将给定值与根结点的值当二叉排序树不为空时，将给定值与根结点的值进行比较，若相等则查找成功
8、。如果给定值小进行比较，若相等则查找成功。如果给定值小于根结点的值，则在根结点的左子树中继续查于根结点的值，则在根结点的左子树中继续查找，否则在根结点的右子树中继续查找。当待找，否则在根结点的右子树中继续查找。当待查找的二叉排序树为空时，查找失败。查找的二叉排序树为空时，查找失败。o平均查找长度平均查找长度n在二叉排序树中查找成功时走过的是一条从根结在二叉排序树中查找成功时走过的是一条从根结点到所寻找结点的一条路径，因此，二叉排序点到所寻找结点的一条路径，因此，二叉排序树查找的平均查找长度取决于二叉排序树的深树查找的平均查找长度取决于二叉排序树的深度。度。你现在浏览的是第十一页，共27页天津大
9、学1227二叉排序树的蜕变o二叉排序树是动态生成的，它的形态与各结二叉排序树是动态生成的，它的形态与各结点插入二叉排序树时的先后顺序有关。当把点插入二叉排序树时的先后顺序有关。当把一组有序值依次插入到一棵二叉排序树时，一组有序值依次插入到一棵二叉排序树时，生成的二叉排序树将蜕变成一棵单支树。例生成的二叉排序树将蜕变成一棵单支树。例如，由整数序列如，由整数序列15,23,26,47,56,89 生成生成的二叉排序树就是一棵单支树。在单支树中的二叉排序树就是一棵单支树。在单支树中查找时，平均查找长度与顺序查找相同。查找时，平均查找长度与顺序查找相同。你现在浏览的是第十二页，共27页天津大学1327
10、哈希存储(哈希表)o以数据元素的关键字以数据元素的关键字k为自变量，通过一定为自变量，通过一定的函数关系的函数关系h(称为哈希函数或散列函数称为哈希函数或散列函数)计计算出对应的函数值算出对应的函数值h(k)，把这个值解释为，把这个值解释为数据元素的存储地址并把数据元素存储到相数据元素的存储地址并把数据元素存储到相应的存储单元内。应的存储单元内。h(k)称为哈希地址。称为哈希地址。o例：设有一组关键字值例：设有一组关键字值85,72,49,58,15,70,90,38，哈希函数，哈希函数h(k)=k mod 12。则对应的哈希地址为。则对应的哈希地址为1,0,1,10,3,10,6,2你现在浏
11、览的是第十三页，共27页天津大学1427哈希存储冲突o若有两个不同的关键字若有两个不同的关键字ki和和kj，即，即ki kj(i j)。但。但h(ki)=h(kj)，这种情况称为冲突。，这种情况称为冲突。如上例的关键字如上例的关键字85和和49，其对应的哈希地，其对应的哈希地址都为址都为1，即产生冲突。，即产生冲突。你现在浏览的是第十四页，共27页天津大学1527常用哈希函数o直接定位法直接定位法n取关键字的某个线性函数作为哈希函数，即取关键字的某个线性函数作为哈希函数，即h(k)=ak+b。其中，。其中，k为关键字，为关键字，a、b为常为常数。数。o数学分析法数学分析法o除留余数法除留余数法
12、n选择一个适当的正整数选择一个适当的正整数p(p通常选为不大于哈通常选为不大于哈希表长度希表长度 m 的最大素数），用的最大素数），用p去除关键字，去除关键字，取其余数作为哈希地址，即取其余数作为哈希地址，即h(k)=k%p(pm)。你现在浏览的是第十五页，共27页天津大学1627解决冲突的方法(1)o开放地址法开放地址法n当冲突发生时形成一个地址序列，按序列顺序逐当冲突发生时形成一个地址序列，按序列顺序逐个检查各地址单元，直至找到一个未被占用的个检查各地址单元，直至找到一个未被占用的单元为止，将发生冲突的数据元素存入该地址单元为止，将发生冲突的数据元素存入该地址单元中。单元中。n设哈希表的长
13、度是设哈希表的长度是m，发生冲突的地址是，发生冲突的地址是do 线性探查序列线性探查序列nd+1,d+2,m-1,0,1,d-1o 平方探查序列平方探查序列n(d+12)%m,(d-12)%m,(d+22)%m,(d-22)%m,你现在浏览的是第十六页，共27页天津大学1727设哈希表的长度设哈希表的长度11，哈希函数是，哈希函数是h(k)=k%11，将整数序列，将整数序列54,77,94,89,14,45,76存入哈希表。按平方探查法处理冲存入哈希表。按平方探查法处理冲突突0123456789105477948954%11=1077%11=094%11=689%11=114%11=345%1
14、1=1(冲突冲突)76%11=10(冲突冲突)144576你现在浏览的是第十七页，共27页天津大学1827解决冲突的方法(2)o链地址法链地址法n将哈希地址相同的数据元素存储到同一个单链表将哈希地址相同的数据元素存储到同一个单链表中，哈希表中的每个存储单元中不再存放数据中，哈希表中的每个存储单元中不再存放数据元素而是存放相应单链表的头指针元素而是存放相应单链表的头指针你现在浏览的是第十八页，共27页天津大学19272.排序排序你现在浏览的是第十九页，共27页天津大学2027 排序的基本概念 排序排序：将文件中的记录按排序码非递减：将文件中的记录按排序码非递减(或非或非递增递增)的顺序重新排列的
15、顺序重新排列 排序码排序码：数据元素中的一个或多个数据项。：数据元素中的一个或多个数据项。排序码可以是关键字，也可以是其他若干数排序码可以是关键字，也可以是其他若干数据项的组合。据项的组合。排序算法的稳定性排序算法的稳定性：如果在待排序的元素序：如果在待排序的元素序列中，存在着多个排序码相同的元素，按照列中，存在着多个排序码相同的元素，按照某种排序算法排序后，这些元素的相对位置某种排序算法排序后，这些元素的相对位置仍保持不变，则称该排序算法是稳定的，否仍保持不变，则称该排序算法是稳定的，否则就是不稳定的。则就是不稳定的。你现在浏览的是第二十页，共27页天津大学2127直接插入排序o以顺序查找的
16、办法找到要插入的元素在已排以顺序查找的办法找到要插入的元素在已排好序的元素序列中应处的位置。好序的元素序列中应处的位置。o所有元素分成所有元素分成2个集合：已排序记录集和待个集合：已排序记录集和待排序记录集。初始时，已排序记录集只有一排序记录集。初始时，已排序记录集只有一个元素，即个元素，即e0，待排序记录集是所有剩余元，待排序记录集是所有剩余元素。然后每次从待排序记录集中选取一个元素。然后每次从待排序记录集中选取一个元素，使用顺序查找的方法，找到其在已排序素，使用顺序查找的方法，找到其在已排序记录集中的位置，将其插入到该位置，直到记录集中的位置，将其插入到该位置，直到待排序记录集为空。待排序
17、记录集为空。你现在浏览的是第二十一页，共27页天津大学2227待排序记录为待排序记录为50,20,75,34,403440752050你现在浏览的是第二十二页，共27页天津大学2327直接选择排序o 基本思想基本思想：用逐个比较的办法从待排序的元：用逐个比较的办法从待排序的元素序列中选出最小的元素。依次对素序列中选出最小的元素。依次对i=0,1,2,n-2分别执行如下的选择和交换步骤：分别执行如下的选择和交换步骤：在元素序列在元素序列ei,ei+1,en-1中选择出最中选择出最小的元素小的元素ek；当；当ki时，交换时，交换ei与与ek的值。的值。经上述经上述n-1次的选择和交换后，排序工作即
18、次的选择和交换后，排序工作即已完成。已完成。你现在浏览的是第二十三页，共27页天津大学2427冒泡排序设待排序的元素序列为设待排序的元素序列为S=e0,e1,en-1，要求按升序排列，要求按升序排列o 基本思想基本思想：n从待排序记录集的一端（这里假定为低端）对相从待排序记录集的一端（这里假定为低端）对相邻的两个元素（邻的两个元素（e0和和e1，e1和和e2，en-2和和en-1）依次比较它们的排序码，若不符合排序的）依次比较它们的排序码，若不符合排序的顺序要求，就将相应的两个元素互换，此过程顺序要求，就将相应的两个元素互换，此过程称为一趟冒泡排序，最多经过称为一趟冒泡排序，最多经过n-1趟冒
19、泡排序，趟冒泡排序，排序工作即可完成。排序工作即可完成。你现在浏览的是第二十四页，共27页天津大学2527o一趟排序方法一趟排序方法n每趟排序的结果是将待排序记录集中排序码最大每趟排序的结果是将待排序记录集中排序码最大的元素交换到待排序记录集最后一个元素的位的元素交换到待排序记录集最后一个元素的位置。假设在一趟冒泡排序时，从置。假设在一趟冒泡排序时，从ej+1以后没有发以后没有发生元素的互换，则说明生元素的互换，则说明ej+1以后的元素是已经排以后的元素是已经排好序的，下面只需要在好序的，下面只需要在e0到到ej范围内进行新一范围内进行新一趟的冒泡排序，即待排序记录集是从趟的冒泡排序，即待排序
20、记录集是从e0到到ej，下一趟只需从下一趟只需从e0到到ej范围内进行范围内进行你现在浏览的是第二十五页，共27页天津大学262797275813496576待排序记录LastExchangeIndex279758134965762758971349657627581397496576275813499765762758134965977627581349657697待排序记录第一趟排序结束第一趟排序结束27581349657697待排序记录已排序记录你现在浏览的是第二十六页，共27页天津大学272727581349657697待待排排序序记记录录2758134965769727135849657697271349586576972713495865769727134958657697第二趟排序结束第二趟排序结束待排序待排序记录记录27134958657697待排序待排序记录记录已已排排序序记记录录你现在浏览的是第二十七页，共27页