《可视化计算》第5章排序与查找(B).ppt

第5章 排序与查找PART B,可视化计算,查找,查找算法和排序算法有密切的联系，因为许多查找算法依赖于要查找的数据集的有序程度基本的查找算法有以下4种：顺序查找；比较查找也称二分查找；基数查找也称分块查找；哈希查找,2,顺序查找,顺序查找过程：通常从表中的第一个（或最后一个）记录开始，将记录的关键字与给定值逐个进行比较当某个记录的关键字与给定值相等时，即找到所查的记录，查找成功；反之，若查到最后一个记录，其关键字和给定值的比较都不相等，则表明表中没有所查的记录，查找失败。,3,顺序查找的算法设计,由于顺序查找的数据表，无需将节点实现排序，所以可以直接使用随机数产生一张线形表，进行查找的实验,4,二分查找,基本思想：将n个元素分成个数大致相同的两半，取an/2与欲查找的x作比较，如果x=an/2则找到x，算法终止如果xan/2，则需要在数组a的右半部继续搜索直至找到x为止或得出关键字不存在的结论算法实现的前提1.必须采用顺序存储结构 2.必须按关键字大小有序排列,5,6,二分查找的算法说明,子程序先将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表否则将继续查找后一子表重复以上过程，直至找到满足条件的记录，或者根本查不到子表，此时查找失败,7,二分查找的算法分析,+折半查找法每执行一次，都可以将查找空间减少一半，是计算机科学中分治思想的完美体现-其缺点是要求待查表为有序表，而有序表的特点则是插入删除困难因此，折半查找方法适用于不经常变动而查找频繁的有序列表,8,分块查找,使用扑克牌计算24点该算法是从数字为110的扑克牌中任意抽出四张，运用加、减、乘、除，在运算中可以引入括号，每张牌只能用一次，使其计算结果为24在广泛的社会实践的基础上可以分析和认识到：在一副牌（只保留数字点数的40张）中任意抽取4张，总共有715种不同组合形式，其中有149种组合的运算结果不可能为24,9,不可计算24的牌组(149个),10,不可计算的牌组如何确定？,计算搜索开始前，先检查某个特定牌组的计算可能性呢？如果肯定得不到24的计算结果（例如，1，1，1，1和10，10，10，10），那么就可以马上重新发牌，开始新一轮计算可以使用查表的方式来解决！,11,问题,每次查阅这张表也不是一个简单的过程，因为该表列出的关键字是使用字符串实现的，尽管字符串也可以转换成数字进行排序，但显然会增加查找过程的计算工作量能否设计一个算法，不用转换关键值，又可以减少顺序查找的扫描工作量？可以考虑采用分块查找算法，该算法又称索引顺序查找，它是顺序查找的一种改进方法,12,分块查询的基本思想,将n个数据元素按块有序划分为m块（m n）每一块中的节点不必有序，但块与块之间必须按块有序；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，,13,分块查找的实现,不可计算牌组保存在（以文本格式）文件中从文件读入后，产生一个索引数组保存各块的起始元素下标,14,分块算法设计的说明,主要子图Main：主流程控制；输入/输出Input_list_stringc：从文件读入149个牌组Indexing：建立分块索引表Random_number：产生测试牌组aSort：将测试牌组a排序Setsample:将测试牌组a转成测试字符串Block_search_test:进行分块查找,15,分块查询,Main子图,16,分块查询,主要数据结构:Str_list:保存文件读入的149个牌组，字符串A：保存随机产生的4张牌（110），数值In_key:保存排序完成的牌组样本，字符串Index，：保存分块索引表，,17,分块查询,Set_sample子图,18,分块查询,Indexing子图,19,分块算法设计的分析,分块查找的第一部分是进行索引表的查询一般来说，索引表长度在10以内，就可以使用顺序查找，否则使用二分查找为了简化算法，本例将149组数据只划分了9个块，以10开始的牌组只有一个，这里将其与9开始的牌组合并了24点牌组的不可计算比为149/715，将查询初值ok赋值为true，可以减少赋值运算的次数,20,分块算法的运行说明,由于采用随机数产生测试牌组，所以测试无需输入样本，只要回答，y/n即可需要自行输入样本，可以自行修改样例算法，再进行测试,21,分块查找的时间复杂度,分块查找的时间复杂度：O（索引表查找+块内查找）O（索引表二分查找+块内顺序查找）O(log2 B)+(M+1）/2O（索引表顺序查找+块内顺序查找）O（(B+1）/2+(M+1）/2）一般描述：O（）分析：实际应用中不一定分成大小相等的块，可按表的特征分块（如本例所设计）提高了顺序查找的效率，但付出了空间的代价（索引表）,22,哈希查找,哈希是hash的音译，意为“杂凑”，也称散列哈希表是一种重要的存储方式，哈希查找技术是一种按照关键字编址的检索方法哈希查找不同于前面的几种查找方法，它是通过对记录的关键字值进行某种运算，直接求出记录文件的地址是关键字到地址的直接转换方法，而不需要反复比较，所以计算复杂性为常数阶：O（1）,23,哈希查找的实现过程,仍以24点不可计算作为基本查找的数据集由于哈希查找需要对牌组内的牌面进行计算注意这一点与分块查找不同每个牌组内的每张牌面，都必须转变成可以计算的数字需要设计哈希函数并构建哈希表,24,哈希表查找方法的基本思想,如果在记录的存储位置与它的关键字之间建立一个确定的关系H（）使每个关键字和一个唯一的存储位置相对应在查找时，只需要根据对应关系计算出给定的关键字值k对应的值H(k)，就可以得到记录的存储位置在使用哈希方法解决24点不可计算牌组时，就是将牌面数字计算后查表，可以查到为不可计算；不可查到就是可以计算,25,哈希表的构建,哈希函数（hash function），记录的关键字值与记录的存储位置的对应关系H称为哈希函数，H(k)的结果被称为哈希地址哈希表（hash table），是根据哈希函数建立的表，以记录的关键字值为自变量，根据哈希函数，计算出对应的哈希地址，并在此存储该记录的内容,26,哈希冲突与解决,冲突（collision），不同的关键字值其哈希函数计算的哈希地址相同，具有相同函数值的关键字值称为同义词（synonym）本例中处理同义词冲突的方法是拉链法，当发生冲突时，在冲突位置的二维数组行上寻找存放记录的空闲单元,27,24点算法的不可计算案例哈希,设定哈希表的长度为149，H关系为：H(key)=key mod 149+1Key的获取原则为：所有10牌面模除7余3，再参与其他牌面的计算，例如，10 10 10 10等同3 3 3 3去掉10以后的所有牌面数：key=d1*1000+d2*100+d3*10+d4H(Key)=3333 mod 149+1=56,28,计算所得的哈希表（局部）,不可计算牌组直接转换成为字符串；按哈希规则寻址保存在文件记录中,29,构建哈希表的一些要点,可以采用149行，N列的二数组保存哈希表（也就是将同义词的牌组，按计算顺序在一行中排放）在运行后，发现最大的冲突数为3，因此该算法的实际哈希表为149*3=447个数据单元在本例构建的哈希表（hash_1）的初始化过程中，所有数组元素皆为数值0，在保存牌组时，首先要检测当前数组元素的数据类型如果不是数值类型，则说明已经填入了数据，需要寻找邻接的属于数值类型的元素再写入,30,哈希表的应用,在应用时，先载入已准备的哈希表随机生成24点牌组，应用哈希规则得到哈希表的地址进行查表操作，可以查到，则为不可计算牌组；不可查到，则为可计算牌组查找的效率在1到3次之间，时间复杂度为：O（1）,31,小结与回顾,查找策略则与数据的排序与否，数据自身的属性有重大关系。顺序查找针对未排序数据，二分查找针对已排序数据，分块查找针对按块有序、块内无序的数据而最能体现计算机科学精髓的查找方法则是哈希查找，哈希查找是通过计算数据元素的存储地址进行查找的算法,32,