1、第5章 排序與查找PART B,可視化計算,查找,查找算法和排序算法有密切的聯(lián)系，因為許多查找算法依賴于要查找的數(shù)據(jù)集的有序程度 基本的查找算法有以下4種： 順序查找； 比較查找也稱二分查找； 基數(shù)查找也稱分塊查找； 哈希查找,2,順序查找,順序查找過程： 通常從表中的第一個（或最后一個）記錄開始，將記錄的關鍵字與給定值逐個進行比較 當某個記錄的關鍵字與給定值相等時，即找到所查的記錄，查找成功； 反之，若查到最后一個記錄，其關鍵字和給定值的比較都不相等，則表明表中沒有所查的記錄，查找失敗。,3,順序查找的算法設計,由于順序查找的數(shù)據(jù)表，無需將節(jié)點實現(xiàn)排序，所以可以直接使用隨機數(shù)產(chǎn)生一張線形表，

2、進行查找的實驗,4,二分查找,基本思想： 將n個元素分成個數(shù)大致相同的兩半，取an/2與欲查找的x作比較，如果x=an/2則找到x，算法終止 如果xan/2，則需要在數(shù)組a的右半部繼續(xù)搜索 直至找到x為止或得出關鍵字不存在的結(jié)論 算法實現(xiàn)的前提 1.必須采用順序存儲結(jié)構(gòu) 2.必須按關鍵字大小有序排列,5,6,二分查找的算法說明,子程序先將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功； 否則利用中間位置記錄將表分成前、后兩個子表 如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表 否則將繼續(xù)查找后一子表 重復以上過程，直至找到滿足條件的記錄，或者根本查不到子表，此時

3、查找失敗,7,二分查找的算法分析,+折半查找法每執(zhí)行一次，都可以將查找空間減少一半，是計算機科學中分治思想的完美體現(xiàn) -其缺點是要求待查表為有序表，而有序表的特點則是插入刪除困難 因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表,8,分塊查找,使用撲克牌計算24點 該算法是從數(shù)字為110的撲克牌中任意抽出四張，運用加、減、乘、除，在運算中可以引入括號，每張牌只能用一次，使其計算結(jié)果為24 在廣泛的社會實踐的基礎上可以分析和認識到： 在一副牌（只保留數(shù)字點數(shù)的40張）中任意抽取4張，總共有715種不同組合形式，其中有149種組合的運算結(jié)果不可能為24,9,不可計算24的牌組(149個),1

4、0,不可計算的牌組如何確定？,計算搜索開始前，先檢查某個特定牌組的計算可能性呢？ 如果肯定得不到24的計算結(jié)果（例如，1，1，1，1和10，10，10，10），那么就可以馬上重新發(fā)牌，開始新一輪計算 可以使用查表的方式來解決！,11,問題,每次查閱這張表也不是一個簡單的過程，因為該表列出的關鍵字是使用字符串實現(xiàn)的，盡管字符串也可以轉(zhuǎn)換成數(shù)字進行排序，但顯然會增加查找過程的計算工作量 能否設計一個算法，不用轉(zhuǎn)換關鍵值，又可以減少順序查找的掃描工作量？ 可以考慮采用分塊查找算法，該算法又稱索引順序查找，它是順序查找的一種改進方法,12,分塊查詢的基本思想,將n個數(shù)據(jù)元素按塊有序劃分為m塊 （m n

5、） 每一塊中的節(jié)點不必有序，但塊與塊之間必須按塊有序； 即第1塊中任一元素的關鍵字都必須小于第2塊中任一元素的關鍵字； 而第2塊中任一元素又都必須小于第3塊中的任一元素，,13,分塊查找的實現(xiàn),不可計算牌組保存在（以文本格式）文件中 從文件讀入后，產(chǎn)生一個索引數(shù)組 保存各塊的起始元素下標,14,分塊算法設計的說明,主要子圖 Main：主流程控制；輸入/輸出 Input_list_stringc：從文件讀入149個牌組 Indexing：建立分塊索引表 Random_number：產(chǎn)生測試牌組a Sort：將測試牌組a排序 Setsample:將測試牌組a轉(zhuǎn)成測試字符串 Block_search

6、_test:進行分塊查找,15,分塊查詢,Main子圖,16,分塊查詢,主要數(shù)據(jù)結(jié)構(gòu): Str_list: 保存文件讀入的149個牌組，字符串 A：保存隨機產(chǎn)生的4張牌（110），數(shù)值 In_key:保存排序完成的牌組樣本，字符串 Index，：保存分塊索引表，,17,分塊查詢,Set_sample子圖,18,分塊查詢,Indexing子圖,19,分塊算法設計的分析,分塊查找的第一部分是進行索引表的查詢 一般來說，索引表長度在10以內(nèi)，就可以使用順序查找，否則使用二分查找 為了簡化算法，本例將149組數(shù)據(jù)只劃分了9個塊，以10開始的牌組只有一個，這里將其與9開始的牌組合并了 24點牌組的不可計

