數(shù)據(jù)結(jié)構(gòu)習(xí)習(xí)題解析第10章

1、第10章 索引與散列一、復(fù)習(xí)要點(diǎn)索引結(jié)構(gòu)和散列結(jié)構(gòu)是用于外部搜索的搜索結(jié)構(gòu)。數(shù)據(jù)在外存的組織即文件結(jié)構(gòu)，主要分順序、直接存?。ㄉ⒘校┖退饕募?。在這些文件組織中使用的主要是索引和散列方法。1、基本知識(shí)點(diǎn)要求掌握靜態(tài)索引結(jié)構(gòu)，包括線性索引、倒排索引、靜態(tài)索引樹的搜索和構(gòu)造方法。掌握動(dòng)態(tài)索引結(jié)構(gòu)，包括B樹的搜索、插入、刪除，通過關(guān)鍵碼個(gè)數(shù)估算B樹的高度的方法；B+樹的搜索、插入與刪除。掌握散列法，包括散列函數(shù)的構(gòu)造、處理溢出的閉散列方法；處理溢出的開散列方法；散列表分析。二、難點(diǎn)與重點(diǎn) 1、線性索引Ø密集索引、稀疏索引、索引表計(jì)算Ø基于屬性查找建立倒排索引、單元式倒排表2、動(dòng)態(tài)

2、搜索樹Ø平衡的m路搜索樹的定義、搜索算法ØB樹的定義、B樹與平衡的m路搜索樹的關(guān)系Ø B樹的插入(包括結(jié)點(diǎn)分裂)、刪除(包括結(jié)點(diǎn)調(diào)整與合并)方法ØB樹中結(jié)點(diǎn)個(gè)數(shù)與高度的關(guān)系ØB+樹的定義、搜索、插入與刪除的方法3、散列表Ø 散列函數(shù)的比較Ø 裝載因子 a 與平均搜索長(zhǎng)度的關(guān)系，平均搜索長(zhǎng)度的關(guān)系Ø 表長(zhǎng)m、表中已有數(shù)據(jù)對(duì)象個(gè)數(shù)n和裝載因子的關(guān)系Ø 解決沖突的(閉散列)線性探查法的運(yùn)用，平均探查次數(shù)的計(jì)算Ø 線性探查法的刪除問題、散列表類的設(shè)計(jì)中必須為各地址設(shè)置三個(gè)狀態(tài)Ø 線性探查法中的

3、堆積聚集問題Ø 解決沖突的(閉散列)雙散列法的運(yùn)用，平均探查次數(shù)計(jì)算Ø 雙散列法中再散列函數(shù)的設(shè)計(jì)要求與表長(zhǎng)m互質(zhì)，為此m設(shè)計(jì)為質(zhì)數(shù)較宜Ø 解決沖突的(閉散列)二次散列法的運(yùn)用，平均探查次數(shù)計(jì)算Ø 注意：二次散列法中裝載因子a與表長(zhǎng)m的設(shè)置Ø 解決沖突的(開散列)開散列法的運(yùn)用，平均探查次數(shù)計(jì)算Ø 由平均探查次數(shù)計(jì)算裝載因子a，再計(jì)算表大小的方法三、教材中習(xí)題的解析10-1 什么是靜態(tài)索引結(jié)構(gòu)什么是動(dòng)態(tài)索引結(jié)構(gòu)它們各有哪些優(yōu)缺點(diǎn)【解答】靜態(tài)索引結(jié)構(gòu)指這種索引結(jié)構(gòu)在初始創(chuàng)建，數(shù)據(jù)裝入時(shí)就已經(jīng)定型，而且在整個(gè)系統(tǒng)運(yùn)行期間，樹的結(jié)構(gòu)不發(fā)生變

