華清遠(yuǎn)見數(shù)據(jù)結(jié)構(gòu)

1、嵌入式學(xué)院華淸遠(yuǎn)見旗下品牌華淸遠(yuǎn)見FARSIGHT嵌入式培訓(xùn)專涼查找嵌入式學(xué)院華清遠(yuǎn)見旗下品牌嵌入式學(xué)院華清遠(yuǎn)見旗下品牌喳找” （Searching）及“排序”（Sorting）是建立在數(shù)據(jù)結(jié)構(gòu)上的兩個(gè)重 要運(yùn)算。查找（或檢索）是在給定信息集上尋找特定信息元素的過(guò)程。據(jù)統(tǒng)計(jì), 一些計(jì)算機(jī)、特別是商用計(jì)算機(jī)，其CPU處理時(shí)間約25%75%花費(fèi)在查找 或排序上。所以對(duì)查找和排序問(wèn)題的處理，有時(shí)直接影響到計(jì)算機(jī)的工作 效率。一、概述待查找的數(shù)據(jù)單位（或數(shù)據(jù)元素）稱為記錄。記錄由若干數(shù)據(jù)項(xiàng)（或 屬性）組成，如學(xué)生記錄：學(xué)號(hào) 姓名性別年齡其中，“學(xué)號(hào)”、“姓名”、“性別”、“年齡”等都是記錄的數(shù) 據(jù)項(xiàng)。

2、若某個(gè)數(shù)據(jù)項(xiàng)的值能標(biāo)識(shí)（或識(shí)別）一個(gè)或一組記錄，稱其為關(guān)鍵字 （key）o若一個(gè)key能唯一標(biāo)識(shí)一個(gè)記錄，稱此key為主key。如“學(xué)號(hào)”的值 給定就唯一對(duì)應(yīng)一個(gè)學(xué)生，不可能多個(gè)學(xué)生的學(xué)號(hào)相同，故“學(xué)號(hào)”在學(xué) 生記錄里可作為主key。若一個(gè)key能標(biāo)識(shí)一組記錄，稱此key為次key。如 “年齡”值為20時(shí)，可能有若干同學(xué)的年齡為20歲，故“年齡”可作次key。 下面主要討論對(duì)主key的查找。1 查找定義設(shè)記錄表L=(R1 R2Rn),其中Rj(lSiSn)為記錄，對(duì)給定的某個(gè)值k, 在表L中確定key=k的記錄的過(guò)程，稱為查找。若表L中存在一個(gè)記錄 的key=k,記為Rj.key=k,則查找成

3、功，返回該記錄在表L中的序號(hào)i(或 尺的地址)，否則值找失敗)返回0(或空地址Null)o2查找方法查找方法很多，有順序查找、折半查找、分塊查找、樹表查找及Hash表查找等等。查找算法的優(yōu)劣將影響到計(jì)算機(jī)的使用效率，應(yīng)根據(jù)應(yīng)用 場(chǎng)合選擇相應(yīng)的查找算法。3平均查找長(zhǎng)度評(píng)價(jià)一個(gè)算法優(yōu)劣的量度，一是時(shí)間復(fù)雜度T(n), n為問(wèn)題的體積， 此時(shí)為表長(zhǎng)；二是空間復(fù)雜度D(n)；三是算法的結(jié)構(gòu)等其他特性。對(duì)查找算法，主要分析其T(n)o查找過(guò)程是key的比較過(guò)程，時(shí)間主 要耗費(fèi)在各記錄的key與給定k值的比較上。比較次數(shù)越多，算法效率越 差(即T(n)量級(jí)越高)，故用“比較次數(shù)”刻畫算法的T(n)o另外，

4、顯 然不能以查找某個(gè)記錄的時(shí)間來(lái)作為T(n), 一般以“平均查找長(zhǎng)度”來(lái) 衡量T(n)o平均查找長(zhǎng)度ASL (Average Search Length):對(duì)給定k,查找表L中 記錄比較次數(shù)的期望值(或平均值)，即： ASL=YPiCiP；為查找R；的概率。等概率情況下P-l/n； C；為查找R；時(shí)key的尿較次數(shù)(或查找次數(shù))。二、順序表的查找所謂順序表(Sequential Table), 存儲(chǔ)于一維數(shù)組空間，如圖所示。 鄰的。記錄&的類型描述如下： typedef struct keytype key; 記錄key/ 記錄其他項(xiàng)/ Retype;是將表中記錄(Ri R?RJ按其序

5、號(hào) 其特點(diǎn)是相鄰記錄的物理位置也是相其中，類型keytype是泛指，即keytype可以是int、float、char或其他的結(jié) 構(gòu)類型等等。為討論問(wèn)題方便，一般取key為整型。順序表類型描述如下：#define maxn 1024;表最大長(zhǎng)度/typedef struct Retype datamaxn; 順序表空間/ int len; 當(dāng)前表長(zhǎng)，表空時(shí)len=0/Jsqlist;若說(shuō)明：sqlist r,貝Li (r.datal, ,r.datar.len)為記錄表(RRn),Rikey知ckitaikey,data稱為監(jiān)視哨，為量法設(shè)計(jì)方便所設(shè)。1順序查找算法及分析順序查找(Sequen

6、tial Search)是最簡(jiǎn)單的一種查找方法。算法思路設(shè)給定值為k,在表(R R2 RJ中，從心開始，查找key二k的記錄。若 存在一個(gè)記錄 (l<i<n)的key%k,則查找成功，返回記錄序號(hào)i；否 則，查找失敗，返回0。算法描述int sqsearch(sqlist r,keytype k) 對(duì)表r順序查找的算法/ inti;r.data0.key=k; k存入監(jiān)視哨i=r.len; 取表長(zhǎng)while(r.datai .key!=k)i-； 順序查找return(i);算法用了一點(diǎn)技巧：先將k存入監(jiān)視哨，若對(duì)某個(gè)i(主0)有 r.datai.key=k,則查找成功，返回i；若

7、i從n遞減到1都無(wú)記錄的key為k, i再減1為0時(shí)，必有r.data.key=k,說(shuō)明查找失敗，返回i=0。一i嵌入式學(xué)院順序查找華;青遠(yuǎn)見旗下品牌算法分析設(shè)C(l<i<n)為查找第i記錄的key比較次數(shù)(或查找次數(shù))：若 Tdatankey=k,若 r.datan-l .key=k,C/2；若 r.datai.key=k,C=n-i+l ；若T.dataJkey=k, nC二 n4- I 所以，ASL二i + l) = ”/=!z=l2故ASL=O(n)o而查找失敗時(shí)，查找次數(shù)等于n+1,同樣為O(n)o對(duì)查找算法，若ASL-O(n),則效率是最低的，意味著查找某記錄幾 乎要掃