7、算比為149/715，將查詢初值ok賦值為true，可以減少賦值運算的次數(shù),20,分塊算法的運行說明,由于采用隨機數(shù)產(chǎn)生測試牌組，所以測試無需輸入樣本，只要回答，y/n即可 需要自行輸入樣本，可以自行修改樣例算法，再進行測試,21,分塊查找的時間復雜度,分塊查找的時間復雜度：O（索引表查找+塊內(nèi)查找） O（索引表二分查找+塊內(nèi)順序查找） O(log2 B) + (M+1）/2 O（索引表順序查找+塊內(nèi)順序查找） O（ (B+1）/2 + (M+1）/2） 一般描述：O（ ） 分析： 實際應用中不一定分成大小相等的塊，可按表的特征分塊（如本例所設計） 提高了順序查找的效率，但付出了空間的代價（索

8、引表）,22,哈希查找,哈希是hash的音譯，意為“雜湊”，也稱散列 哈希表是一種重要的存儲方式，哈希查找技術(shù)是一種按照關鍵字編址的檢索方法 哈希查找不同于前面的幾種查找方法，它是通過對記錄的關鍵字值進行某種運算，直接求出記錄文件的地址 是關鍵字到地址的直接轉(zhuǎn)換方法，而不需要反復比較，所以計算復雜性為常數(shù)階：O（1）,23,哈希查找的實現(xiàn)過程,仍以24點不可計算作為基本查找的數(shù)據(jù)集 由于哈希查找需要對牌組內(nèi)的牌面進行計算 注意這一點與分塊查找不同 每個牌組內(nèi)的每張牌面，都必須轉(zhuǎn)變成可以計算的數(shù)字 需要設計哈希函數(shù)并構(gòu)建哈希表,24,哈希表查找方法的基本思想,如果在記錄的存儲位置與它的關鍵字之間

9、建立一個確定的關系H（） 使每個關鍵字和一個唯一的存儲位置相對應 在查找時，只需要根據(jù)對應關系計算出給定的關鍵字值k對應的值H(k)，就可以得到記錄的存儲位置 在使用哈希方法解決24點不可計算牌組時，就是將牌面數(shù)字計算后查表，可以查到為不可計算；不可查到就是可以計算,25,哈希表的構(gòu)建,哈希函數(shù)（hash function），記錄的關鍵字值與記錄的存儲位置的對應關系H稱為哈希函數(shù)，H(k)的結(jié)果被稱為哈希地址 哈希表（hash table），是根據(jù)哈希函數(shù)建立的表，以記錄的關鍵字值為自變量，根據(jù)哈希函數(shù)，計算出對應的哈希地址，并在此存儲該記錄的內(nèi)容,26,哈希沖突與解決,沖突（collisio

10、n），不同的關鍵字值其哈希函數(shù)計算的哈希地址相同，具有相同函數(shù)值的關鍵字值稱為同義詞（synonym） 本例中處理同義詞沖突的方法是拉鏈法 ，當發(fā)生沖突時，在沖突位置的二維數(shù)組行上尋找存放記錄的空閑單元,27,24點算法的不可計算案例哈希,設定哈希表的長度為149，H關系為： H(key)=key mod 149 + 1 Key的獲取原則為： 所有10牌面模除7余3，再參與其他牌面的計算，例如，10 10 10 10等同3 3 3 3 去掉10以后的所有牌面數(shù)：key=d1*1000+d2*100+d3*10+d4 H(Key)=3333 mod 149+1=56,28,計算所得的哈希表（局部

11、）,不可計算牌組直接轉(zhuǎn)換成為字符串； 按哈希規(guī)則尋址保存在文件記錄中,29,構(gòu)建哈希表的一些要點,可以采用149行，N列的二數(shù)組保存哈希表（也就是將同義詞的牌組，按計算順序在一行中排放） 在運行后，發(fā)現(xiàn)最大的沖突數(shù)為3，因此該算法的實際哈希表為149*3=447個數(shù)據(jù)單元 在本例構(gòu)建的哈希表（hash_1）的初始化過程中，所有數(shù)組元素皆為數(shù)值0，在保存牌組時，首先要檢測當前數(shù)組元素的數(shù)據(jù)類型 如果不是數(shù)值類型，則說明已經(jīng)填入了數(shù)據(jù)，需要尋找鄰接的屬于數(shù)值類型的元素再寫入,30,哈希表的應用,在應用時，先載入已準備的哈希表 隨機生成24點牌組，應用哈希規(guī)則得到哈希表的地址 進行查表操作，可以查到，則為不可計算牌組