4、化，只是數(shù)據(jù)在更新。動(dòng)態(tài)索引結(jié)構(gòu)是指在整個(gè)系統(tǒng)運(yùn)行期間，樹的結(jié)構(gòu)隨數(shù)據(jù)的增刪及時(shí)調(diào)整，以保持最佳的搜索效率。靜態(tài)索引結(jié)構(gòu)的優(yōu)點(diǎn)是結(jié)構(gòu)定型，建立方法簡(jiǎn)單，存取方便；缺點(diǎn)是不利于更新，插入或刪除時(shí)效率低。動(dòng)態(tài)索引結(jié)構(gòu)的優(yōu)點(diǎn)是在插入或刪除時(shí)能夠自動(dòng)調(diào)整索引樹結(jié)構(gòu)，以保持最佳的搜索效率；缺點(diǎn)是實(shí)現(xiàn)算法復(fù)雜。10-2 設(shè)有10000個(gè)記錄對(duì)象, 通過分塊劃分為若干子表并建立索引, 那么為了提高搜索效率, 每一個(gè)子表的大小應(yīng)設(shè)計(jì)為多大 【解答】每個(gè)子表的大小 s = énù = é10000ù = 100 個(gè)記錄對(duì)象。10-3如果一個(gè)磁盤頁(yè)塊大小為1024 (=1K

5、) 字節(jié)，存儲(chǔ)的每個(gè)記錄對(duì)象需要占用16字節(jié)，其中關(guān)鍵碼占4字節(jié)，其它數(shù)據(jù)占12字節(jié)。所有記錄均已按關(guān)鍵碼有序地存儲(chǔ)在磁盤文件中，每個(gè)頁(yè)塊的第1個(gè)記錄用于存放線性索引。另外在內(nèi)存中開辟了256K字節(jié)的空間可用于存放線性索引。試問：(1) 若將線性索引常駐內(nèi)存，文件中最多可以存放多少個(gè)記錄(每個(gè)索引項(xiàng)8字節(jié)，其中關(guān)鍵碼4字節(jié)，地址4字節(jié))(2) 如果使用二級(jí)索引，第二級(jí)索引占用1024字節(jié)（有128個(gè)索引項(xiàng)），這時(shí)文件中最多可以存放多少個(gè)記錄？【解答】(1) 因?yàn)橐粋€(gè)磁盤頁(yè)塊大小為1024字節(jié)，每個(gè)記錄對(duì)象需要占用16字節(jié)，則每個(gè)頁(yè)塊可存放1024 / 16 = 64個(gè)記錄，除第一個(gè)記錄存儲(chǔ)線性

6、索引外，每個(gè)頁(yè)塊可存儲(chǔ)63個(gè)記錄對(duì)象。又因?yàn)樵诖疟P文件中所有記錄對(duì)象按關(guān)鍵碼有序存儲(chǔ)，所以線性索引可以是稀疏索引，每一個(gè)索引項(xiàng)存放一個(gè)頁(yè)塊的最大關(guān)鍵碼及該頁(yè)塊的地址。若線性索引常駐內(nèi)存，那么它最多可存放256 * (1024 / 8 ) = 256 * 128 = 32768個(gè)索引項(xiàng)，文件中可存放 32768 * 63 = 2064384個(gè)記錄對(duì)象。(2) 由于第二級(jí)索引占用1024個(gè)字節(jié)，內(nèi)存中還剩255K 字節(jié)用于第一級(jí)索引。第一級(jí)索引有255 * 128 = 32640個(gè)索引項(xiàng)，作為稀疏索引，每個(gè)索引項(xiàng)索引一個(gè)頁(yè)塊，則索引文件中可存放32640 * 63 = 2056320。 397 H

7、ello World! 82 XYZ 1038 This string is rather long 1037 This is Shorter 42 ABC 2222 Hello new World! 10-4 假設(shè)在數(shù)據(jù)庫(kù)文件中的每一個(gè)記錄是由占2個(gè)字節(jié)的整型數(shù)關(guān)鍵碼和一個(gè)變長(zhǎng)的數(shù)據(jù)字段組成。數(shù)據(jù)字段都是字符串。為了存放右面的那些記錄，應(yīng)如何組織線性索引？【解答】將所有字符串依加入的先后次序存放于一個(gè)連續(xù)的存儲(chǔ)空間store中，這個(gè)空間也叫做“堆”，它是存放所有字符串的順序文件。它有一個(gè)指針free，指示在堆store中當(dāng)前可存放數(shù)據(jù)的開始地址。初始時(shí)free置為0，表示可從文件的0號(hào)位置開

