【文章內(nèi)容簡(jiǎn)介】 else //沖突 { do { d=(d+NameList[i].k%10+1)%M。 //偽隨機(jī)探測(cè)再散列法處理沖突 7 sum=sum+1。 //查找次數(shù)加 1 }while (HashList[d].k!=0)。 HashList[d].k=NameList[i].k。 HashList[d].py=NameList[i].py。 HashList[d].si=sum+1。 } } } （ 3） 查找哈希表 ? 若查找 成功，則 輸出姓名、關(guān)鍵字和查找長(zhǎng)度； 查找失敗，則返回相應(yīng)的失敗信息。 ? 查找函數(shù) void FindList()的實(shí)現(xiàn)： void FindList() //查找 { char name[20]={0}。 int s0=0,r,sum=1,adr,d。 printf(請(qǐng)輸入姓名的拼音 :)。 scanf(%s,name)。 for(r=0。r20。r++) //求 出姓名的拼音所對(duì)應(yīng)的整數(shù) (關(guān)鍵字 ) s0+=name[r]。 adr=s0%M。 //使用哈希函數(shù) d=adr。 if(HashList[adr].k==s0) //分 3 種情況進(jìn)行判斷 printf(\n 姓名 :%s 關(guān)鍵字 :%d 查 找 長(zhǎng) 度 為 : 1,HashList[d].py,s0)。 else if (HashList[adr].k==0) printf(無(wú)此記錄 !)。 else { int g=0。 do { d=(d+s0%10+1)%M。 //偽隨機(jī)探測(cè)再散列法處理沖突 sum=sum+1。 if(HashList[d].k==0) { printf(無(wú)此記錄 ! )。 g=1。 } if(HashList[d].k==s0) { printf(\n 姓名 :%s 關(guān)鍵字 :%d 查找長(zhǎng)度為 :%d,HashList[d].py,s0,sum)。 g=1。 } }while(g==0)。 } } 8 （ 4） 顯示哈希表 ? 顯示哈希表的的格式： \n地址 \t關(guān)鍵字 \t\t搜索長(zhǎng)度 \tH(key)\t 姓名 \n ? 顯示哈希表的函數(shù) void Display()的： void Display() //顯示 { int i。 float average=0。 printf(\n 地址 \t 關(guān)鍵字 \t\t 搜索長(zhǎng)度 \tH(key)\t 姓名 \n)。 //顯示的格式 for(i=0。 i50。 i++) { printf(%d ,i)。 printf(\t%d ,HashList[i].k)。 printf(\t\t%d ,HashList[i].si)。 printf(\t\t%d ,HashList[i].k%M)。 printf(\t %s ,HashList[i].py)。 printf(\n)。 } for(i=0。iHASH_LENGTH。i++) average+=HashList[i].si。 average/=NAME_NO。 printf(\n 平均查找長(zhǎng)度： ASL(%d)=%f \n,NAME_NO,average)。 } （ 5） 主函數(shù)設(shè)計(jì) void main() { char ch1。 InitNameList()。 CreateHashList ()。 do { printf(D. 顯示哈希表 \nF. 查找 \nQ. 退出 \n 請(qǐng)選擇： )。 cinamp。ch1。 switch(ch1) { case 39。D39。:Display()。 coutendl。break。 case 39。F39。:FindList()。coutendl。break。 case 39。Q39。:exit(0)。 } coute on !(y/n):。 cinamp。ch1。 }while(ch1!=39。n39。)。 } 9 函數(shù)模塊 模塊調(diào)用關(guān)系 程序流程圖 本次程序流程圖如下 主函數(shù)模塊 姓名初始化模塊 哈希表模塊 查找模塊 輸出模塊 10 開(kāi)始 選擇操作 S、 F、 Q 顯 示 哈 希 表 查 找 哈 希 表 S F Q 退 出 程 序 、 繼續(xù) Y 退出 N Y N 結(jié)束 11 調(diào)試中的問(wèn)題 經(jīng)過(guò)對(duì)哈希表的研究后，即進(jìn)行程序的設(shè)計(jì)和編碼；將原程序編好后，經(jīng)過(guò)編譯，有如下幾個(gè)問(wèn)題： ? 在聲明了結(jié)構(gòu)體 NAME 后，最開(kāi)始結(jié)構(gòu)體內(nèi)的 char name[20]用來(lái)存放姓名拼音，最長(zhǎng)為 20 位； 經(jīng)分析， name 表示所存姓名拼音的首地址，無(wú)需再申明具體的數(shù)組長(zhǎng)度來(lái)存放姓名拼 音，這樣增加了系統(tǒng)的開(kāi)銷，最后改成 char*name， 對(duì)存放姓名拼音時(shí)直接對(duì) name 賦值，系統(tǒng)直接按照字符數(shù)組來(lái)存放姓名拼音，而存放長(zhǎng)度沒(méi)有固定。 ? 建立哈希表 的函數(shù)： void CreateHashList()中，如果遇到?jīng)_突后，在 do{}while()； 語(yǔ)句中，利用 偽隨機(jī)探測(cè)再散列法處理沖突 ，沒(méi)執(zhí)行一次就要將記錄查找長(zhǎng)度的 sum 增加一次，在這個(gè)循環(huán)執(zhí)行完后，即找到一個(gè)不沖突的地址來(lái)存放姓名拼音，經(jīng)過(guò)自習(xí)分析，此時(shí) 的查 找長(zhǎng)度 需要加 1，即 將原 來(lái)的語(yǔ) 句 HashList[d].si=sum。 改成HashList[d].si=sum+1。此時(shí)的 HashList[d].si 才是正確的查找長(zhǎng)度。 ? main 函數(shù)中的 do{}while()語(yǔ)句中，最開(kāi)始 while()語(yǔ)句是： while(a!=39。N39。||a!=39。n39。) 經(jīng)過(guò)分析，在用戶需要退出時(shí)，不論輸入 a=N 還是 a=n，都將繼續(xù)循環(huán)；經(jīng)過(guò)自習(xí)思考，最終將 while()語(yǔ)句改成： while(a==39。Y39。||a==39。y39。)，這樣就實(shí)現(xiàn)了用戶的選擇。 對(duì)設(shè)計(jì)和編碼的討論和分析 算法采用結(jié)構(gòu)體和數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)，利用除留余數(shù)法得到哈希地址，利用為隨機(jī)序列法來(lái)處理沖突，姓名拼音的關(guān)鍵字為 字符串的各個(gè)字符所對(duì)應(yīng)的 ASCII 碼相加，所得的整數(shù) 。求哈希地址時(shí)模為 51，哈希表的總長(zhǎng)度為 50，而實(shí)際名字只有 30 個(gè)，因此有 20 個(gè)地址空間被空閑著，這浪費(fèi)了一定的內(nèi)存。 算法的時(shí)間復(fù)雜度為： O(n)。 平均查找長(zhǎng)度為： 裝填因子為： 30/50= 5. 程序運(yùn)行結(jié)果 經(jīng)過(guò)對(duì)程序錯(cuò)誤的修改后，程序執(zhí)行，經(jīng)過(guò)分析，程序運(yùn)行結(jié)果正確，滿足題目要求！12 運(yùn)行結(jié)果主要截圖如下： ? 程序開(kāi)始后，初 始界面為： ? 選擇 S 后結(jié)果為： 13 結(jié)果顯示，平均查找長(zhǎng)度為 ，符合題設(shè)要求！ ? 選擇 Y 繼續(xù)后選擇 F 查找 查找成功結(jié)果為： 查找失敗結(jié)果為： 感受和體會(huì) 《數(shù)據(jù)結(jié)構(gòu)》這門課程是計(jì)算機(jī)專業(yè)一門基礎(chǔ)性學(xué)科，重要性可見(jiàn)一斑，學(xué)好這門課程對(duì)以后人生的發(fā)展具有深遠(yuǎn)的影響。而數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)便是對(duì)學(xué)習(xí)效果的檢驗(yàn)。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)不僅可以鍛煉我們獨(dú)立思考問(wèn)題、解決問(wèn)題的能力，而且可以培養(yǎng)我們的整體性思維的能力；通過(guò)課程設(shè)計(jì)，使我了解了很多數(shù)據(jù)結(jié)構(gòu)的經(jīng)典問(wèn)題和經(jīng)典算法，加深 了對(duì)數(shù)據(jù)結(jié)構(gòu)的再認(rèn)識(shí)，