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

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

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

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

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

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

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

7、i從n遞減到1都無記錄的key為k, i再減1為0時，必有r.data.key=k,說明查找失敗，返回i=0。一i嵌入式學院順序查找華;青遠見旗下品牌算法分析設(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ù)等于n+1,同樣為O(n)o對查找算法，若ASL-O(n),則效率是最低的，意味著查找某記錄幾 乎要掃

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

9、d二 （low+higfi）/2指向當前待查找表中間的那個記錄。下面舉例說明折半查找的過程。例1設(shè)記錄表的key序列如下：0312182032556068808690100highhigh mid序號：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嵌入式學院華清遠見旗下品牌折半查找| 0312182032556068808690100lowmid lowmid low序號：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%問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此時,下界low=10,而上界high=9,表 明搜索空間不存在，故查找失敗，返回0。算法描述int Binsearch(sqlist r,keytype k) 對有序表r折半查找的算法/ int low,hig

12、h,mid; low=l;high=r.len; 上下界初值/ while(low<=high) 表空間存在時 mid=(low+high)/2; 求當前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ù)算法分析對例1中記錄表的查找過程不失一般性，設(shè)表長n=2h-l, h=log2(n+1)o記錄數(shù)n恰為一棵h層的滿二 叉樹的結(jié)點數(shù)

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

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

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

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

18、義詞。這種現(xiàn)象稱為“沖突” 或“碰撞”，因為一個數(shù)據(jù)單位只可存放一條記錄。嵌入式學院華清遠見旗下品牌Hash 表一般，選取Hash函數(shù)只能做到使沖突盡可能少，卻不能完全避免。這 就要求在出現(xiàn)沖突之后，尋求適當?shù)姆椒▉斫鉀Q沖突記錄的存放問題。例3設(shè)記錄的key集合為C語言的一些保留字，即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表時，可按不同的方法選取 H(key) o(1)令H(key)=keyOa，其中key0為key的第一個字符。顯然這樣選取的Hash函數(shù)沖突現(xiàn)象頻繁。女口： H(float)=H(for)=fa'=5。 解決沖突的方法之一是為“for"尋求另一個有效位置。(2)令H2(key)=(key0+keyi-l-2*ta)/2o 其中keyi-l為key的最后一個字符。 如:H2(float)=(f+f2*'a')/2=12, H2(for)=(T+tr,-2*ta)/2=l 1,從而消除 了一些沖突的疫生，但仍無法完全避免，女口： H2(case

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

21、稱H(key)為直接Hash函數(shù)或自身函數(shù)。 例4設(shè)某地區(qū)1100歲的人口統(tǒng)計表如表：記錄%R2只25R100歲數(shù)1225100人數(shù)300025002000010給定的存儲空間為b+1b+100號單元(b為起始地址)，每個單元可以 存放一條記錄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當Hash表構(gòu)造好后，如查找key二25歲 的人口，取H(25)=b+25，該地址單元便是 要查找的內(nèi)容。直接地址不是

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

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

24、工 彳口 Uprivh 小土口 iw彳卄彳擊久佇?口riza、八加5彳耳Hash函數(shù)的構(gòu)造3. 平方取中法當取key中某些位為Hash地址而不能使記錄均勻分布時,根據(jù)數(shù)學原理， 取(key)?中的某些位可能會比較理想，所以平方取中法中，令：H(key)=伙心)即取(key)?中從左數(shù)第1位到第1+1位為選取的Hash函數(shù)，俱體多大，視給定 的存儲空間而定。例6設(shè)Hash表地址空間為000999。對一組隨機性不好的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的隨機性比key要好得多，從 而使沖突現(xiàn)象減少。Hash函數(shù)的構(gòu)造4.疊加法將key分割成位數(shù)相同的幾部分(最后一部分位數(shù)可以不同)，然后取 各部分的疊加值作為H(key)o該方法又分為“移位疊加”和“間界疊 加”，前者是將分割后的每部分低位對齊相加；后者是沿分割線來回折 疊、對齊相加。例7設(shè)圖書記錄：(ISBN,書名，作者，種類，出版日期)，其中ISBN為 圖書的國際標準編號，它是帶分隔符的10進制數(shù)，取ISBN為key。當圖書種類少于10000時，地址空