8、始存放。線性索引中每個(gè)索引項(xiàng)給出記錄關(guān)鍵碼，字符串在store中的起始地址和字符串的長(zhǎng)度：索引表ID 堆store 關(guān)鍵碼串長(zhǎng)度串起始地址 0Hello World! XYZ This string is rather long This 4235682312is Shorter ABC Hello new World!free39712010371541103826152222165910-5 設(shè)有一個(gè)職工文件： 記錄地址 職工號(hào) 姓 名 性別 職 業(yè) 年齡 籍貫 月工資(元) 10032 034 劉激揚(yáng) 男 教 師 29 山東720.00 10068 064 蔡曉莉 女 教 師 32 遼寧

9、1200.00 10104 073 朱 力 男 實(shí)驗(yàn)員 26 廣東480.00 10140 081 洪 偉 男 教 師 36 北京1400.00 10176 092 盧聲凱 男 教 師 28 湖北720.00 10212 123 林德康 男 行政秘書 33 江西480.00 10248 140 熊南燕 女 教 師 27 上海 780.00 10284 175 呂 穎 女 實(shí)驗(yàn)員 28 江蘇480.00 10320 209 袁秋慧 女 教 師 24 廣東720.00其中，關(guān)鍵碼為職工號(hào)。試根據(jù)此文件，對(duì)下列查詢組織主索引和倒排索引，再寫出搜索結(jié)果關(guān)鍵碼。(1) 男性職工；(2) 月工資超過800

10、元的職工；(3) 月工資超過平均工資的職工；(4) 職業(yè)為實(shí)驗(yàn)員和行政秘書的男性職工；(5) 男性教師或者年齡超過25歲且職業(yè)為實(shí)驗(yàn)員和教師的女性職工。【解答】 主索引 月工資 倒排索引 職務(wù) 倒排索引 職工號(hào)記錄地址月工資長(zhǎng)度指針職務(wù)長(zhǎng)度指針003410032480.3073教師6034106410068123064207310104175081308110140720.3034092409210176092140512310212209209614010248780.1140實(shí)驗(yàn)員20737175102841200.10641758209103201400.1081行政秘書1123 性別

11、倒排索引 年齡 倒排索引性別長(zhǎng)度指針年齡長(zhǎng)度指針男5034241209073261073081271140092282092123175女4064291034140321064175331123209361081搜索結(jié)果： (1) 男性職工 (搜索性別倒排索引)：034, 073, 081, 092, 123(2) 月工資超過800元的職工 (搜索月工資倒排索引)：064, 081(3) 月工資超過平均工資的職工(搜索月工資倒排索引) 月平均工資776元：064, 081, 140(4) 職業(yè)為實(shí)驗(yàn)員和行政秘書的男性職工(搜索職務(wù)和性別倒排索引)：073, 123, 175 &&

12、; 034, 073, 081, 092, 123 = 073, 123(5) 男性教師 (搜索性別與職務(wù)倒排索引)：034, 073, 081, 092, 123 && 034, 064, 081, 092, 140, 209 = 034, 081, 092年齡超過25歲且職業(yè)為實(shí)驗(yàn)員和教師的女性職工 (搜索性別、職務(wù)和年齡倒排索引)：064, 140, 175, 209 && 034, 064, 073, 081, 092, 140, 175, 209 && 034, 064, 073, 081,092, 123, 140, 175 = 06

13、4, 140, 17510-6 倒排索引中的記錄地址可以是記錄的實(shí)際存放地址，也可以是記錄的關(guān)鍵碼。試比較這兩種方式的優(yōu)缺點(diǎn)。 【解答】在倒排索引中的記錄地址用記錄的實(shí)際存放地址，搜索的速度快；但以后在文件中插入或刪除記錄對(duì)象時(shí)需要移動(dòng)文件中的記錄對(duì)象，從而改變記錄的實(shí)際存放地址，這將對(duì)所有的索引產(chǎn)生影響：修改所有倒排索引的指針，不但工作量大而且容易引入新的錯(cuò)誤或遺漏，使得系統(tǒng)不易維護(hù)。記錄地址采用記錄的關(guān)鍵碼，缺點(diǎn)是尋找實(shí)際記錄對(duì)象需要再經(jīng)過主索引，降低了搜索速度；但以后在文件中插入或刪除記錄對(duì)象時(shí)，如果移動(dòng)文件中的記錄對(duì)象，導(dǎo)致許多記錄對(duì)象的實(shí)際存放地址發(fā)生變化，只需改變主索引中的相應(yīng)記錄

