數(shù)據(jù)查找順序、二分、索引、哈希查找.doc

選題八數(shù)據(jù)查找一、基本概念查找表：是由同一類型的數(shù)據(jù)元素(或記錄)構成的集合。 查找：也稱檢索，即根據(jù)給定的某個值，在查找表中確定一個其關鍵字等于給定值的第一條記錄(元素)或全部記錄。若表中存在這樣的記錄，則查找成功，通常要求返回該記錄存儲位置；若不存在這樣的記錄，表明查找失敗，返回特定值。例：在下表中查找 學號為“98182”的學生信息學 號姓 名性別籍 貫出生年月198131劉激揚男北 京1979.12298164衣春生男青 島1979.07398165盧聲凱男天 津1981.02498182袁秋慧女廣 州1980.10598203林德康男上 海1980.05平均查找長度：在查找成功情況下平均比較次數(shù)，可用作判定一個查找算法的時間復雜度：其中：n：查找表長；Pi：查找第i個元素；Ci：查找第i個元素比較次數(shù)。二、順序查找1查找思路順序表：指線性表的順序存儲結構。本章討論中，設順序表采用一維數(shù)組A表示，其元素類型為ElemType，它含有關鍵字域key和其它一些數(shù)據(jù)域，并設定A的大小為整型常量MaxSize，數(shù)組的元素個數(shù)為n，n應小于等于MaxSize。typedef struct KeyType key;ElemType;順序查找：又稱線性查找，它是一種最簡單最基本查找方法。查找思路：從順序表的一端開始，依次將每個元素關鍵字同給定值K進行比較，若某個元素關鍵字等于K，則查找成功，返回該元素所在下標，若直到所有元素都比較完畢，仍找不到關鍵字為K的元素，則查找失敗，反回特定值(常用-1表示)?；舅惴╥nt Seqsch(ElemType A ,int n,KeyType K) /從順序表A的n個元素中順序查找關鍵字為K的元素，若成功返回其下標，否則返回-1for(int i=0;in;i+)if(Ai.key=K)break; if(in)/查找成功返回下標，否則返回-1 return i;else return -1;如下圖：0123452345643278在順序表中查找56，比較3次。改進算法對該算法作一改進：在表的尾端An設一崗哨，在查找前先將K賦給An,這樣每循環(huán)一次不需比較下標是否越界，當比較到第n位置時，由于An.key=K成立，必退出循環(huán)。 int Seqsch(ElemType A ,int n,KeyType K) /從順序表A的n個元素中順序查找關鍵字為K的元素，若成功返回其下標，否則返回-1An.key=k; /設置崗哨for(int i=0; ;i+)if(Ai.key=K)break;if(in)return i;elsereturn -1;在順序表中查找56，設A6=56為崗哨：0123456234564327856性能描述平均查找長度為：順序查找時間復雜度為O(n)。缺點：速度較慢，查找成功最多需比較n次，平均查找長度約為表長一半。優(yōu)點：算法簡單，適應面廣，對表結構無任何要求。三、二分查找二分查找又稱折半查找。作為二分查找對象的表必須是順序存儲的有序表。查找過程：首先取整個有序表A0An-1的中點元素Amid(mid=(n-1)/2的關鍵字與K比較。如下圖所示：例如：查找23：查找96：查找58：1二分查找的遞歸算法int Binsch(ElemType A ,int low,int high,KeyType K)/在AlowAhigh內查找K,low初值為0,high初值n-1if(low=high) int mid=(low+high)/2; /求中間點下標if(K=Amid.key)return mid; /查找成功返回else if(KAmid.key)return Binsch(A,low,mid-1,K); /左子表上查找elsereturn Binsch(A,mid+1,hign,K);/右子表上查找else return -1; /查找失敗反回-12二分查找的非遞歸算法在下面的遞增有序序列中查找關鍵字6。四、索引查找1概念索引查找：又稱分級查找，計算機中為索引查找建立一張主表和各級索引表。索引存儲的基本思想是：首先把一個線性表(主表)按一定的函數(shù)關系劃分成若干邏輯上的子表，為每個子表分別建立一個索引項，由所有這些索引項構成主表的一個索引表，然后可采用順序或鏈接方式存儲索引表和子表。職工號姓名單位職稱工資JS001王大明計算機教授680JS002吳進計算機講師440JS003邢懷學計算機講師460DZ001趙利電子助教380DZ002劉平電子講師480DZ003張衛(wèi)電子副教授600JJ001安曉軍機械講師450JJ002趙京華機械講師440HG001孫亮化工教授720HG002陸新化工副教授580HG003王方化工助教400索引表中每個索引項通常包含三個域：一是索引值域(index)；二是子表開始位置域(start)；三是子表長度域(length)。一個學校的教師登記表如下表，其中職工號作為關鍵字：以每個記錄的“職工號”作關鍵字，則線性表可簡記：LA=(JS001,JS002,JS003,JS004,DZ001,DZ002,DZ003,JJ001,JJ002,HG001,HG002,HG003)若按“單位”數(shù)據(jù)項值對LA劃分，則得四個子表：JS=(JS001,JS002,JS003)DZ=(DZ001,DZ002,DZ003)JJ=(JJ001,JJ002)HG=(HG001,HG002,HG003)可得索引表b1，如圖所示：indexstartlength0JS031DZ332JJ623HG832索引表類型定義索引項的類型和順序存儲的索引表類型如下定義：struct IndexItemIndexKeyType index; /IndexKeyType為事先定義/的索引值類型int start; /子表中第一個元素所在下標位置int length; /子表的長度;typedef IndexItem indexlistILMSize ; /ILMSize為事先定義整型常量，它大于等于索引項m。若所有子表(合稱為主表)被順序存儲在同一數(shù)組中，類型定義如下：typedef ElemType mainlistMaxSize; /MaxSize為事先定義的整型常量，它大于等于n。indexstartlength0JS031DZ332JJ623HG833索引查找算法算法思路：索引查找是有索引表和主表上進行的查找，其過程是：先根據(jù)給定的索引值K1，在索引表上查找出索引值等于K1的索引項，以確定對應子表在主表中開始位置和長度，再根據(jù)給定關鍵字K2，在對應子表中查找出關鍵字等于K2的結點。一個學校的教師登記表如下，職工號作為關鍵字： 職工號姓名單位職稱工資JS001王大明計算機教授680JS002 吳進計算機講師440JS003邢懷學計算機講師460DZ001 趙利電子助教380DZ002劉平電子講師480DZ003 張衛(wèi)電子副教授600JJ001安曉軍機械講師450JJ002趙京華機械講師440HG001孫亮化工教授720HG002陸新化工副教授580HG003王方化工助教400按“單位”數(shù)據(jù)項值對線性表劃分，則得四個子表：JS=(JS001,JS002,JS003)DZ=(DZ001,DZ002,DZ003)JJ=(JJ001,JJ002)HG=(HG001,HG002,HG003)可得索引表b1，如圖所示：indexstartlength0JS031DZ332JJ623HG83nt Indsch(mainlist A,indexlist B,int m,IndexKeyType K1,KeyType K2)/利用主表A和大小為m的索引表B索引查找索引值為K1,關鍵字為K2的記錄，返回該記錄在主表中的下標位置，若查找失敗返回-1int i,j;/在索引表中順序查找索引值為K1的索引項for(i=0;im;i+)if(K1=Bi.index) break;if(i=m) return -1；/在已查找到的第i個子表中順序查找關鍵字為K2的記錄j=Bi.start;while(jBi.start+Bi.length)if(K2=Aj.key) break;else j+;if(jBi.start+Bi.length) return j;else return -1;設索引表長度為m,相應子表長度為s,索引查找的平均查找長度為：(m+1)/2+(s+1)/24分塊查找分塊查找：屬于索引查找，它要求主表中每個子表之間遞增(遞減)有序，并且索引表中每個索引項的索引值域用來存儲對應塊中最大關鍵字。分塊查找算法：int Blocksch(mainlist A,indexlist B,int m,KeyType K)/利用主表A和大小為m的索引表B分塊查找關鍵字為K的記錄int i,j;/在索引表中順序查找關鍵字為K所對應的索引項for(i=0;im;i+)if(K=Bi.index) break;if(i=m) return -1;/在已經(jīng)查找到的第i個子表中順序查找關鍵字Kj=Bi.start;while(jBi.start+Bi.length)if(K=Aj.key) break;else j+;/若查找成功則返回元素的下標位置，否則返回-1if(jBi.start+Bi.length) return j;else return -1;五、散列查找1基本概念散列函數(shù)：在進行查找時，在記錄的存儲位置與它的關鍵字之間建立一個確定的對應關系h,以線性表中每個元素的關鍵字K為自變量，通過函數(shù)h(K)計算出該元素的存儲位置，我們將h函數(shù)稱為散列函數(shù)或哈希函數(shù)。h(K)的值稱為散列地址或哈希地址。例：假定一個線性表為 A=(18,75,60,43,54,90,46)，選取散列函數(shù)為：h(K)=K%m 取m=13則得每個元素散列地址：h(18)=18 % 13=5 h(75)=75 % 13=10 h(60)=60 % 13=8 h(43)=43 % 13=4h(54)=54 % 13=2 h(90)=90 % 13=12 h(46)=46 % 13=7根據(jù)散列地址，實現(xiàn)元素的存儲映象Hm：0123456789101112H54431846607590沖突：在實際應用中，通?？赡艹霈F(xiàn)一個待插入元素的散列地址單元已被占用情況，使得該元素無法直接存入此單元，這種情況稱為沖突。同義詞：具有不同關鍵字而具有相同散列地址的元素稱為同義詞，即key1key2，但h(key1)=h(key2)。由同義詞引起的沖突稱作同義詞沖突。例：如向下表中再插入元素70時，70%13=5，則出現(xiàn)了沖突 0123456789101112H54431846607590裝填因子()：指散列表中已存入的元素數(shù)n與散列表空間大小m的比值,即：=n/m。當越小時，沖突可能性就越小，但同時，存儲空間利用率就越低。散列表：根據(jù)設定的哈希函數(shù)及處理沖突的方法將一組關鍵字映象到一個有限的連續(xù)的地址集上，即把記錄存放在表中映象的位置上，這種表便稱為散列表(哈希表)。一個散列表的好壞與三個因素有關：l 裝填因子l 所采用的散列函數(shù)l 解決沖突的方法 2散列函數(shù)構造散列函數(shù)的目標是使散列地址盡可能均勻分布在散列空間上，同時使計算盡可能簡單，以節(jié)省計算時間。直接定址法以關鍵字K本身或關鍵字加上某個數(shù)值常量C作為散列地址的方法，對應的散列函數(shù)：h(K)=K+C (C為常數(shù))例：有一個解放后出生的人口調查表，關鍵字是年份，h(K)=K+(-1948)，如表所示：地址 01 02 03 22 年份1949 1950 1951 1970 人數(shù) 15000 .除留余數(shù)法以關鍵字K除以散列長度m所得余數(shù)作為散列地址的方法，對應的散列函數(shù)：h(K)=K%m m為散列表長，取m=13,得散列表：0123456789101112H54431846607590l 取m為奇數(shù)比取m為偶數(shù)好l 確保m的值大于等于待散列的線性表的長度nl 當關鍵字K為字符串時，需轉換為整數(shù)(先求K長，接著把每個字符的ASCII碼累加到無符號整型量h上，并且每次累加前，h值左移3位，擴大8倍)int Hash(char * K, int m)/把字符串K轉換為0m-1之間的一個值作為對應記錄的散列地址int len=strlen(K); /求字符串K的長度unsigned int h=0;for(int i=0;ilen;i+)/采用一種方法計算K所對應的整數(shù)h=3; /h的值左移3位h+=Ki; return h%m;數(shù)字分析法取關鍵字中某些數(shù)值較分散的數(shù)字位作為散列地址的方法，適用于所有關鍵字已知，并對關鍵字中每一位的取值分布情況作了分析。例：有一組關鍵字如下：92326875927396289234363492706816927746389238126292394220通過分析：每個關鍵字從左到右第1、2、3位和第6位取值較集中，不宜作散列地址，其余的第4、5、7、8位取值分散，可以選擇，若取最后兩位作散列地址，得：(2,75,28,34,16,38,62,20)平方取中法取關鍵字平方的中間幾位作為散列地址的方法，由平方取中法得到的散列地址同關鍵字的每一位都有關，使得散列地址有較好分散性。它適用于關鍵字中每一位取值都不夠分散或者較分散的位數(shù)小于散列地址所需要的位數(shù)的情況。折疊法：首先將關鍵字分割成位數(shù)相同的幾段(最后一段位數(shù)可少一些)，然后將它們的疊加和(舍去最高位進位)作為散列地址的方法。例：有一關鍵字：K=68242324，散列地址3位，將此關鍵字從左到右每三位一段劃分后相疊加得： 3處理沖突的方法1) 開放定址法思路：從發(fā)生沖突的那個單元開始，按照一定次序，從散列表中查找出一個空閑的存儲單元，把發(fā)生沖突的待插入元素存入到該單元的一類處理沖突的方法。在使用該方法處理沖突的散列表中，查找一個元素的過程是：先根據(jù)給定關鍵字K，利用與插入時使用的同一散列函數(shù)h(K)計算出散列地址(設下標為d),然后用K同d單元的關鍵字比較，若相等則查找成功，否則按插入時處理沖突的相同次序，依次用K同所查單元的關鍵字比較，直到查找成功或查找到一空單元(表明查找失敗)為止。三種方法： 線性探查法是用開放定址法處理沖突的一種最簡單的探查方法。從發(fā)生沖突的d單元起,依次探查下一個單元,直到碰到一個空閑單元或探查完所有單元為止探查時,當達到下標為m-1的表尾單元時,下一個探查的單元是下標為0的表首單元。探查序列為d,d+1,d+2，表示為(d+i)%m (0im-1)。例如：構取m=13,線性表為 A=(18,75,60,43,54,90,46)，構造的散列表如下：0123456789101112H54431846607590現(xiàn)向表中再插入關鍵字為31和58的兩個元素,用線性探查法解決沖突。先插入31，h(31)=31%13=5,因H5被占用，探查下一個即下標為6的單元，空閑，插入31。0123456789101112H5443183146607590再插入58，h(58)=58%13=6,因H6被占用，探查下一個即下標為7的單元，因H7仍不空閑，再接著向下探查，當探查到下標為9的單元時，空閑，插入58。0123456789101112H544318314660587590利用線性探查法處理沖突易造成元素的“堆積”(聚集) 0123456789101112H54431846607590向散列表中插入一個元素：int Insert (hashlist1 HT,int m,ElemType item)/向長度為m的散列表HT中插入一個元素int d=H(item.key,m); /可選一種合適的構造散列函數(shù)的方法，計算散列地址int temp=d;while(HTd.key != NullTag)/當d單元不空時繼續(xù)向后查找空位置d=(d+1)%m;if(d=temp) return 0;HTd=item; /將新元素插入到下標為d的位置return 1; 從散列表中查找一個元素：int Search (hashlist1 HT,int m, ElemType item)/從長度為m的散列表HT中查找int d=H(item.key, m);int temp=d;while(HTd.key!=NullTag)/當散列地址中的關鍵字域不為空則循環(huán)if(HTd.key=item.key) return d;else d=(d+1)%m;if(d=temp) return -1;return -1; 平方探查法探查序列為d,d+12,d+22,表示為(d+i2)%m(0im-1)。遞推公式為：優(yōu)點：它是一種較好的處理沖突的方法，可以較好避免堆積現(xiàn)象缺點：不能探查到散列表上所有單元。例：當d0=5,m=17時，只能探查到下標依次為5、6、9、14、4、13、7、3、1的單元。d0=5;d1=(5 +2*1-1)%17=6; d2=(6 +2*2-1)%17=9;d3=(9 +2*3-1)%17=14; d4=(14 +2*4-1)%17=4;d5=(4 +2*5-1)%17=13; d6=(13 +2*6-1)%17=7;d7=(7 +2*7-1)%17=3; d8=(3 +2*8-1)%17=1; d9=(1 +2*9-1)%17=1; 雙散列函數(shù)探查法思路：該方法使用兩個散列函數(shù)h1和h2，其中h1和前面的h(K)一樣，以關鍵字為自變量，產生一個0m-1之間的數(shù)作散列地址;h2也以關鍵字為自變量，產生一個1m-1之間的、并和m互素的數(shù)作散列地址。它的探查序列為：利用雙散列法，按一定的距離，跳躍式地尋找“下一個”桶，減少了“堆積”的機會，最多經(jīng)過m-1次探查，它會遍歷表中所有位置，回到H0 位置。例：給出一組表項關鍵碼22,41,53,46,30,13,01,67。散列表為 HT0.10，m = 11。散列函數(shù)為：Hash(x)(3x) % 11再散列函數(shù)為：ReHash(x) = (7x) % 10 +1Hi = ( Hi-1 + (7x) % 10 +1 ) % 11, i = 1, 2, H0(22) = 0 H0(41) = 2 H0(53) = 5 H0(46) = 6H0(30) = 2 沖突 H1 = (2+1) = 3 ,H0(13) = 6 沖突 H1 = (6+2) = 8H0(01) = 3 沖突 H1 = (3+8) = 0 ,H2 = (0+8) = 8 H3 = (8+8) = 5H4 =(5+8)=2 H5 =(2+8)=10,H0(67)=3 沖突, H1 = (3+10) = 2 H2 = (2+10) = 1搜索成功的平均搜索長度：2) 鏈接法思路：就是把發(fā)生沖突的同義詞元素(結點)用單鏈表鏈接起來的方法。例：假定一個線性表B為：B=(18,75,60,43,54,90,46,31,58,73,15,34)。設采用的散列函數(shù)為h(K)=K%13,采用鏈接法處理：在該例中，查找成功時平均查找長度為：ASL=(8132+13)/121.42若線性探查法處理沖突進行散列存儲，得到：查找成功時平均查找長度為：ASL=(7112+14+14+12+16)/122.13) 多種方法分析在散列表的插入和查找算法中，平均查找長度與表的大小m無關，只與選取的散列函數(shù)、值和處理沖突的方法有關,若假定所選取的散列函數(shù)能夠使任一關鍵字等概率地映射到散列空間的任一地址上，理論上證明：當采用線性探查法處理沖突時， ASL=當采用鏈地址法處理沖突時，ASL=當采用平方探查法、雙散列函數(shù)法處理沖突時，ASL=散列存儲優(yōu)缺點 插入與查找的速度相當快 根據(jù)關鍵字計算散列地址需要開銷一定計算時間 占用存儲空間較多 在散列表中只能按關鍵字查找元素 線性表中元素的邏輯關系無法在散列表中體現(xiàn)4散列表的運算設用HashMaxSize常量表示待定義的散列表類型的長度。假定采用開放定址法,其散列表類型用hashlist1表示,類型定義為：typedef ElemType hashlist1HashMaxSize;若采用鏈接表，其散列表類型用hashlist2表示，類型定義為：typedef LNode * hashlist2HashMaxSize;Lnode 定義如下：struct Lnode ElemType data;Lnode *next; 在類型為hashlist1的散列表上進行的運算類型定義：typedef ElemType hashlist1HashMaxSize;l 初始化散列表void InitHashList (hashlist1 HT)/把散列表HT中每一單元的關鍵字key域都置空for(int i=0;iHashMaxSize;i+)HTi.key=NullTag; /NullTag常量表示空標志，l 清空一個散列表void ClearHashList (hashlist1 HT)/把散列表HT中每一單元的關鍵字key域都置空for(int i=0;iHashMaxSize;i+)HTi.key=NullTag;l 向散列表中插入一個元素int Insert (hashlist1 HT,int m,ElemType item)/向長度為m的散列表HT中插入一個元素itemint d=H(item.key,m);int temp=d;while(HTd.key != NullTag)/當d單元不空時繼續(xù)向后查找空位置d=(d+1)%m;if(d=temp) return 0;HTd=item; /將新元素插入到下標為d的位置return 1; /返回1表示插入成功l 從散列表中查找一個元素int Search (hashlist1 HT,int m, ElemType item)/從長度為m的散列表HT中查找關鍵字為item.key的一個元素int d=H(item.key, m);int temp=d;while(HTd.key!=NullTag)/當散列地址中的關鍵字域不為空則循環(huán)if(HTd.key=item.key) return d; /查找成功則反回下標delse d=(d+1)%m;if(d=temp) return -1; /查找失敗反回-1return -1; l 從散列表中刪除一個元素int Delete (hashlist1 HT,int m, ElemType item)/從長度為m的散列表HT中刪除關鍵字為item.key的一個元素int d=H(item.key, m);int temp=d;while(HTd.key!=NullTag)if(HTd.key=item.key) HTd.key=DeleteTag;/DeleteTag常量為一刪除標記return 1;else d=(d+1)%m; /繼續(xù)向后探查if(d=temp) return 0;return 0; /刪除失敗返回0 在類型為hashlist2的散列表上進行的運算類型定義：struct Lnode ElemType data;Lnode *nex