8、描整個(gè)表，當(dāng)表長(zhǎng)n很大時(shí)，會(huì)令人無(wú)法忍受。下面關(guān)于查找的 一些討論，大多都是圍繞降低算法的ASL量級(jí)而展開的。2折半查找算法及分析當(dāng)記錄的key按關(guān)系S或N有序時(shí)，即：一Rrkey<R9.key<<Rn.key (升序)川米用折半或一分法查找或 Rkey2R；keyN>R,key (降序)(氏Search)。嵌入式學(xué)I魚見誹僦1算法思路對(duì)給定值k,逐步確定待查記錄所在區(qū)間，每次將搜索 半），直到查找成功或失敗為止。設(shè)兩個(gè)指針（或游標(biāo)）low、high,分別指向當(dāng)前待查找表的上界（表頭）和 下界（表尾）。對(duì)于表（R R?R）初始時(shí)low=l> high=n,令：mi

9、d二 （low+higfi）/2指向當(dāng)前待查找表中間的那個(gè)記錄。下面舉例說(shuō)明折半查找的過(guò)程。例1設(shè)記錄表的key序列如下：0312182032556068808690100highhigh mid序號(hào)：123456789101112 （n=12）low. , , 1mid low 現(xiàn)查找k=20的記錄。rn記若20存在，一定落在“55”的左若20存在，一定落在“18”的右查找成功，返回mid=4。 mid二(1 +12) / 2J =6 o 因k<r.data6 .key=55,半?yún)^(qū)間(搜索空間折半)。令：high=mid-lo mid= |_(1 + 5) / 2=3o 因k>r

10、.data3.key= 18,半?yún)^(qū)間。令:low=mid+1 omid= |_(4 + 5) / 2=4。因k=r.data4 .key=20,折半查找A嵌入式學(xué)院華清遠(yuǎn)見旗下品牌折半查找| 0312182032556068808690100lowmid lowmid low序號(hào)：123456789101112 (n=12)再看查找失敗的情況，設(shè)要查找k=85的記錄。mid high high highmid midl(l + 12)/2=6。因k>r.data.key=55,若85存在，一定落在 “55”叫右半?yún)^(qū)間。令：low=mid+l o midW +12)/2今。因k>r.

11、data9.key=80,若85存在，一定落在 “80”旳右半1%問(wèn)c令:low=mid+1 o midL(10+12)/2=11。因k<r.datall.key=90,若85存在，一定落在 “90”的左半?yún)^(qū)間。令：high=mid-lo mid10+10)/2=10。因k<r.data10.key=86,若85存在，一定落在 “86”的左半?yún)^(qū)間。令：high=mid-lo此時(shí),下界low=10,而上界high=9,表 明搜索空間不存在，故查找失敗，返回0。算法描述int Binsearch(sqlist r,keytype k) 對(duì)有序表r折半查找的算法/ int low,hig

12、h,mid; low=l;high=r.len; 上下界初值/ while(low<=high) 表空間存在時(shí) mid=(low+high)/2; 求當(dāng)前mid/if (k=r.datamid.key) return(mid); 查找成功，返回mid/if (k<r.datamid.key) high=mid-1; /調(diào)整上界，向左部查找 else low=mid+l; 調(diào)整下界，向右部查找return(O); /low>high,查找失敗查找次數(shù)算法分析對(duì)例1中記錄表的查找過(guò)程不失一般性，設(shè)表長(zhǎng)n=2h-l, h=log2(n+1)o記錄數(shù)n恰為一棵h層的滿二 叉樹的結(jié)點(diǎn)數(shù)

