數(shù)據(jù)結(jié)構(gòu)與算法查找

1、數(shù)據(jù)結(jié)構(gòu)與算法查找,,趙穎 zhaoying511@126.com 中南大學(xué),，,目錄,查找基本概念靜態(tài)查找順序查找二分查找,查找基本概念,查找操作十分常見在英漢字典中查找某個(gè)英文單詞的中文解釋；在新華字典中查找某個(gè)漢字的讀音、含義；郵遞員送信件要按收件人的地址確定位置等等?？梢哉f查找是為了得到某個(gè)信息而常常進(jìn)行的工作。計(jì)算機(jī)的查找計(jì)算機(jī)、計(jì)算機(jī)網(wǎng)絡(luò)使信息查詢更快捷、方便、準(zhǔn)確。要從計(jì)算機(jī)、計(jì)算機(jī)網(wǎng)絡(luò)中查找特定的信息

2、，就需要在計(jì)算機(jī)中存儲(chǔ)包含該特定信息的表。如要從計(jì)算機(jī)中查找英文單詞的中文解釋，就需要存儲(chǔ)類似英漢字典這樣的信息表，以及對(duì)該表進(jìn)行的查找操作。查找是許多程序中最消耗時(shí)間的一部分。因而，一個(gè)好的查找方法會(huì)大大提高運(yùn)行速度。本章將討論的問題即是“信息的存儲(chǔ)和查找”。,查找基本概念,查找表用于查找的數(shù)據(jù)元素集合稱為查找表。查找表由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成。關(guān)鍵字關(guān)鍵字是數(shù)據(jù)元素中的某個(gè)數(shù)據(jù)項(xiàng)。唯一能標(biāo)識(shí)數(shù)據(jù)元素（或記

3、錄）的關(guān)鍵字，即每個(gè)元素的關(guān)鍵字值互不相同，我們稱這種關(guān)鍵字為主關(guān)鍵字；若查找表中某些元素的關(guān)鍵字值相同，稱這種關(guān)鍵字為次關(guān)鍵字。例如，銀行帳戶中的帳號(hào)是主關(guān)鍵字，而姓名是次關(guān)鍵字。,查找基本概念,查找在數(shù)據(jù)元素集合中查找滿足某種條件的數(shù)據(jù)元素的過程稱為查找。最簡單且最常用的查找條件是“關(guān)鍵字值等于某個(gè)給定值”。若按主關(guān)鍵字查找，查找結(jié)果是唯一的；若按次關(guān)鍵字查找，結(jié)果可能是多個(gè)記錄，即結(jié)果可能不唯一。查找表的存儲(chǔ)結(jié)構(gòu)對(duì)于不

4、同的存儲(chǔ)結(jié)構(gòu)的查找表，其查找方法不同。為了提高查找速度，有時(shí)會(huì)采用一些特殊的存儲(chǔ)結(jié)構(gòu)，比如：線性結(jié)構(gòu)（順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)）、樹形結(jié)構(gòu)、哈希表結(jié)構(gòu)等等查找算法的時(shí)間效率查找過程的主要操作是關(guān)鍵字的比較，所以通常以“平均比較次數(shù)”來衡量查找算法的時(shí)間效率。,查找基本概念,靜態(tài)查找表靜態(tài)查找表在查找過程中查找表本身不發(fā)生變化，只對(duì)查找表進(jìn)行如下兩種操作：（1）在查找表中查看某個(gè)特定的數(shù)據(jù)元素是否在查找表中（2）檢索某個(gè)特定元素的各種

5、屬性，則稱這類查找表為靜態(tài)查找表。對(duì)靜態(tài)查找表進(jìn)行的查找操作稱為靜態(tài)查找。動(dòng)態(tài)查找表動(dòng)態(tài)查找表在查找過程中查找表可能會(huì)發(fā)生變化在查找過程中可以將查找表中不存在的數(shù)據(jù)元素插入或者從查找表中刪除某個(gè)數(shù)據(jù)元素，則稱這類查找表為動(dòng)態(tài)查找表。對(duì)動(dòng)態(tài)查找表進(jìn)行的查找操作稱為動(dòng)態(tài)查找。,目錄,查找基本概念靜態(tài)查找順序查找二分查找,順序查找,順序查找的基本思想順序查找是一種最簡單的查找方法。其基本思想是：將查找表作為一個(gè)線性表，