14、地址，其他倒排索引中的指針一律不變，使得系統(tǒng)容易維護(hù)，且不易產(chǎn)生新的錯(cuò)誤和遺漏。10-7 m = 2的平衡m路搜索樹是AVL樹，m = 3的平衡m路搜索樹是2-3樹。它們的葉結(jié)點(diǎn)必須在同一層嗎m階B樹是平衡m路搜索樹，反過來，平衡m路搜索樹一定是B樹嗎為什么【解答】m = 3的平衡m路搜索樹的葉結(jié)點(diǎn)不一定在同一層，而m階B_樹的葉結(jié)點(diǎn)必須在同一層，所以m階B_樹是平衡m路搜索樹，反過來，平衡m路搜索樹不一定是B_樹。10-8 下圖是一個(gè)3階B樹。試分別畫出在插入65、15、40、30之后B樹的變化。5580 904560 7025 35508595【解答】插入65后：55 80 4565902

15、5 35508595607055 80 插入15后：659025 4550859560701535插入40后：55 80 659025 4550859560701535 40插入30后：55 358045306590254050859560701510-9 下圖是一個(gè)3階B樹。試分別畫出在刪除50、40之后B樹的變化。5060 80305520407095【解答】刪除50后： 558030204060 7095刪除40后：55 8020 3060 709510-10 對(duì)于一棵有1999999個(gè)關(guān)鍵碼的199階B樹，試估計(jì)其最大層數(shù)(不包括失敗結(jié)點(diǎn))及最小層數(shù)(不包括失敗結(jié)點(diǎn))。【解答】設(shè)B樹的

16、階數(shù)m = 199，則ém/2ù = 100。若不包括失敗結(jié)點(diǎn)層，則其最大層數(shù)為ëlogém/2ù (N+1)/2)û = ëlog100 1000000û = 3若使得每一層關(guān)鍵碼數(shù)達(dá)到最大，可使其層數(shù)達(dá)到最小。第0層最多有 (m-1) 個(gè)關(guān)鍵碼，第1層最多有m(m-1) 個(gè)關(guān)鍵碼，第2層最多有 m2 (m-1) 個(gè)關(guān)鍵碼，¼，第h-1層最多有mh-1 (m-1) 個(gè)關(guān)鍵碼。層數(shù)為h的B樹最多有 (m-1) + m (m-1) + m2 (m-1) + + mh-1 (m-1) = (m-1) (mh1

17、) / (m-1) = mh1個(gè)關(guān)鍵碼。反之，若有n個(gè)關(guān)鍵碼，nmh1，則 h log m (n+1)，所以，有1999999個(gè)關(guān)鍵碼的199階B樹的最小層數(shù)為élog m (n+1)ù = élog199 (1999999 +1)ù = élog 199 2000000ù = 310-11 給定一組記錄，其關(guān)鍵碼為字符。記錄的插入順序?yàn)?C, S, D, T, A, M, P, I, B, W, N, G, U, R, K, E, H, O, L, J ，給出插入這些記錄后的4階B+樹。假定葉結(jié)點(diǎn)最多可存放3個(gè)記錄?！窘獯稹?插入C

18、, S, D 插入T 插入A 插入M C D S S S D S C D S T A C D S T A CS T D M 插入P 插入ID S D M S A CS T D M PA CD IS T M PD M S U 插入B, W, N, G 插入U(xiǎn) D M S U W M N PS T D G IA B CM N PS T W D G IA B C 插入RP D M S U A B CD G IP R M N S T U W 插入KP D I M S U A B CD G M N U W P R S T I K P 插入ED I M S U A B CD E G M N U W P R

19、 S T I K 插入HP D G I M S U A B CD E M N G H P R S T I K U W 插入O, LP S U D G I M D E M N O G H P R S T I K L U W A B C 插入JI P S U D G K M U W A B CK L I J S T P R G H M N O D E 10-12 設(shè)有一棵B+樹，其內(nèi)部結(jié)點(diǎn)最多可存放100個(gè)子女，葉結(jié)點(diǎn)最多可存儲(chǔ)15個(gè)記錄。對(duì)于1, 2, 3, 4, 5層的B+樹，最多能存儲(chǔ)多少記錄，最少能存儲(chǔ)多少記錄?！窘獯稹恳粚覤+樹：根據(jù)B+樹定義，一層B+樹的結(jié)點(diǎn)只有一個(gè)，它既是根結(jié)點(diǎn)又是