13、。對(duì)照例1,得出表的判定樹及各記錄也直找幽如圖所 帚-查找次數(shù)1x2°2x2】3x22O O O O hx2h-i"1 hhASL二=一刃2山 令4 工八2口 二 12° + 20+322 + +(/z-l)2/,-24-/r2,?-1 Zi"“侍/=12S= 1.21 +2-22 +3-23 + (/ -1)2/7_1 +h-2hS=2S-S= /i2“ 一(2° + 2】+ 2? + +2心) = h-2h-(2h-I) = (n +1)log2(n + l)-n 故ASL= (n + l)log2 (n +1) - n) = log2 (

14、n + l)-ln too 時(shí)，ASL=0(log2(n+l),大大優(yōu)O(n)Q嵌入式學(xué)院華清遠(yuǎn)見旗下品牌3分塊查找算法及分析分塊查找(Blocking Search),又稱索引順序查找(Indexed Sequential Search),是順序查找方法的一種改進(jìn)，目的也是為了提高查找效率。1.分塊設(shè)記錄表長(zhǎng)為n,將表的n個(gè)記錄分成b二pz/訂個(gè)塊，每塊s個(gè)記錄(最后 一塊記錄數(shù)可口小干"豹R$ Rs+| - R2sRn)塊塊2塊b且表分塊有序，即第i (l<i<b-l)塊所有記錄的key小于第i+1塊中記錄的key, 但塊內(nèi)記錄可以無(wú)序。2.建立索引每塊對(duì)應(yīng)一索引項(xiàng):

15、其中kmax為該塊內(nèi)記錄的最大key； link為該塊第一記錄的序號(hào)(或指針)。分塊查找例2設(shè)表長(zhǎng)n=19,取s=5, b=19/5 = 4,分塊索引結(jié)構(gòu)匸 如圖所示。3算法思路 分塊索引查找分兩步進(jìn)行：(1) 由索引表確定待查找記錄所在的塊；(2) 在塊內(nèi)順序查找。如查找k二19的記錄，因19>18, 不會(huì)落在第1塊；又19<50,若 19存在，必在第2塊內(nèi)。取第2 塊起址(6),查找到key為19的記 錄號(hào)為9。查找失敗情況，一是給定k值 超出索引表范圍；二是若k落在 某塊內(nèi)，但該塊中無(wú)key二k的記 錄。181 150684111|108|i6bmax嗦引表)K"序

16、號(hào)/塊2，塊3丿塊4丿、丿、/K嵌入式學(xué)院 厶厶華清遠(yuǎn)見旗下品牌 序號(hào)R-keymi索引表是按照匕仆有序的，可 對(duì)其折半查找。而加內(nèi)按順序 方法查找。三、Hash表的查找1 Hash表的含義Hash表，又稱散列表、雜湊表。在前而討論的順序、折半、分塊查找和樹表的查找中，其ASL的量級(jí)在O(n)O(log2n)之間。不論ASL在哪個(gè)量級(jí),都與記錄長(zhǎng)度n有關(guān)。隨著n的擴(kuò)大,算法的效率會(huì)越來(lái)越低。ASL與n有關(guān)是因?yàn)橛涗浽诖鎯?chǔ)器中的存放是隨機(jī)的，或者說(shuō)記錄的key 與記錄的存放地址無(wú)關(guān)，因而查找只能建立在key的“比較”基礎(chǔ)上。理想的查找方法是：對(duì)給定的k,不經(jīng)任何比較便能獲取所需的記錄， 其查找的

17、時(shí)間復(fù)雜度為常數(shù)級(jí)O(C)。這就要求在建立記錄表的時(shí)候，確 定記錄的key與其存儲(chǔ)啤址之間的違系f,即使fey與記錄的存放地址H相 對(duì)應(yīng)：key H： 記錄或者說(shuō)，記錄按key存放。之后，當(dāng)要查找key二k的記錄時(shí)，通過(guò)關(guān)系f 就可得到相應(yīng)記錄的地址而獲取記錄，從而免去了key的比較過(guò)程。這 個(gè)關(guān)系f就是所1胃的Hash函數(shù)(或稱散列函數(shù)、雜湊函數(shù))，記為 H(key)o它實(shí)際上是一個(gè)地址映象函數(shù)，其自變量為記錄的key,函數(shù) 值為記錄的存儲(chǔ)地址(或稱Hash地址)。另外，不同的key可能得到同一個(gè)Hash地址,即當(dāng)keykey時(shí)，可能 有H(keyJ二H(key)此時(shí)稱key】和key?為同

18、義詞。這種現(xiàn)象稱為“沖突” 或“碰撞”，因?yàn)橐粋€(gè)數(shù)據(jù)單位只可存放一條記錄。嵌入式學(xué)院華清遠(yuǎn)見旗下品牌Hash 表一般，選取Hash函數(shù)只能做到使沖突盡可能少，卻不能完全避免。這 就要求在出現(xiàn)沖突之后，尋求適當(dāng)?shù)姆椒▉?lái)解決沖突記錄的存放問(wèn)題。例3設(shè)記錄的key集合為C語(yǔ)言的一些保留字，即k二case、char、float、for> int> while > struct > typedef> union > goto> viod> return > switch > if> break> continue> else,

19、構(gòu)造關(guān)于k的Hash表時(shí)，可按不同的方法選取 H(key) o(1)令H(key)=keyOa，其中key0為key的第一個(gè)字符。顯然這樣選取的Hash函數(shù)沖突現(xiàn)象頻繁。女口： H(float)=H(for)=fa'=5。 解決沖突的方法之一是為“for"尋求另一個(gè)有效位置。(2)令H2(key)=(key0+keyi-l-2*ta)/2o 其中keyi-l為key的最后一個(gè)字符。 如:H2(float)=(f+f2*'a')/2=12, H2(for)=(T+tr,-2*ta)/2=l 1,從而消除 了一些沖突的疫生，但仍無(wú)法完全避免，女口： H2(case

