【正文】 下一頁 上一頁 停止放映 [第 50頁 /81] 插入排序算法 ? 基本思想： 將 n個(gè)元素的數(shù)列分為已有序和無序兩個(gè)部分 。 若整個(gè)排序過程不需要訪問外存便能完成，則稱此類排序問題為 內(nèi)部排序 ； 反之，若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過程不可能在內(nèi)存中完成，則稱此類排序問題為 外部排序 。 例如將學(xué)生記錄按學(xué)號(hào)排序 ，將課程記錄按課程編碼排序 。 下一頁 上一頁 停止放映 [第 46頁 /81] 查找舉例 以上述哈希表為例 。 0 1 2 3 4 5 6 7 8 22 22 0 1 2 3 4 5 6 7 8 41 比較次數(shù)： 1 1 取 41，計(jì)算 H（ 41） =1，該地址空，可用； 取 22，計(jì)算 H（ 22） =6，該地址空，可用； 下一頁 上一頁 停止放映 [第 42頁 /81] 舉例（續(xù)一） 取 53，計(jì)算 H（ 53） = 5，該地址空，可用； 22 41 0 1 2 3 4 5 6 7 8 53 比較次數(shù)： 1 1 1 22 41 53 46 0 1 2 3 4 5 6 7 8 比較次數(shù)： 1 1 1 2 取 46，計(jì)算 H（ 46） = 6，該地址沖突，用線性探測(cè)法計(jì)算下一個(gè)可用地址 Hi=（ 6+1） MOD 8 = 7，該地址空，可用； 下一頁 上一頁 停止放映 [第 43頁 /81] 舉例（續(xù)二） 取 30，計(jì)算 H（ 30） = 6，該地址沖突，用線性探測(cè)法計(jì)算下一個(gè)可用地址 Hi=（ 6+1） MOD 8 = 7，該地址沖突，再用線性探測(cè)法計(jì)算下一個(gè)可用地址； Hi=0，地址空，可用； 22 41 0 1 2 3 4 5 6 7 8 53 比較次數(shù)： 3 1 1 1 2 46 30 22 41 53 46 0 1 2 3 4 5 6 7 8 比較次數(shù)： 3 1 6 1 1 2 30 13 取 13，計(jì)算 H（ 13） = 5，依法解決沖突，得出： 下一頁 上一頁 停止放映 [第 44頁 /81] 舉例（續(xù)三） 取 1，計(jì)算 H（ 1） = 1，該地址沖突，解決沖突可得： 22 41 0 1 2 3 4 5 6 7 8 53 46 30 13 比較次數(shù)： 3 1 6 3 1 1 2 1 22 41 53 46 30 13 1 67 比較次數(shù)： 3 1 6 3 2 1 1 2 0 1 2 3 4 5 6 7 8 取 67，計(jì)算 H（ 67） = 3，沖突，解決沖突，得出： 下一頁 上一頁 停止放映 [第 45頁 /81] 哈希查找 哈希查找的過程和建立哈希表的過程是一致的 。 若下一個(gè)存儲(chǔ)地址仍被占用 ， 則繼續(xù)執(zhí)行 step2， 直到找到能用的存儲(chǔ)地址為止 。 哈希函數(shù)設(shè)定為 : H(key) = key MOD 8 。 增量序列的不同取法 ， 又構(gòu)成不同的開放地址法 。 均勻的哈希函數(shù)可以減少?zèng)_突 ， 但不能避免沖突 。將數(shù)據(jù)元素的關(guān)鍵字 K作為自變量 ， 通過一定的函數(shù)關(guān)系 （ 稱為哈希函數(shù) ） ， 計(jì)算出的值 ，即為該元素的存儲(chǔ)地址 。 下一頁 上一頁 停止放映 [第 34頁 /81] 哈希查找的基本概念 哈希表 由哈希函數(shù)的值組成的表 。 (5) 依次插入剩余的其他元素 下一頁 上一頁 停止放映 [第 33頁 /81] 哈希（ hash）查找 哈希查找也稱為散列查找 。 return root 。 //沿左路查找 else root=rootright。il。 } return r。 if (root) //若根非空 { if(inforootinfo) root left=r。 exit(0)。 key=search_btree(root,c)。 print_btree(root,0)。 gets(s)。 //右子指針 }*BinNodePtr。 step2 將待查關(guān)鍵字值與樹根結(jié)點(diǎn)進(jìn)行比較 ， 若相等 ， 查找成功； step3 否則根據(jù)比較結(jié)果確定查找路徑： 若小于根結(jié)點(diǎn)的關(guān)鍵字值 ， 則與左子樹的根結(jié)點(diǎn)的關(guān)鍵字值進(jìn)行比較； 若大于等于根結(jié)點(diǎn)的關(guān)鍵字值 ， 則與右子樹的根結(jié)點(diǎn)的關(guān)鍵字值進(jìn)行比較 。這里主要介紹簡(jiǎn)單易用的二叉排序樹。 示例 下一頁 上一頁 停止放映 [第 21頁 /81] 動(dòng)態(tài)查找技術(shù) ? 前兩種查找方法各有千秋。在第 3塊中用順序法查找 ,比較兩次 ,就可以找出 60的元素來。 每個(gè)塊中元素不一定是有序的 。 //不存在待查元素 } 下一頁 上一頁 停止放映 [第 16頁 /81] 對(duì)給定有序數(shù)列 { 5， 6， 11， 17， 21， 23， 28， 30，32， 40}進(jìn)行半查找算法 ， 查找關(guān)鍵字值為 30的數(shù)據(jù)元素 。 if(key==[mid].x) return mid+1。L, KeyType key ) { int low, high, mid。 但是 ， 二分查找的先決條件是查找表中的數(shù)據(jù)元素必須有序 。 算法討論 例子 下一頁 上一頁 停止放映 [第 13頁 /81] 2．折半查找 (也稱二分查找 ) ? 算法思想： 將 有序數(shù)列 的 中點(diǎn) 設(shè)置為比較對(duì)象 ， 如果要找的元素值小于該中點(diǎn)元素 ， 則將待查序列縮小為左半部分 ， 否則為右半部分 。 while([k].x!=key) k=k1。 因?yàn)檠h(huán)查找過程至少會(huì)在 0號(hào)單元停止，這樣就不必在每一次循環(huán)中都判別是否數(shù)組出界。 這里元素位置從 1開始算起 。[k].x!=key) k++。A[i]!=key? Y N 查找 key的循環(huán) 顯示“查找失敗” 返回 開始 i++ A[i]==key? Y N 顯示“查找成功” 下一頁 上一頁 停止放映 [第 9頁 /81] 順序查找算法 C++語言描述如下： int SqSearch(SSTable amp。 下一頁 上一頁 停止放映 [第 6頁 /81] 1．順序查找 順序查找的方法是從表的一端開始 ， 逐一比較給定的數(shù)據(jù) key和表中數(shù)據(jù)元素的關(guān)鍵字 x的值 ， 若兩個(gè)數(shù)據(jù)一致則查找成功 ， 同時(shí)給出該數(shù)據(jù)元素在表中的位置 ，否則查找失敗 。 在等概率條件下（ Pi=1/n）這時(shí)平均查找長(zhǎng)度為： 11???niiP其中 ： ???niiCnA S L11下一頁 上一頁 停止放映 [第 5頁 /81] 靜態(tài)查找技術(shù) 假設(shè)靜態(tài)順序查找表的存儲(chǔ)結(jié)構(gòu)為： struct SSTable{ ElemType *data。顯然，這個(gè)查找表是不斷擴(kuò)張的。 它所對(duì)應(yīng)的查找算法屬于動(dòng)態(tài)查找技術(shù) 。這種被用于查找的元素屬性一般稱為 關(guān)鍵字 ，它往往可以唯一標(biāo)識(shí)一個(gè)元素。下一頁 上一頁 停止放映 第 2章 查找和排序 西安交通大學(xué)計(jì)教中心 下一頁 上一頁 停止放映 [第 2頁 /81] 查找基本概念 查找表 : 由同一類數(shù)據(jù)構(gòu)成的用于查找的集合被稱作查找表。例如根據(jù)學(xué)號(hào)查找某個(gè)學(xué)生記錄。 動(dòng)態(tài)查找表 ： 查找表建立后 ， 在后來的查找過程中仍會(huì)改變查找表的內(nèi)容 。 解決方法是先建立一個(gè)空的查找表，以后每讀到一個(gè)詞就在查找表中查詢一下，如果該詞匯存在則將其使用次數(shù)加一，否則將新詞插入到查找表中并設(shè)使用次數(shù)為一次。 Ci為找到該記錄時(shí)，曾和給定值比較過的數(shù)據(jù)元素的個(gè)數(shù)。 順序查找表元素存放在 data[0]至 data[length1]中。amp。amp。 } 該算法若查找成功 ， 則函數(shù)返回值為目標(biāo)元素在表中的位置 ， 否則返回 0。改寫查找過程為從后往前查找。 //監(jiān)視哨 int k = 。 下一頁 上一頁 停止放映 [第 12頁 /81] 對(duì)于改進(jìn)的順序查找而言 ， 找到第 i個(gè)元素的比較次數(shù) Ci = ni+1， 所以在等概率查找的情況下 ， 順序表查找的平均查找長(zhǎng)度為： ? ? 2 1111????? ??ninnA SLniASL≤ n 2 ?優(yōu)點(diǎn) : ?對(duì)結(jié)點(diǎn)的邏輯次序 (不必有序 )和存儲(chǔ)結(jié)構(gòu) (順序、鏈表均可）無要求； ?當(dāng)序列中記錄 “ 基本有序 ” 或 N值較小時(shí)，是較好的算法； ?缺點(diǎn)： ?ASL較長(zhǎng) ?討論：能否減少比較次數(shù)，以提高效率。 它可以明顯減少比較次數(shù) ， 提高查找效率 。 下一頁 上一頁 停止放映 [第 15頁 /81] 折半查找算法的 C++語言描述如下： int BinSearch( SSTable amp。 //設(shè)置查找區(qū)間初值 while (low = high) { mid = (low + high) / 2。 //繼續(xù)在后半?yún)^(qū)間進(jìn)行查找 } return 0。 每一塊中的結(jié)點(diǎn)不必有序 ，