數(shù)據(jù)結(jié)構(gòu)與算法課程設計說明書-布谷鳥散列

PAGE課程設計說明書課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法設計題目：布谷鳥散列院系：計算機科學與信息工程學院設計題目布谷鳥散列學生姓名所在院系計算機科學與信息工程系專業(yè)、年級、班13軟件工程1班設計要求：設計、實現(xiàn)一個布谷鳥散列程序：(1)插入；(2)沖突處理；(3)顯示；(4)退出。學生應完成的工作：(1)根據(jù)課程設計要求，分析思路并構(gòu)建模型，劃分子模塊、完善其功能；(2)根據(jù)各模塊的功能設計并編寫程序段、連接各程序段使之形成一個有機的整體；(3)調(diào)試、運行程序進而得到正確的結(jié)果；(4)根據(jù)實驗設計運行過程，寫出實驗論文并總結(jié)實驗教訓。參考文獻閱讀：(1)C++語言程序設計（潭浩強第二版，清華大學出版社）；(2)數(shù)據(jù)結(jié)構(gòu)（吳偉民等C++語言版，清華大學出版社）；(3)數(shù)據(jù)結(jié)構(gòu)實驗教程（高曉兵等，清華大學出版社）；(4)算法分析與設計（鄭宗漢、鄭曉明，清華大學出版社）。工作計劃：(1)第一周的第一天：小組布置設計題目；說明進度安排。(2)第一周的第二天：小組審題，查閱資料，進行設計前的必要資料準備。(3)第一周的第三天、第四天、第五天：程序編寫、上機調(diào)試(4)第二周的第一天至第三天：上機調(diào)試程序、結(jié)果分析。(5)第二周的第四天：撰寫設計報告。(6)第二周的第五天：設計答辯。任務下達日期：2015年6月日任務完成日期：2015年6月日指導教師（簽名）：學生（簽名）：布谷鳥散列摘要布谷鳥散列最早于2001年由RasmusPagh和FlemmingFricheRodler提出。該散列方法是為了解決散列沖突的問題而提出，利用較少計算換取了較大空間。名稱源于該散列方法行為類似于布谷鳥在別的鳥巢中下蛋，并將別的鳥蛋擠出的行為。它具有占用空間小、查詢迅速等特性，可用于Bloomfilter和內(nèi)存管理算法使用兩個不同散列函數(shù)計算對應key的位置。1.當兩個散列任意位置為空，則選擇一個位置插入2.讓兩個散列有位置為空時，則插入到空位置3.當兩個散列位置均不為空時，隨機選擇兩者之一的位置上key踢出，計算踢出的key另一個散列值對應的位置進行插入，轉(zhuǎn)至2執(zhí)行（即當再次插入位置為空時插入，仍舊不為空時，再踢出這個key）關鍵詞：布谷鳥散列；插入；沖突；踢出。目錄1設計背景………………51.1布谷鳥散列的需求…………51.2布谷鳥散列的應用…………52．設計方案 ……………52.1總體設計流程…………………52.2系統(tǒng)的模塊化…………………53.方案實施……………63.1布谷鳥散列的建立………64．結(jié)果與結(jié)論…………74.1源程序代碼概要………………74.2關鍵程序代碼段詳細描述……84.3運行結(jié)果………104.4課程設計總結(jié)…………………135.收獲與致謝…………136.參考文獻……………137.附件…………………13PAGE21.設計背景1.1布谷鳥散列的需求在散列的設計中，如果一個表滿了，不可能再插入新的元素，或者如果表達到飽和狀態(tài)，散列就會變慢，需要想各種辦法來找到空槽放置元素。有一種解決方法是再散列，也就是對于一個大表，修改散列函數(shù)（至少TSize），將所有元素從舊表散列到新表中，丟棄舊表，利用新的散列函數(shù)對新表進行散列。新表的大小可以是舊表的兩倍，可以是最接近當前表大小的兩倍的一個素數(shù)，也可以是當前表大小再加上預定義的值的大小等。1.2布谷鳥散列的應用至今為止所說的所有方法都可以使用再散列，再散列結(jié)束后，還可以接著使用先前的散列方法及沖突解決方法來處理數(shù)據(jù)，再散列有一種非常重要的方法是布谷鳥散列。2.設計方案2.1總體設計流程1.建立散列表（1）插入；（2）解決沖突。2.再散列（1）將表1中的值取出；（2）插入到表2；2.2系統(tǒng)的模塊化1.程序用到的抽象數(shù)據(jù)類型的定義；2.定義表；3.系統(tǒng)子程序及功能；4.實現(xiàn)人機交互。3.方案實施3.1布谷鳥散列的建立布谷鳥散列使用兩個表T1和T2，以及兩個散列函數(shù)h1和h2。為了插入關鍵字k1，使用h1來檢查表T1，如果位置T1[h1(k1)]是空的，就將關鍵字插入。如果位置被關鍵字k2占了，就將k2移出，以騰出地方給k1，然后用第二個散列函數(shù)在第二個表中找到位置T2[h2(k2)]，將k2放入其中。如果該位置被k3占了，則插入失敗。4.結(jié)果與結(jié)論4.1源程序代碼概要系統(tǒng)用到的抽象數(shù)據(jù)類型定義：ADTcuckoo{數(shù)據(jù)對象：constintAddLen=20;constintMulLen=90;intAddTable[20];intMulTable[90];intNum;intNumAdd;intNumMul;基本操作：intHash1();intHash2();voidProcess();voidShow();voidMenu();voidInit();}ADTcuckoo系統(tǒng)中子程序及功能要求：1．Hash1()：求數(shù)字各位的和。2．Hash2()：求數(shù)字各位的積。3．Process()：處理選項函數(shù)。4.Show()：顯示hash表函數(shù)。5．Menu()：菜單函數(shù)。6.Init()：初始化hash表函數(shù)。各程序模塊之間的調(diào)用關系（子程序編號見上）：主函數(shù)可調(diào)用子程序5，6子程序5可調(diào)用子程序34.2關鍵程序代碼段詳細描述1．Hash1()：求數(shù)字各位的和。intcuckoo::Hash1() //hash函數(shù)1：數(shù)字各位和{ inttnum=Num; NumAdd=0; //Num的各位和保存在NumAdd中，循環(huán)累加 while(tnum) { NumAdd+=tnum%10; tnum/=10; } cout<<"NumAdd="<<NumAdd<<endl; if(AddTable[NumAdd]==-1) { AddTable[NumAdd]=Num; return1; } else { tnum=Num; Num=AddTable[NumAdd]; AddTable[NumAdd]=tnum; return0; }}2．Hash2()：求數(shù)字各位的積。intcuckoo::Hash2() //hash函數(shù)2：數(shù)字各位積{ inttnum=Num; NumMul=1; while(tnum) { NumMul*=tnum%10; tnum/=10; } if(MulTable[NumMul]==-1) { MulTable[NumMul]=Num; return1; } elsereturn0; }3．Process()：處理選項函數(shù)。voidcuckoo::Process(){ intcas; cin>>cas; if(cas==1) { cout<<"請輸入一個1-100的整數(shù)："; cin>>Num; if(Hash1()==1) { cout<<"\n成功插入hash表1！\n"; Menu(); } //插入表1時發(fā)生沖突，將表1中的值取出向表2插入 elseif(Hash2()==1) { cout<<"\n成功插入hash表2！\n"; Menu(); } else { cout<<"\n插入失??！\n"; Menu(); } } elseif(cas==2) { Show();}}4.Show()：顯示hash表函數(shù)。voidcuckoo::Show(){ //輸出表1中元素，值不為-1的表示插入了元素 cout<<"hash表1中元素為：\n"; for(inti=0;i<AddLen;i++) { if(AddTable[i]!=-1) { cout<<"Table1["<<i<<"]="; cout<<AddTable[i]<<endl; } } cout<<"hash表2中元素為：\n"; for(inti=0;i<MulLen;i++) { if(MulTable[i]!=-1) { cout<<"Table2["<<i<<"]="; cout<<MulTable[i]<<endl; } } Menu();}5．Menu()：菜單函數(shù)。voidcuckoo::Menu(){ cout<<"*********************************\n"; cout<<"*******歡迎來到布谷鳥散列*******\n"; cout<<"*********1.插入********\n"; cout<<"*********2.顯示********\n"; cout<<"*********3.退出********\n"; cout<<"請按提示選擇："; Process();}6.Init()：初始化hash表函數(shù)。voidcuckoo::Init(){ for(inti=0;i<AddLen;i++) { AddTable[i]=-1; } for(inti=0;i<MulLen;i++) { MulTable[i]=-1; }}4.3程序運行結(jié)果（1）系統(tǒng)初始化界面（2）向表1中插入元素（3）向表1插入元素沖突時（4）插入失敗（5）顯示表中數(shù)據(jù)4.4課程設計總結(jié)通過本次設計，明白了布谷鳥散列的運算過程。還加入了兩個函數(shù)，程序顯得很高大上。在當今信息時代，如何有效的利用計算機為人類服務已越來越引起人們的重視，散列算法正是一種應用廣泛且非常有效的解決各種問題的算法。5.收獲與致謝總的來說,在整個設計的過程中,對知識有了相當程度的了解掌握,基本上學會了對散列的設計和對散列的操作等。在對散列的自學過程中也認識，在學習的過程中要靈活的把所學的知識運用到實踐當中，并且還要鞏固練習和運用，這樣才可以牢牢的記住。試驗也對數(shù)據(jù)結(jié)構(gòu)的知識進行了復習，尤其是散列及它的實現(xiàn)等知識點，在對程序不斷的修改和逐步改進提升的過程中，積累了不少經(jīng)驗，為在以后的學習和實踐應用奠定了一定的基礎。這次課程設計受益非淺，學到了不少知識，同時也認識到自身的不足，需要加強自身訓練，學以致用，學會自我總結(jié)，吸取教訓，積累經(jīng)驗，在學習和實踐中來不斷的提升自己。6.參考文獻[1]C++語言程序設計（潭浩強第二版，清華大學出版社）；[2]數(shù)據(jù)結(jié)構(gòu)（吳偉民等c++語言版，清華大學出版社）；[3]數(shù)據(jù)結(jié)構(gòu)實驗教程（高曉兵等，清華大學出版社）；[4]算法分析與設計（鄭宗漢、鄭曉明，清華大學出版社）。[5]c++數(shù)據(jù)結(jié)構(gòu)與算法（AdamDrozdek）7.附件附源程序清單電子檔一份指導教師評語：1、課程設計報告：a、內(nèi)容：不完整□完整□詳細□b、方案設計：較差□合理□非常合理□c、實現(xiàn)：未實現(xiàn)□部分實現(xiàn)□全部實現(xiàn)□d、文檔格式：不規(guī)范□基本規(guī)范□規(guī)范□2、出勤：全勤□缺勤次3、答辯：