20、)=H2(continue)o 綜上所述，對(duì)Hash表的含義描述如下：根據(jù)選取的Hash函數(shù)H(key)和處理沖突的方法，將一組記錄(RR2RJ映象到記錄的存儲(chǔ)空間，所得到的記錄表稱為Hash痕，如圖:(R, R,H(key).(Hash 表)2 Hash函數(shù)的構(gòu)造方法關(guān)于Hash表的討論關(guān)鍵是兩個(gè)問(wèn)題，一是選取Hash函數(shù)的方法；二 是確定解決沖突的方法。選取(或構(gòu)造)Hash函數(shù)的方法很多，原則是盡可能將記錄均勻分布, 以減少?zèng)_突現(xiàn)象的發(fā)生。以下介紹幾種常用的構(gòu)造方法。1. 直接地址法此方法是取key的某個(gè)線性函數(shù)為Hash函數(shù)，即令:H(key)=a - key+b其中a、b為常數(shù)，此時(shí)

21、稱H(key)為直接Hash函數(shù)或自身函數(shù)。 例4設(shè)某地區(qū)1100歲的人口統(tǒng)計(jì)表如表：記錄%R2只25R100歲數(shù)1225100人數(shù)300025002000010給定的存儲(chǔ)空間為b+1b+100號(hào)單元(b為起始地址)，每個(gè)單元可以 存放一條記錄Ri(l<i<100)o取“歲數(shù)”為key,令：H(key)=key+b則按此函數(shù)構(gòu)造的Hash表如下圖所示：Hash函數(shù)的構(gòu)造H(key)歲數(shù)人數(shù)b+l1300022500 2520000 10010b+2b+25b+100當(dāng)Hash表構(gòu)造好后，如查找key二25歲 的人口，取H(25)=b+25，該地址單元便是 要查找的內(nèi)容。直接地址不是

22、壓縮映象， 即用直接地址法產(chǎn)生Hash函數(shù)時(shí)，要隸 key集與地址集的大小相等，所以不同的 key之間無(wú)沖突現(xiàn)象發(fā)生。用直接地址方 法選取Hash函數(shù)受到很大的限制，因?yàn)?key的取值范圍一般遠(yuǎn)大于表的地址空間。嵌入式學(xué)院華清遠(yuǎn)見旗下品牌klk2kJk5k6231586242346233796239886 2457862342962. 數(shù)字分析法例5設(shè)記錄數(shù)等于80,記錄的key為6位10進(jìn)制數(shù)，即key=(k1 & k3 k4 k5 k6)10,(1<1<6)=01112119o另設(shè)表長(zhǎng)為100,地址空間為0099,則可令：H(key)=k.k.%、$為key中的某兩位。

23、具體取哪兩位呢？要進(jìn)行具體的“分析”,原則 乩使這80個(gè)記錄能較均勻地分布。例如這80個(gè)記錄的key如表：其中，kp k°和1<6不可取, 否則沖突現(xiàn)象太嚴(yán)重；ks的 隨機(jī)性也不理想；而ks、k4 的隨機(jī)性較好，故取 H(key)= k3 k4 o 于是，在構(gòu) 造 Hash表時(shí)，key二23086 旳記錄被映象到“15"號(hào)單 元，key二242146的記錄被 映象到“23"號(hào)單元,依此 類推。此方法也受到限制。當(dāng)記錄動(dòng)態(tài)產(chǎn)生時(shí)，事先無(wú)法得到記錄表，因而 很難進(jìn)行“分析”。也可能存在這種情況:如記錄&Rio中,1<出的隨 卡I【兀、/“ v后,/

24、工 彳口 Uprivh 小土口 iw彳卄彳擊久佇?口riza、八加5彳耳Hash函數(shù)的構(gòu)造3. 平方取中法當(dāng)取key中某些位為Hash地址而不能使記錄均勻分布時(shí),根據(jù)數(shù)學(xué)原理， 取(key)?中的某些位可能會(huì)比較理想，所以平方取中法中，令：H(key)=伙心)即取(key)?中從左數(shù)第1位到第1+1位為選取的Hash函數(shù)，俱體多大，視給定 的存儲(chǔ)空間而定。例6設(shè)Hash表地址空間為000999。對(duì)一組隨機(jī)性不好的key,按平方取中 法選取的H(key)如I表所歹壯key(key)2H(key)010000 100 00100011000 121 00121101010 201 00201100

25、110 020 01020011100 123 21123令：H(key)=(key)23_5 , 1=3> r=2o (key)2的隨機(jī)性比key要好得多，從 而使沖突現(xiàn)象減少。Hash函數(shù)的構(gòu)造4.疊加法將key分割成位數(shù)相同的幾部分(最后一部分位數(shù)可以不同)，然后取 各部分的疊加值作為H(key)o該方法又分為“移位疊加”和“間界疊 加”，前者是將分割后的每部分低位對(duì)齊相加；后者是沿分割線來(lái)回折 疊、對(duì)齊相加。例7設(shè)圖書記錄：(ISBN,書名，作者，種類，出版日期)，其中ISBN為 圖書的國(guó)際標(biāo)準(zhǔn)編號(hào)，它是帶分隔符的10進(jìn)制數(shù)，取ISBN為key。當(dāng)圖書種類少于10000時(shí)，地址空

26、間取00009999,用疊加法構(gòu)造值為4 位的Hash函數(shù)。例如某圖書的ISBN=704005265-2,從低位起，每4位分 害9。7-0 I 4-005 I 265-2移位疊加：2652間界疊加：2652嵌入式學(xué)院華清遠(yuǎn)見旗下品牌50044005+ 70+ 7067277726移位疊加時(shí)，H(7-04-005265-2)=6727,亦即該書對(duì)應(yīng)的記錄映象到表的6727號(hào)單元；用間界疊加時(shí)，該書被映象到7726號(hào)單元。Hash函數(shù)的構(gòu)造A嵌入式學(xué)院華清遠(yuǎn)見旗下品牌5.保留除數(shù)法又稱質(zhì)數(shù)除余法，設(shè)Hash表空間長(zhǎng)度為m,選取一個(gè)不大于m的最大質(zhì)數(shù)p,令:H(key)=key % p例如:m=8