6、可以是順序表，也可以是鏈表依次用查找條件中給定的值與查找表中數(shù)據(jù)元素的關(guān)鍵字值進(jìn)行比較若某個(gè)記錄的關(guān)鍵字值與給定值相等則查找成功，返回該記錄的位置反之，若直到最后一個(gè)記錄，其關(guān)鍵字值與給定值均不相等，則查找失敗，返回查找失敗標(biāo)志。下面講解順序表的順序查找鏈?zhǔn)奖淼捻樞虿檎?順序查找,順序表的類型定義：#define MAX_NUM 100 //用于定義表的長度typedef struct elemty

7、pe{ keytype key; anytype otheritem; }Se_List[MAX_NUM],Se_Item;順序表的順序查找算法：int seq_search (Se_List a，keytype k){ //在順序表中查找關(guān)鍵字值等于k的記錄，若查找成功，返回該記錄的位置下標(biāo)序號(hào)，否則返回0 i=1; //假設(shè)在查找表中，數(shù)據(jù)元素個(gè)數(shù)為n（n<MAX_N

8、UM），數(shù)組下標(biāo)為a[1]~a[n] while (i<=n && a[i].key != k) i++; if (i<=n) retrun i; else return 0;},很簡單，容易理解還能改進(jìn)嗎？,順序查找,順序表的順序查找算法（改進(jìn)版）：int seq_search2 (Se_List a，keytype k){ //設(shè)置了監(jiān)視哨的順序表查找，查找關(guān)鍵字值等

9、于指定值k的記錄 i=n ; //從后往前查找 a[0].key=k ; //a[0]為監(jiān)視哨，算法中監(jiān)視哨的作用是為了在while循環(huán)中省去判定防止下標(biāo)越界的條件 i<n，從而節(jié)省比較的時(shí)間。 while ( a[i].key != k) i--; return ( i ) ;},順序查找,平均查找長度ASL 定義：在查找成功時(shí)，平均查找長度ASL是指為確定數(shù)據(jù)元素在表中的位

10、置所進(jìn)行的關(guān)鍵碼比較次數(shù)的期望值。對(duì)一個(gè)含n個(gè)數(shù)據(jù)元素的表，查找成功時(shí)：Pi為表中第i個(gè)數(shù)據(jù)元素的查找概率Ci為表中第i個(gè)數(shù)據(jù)元素的關(guān)鍵碼與給定值kx相等時(shí)，按算法定位時(shí)關(guān)鍵碼的比較次數(shù)。顯然，不同的查找方法，Ci可以不同。,順序查找,順序查找效率分析順序查找：對(duì)于n個(gè)數(shù)據(jù)元素的表，給定值kx與表中第i個(gè)元素關(guān)鍵碼相等，即定位第i個(gè)記錄時(shí)，需進(jìn)行n-i+1次關(guān)鍵碼比較，即Ci=n-i+1。則查找成功時(shí)，順序查找的平均查找長

11、度為：設(shè)每個(gè)數(shù)據(jù)元素的查找概率相等，即 　 ，則等概率情況下有 ：查找不成功時(shí)，關(guān)鍵碼的比較次數(shù)總是n+1次。算法的時(shí)間復(fù)雜度，其為O(n)。,順序查找,鏈表的類型定義如下所示：typedef struct node { keytype key; //結(jié)點(diǎn)的關(guān)鍵字類型 anytype otheritem;//結(jié)點(diǎn)的其他成分 struct no

12、de *next;//指向鏈表結(jié)點(diǎn)的指針}Link_Node,*Link;鏈表表的順序查找算法：Link_Node *link_search (Link h , keytype k){ //link為帶頭結(jié)點(diǎn)鏈表的頭指針，查找關(guān)鍵字值等于k的記錄， //查找成功，返回指向找到的結(jié)點(diǎn)的指針，查找失敗返回空指針 p=h->next; ？？？？？？？？？？？？？？？？？自己寫寫看; return

13、 p;},順序查找,Link_Node *link_search (Link h , keytype k){ //link為帶頭結(jié)點(diǎn)鏈表的頭指針，查找關(guān)鍵字值等于k的記錄， //查找成功，返回指向找到的結(jié)點(diǎn)的指針，查找失敗返回空指針 p=h->next; while ((p!=NULL) && (p->key!=k)) p=p->next; return p;},

14、目錄,查找基本概念靜態(tài)查找順序查找二分查找,二分查找,二分查找 二分查找又稱為折半查找。二分查找要求線性表是有序的（遞增或遞減），并且使用順序存儲(chǔ)方式（向量存儲(chǔ)）。二分查找的基本思想是：首先將待查的K值與有序表R[0]到R[n-1]的中間位置mid上的結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較，若相等，則查找完成；否則，若R[mid].key>K，則說明待查找的結(jié)點(diǎn)只可能在左子表R[0]到R[mid-1]中，只需在左子表中繼續(xù)查找；否則

15、在右子表中繼續(xù)查找。這樣，經(jīng)過一次關(guān)鍵字的比較就縮小了一半的查找區(qū)間。如此進(jìn)行下去，直到找到為止（也存在最后找不到的可能）,[05 13 19 21 37 56 64 75 80 88 92],[05 13 19 21 37] 56 64 75 80 88 92,05 13 19 [21 37] 56 64 75 80 88

16、 92,,,,查找K=21的過程（查找成功）,[05 13 19 21 37 56 64 75 80 88 92],05 13 19 21 37 56 [64 75 80 88 92],05 13 19 21 37 56 64 75 80 [88 92],,,,查找K=85的過程（查找失?。?05 13 19

17、21 37 56 64 75 80] [88 92,二分查找,二分查找算法int BINSEARCH(table R[],keytype K){ int low,mid,high; low＝0; high＝n-1; //設(shè)置查找區(qū)間的上下界初值 while (low<=high) //當(dāng)查找區(qū)間為非空 { mid＝(low+high)/2; if (K=R[mi

18、d].key) return mid; //查找成功返回 if (K<R[mid].key) high＝mid-1; //縮小查找區(qū)間為左子表 esle low＝mid+1; //縮小查找區(qū)間為右子表 } return -1;},二分查找,二分查找效率分析如果把當(dāng)前查找位置上的結(jié)點(diǎn)作為根，左子表和右子表的結(jié)點(diǎn)分別作為根的左子樹和右子樹，由此得到的二叉樹稱為二分查找的判定樹。借助于判定樹很容易

19、求得二分查找的平均查找長度。在最壞情況下，二分查找方法查找成功的比較次數(shù)不超過判定樹的深度：雖然二分查找的效率較高，但它要求被查找序列事先按關(guān)鍵字排好序，而排序本身是一種很費(fèi)時(shí)的運(yùn)算；另外，二分查找只適用于順序存儲(chǔ)結(jié)構(gòu)，因此，二分查找特別適用于那種一經(jīng)建立就很少改動(dòng)、而又需要經(jīng)常查找的線性表。,例key =70 的查找過程,0 1 2 3 4 5 6

20、 7 8 9 10,5 13 19 21 37 56 64 75 80 88 92,,,,,,,,,,,,low,,high,,mid,找70,寫出各趟查找過程,例key =70 的查找過程,0 1 2 3 4 5 6 7

21、 8 9 10,5 13 19 21 37 56 64 75 80 88 92,,,,,,,,,,,,low,,high,,mid,找70,0 1 2 3 4 5 6 7 8 9

22、 10,5 13 19 21 37 56 64 75 80 88 92,,,,,,,,,,,,low,,high,,mid,0 1 2 3 4 5 6 7 8 9 10,5 13 19

23、 21 37 56 64 75 80 88 92,,,,,,,,,,,,low,,high,,mid,0 1 2 3 4 5 6 7 8 9 10,5 13 19 21 37 56 64

24、 75 80 88 92,,,,,,,,,,,,low,,high,,mid,0 1 2 3 4 5 6 7 8 9 10,5 13 19 21 37 56 64 75 80 88 9

25、2,,,,,,,,,,,,low,,high,0 1 2 3 4 5 6 7 8 9 10,5 13 19 21 37 56 64 75 80 88 92,,,,,,,,,,,當(dāng)下界low大于上界high時(shí)，則說明表