20、葉結(jié)點(diǎn)，最多可存儲(chǔ)m1 = 15個(gè)記錄，最少可存儲(chǔ) ém1/2ù = 8個(gè)記錄。二層B+樹：第0層是根結(jié)點(diǎn)，它最多有m = 100棵子樹，最少有2個(gè)結(jié)點(diǎn)；第1層是葉結(jié)點(diǎn)，它最多有m個(gè)結(jié)點(diǎn)，最多可存儲(chǔ)m*m1 = 100*15 = 1500個(gè)記錄，最少有2個(gè)結(jié)點(diǎn)，最少可存儲(chǔ)2* ém1/2ù = 16個(gè)記錄。三層B+樹：第2層是葉結(jié)點(diǎn)。它最多有m2個(gè)結(jié)點(diǎn)，最多可存儲(chǔ)m2 * m1 = 150000個(gè)記錄。最少有2* ém/2ù = 100個(gè)結(jié)點(diǎn)，最少可存儲(chǔ)2* ém/2ù * ém1/2ù = 8

21、00個(gè)記錄。四層B+樹：第3層是葉結(jié)點(diǎn)。它最多有m3個(gè)結(jié)點(diǎn)，可存儲(chǔ)m3 * m1 = 個(gè)記錄。最少有2* ém/2ù 2 = 2 * 502 = 5000個(gè)結(jié)點(diǎn)，存儲(chǔ)2* ém/2ù 2 * ém1/2ù = 40000個(gè)記錄。五層B+樹：第4層是葉結(jié)點(diǎn)。它最多有m4個(gè)結(jié)點(diǎn)，可存儲(chǔ)m4 * m1 = 00個(gè)記錄。最少有2* ém/2ù 3 = 2 * 503 = 250000個(gè)結(jié)點(diǎn)，存儲(chǔ)2* ém/2ù 3 * ém1/2ù = 2000000個(gè)記錄。10-13設(shè)散列表為HT

22、13, 散列函數(shù)為 H (key) = key %13。用閉散列法解決沖突, 對(duì)下列關(guān)鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。(1) 采用線性探查法尋找下一個(gè)空位, 畫出相應(yīng)的散列表, 并計(jì)算等概率下搜索成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度。(2) 采用雙散列法尋找下一個(gè)空位, 再散列函數(shù)為 RH (key) = (7*key) % 10 + 1, 尋找下一個(gè)空位的公式為 Hi = (Hi-1 + RH (key) % 13, H1 = H (key)。畫出相應(yīng)的散列表, 并計(jì)算等概率下搜索成功的平均搜索長(zhǎng)度?！窘獯稹渴褂蒙⒘泻瘮?shù)

23、H(key) = key mod 13，有H(12) = 12, H(23) = 10,H(45) = 6,H(57) = 5,H(20) = 7,H(03) = 3,H(78) = 0,H(31) = 5,H(15) = 2,H(36) = 10.(1) 利用線性探查法造表： 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 (1) (1) (1) (1) (1) (1) (4) (1) (2) (1)搜索成功的平均搜索長(zhǎng)度為ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1)

24、= 搜索不成功的平均搜索長(zhǎng)度為ASLunsucc = (2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) = (2) 利用雙散列法造表：Hi = (Hi-1 + RH (key) % 13, H1 = H (key) 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 36 23 12 (1) (1) (1) (1) (1) (1) (3) (5) (1) (1)搜索成功的平均搜索長(zhǎng)度為ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) = 10-

25、14 設(shè)有150個(gè)記錄要存儲(chǔ)到散列表中, 要求利用線性探查法解決沖突, 同時(shí)要求找到所需記錄的平均比較次數(shù)不超過2次。試問散列表需要設(shè)計(jì)多大 設(shè)a是散列表的裝載因子，則有【解答】已知要存儲(chǔ)的記錄數(shù)為n = 150，查找成功的平均查找長(zhǎng)度為ASLsucc £ 2，則有ASLsucc =£ 2，解得 a £。又有a = £ ，則 m ³ 225。10-15 若設(shè)散列表的大小為m，利用散列函數(shù)計(jì)算出的散列地址為h = hash(x)。(1) 試證明：如果二次探查的順序?yàn)?h + q2), (h + (q-1)2), , (h+1), h, (h-1)