27、16 32 64 128 256 512 1024 p=7 13 31 61 127 251 503 1019 為何選取p為不大于m的最大質(zhì)數(shù)呢？舉例說(shuō)明。例8設(shè)記錄的key集合k二28, 35, 63, 77, 105,若選取p=21=3*7 (包括質(zhì) 數(shù)因子7),有：key： 28 35 63 77 105 H(key)=key%21： 7 14 0 14 0使得包含質(zhì)數(shù)因子7的key都可能被映象到相同的單元，沖突現(xiàn)象嚴(yán)重。若取 p=19 (質(zhì)數(shù))，同樣對(duì)上面給定的key集合k,有：key： 28 35 63 77 105H(key)=key%19： 9 16 6110H(key)的隨機(jī)度

28、就好多了。6.隨機(jī)函數(shù)法編程語(yǔ)言中一般都提供一些隨機(jī)函數(shù)，令:H(key)=Cxrandom(key)其中random(key)為相應(yīng)于key的一個(gè)隨機(jī)函數(shù)；C為常數(shù),選取相應(yīng)的C 值使得H(key)符合Hash地址的要求。當(dāng)key長(zhǎng)度不一時(shí)，用此方法選取 Hash函數(shù)是合適的。以上介紹了選取Hash函數(shù)的6種方法。從中看出，選取Hash函數(shù)要考 慮的因素為：(1) key的長(zhǎng)度、類型以及分布的情況；(2) 給定的Hash表表長(zhǎng)m；(3) 記錄的查找效率等。通常是幾種方法結(jié)合使用，目的是使記錄更好地均勻分布，減少?zèng)_突的發(fā) 生。嵌入式學(xué)院華清遠(yuǎn)見旗下品牌3處理沖突的方法選取隨機(jī)度好的Hash函數(shù)

29、可使沖突減少，一般來(lái)講不能完全避免沖突。 因此，如何處理沖突是Hash表不可缺少的另一方面。設(shè)Hash表地址空間為0mJ (表長(zhǎng)為m):J+1m-1H(key):0沖突是指：表中某地址jWO, m-l中己存放有記錄，而另一個(gè)記錄的 H(key)值也為j。處理沖突的方法一般為：在地址j的前面或后面找一個(gè) 空閑單元存放沖突的記錄，或?qū)⑾鄾_突的諸記錄拉成鏈表等等。在處理沖突的過(guò)程中，可能發(fā)生一連串的沖突現(xiàn)象，即可能得到一個(gè) 地址序列H、H2Hn, H冃0, m-lo H是沖突時(shí)選取的下一地址, 而比中可能己有記錄，又設(shè)法得到下一地址比直到某個(gè)也不發(fā)生 沖突為止。這種現(xiàn)象稱為“聚積”，它嚴(yán)重影響了Ha

30、sh表的查找效率。沖突現(xiàn)象的發(fā)生有時(shí)并不完全是由于Hash函數(shù)的隨機(jī)性不好引起的, 聚積的發(fā)生也會(huì)加重沖突。還有一個(gè)因素是表的裝填因子 a=n/m, 其中m為表長(zhǎng)，n為表中記錄個(gè)數(shù)。一般a在0.708之間，使表保持一 定的空閑余量，以減少?zèng)_突和聚積現(xiàn)象。處理沖突的方法1. 開放地址法當(dāng)發(fā)生沖突時(shí)，在H(key)的前后找一個(gè)空閑單元來(lái)存放沖突的記 錄, 即在H(key)的基礎(chǔ)上獲取下一地址：Hi=(H(key)+di)%m其中m為表長(zhǎng)，運(yùn)算是保證耳落在0, mJ區(qū)間；4為地址增量。4的 取法有多種：(1) 4=1, 2, 3,.(m-1)稱為線性探查法;(2) 4=12, J2, 22, -22

31、, 稱為二次探查法。式(1)、(2)表示：第1次發(fā)生沖突時(shí)，地址增量4取1或12；再?zèng)_突時(shí)， 取2或-卩，,依此類推。例9 設(shè)記錄的key集合k二23, 34, 14, 38, 46, 16, 68, 15, 07, 31, 26, 記錄數(shù)n=ll。令裝填因子a=0.75,取表長(zhǎng)m=n/a =15。用“保留余數(shù) 法”選取Hash函數(shù)(p=13):H(key)=key%13采用“線性探查法”解決沖突。依據(jù)以上條件，依次取k中各值構(gòu)造的 Hash表HT,如下圖所示(表HT初始為空)。，亠，力嵌入式學(xué)院處理沖突的方法么Z華漬遠(yuǎn)見旗下品牌k二23, 34, 14, 38, 46, 16,(68)15,

32、 31, 26(m-悶冋77()7 23 mi 38 .H(key)=key%13; H.=(H(key)+d.)%15; di=l, 2, 3,1)HT:H(key) 01234567891011121314H（68）=68% 13=3（沖突），取H嚴(yán)（3+l）%15二4（空）,故68存入4單元。H（07>7% 13=7（沖突），取匕=（7+1）%15 二 8（沖突），取比二（7+2）%15 二9（空），故 07存入9單元。若釆用二次探測(cè)法:4",22, -22,表為:HT:H(key) 01234567891011121314其中，H（07）=7%13=7（沖突），取H尸（

33、7+卩）15=8（沖突），取 H2=（7-l2）% 15=6（空），故07存入6單元。嵌入式學(xué)院華清遠(yuǎn)見旗下品牌處理沖突的方法2.鏈地址法發(fā)生沖突時(shí)，將各沖突記錄鏈在一起,即同義詞的記錄存于同一鏈表。設(shè)H(key)取值范圍(值域)(0<i<m-l)初值為空。凡為0, m-1,建立頭指針向量HPm, HPi t(kev)=i的記錄都鏈入頭指針為HP的鏈表。例 10 設(shè) H(key)=key%13,其值域?yàn)?,12,建立指針向量HP12O對(duì)例9中:k= 23, 34, 14, 38, 46,16, 68, 15, 07, 31, 26依次取其中各值，用鏈地址法 解決沖突時(shí)的Hash表如