26、間取00009999,用疊加法構(gòu)造值為4 位的Hash函數(shù)。例如某圖書的ISBN=704005265-2,從低位起，每4位分 害9。7-0 I 4-005 I 265-2移位疊加：2652間界疊加：2652嵌入式學院華清遠見旗下品牌50044005+ 70+ 7067277726移位疊加時，H(7-04-005265-2)=6727,亦即該書對應(yīng)的記錄映象到表的6727號單元；用間界疊加時，該書被映象到7726號單元。Hash函數(shù)的構(gòu)造A嵌入式學院華清遠見旗下品牌5.保留除數(shù)法又稱質(zhì)數(shù)除余法，設(shè)Hash表空間長度為m,選取一個不大于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ù)呢？舉例說明。例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)象嚴重。若取 p=19 (質(zhì)數(shù))，同樣對上面給定的key集合k,有：key： 28 35 63 77 105H(key)=key%19： 9 16 6110H(key)的隨機度

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

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

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

31、, 稱為二次探查法。式(1)、(2)表示：第1次發(fā)生沖突時，地址增量4取1或12；再沖突時， 取2或-卩，,依此類推。例9 設(shè)記錄的key集合k二23, 34, 14, 38, 46, 16, 68, 15, 07, 31, 26, 記錄數(shù)n=ll。令裝填因子a=0.75,取表長m=n/a =15。用“保留余數(shù) 法”選取Hash函數(shù)(p=13):H(key)=key%13采用“線性探查法”解決沖突。依據(jù)以上條件，依次取k中各值構(gòu)造的 Hash表HT,如下圖所示(表HT初始為空)。，亠，力嵌入式學院處理沖突的方法么Z華漬遠見旗下品牌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嚴（3+l）%15二4（空）,故68存入4單元。H（07>7% 13=7（沖突），取匕=（7+1）%15 二 8（沖突），取比二（7+2）%15 二9（空），故 07存入9單元。若釆用二次探測法:4",22, -22,表為:HT:H(key) 01234567891011121314其中，H（07）=7%13=7（沖突），取H尸（

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

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

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

36、=m) return(-l); 表溢出時返回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. 鏈地址法解決沖突時Hash表的查找及插入typedef struct node 記錄對應(yīng)結(jié)點 keytype key

37、;struct node *next; Renode;Renode *LinkHsearch(Renodekey type k) /鏈地址法解決沖突時的查找/Renode *p;int d=H(k); 求Hash地址dp=HTd; 取鏈表頭結(jié)點指針/while(p&&(p->key!=k)p=p->next; 沖突時取下一同義詞結(jié)點/return(p);查找成功時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é)點 if(p) ERROR(); 記錄已存在/elsed=H(S->key); S->next=HTd; HTd=S;插入圖示:/K嵌入式學院厶厶華清遠見旗下品牌/K嵌入式學院厶厶華清遠見旗下品牌圖 6.37嵌入式學院華淸遠見旗下品牌華淸遠見FARSIGHT嵌入式培訓專涼排序嵌入式學院華淸遠見旗下品牌、概述排序（Sort）是將無序的記錄序列（或稱文件）調(diào)整成有序的 序列。對文件（File）進行排序有重要的意義。如羋文件按灶丫力 序，可對其折半查找，使查找效率提高；在數(shù)拯庫（DataBase）和知識庫（Knowl

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

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

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

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

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

