基于hash表的班級成員管理_數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-文庫吧
2025-06-06 20:19 本頁面
【正文】 利用線性探測再散列和 偽隨機(jī)數(shù)探測再散列進(jìn)行沖突處理得到新的哈希地址，并存入哈希表中。 3. 給出每個用戶名的查找長度和該函數(shù)的平均查找長度，并比較哪種方法最好。 基本功能 1. CreateHashList() 建立 Hash 函數(shù)，并采用兩種沖突處理方法進(jìn)行操作。 2. SearchHash() 查找 Hash 表，將用戶所輸入的信息從 Hash 表中調(diào)出，并給出查找長度 沈陽航空航天大學(xué) 課程設(shè)計(jì)報告 2 2 系統(tǒng)功能模塊結(jié)構(gòu)圖 系統(tǒng)功能結(jié)構(gòu)框圖 圖 系統(tǒng)功能結(jié)構(gòu)框圖 系統(tǒng)主要模塊的功能說明 1. 哈希模塊 CreateHashList()； （ adr 為哈希地址） 初始化 Hash 表 ，并創(chuàng)建 Hash 函數(shù)，并將用戶姓名添加至 Hash 表中。 1) 除留取余法： adr=(DATALIST[i].k)%M。（將 DATALIST[i].k 所存的ASCII 碼除以 M 取余所得的哈希地址賦給 adr） 2) 隨機(jī)函數(shù)法 : srand(DATALIST[i].k)。 int adr=rand()%L。(將 DATALIST[i].k 所存的 ASCII 碼作為種子傳入至 srand 函數(shù) 中，并用 rand 函數(shù)產(chǎn)生 L 以內(nèi)的隨機(jī)值為哈希地址賦給 adr) 創(chuàng)建 Hash 表 哈希函數(shù) 模塊 （除留取余） 哈希函數(shù) 模塊 （隨機(jī)數(shù)法） 哈希函數(shù) 模塊 （分割法） 沖突處理模塊 沖突處理模塊 沖突處理模塊 沖突處理模塊 查找模塊 沖突處理模塊 沖突處理模塊 查找模塊 查找模塊 沈陽航空航天大學(xué) 課程設(shè)計(jì)報告 3 3) 分割法 : change(DATALIST,A,i)。 int adr=A[1]*10+A[2]。( DATALIST[i].k 所存的 ASCII 碼利用change()函數(shù)分割開，并去第二個數(shù)字和第三個數(shù)字作為哈希地址 賦給 adr) 2. 沖突處理模塊 1) srand(姓名 ASCII 碼 )。 d=(d+rand()%L)%M。 偽隨機(jī)探測再散列 2) d=d+1。 線性探測再散列 3. 查找模塊 SearchHash()。 查找用戶輸入姓名是否在 Hash 表中； 給出該姓名的查 找長度和該 Hash 函數(shù)的平均查找長度。 沈陽航空航天大學(xué) 課程設(shè)計(jì)報告 4 3 使用的數(shù)據(jù)結(jié)構(gòu)的描述 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 建立一個確定的對應(yīng)關(guān)系 f，使每個關(guān)鍵字和結(jié)構(gòu)中的一個唯一的存儲位置相對應(yīng)。在查找時，只要根據(jù)這個對應(yīng)關(guān)系 f 找到給定值 K 的像 f（ K）為存儲地址的結(jié)構(gòu)體數(shù)組即為哈希表。 哈希表舉例（平方取中法）： A B C …… Z 0 1 2 …… 9 01 02 03 32 60 61 62 71 記錄 關(guān)鍵字 (關(guān)鍵字） 2 哈希地址（ 21729） A I J I0 P1 P2 Q1 Q2 Q3 0100 1100 1200 1160 2061 2062 2161 2162 2163 0010000 1210000 1440000 1370400 4310541 4314704 4734741 4741304 4745651 010 210 440 370 310 314 734 741 745 表 哈希表 數(shù)據(jù)結(jié)構(gòu)用法說明 取關(guān)鍵字平方后的中間幾位為哈希地址。這是一種比較常用的構(gòu)造哈希函數(shù)的方法。通常在選定哈希函數(shù)時不一定能知道關(guān)鍵字的全部情況，取其中哪幾位也不一定 合適，而一個數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)，由此使隨即分布的關(guān)鍵字得到的哈希地址也是隨即的。取的位數(shù)由表長決定。如表 列出了一些標(biāo)識符及它們的哈希地址。 沈陽航空航天大學(xué) 課程設(shè)計(jì)報告 5 4 函數(shù)的描述 主要函數(shù)設(shè)計(jì) 1. Input ()； 作用 ：將用戶姓名換算成 ASCII 碼。 2. CreateHashList()； 作用 ：將用戶名輸入至哈希表中，并用兩種沖突處理方法進(jìn)行沖突處理。 3. SearchHash()。 作用 ：將用戶輸入的用戶名在哈希表中進(jìn)行查找，并給出查找結(jié)果和查找長度 ，和該函數(shù)的平均查找長度。 4. Print ()； 作用 ：打印出程序的主菜單和界面。 5. Change()。 作用 : 將用戶姓名的 ASCII 碼分割為多個數(shù)字并存入數(shù)組中。 主 要 函數(shù)流程圖 1. CreateHashList()； 沈陽航空航天大學(xué) 課程設(shè)計(jì)報告 6 開 始N u m哈 希 表 初 始 化哈 希 函 數(shù) 處 理線 性 探 測 再 散 列 沖突 處 理 后 將 數(shù) 據(jù) 導(dǎo)入 哈 希 表 中判 斷 沖 突將 數(shù) 據(jù) 導(dǎo) 入 哈 希 表中YN1哈 希 表 初 始 化哈 希 函 數(shù) 處 理判 斷 沖 突將 數(shù) 據(jù) 導(dǎo) 入 哈 希 表中YN偽 隨 機(jī) 數(shù) 探 測 再 散列 沖 突 處 理 后 將 數(shù)據(jù) 導(dǎo) 入 哈 希 表 中2結(jié) 束 圖 2. SearchHash()。 沈陽航空航天大學(xué) 課程設(shè)計(jì)報告
研究報告相關(guān)推薦
鄂ICP備17016276號-1