34、圖：ey) HPo 鏈地址法解決沖突的優(yōu)點(diǎn)： 無(wú)聚積現(xiàn)象；刪除表中記錄容 易實(shí)現(xiàn)。而開放地址法的Hash 表作刪除時(shí)，不能將記錄所在 單元置空，只能作刪除標(biāo)記。2345678910111226A 114A15A16> 68A07434A> 3146 A23A38A/K嵌入式學(xué)院厶厶華清遠(yuǎn)見旗下品牌4 Hash表的查找及分析Hash表的查找特點(diǎn)是：怎么構(gòu)造的表就怎么查找，即造表與查找過(guò)程統(tǒng)O算法思路：對(duì)給定k,根據(jù)造表時(shí)選取的H(key)求H(k)。若H(k)單元" 則查找失敗，否則k與該單元存放的key比較，若相等，則查找成功；若 不等，則根據(jù)設(shè)定的處理沖突方法，找下一地

35、址耳，直到查找到或等于 空為止。1.線性探查法解決沖突時(shí)Hash表的查找及插入#define m 64 設(shè)定表長(zhǎng)mtypedef struct keytype key; 記錄關(guān)鍵字/JHretype;Hretype HTm; /Hash表存儲(chǔ)空間int Lhashsearch(Hretype HTm,keytype k) 線性探杳法解決沖突時(shí)的查找 intj,d,i=O;j=d=H(k); 求Hash地址并賦給j和dwhile(i<m)&&(HTj.key!二 NULL)&&(HTj.key!=k) i+; j=(d+i)%m; 沖突時(shí)形成下一地址if(i

36、=m) return(-l); 表溢出時(shí)返回1else return(j); /HTj.key=k,查找成功;HTjkey二二NULL,查找失敗/Hash表的查找及分析void LHinsert(Hretype HTm, Hretype R) 記錄R插入Hash表的算法 intj=LHashsearch(HT,R.key); 查找R,確定其位置if(j= = -l)ll(HTj.key=R.key) ERROR(); 表溢出或記錄已存/ else HTj=R;插入HTj單元2. 鏈地址法解決沖突時(shí)Hash表的查找及插入typedef struct node 記錄對(duì)應(yīng)結(jié)點(diǎn) keytype key

37、;struct node *next; Renode;Renode *LinkHsearch(Renodekey type k) /鏈地址法解決沖突時(shí)的查找/Renode *p;int d=H(k); 求Hash地址dp=HTd; 取鏈表頭結(jié)點(diǎn)指針/while(p&&(p->key!=k)p=p->next; 沖突時(shí)取下一同義詞結(jié)點(diǎn)/return(p);查找成功時(shí)p->key=k,否則p=A/Hash表的查找及分析void LinkHinsert(Renode *HTm, Renode紹)將指針S所指記錄插入表HT的算法(如圖所示) int d;Renode

38、*p;p=LinkHsearch(HT,S->key); 查找S結(jié)點(diǎn) if(p) ERROR(); 記錄已存在/elsed=H(S->key); S->next=HTd; HTd=S;插入圖示:/K嵌入式學(xué)院厶厶華清遠(yuǎn)見旗下品牌/K嵌入式學(xué)院厶厶華清遠(yuǎn)見旗下品牌圖 6.37嵌入式學(xué)院華淸遠(yuǎn)見旗下品牌華淸遠(yuǎn)見FARSIGHT嵌入式培訓(xùn)專涼排序嵌入式學(xué)院華淸遠(yuǎn)見旗下品牌、概述排序（Sort）是將無(wú)序的記錄序列（或稱文件）調(diào)整成有序的 序列。對(duì)文件（File）進(jìn)行排序有重要的意義。如羋文件按灶丫力 序，可對(duì)其折半查找，使查找效率提高；在數(shù)拯庫(kù)（DataBase）和知識(shí)庫(kù)（Knowl

39、edge Base）等系統(tǒng)中，一般要建立若 J索引文件，就牽涉到排序問(wèn)題；在一些計(jì)算機(jī)的應(yīng)用系統(tǒng) 馳詈弐f同毆警據(jù)段作出若干統(tǒng)計(jì)，也涉及到排序。a 效率的咼低，直接影響到計(jì)算機(jī)的工作效率。1排序定義/h嵌入式學(xué)監(jiān)華清遠(yuǎn)見旗下品牌 設(shè)含有n個(gè)記錄的文件f=（R, R2Rn）,相應(yīng)記錄關(guān)鍵字（key）集合 k=kj k2kno 若對(duì) 1、2n的一種*|乍列：PP（2）P（n）（1空（戶，詢時(shí)，P（臚P）有：kp<kp（2） <<kP（n）遞增關(guān)系或kp>kp（2） >>kp（n） 遞減關(guān)系則使f按key線性有序：（Rp（）Rp（2）Rp（n）,稱這種運(yùn)算為排序（

40、或分類）。關(guān)系符或并不一定是數(shù)學(xué)意義上的“小于等于”或“大于等 于”，而是一種次序關(guān)系。但為討論問(wèn)題方便，取整型數(shù)作為key,故 或可看作通常意義上的符號(hào)。2.穩(wěn)定排序和非穩(wěn)定排序設(shè)文件f二（R尺氣Rn）中記錄&、片（i力，i、j=ln）的key相等，即K尸Kj。若在排序前領(lǐng)先于排序后仍領(lǐng)先于則稱 這種排序是穩(wěn)定的，其含義是它沒(méi)有破壞原本已有序的次序。反之，若排 序后與笛的次序有可能顛倒，則這種排序是非穩(wěn)定的，即它有可能破壞 了原本已有序記錄的次序。嵌入式學(xué)院華清遠(yuǎn)見旗下品牌3內(nèi)排序和外排序若待排文件f在計(jì)算機(jī)的內(nèi)存儲(chǔ)器中，且排序過(guò)程也在內(nèi)存中進(jìn)行，稱 這種排序?yàn)閮?nèi)排序。內(nèi)排序速度快，