44、, 66, 76, 95, 12, 25, 36（考慮到對 記錄次key排序的情況，允許多個key相同。如此例中有2個key為36,后一 個表示成翌，以示區(qū)別），按直接插入排序方法對k的排序過程如下：直接插入排序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),當出企vk計匕“時，先將子表氏十kJ從起順序向后移動一個記錄位置，然后插入到第j+1位置，即

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

46、品牌2 算法描述void Insort (sqfile F) 對順序文件F直接插入排序的算法 int i,j;for (i=2;i<=F.len;i+) 插入nl 個記錄 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 位置排序的時間復雜度取耗時最高的量級，故直接插入排序的T(n)=O(n2)o折半插入排序A嵌入式學院華清遠見旗下品牌排序算法的T(n)=O(n2),是內(nèi)排序時耗最高的時間復雜度。隨著文件記錄 數(shù)n的增大，效率降低較快

47、。下面的一些插入排序的方法，都是圍繞著改 善算法的時間復雜度而展開的。另外，直接插入排序是穩(wěn)定排序。為減少插入排序過程中key的比較次數(shù)，可采用折半插入排序。1 排序方法同直接插入排序，先將(Rl)看成一個子文件，然后依次插入R2Rno但在插入Ri時，子表RlRi-1已是有序的，查找 Ri在子表中的位置可按折半查找方法進行，從而降低key的比較次數(shù)。例2設(shè)當前子表key序列及插入的=28如下:序號：12345甲low 令：20 評 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 此時,low>high,所以“28”應(yīng) 插在low二4所指示的位置。2 算法描述void Binsort (sqfile F)對文件F折半插入排序的算法 int ij Jow,high,mid;for (i=2;i<=F.len;i+) / 插入n 1 個記錄 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 位置嵌入式學院華清遠見旗下品牌折半插入排序3 算法分析插入Ri (2<i<n)時，子表記錄數(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(/)。但折半插入排序的記錄移動次數(shù)并未減少，仍為0(/)。 故算法的時間復雜度

50、T(n)仍為0(112)。3鏈表插入排序設(shè)待排序文件f二魚衛(wèi)2Rn)，對應(yīng)的存儲結(jié)構(gòu)為單鏈表結(jié)構(gòu)，如圖:1 排序方法鏈表插入排序?qū)嶋H上是一個對鏈表遍歷的過程。先將表置為空表，然后 依次掃描鏈表中每個結(jié)點，設(shè)其指針為p,搜索到p結(jié)點在當前子表的適當 位置，將其插入。鏈表插入排序/h嵌入逍學監(jiān)華清遠見旗下品牌例3設(shè)含4個記錄的鏈表如圖：鏈表插入排序/h嵌入逍學監(jiān)華清遠見旗下品牌例3設(shè)含4個記錄的鏈表如圖：50366612A初始化:插入36 :T 4 3650 | 八 | EI 6612 八3650A6612A插入66 :2算法描述typedef struct node 存放記錄的結(jié)點 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é)點指針L->next=NULL; 置子表為空while(p) 若待排序結(jié)點存在P r=L; q=L->next; r為q的前驅(qū)指針while (q&&q->key<=p->key) /找p結(jié)點位置 r=q; q=q->next; u=p->next;p->next=q; r->next=p; 插入p=u;/K嵌入式學院 厶厶華清遠見旗下品牌4 Shell排序Shell （希爾）排序又稱“縮小增量”排序,1959年由D.L.Shell提出。希 爾發(fā)現(xiàn)：直接插入排序中，key比較次數(shù)及記錄移動次數(shù)會比較大，若將 待排序文件按某種次序分隔成若干個子文件，對各子文件“跳躍”式的排 序，然后調(diào)整子文件個數(shù)，逐步對原文件排序，這樣總的key比較次數(shù)蕪 其是記錄移動次數(shù)也許會大大降低。Shell排序方法設(shè)待排文件匸（RR2Rn），先將f中相隔增量d （如令d=n/2）的記錄 組成一個個子文件，對各子文件插入排序；然后縮小增量d （如令d=d/2）,