26、, , (h-q2)，其中， q = (m-1)/2。因此在相繼被探查的兩個(gè)桶之間地址相減所得的差取模(%m)的結(jié)果為m-2, m-4, m-6, , 5, 3, 1, 1, 3, 5, , m-6, m-4, m-2(2) 編寫一個(gè)算法，使用課文中討論的散列函數(shù)h(x)和二次探查解決沖突的方法，按給定值x來搜索一個(gè)大小為m的散列表。如果x不在表中，則將它插入到表中?！窘獯稹?1) 將探查序列分兩部分討論： (h + q2), (h + (q-1)2), , (h+1), h 和 (h-1), (h-22), , (h-q2)。對(duì)于前一部分，設(shè)其通項(xiàng)為h + ( q d )2, d = 0,

27、1, , q，則相鄰兩個(gè)桶之間地址相減所得的差取模： ( h + (q (d -1) )2 ( h + (q d )2 ) ) % m = ( (q (d -1 ) )2 (q d )2 ) % m= (2*q -2*d +1) % m = ( m 2*d ) % m. ( 代換 q = (m-1)/2 )代入 d = 1, 2, , q，則可得到探查序列如下：m-2, m-4, m-6, , 5, 3, 1。 ( m 2*q = m 2* (m-1)/2 = 1 )對(duì)于后一部分，其通項(xiàng)為h ( q d )2, d = q, q+1, , 2q，則相鄰兩個(gè)桶之間地址相減所得的差取模：( h (

28、 q d )2 ( h ( q (d+1) )2 ) ) % m = ( ( q (d+1)2 (q d )2 ) % m= ( 2*d 2*q +1) % m = ( 2*d m + 2) % m ( 代換 q = (m-1)/2 )代入 d = q, q+1, , 2q-1，則可得到2*dm+2 = 2*q m +2 = m 1 m +2 = 1,2*dm+2 = 2*q + 2 m +2 = m 1 + 2 m +2 = 3, , 2*dm+2 = 2*(2*q-1) m +2 = 2*(m11) m + 2 = 2*m 4 m +2 = m 2。證畢(2) 編寫算法下面是使用二次探查法

29、處理溢出時(shí)的散列表類的聲明。template <class Type> class HashTable /散列表類的定義public: enum KindOfEntry Active, Empty, Deleted ;/表項(xiàng)分類 (活動(dòng) / 空 / 刪) HashTable ( ) : TableSize ( DefaultSize ) AllocateHt ( ); CurrentSize = 0; /構(gòu)造函數(shù) HashTable ( ) delete ht; /析構(gòu)函數(shù) const HashTable & operator = ( const HashTable &am

30、p; ht2 );/重載函數(shù)：表賦值7 int Find ( const Type & x );/在散列表中搜索x int IsEmpty ( ) return !CurrentSize 1 : 0; /判散列表空否，空則返回1 private: struct HashEntry /散列表的表項(xiàng)定義 Type Element;/表項(xiàng)的數(shù)據(jù), 即表項(xiàng)的關(guān)鍵碼 KindOfEntry info;/三種狀態(tài): Active, Empty, Deleted HashEntry ( ) : info (Empty ) /表項(xiàng)構(gòu)造函數(shù) HashEntry ( const Type &E,

31、KindOfEntry i = Empty ) : Element (E), info (i) ; enum DefualtSize = 31; HashEntry *ht; /散列表存儲(chǔ)數(shù)組 int TableSize;/數(shù)組長(zhǎng)度，是滿足4k+3的質(zhì)數(shù)，k是整數(shù) int CurrentSize;/已占據(jù)散列地址數(shù)目 void AllocateHt ( ) ht = new HashEntryTableSize ; /為散列表分配存儲(chǔ)空間; int FindPos ( const Type & x );/散列函數(shù);template <class Type> const Ha

32、shTable<Type> & HashTable<Type> : operator = ( const HashTable<Type> &ht2 ) /重載函數(shù)：復(fù)制一個(gè)散列表ht2 if ( this != &ht2 ) delete ht; TableSize = ht2.TableSize; AllocateHt ( ); /重新分配目標(biāo)散列表存儲(chǔ)空間 for ( int i = 0; i < TableSize; i+ ) hti = ht2.hti;/從源散列表向目標(biāo)散列表傳送 CurrentSize = ht2.C

33、urrentSize;/傳送當(dāng)前表項(xiàng)個(gè)數(shù) return *this;/返回目標(biāo)散列表結(jié)構(gòu)指針 template <class Type> int HashTable<Type> : Find ( const Type& x ) /共有函數(shù)： 找下一散列位置的函數(shù) int i = 0, q = ( TableSize -1 ) / 2, h0;/ i為探查次數(shù) int CurrentPos = h0 = HashPos ( x );/利用散列函數(shù)計(jì)算x的散列地址 while ( htCurrentP != Empty && htCur

34、rentPos.Element != x ) /搜索是否要求表項(xiàng) if ( i <= q ) /求“下一個(gè)”桶 CurrentPos = h0 + (q - i ) * ( q - i ); while ( CurrentPos >= TableSize ) CurrentPos -= TableSize;/實(shí)現(xiàn)取模 else CurrentPos = h0 - ( i -q ) * ( i - q ); while ( CurrentPos < 0 ) CurrentPos += TableSize; /實(shí)現(xiàn)取模 i+; if ( htCurrentP = A

35、ctive && htCurrentPos.Element = x ) return CurrentPos;/返回桶號(hào) else htCurrentP = Active; htCurrentPos.Element = x; /插入x if ( +CurrentSize < TableSize / 2 ) return CurrentPos;/當(dāng)前已有項(xiàng)數(shù)加1, 不超過表長(zhǎng)的一半返回HashEntry *Oldht = ht;/分裂空間處理: 保存原來的散列表int OldTableSize = TableSize;CurrentSize = 0;TableS

36、ize = NextPrime ( 2 * OldTableSize );/原表大小的2倍，取質(zhì)數(shù)Allocateht ( );/建立新的二倍大小的空表for ( i = 0; i < OldTableSize; i+)/原來的元素重新散列到新表中 if ( O = Active ) Find ( Oldhti.Element );/遞歸調(diào)用 if ( Oldhti.Element = x ) CurrentPos = i; delete Oldht;return CurrentPos; 求下一個(gè)大于參數(shù)表中所給正整數(shù)N的質(zhì)數(shù)的算法。int NextPrime ( i

37、nt N ) /求下一個(gè)>N的質(zhì)數(shù)，設(shè)N >= 5 if ( N % 2 = 0 ) N+;/偶數(shù)不是質(zhì)數(shù) for ( ; !IsPrime (N); N += 2 );/尋找質(zhì)數(shù) return N;int IsPrime ( int N ) /測(cè)試N是否質(zhì)數(shù) for ( int i = 3; i*i <= N; i += 2 )/若N能分解為兩個(gè)整數(shù)的乘積, 其中一個(gè)一定 if ( N % i = 0 ) return 0;/N能整除i, N不是質(zhì)數(shù) return 1;/N是質(zhì)數(shù)10-16 編寫一個(gè)算法，以字典順序輸出散列表中的所有標(biāo)識(shí)符。設(shè)散列函數(shù)為hash(x) = x

38、中的第一個(gè)字符，采用線性探查法來解決沖突。試估計(jì)該算法所需的時(shí)間。 【解答】用線性探查法處理溢出時(shí)散列表的類的聲明。#define DefaultSize 1000#include <iostream.h>#include <string.h>#include <stdlib.h>class HashTable /散列表類定義public: enum KindOfEntry Active, Empty, Deleted ;/表項(xiàng)分類 (活動(dòng) / 空 / 刪) HashTable ( ) : TableSize ( DefaultSize ) ht = new

39、 HashEntryTableSize; /構(gòu)造函數(shù) HashTable ( ) delete ht; /析構(gòu)函數(shù) int Find-Ins ( const char * id );/在散列表中搜索標(biāo)識(shí)符id void HashSort ( );private: struct HashEntry /表項(xiàng)定義 Type Element;/表項(xiàng)的數(shù)據(jù), 即表項(xiàng)的關(guān)鍵碼 KindOfEntry info;/三種狀態(tài): Active, Empty, Deleted HashEntry ( ) : info (Empty ) /表項(xiàng)構(gòu)造函數(shù), 置空 ; HashEntry *ht;/散列表存儲(chǔ)數(shù)組 in

40、t TableSize;/最大桶數(shù) int FindPos ( string s ) const return atoi (*s) - 32; /散列函數(shù)int HashTable : Find-Ins ( const char * id ) int i = FindPos ( id ), j = i; /i是計(jì)算出來的散列地址 while ( != Empty && strcmp ( htj.Element, id ) != 0 ) /沖突 j = ( j + 1 ) % TableSize;/當(dāng)做循環(huán)表處理, 找下一個(gè)空桶 if ( j = i ) ret

41、urn -TableSize;/轉(zhuǎn)一圈回到開始點(diǎn), 表已滿, 失敗 if ( != Active ) /插入if ( j > i ) while ( int k = j; k > i; k- ) htk.Element = htk-1.Element; = ; hti.Element = id; = Active; /插入 else HashEntry temp; temp.Element = htTableSize-1.Element; = htTableS; whi

42、le ( int k = TableSize-1; k > i; k- ) htk.Element = htk-1.Element; = ; hti.Element = id; = Active; /插入 while ( int k = j; k > 0; k- ) htk.Element = htk-1.Element; = ; ht0.Element = temp.Element; = ; return j;void HashTable : Hash

43、Sort ( ) int n, i; char * str; cin >> n >> str; for ( i = 0; i < n; i+ ) if ( Find-Ins ( str ) = - Tablesize ) cout << "表已滿" << endl; break; cin >> str; for ( i = 0; i < TableSize; i+ ) if ( = Active ) cout << hti.Element << endl;10-

44、17 設(shè)有1000個(gè)值在1到10000的整數(shù)，試設(shè)計(jì)一個(gè)利用散列方法的算法，以最少的數(shù)據(jù)比較次數(shù)和移動(dòng)次數(shù)對(duì)它們進(jìn)行排序?！窘獯?】建立TableSize = 10000的散列表，散列函數(shù)定義為int HashTable : FindPos ( const int x ) return x-1; 相應(yīng)排序算法基于散列表類#define DefaultSize 10000#define n 1000class HashTable /散列表類的定義public: enum KindOfEntry Active, Empty, Deleted ;/表項(xiàng)分類 (活動(dòng) / 空 / 刪) HashTabl

45、e ( ) : TableSize ( DefaultSize ) ht = new HashEntryTableSize ; /構(gòu)造函數(shù) HashTable ( ) delete ht; /析構(gòu)函數(shù) void HashSort ( int A , int n );/散列法排序 private: struct HashEntry /散列表的表項(xiàng)定義 int Element;/表項(xiàng)的數(shù)據(jù), 整數(shù) KindOfEntry info;/三種狀態(tài): Active, Empty, Deleted HashEntry ( ) : info (Empty ) /表項(xiàng)構(gòu)造函數(shù) ; HashEntry *ht;

46、 /散列表存儲(chǔ)數(shù)組 int TableSize;/數(shù)組長(zhǎng)度 int FindPos ( int x );/散列函數(shù);void HashTable<Type> : HashSort ( int A , int n ) /散列法排序 for ( int i = 0; i < n; i+ ) int position = FindPos( Ai ); = Active; htposition.Element = Ai; int pos = 0; for ( int i = 0; i < TableSize; i+ ) if (

47、 = Active ) cout << hti.Element << endl; Apos = hti.Element; pos+; 【解答2】利用開散列的方法進(jìn)行排序。其散列表類及散列表鏈結(jié)點(diǎn)類的定義如下：#define DefaultSize 3334#define n 1000class HashTable;/散列表類的前視聲明class ListNode /各桶中同義詞子表的鏈結(jié)點(diǎn)(表項(xiàng))定義friend class HashTable;private: int key; /整數(shù)數(shù)據(jù) ListNode *link; /鏈指針public: ListNode (

48、int x ) : key(x), link(NULL) /構(gòu)造函數(shù);typedef ListNode *ListPtr; /鏈表指針class HashTable /散列表(表頭指針向量)定義public: HashTable( int size = DefaultSize ) /散列表的構(gòu)造函數(shù) TableSize = size; ht = new ListPtrsize; /確定容量及創(chuàng)建指針數(shù)組 void HashSort ( int A ; int n )private: int TableSize;/容量(桶的個(gè)數(shù)) ListPtr *ht;/散列表定義 int FindPos ( int x ) return x / 3; void HashTable<Type> : HashSort ( int A ; int n ) ListPtr * p , *q; int i, bucket, k = 0; for ( i = 0; i < n; i+ ) /對(duì)所有數(shù)據(jù)散列, 同義詞子表是有序鏈表buc