41、但由于內(nèi)存容量一般很小，文件的長(zhǎng) 度（記隸個(gè)藪）n受到一定限制。若排序申的文件存入外吞儲(chǔ)器，排序過(guò)程借助于內(nèi)外存數(shù)據(jù)交換（或歸并）來(lái)完成，則稱這種排序?yàn)橥馀判?。?們重點(diǎn)討論內(nèi)排序的一些方法、算法以及時(shí)間復(fù)雜度的分析。4內(nèi)排序方法截止目前，各種內(nèi)排序方法可歸納為以下五類：（1）插入排序；（2）交換排序；（3）選擇排序；（4）歸并排序；（5）基數(shù)排序。5文件存儲(chǔ)結(jié)構(gòu)（1）順序結(jié)構(gòu)類似線性表的順序存儲(chǔ)，將文件f二（R| R2Rn）存于一片連續(xù)的存儲(chǔ)空 間，邏輯上相鄰的記錄在存儲(chǔ)器中的物理位置也是相鄰的，如圖：Rir2在這種結(jié)構(gòu)上對(duì)文件排序，一般要作記錄的移動(dòng)。當(dāng)發(fā)生成片記錄移動(dòng) 時(shí)，是一個(gè)很耗時(shí)的

42、工作。（2）鏈表結(jié)構(gòu)理嵌入式學(xué)監(jiān)華清遠(yuǎn)見旗下品牌 類似于線性表的鏈?zhǔn)酱鎯?chǔ)，文件中記錄用結(jié)點(diǎn)來(lái)表示，其物理位置任 意，結(jié)點(diǎn)之間用指針相連，如圖：RiRnL鏈表結(jié)構(gòu)的優(yōu)點(diǎn)在于排序時(shí)無(wú)須移動(dòng)記錄，只需修改相應(yīng)記錄的指針即可。（3）地址映象結(jié)構(gòu)該結(jié)構(gòu)是另設(shè)一地址向量，存儲(chǔ)文件中各記錄的地址（或序號(hào)），如圖：（地址向量）（地址向量）排序可在地址向量上進(jìn)行，一定程度上 免去了排序時(shí)記錄的移動(dòng)。排序可在地址向量上進(jìn)行，一定程度上免去了排序時(shí)記錄的移動(dòng)。（數(shù)據(jù)文件）二、插入排序理嵌入式學(xué)監(jiān)華清遠(yuǎn)見旗下品牌插入排序（Insert Sort）可分為：直接插入排序、折半插入排序、鏈表 插入排序以及Shell （希爾

43、）排序等。每種排序按照排序方法、舉例說(shuō)明、 算法描述以及算法分析等幾個(gè)步驟討論。1直接插入排序設(shè)待排文件f=（R R2Rn）相應(yīng)的key集合為k=k k2kJ,文件f 對(duì)應(yīng)的結(jié)構(gòu)可以是前面所述的三種文件結(jié)構(gòu)之一。1.排序方法先將文件中的（R）看成只含一個(gè)記錄的有序子文件，然后從R?起，逐 個(gè)將R?至&按key插入到當(dāng)前有序子文件中，最后得到一個(gè)有序的文件。 插入的過(guò)程上是一個(gè)key的比較過(guò)程，即每插入一個(gè)記錄時(shí),將其key與當(dāng) 前有序子表中的key進(jìn)行比較，找到待插入記錄的位置后，將其插入即可。 另外，假定排序后的文件按遞增次序排列（以下同）。例1設(shè)文件記錄的key集合k二50, 36

44、, 66, 76, 95, 12, 25, 36（考慮到對(duì) 記錄次key排序的情況，允許多個(gè)key相同。如此例中有2個(gè)key為36,后一 個(gè)表示成翌，以示區(qū)別），按直接插入排序方法對(duì)k的排序過(guò)程如下：直接插入排序k=50, 36, 66, 76, 95, 12, 25, 3636，50 6636，50，66 7636, 50, 66, 76 9512, 36，50，66, 76，95 25 12, 25, 12, 25，36，36, 50，66, 76，95 一般，插入kj (2<i<n),當(dāng)出企vk計(jì)匕“時(shí)，先將子表氏十kJ從起順序向后移動(dòng)一個(gè)記錄位置，然后插入到第j+1位置，即

45、：文件結(jié)構(gòu)說(shuō)明：#define maxsize 1024 文件最大長(zhǎng)度 typedef int keytype; / 設(shè)key為整型 typedef struct / 記錄類型 key type key; 記錄關(guān)鍵字記錄其它域 Retype;typedefstruct 文件或表的類型 Retype Rmaxsize+1; 文件存儲(chǔ)空間 int len; /當(dāng)前記錄數(shù)Jsqfile;若說(shuō)明sqfileF；則:(F.R1, F.R2F.RF.len)為待排文件，它是 一種順序結(jié)構(gòu)；文件長(zhǎng)度n=F.len； F.R0為工作單元，起到“監(jiān)視哨”作 用；記錄的關(guān)鍵字寫作F.Ri.keyo厶厶華潰遠(yuǎn)見旗下

46、品牌2 算法描述void Insort (sqfile F) 對(duì)順序文件F直接插入排序的算法 int i,j;for (i=2;i<=F.len;i+) 插入nl 個(gè)記錄 F.R0=F.Ri; 待插入記錄先存于監(jiān)視哨while (F.RO.key<F.Rj.key) #key th較 F.Rj+1=F.Rj; 記錄順序后移j；F.Rj+l=F.R0; 原Ri插入j+1 位置排序的時(shí)間復(fù)雜度取耗時(shí)最高的量級(jí)，故直接插入排序的T(n)=O(n2)o折半插入排序A嵌入式學(xué)院華清遠(yuǎn)見旗下品牌排序算法的T(n)=O(n2),是內(nèi)排序時(shí)耗最高的時(shí)間復(fù)雜度。隨著文件記錄 數(shù)n的增大，效率降低較快

47、。下面的一些插入排序的方法，都是圍繞著改 善算法的時(shí)間復(fù)雜度而展開的。另外，直接插入排序是穩(wěn)定排序。為減少插入排序過(guò)程中key的比較次數(shù)，可采用折半插入排序。1 排序方法同直接插入排序，先將(Rl)看成一個(gè)子文件，然后依次插入R2Rno但在插入Ri時(shí)，子表RlRi-1已是有序的，查找 Ri在子表中的位置可按折半查找方法進(jìn)行，從而降低key的比較次數(shù)。例2設(shè)當(dāng)前子表key序列及插入的=28如下:序號(hào)：12345甲low 令：20 評(píng) 3A 35lowhighhigh40 28highmid = (low+high)/228>R3.key=25, low二3+1=4； 28<R5.ke

48、y=35 , high二5 - 1=4； 28<R4.key=30, high=4-l=3o 此時(shí),low>high,所以“28”應(yīng) 插在low二4所指示的位置。2 算法描述void Binsort (sqfile F)對(duì)文件F折半插入排序的算法 int ij Jow,high,mid;for (i=2;i<=F.len;i+) / 插入n 1 個(gè)記錄 F.R0=F.Ri; 待插入記錄存入監(jiān)視哨low= 1; high=i-1;while (low<=high) / 查找Ri的位置 mid=(low+high)/2;if (F.RO.key>=F.Rmid.key

49、) low=mid+l; 調(diào)整下界 else high=mid-1; 調(diào)整上界for (j=i-l;j>=low;j-)F.Rj+l=F.Rj; 記錄順移F.Rlow=F.R0; 原 Ri插入 low 位置嵌入式學(xué)院華清遠(yuǎn)見旗下品牌折半插入排序3 算法分析插入Ri (2<i<n)時(shí)，子表記錄數(shù)為i1。同折半查找算法的討論，查找 Ri的key比較次數(shù)為 O(log2 /,)故總的key比較次數(shù)C為：nC = ylog2 z < (n -1)log2 n = 0(nlog2 n)i=2顯然優(yōu)于0(/)。但折半插入排序的記錄移動(dòng)次數(shù)并未減少，仍為0(/)。 故算法的時(shí)間復(fù)雜度

50、T(n)仍為0(112)。3鏈表插入排序設(shè)待排序文件f二魚衛(wèi)2Rn)，對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)為單鏈表結(jié)構(gòu)，如圖:1 排序方法鏈表插入排序?qū)嶋H上是一個(gè)對(duì)鏈表遍歷的過(guò)程。先將表置為空表，然后 依次掃描鏈表中每個(gè)結(jié)點(diǎn)，設(shè)其指針為p,搜索到p結(jié)點(diǎn)在當(dāng)前子表的適當(dāng) 位置，將其插入。鏈表插入排序/h嵌入逍學(xué)監(jiān)華清遠(yuǎn)見旗下品牌例3設(shè)含4個(gè)記錄的鏈表如圖：鏈表插入排序/h嵌入逍學(xué)監(jiān)華清遠(yuǎn)見旗下品牌例3設(shè)含4個(gè)記錄的鏈表如圖：50366612A初始化:插入36 :T 4 3650 | 八 | EI 6612 八3650A6612A插入66 :2算法描述typedef struct node 存放記錄的結(jié)點(diǎn) keytyp

51、e key; /記錄關(guān)鍵字 記錄其它域struct node *next; / 鏈指針Lnode,*linklist;void Linsertsort (linklist L) / 鏈表插入排序算法 linklist p,q,r,u;p=L->next;p為待插入結(jié)點(diǎn)指針L->next=NULL; 置子表為空while(p) 若待排序結(jié)點(diǎn)存在P r=L; q=L->next; r為q的前驅(qū)指針while (q&&q->key<=p->key) /找p結(jié)點(diǎn)位置 r=q; q=q->next; u=p->next;p->next=q; r->next=p; 插入p=u;/K嵌入式學(xué)院 厶厶華清遠(yuǎn)見旗下品牌4 Shell排序Shell （希爾）排序又稱“縮小增量”排序,1959年由D.L.Shell提出。希 爾發(fā)現(xiàn)：直接插入排序中，key比較次數(shù)及記錄移動(dòng)次數(shù)會(huì)比較大，若將 待排序文件按某種次序分隔成若干個(gè)子文件，對(duì)各子文件“跳躍”式的排 序，然后調(diào)整子文件個(gè)數(shù)，逐步對(duì)原文件排序，這樣總的key比較次數(shù)蕪 其是記錄移動(dòng)次數(shù)也許會(huì)大大降低。Shell排序方法設(shè)待排文件匸（RR2Rn），先將f中相隔增量d （如令d=n/2）的記錄 組成一個(gè)個(gè)子文件，對(duì)各子文件插入排序；然后縮小增量d （如令d=d/2）,