目錄第1章需求分析……………………第2章概要設計……………………第3章詳細設計……………………第4章調試分析……..........................第5章核心源程序清單和執行結果……………....第6章設計體會………….................第7章附錄…………………...........需求分析1.問題描述：針對某個集體〔比方你所在的班級〕中的人名設計一個哈希表，使得平均查找長度不超過R，完成相應的建表和查表程序；2.人名為中國人姓名的漢語拼音，人名有30個，平均查找長度的上限為2；3.用偽隨機探測再散列法處理沖突；4.輸入為所要查詢的人姓名〔拼音〕；輸出為該關鍵字的查找信息；5.測試數據：輸入：lihaojie輸出：姓名：lihaojie關鍵字：837查找長度：1輸入：wangzhou輸出：姓名：wangzhou關鍵字：查找長度：3輸入：d輸出：顯示哈希表6.本程序用C++語言編寫，在vc++6.0環境下運行。概要設計2.1算法思想：1定義：哈希表是為了便于快速搜索而組織的鍵/值組合的集合。HashTable是一種數組，可以用任意簡單變量值來訪問其元素，這種數組叫哈希表。2優點：哈希表最大的優點就是把數據的存儲和查找消耗的時間大大降低，幾乎可以看成是常數時間；而代價僅僅是消耗比擬多的內存。然而在當前可利用內存越來越多的情況下，用空間換時間的做法是值得的。另外，編碼比擬容易也是它的特點之一。3根本原理：使用一個下標范圍比擬大的數組來存儲元素。可以設計一個函數〔哈希函數，也叫做散列函數〕，使得每個元素的關鍵字都與一個函數值〔即數組下標，hash值〕存在一一對應的關系，于是用這個數組單元來存儲這個元素。也可以簡單的理解為，按照關鍵字為每一個元素“分類〞。4哈希表的不可防止沖突(collision)現象：對不同的關鍵字可能得到同一個哈希地址即key1≠key2，而f(key1)=f(key2)。因此，在建造哈希表時不僅要設定一個好的哈希函數，而且要設定一種處理沖突的方法。用偽隨機探測法。求下一個開放地址的公式為：Hi=(H(k)+di)MODm注意：Di=偽隨機數序列；2.2關于程序設計的根本操作：1.對哈希表的操作InitNameList()操作結果：姓名〔結構體數組〕初始化CreateHashList()操作結果：建立哈希表FindList()操作結果：在哈希表中查找Display()操作結果：顯示哈希表2.主程序intmain(){初始化；InitNameList()；CreateHashList()；do{接受命令；處理命令；}while〔“命令〞=“退出〞〕；return0;}3.本程序包含的模塊}1〕初始化操作，結構體定義；2〕姓名結構體建立模塊；3〕建立哈希表模塊；4〕查找模塊；5〕顯示哈希表模塊；4〕主程序模塊4程序流程圖主程序主程序初始化姓名建立哈希表查找初始化姓名建立哈希表查找顯示哈希表表詳細設計主要功能模塊：模塊一：建立哈希表voidCreateHashList()//建立哈希表{ inti;for(i=0;i<HASH_LENGTH;i++) {HashList[i].py="";HashList[i].k=0;HashList[i].si=0; }for(i=0;i<HASH_LENGTH;i++) {intsum=0;intadr=(NameList[i].k)%M;//哈希函數intd=adr;if(HashList[adr].si==0)//如果不沖突 {HashList[adr].k=NameList[i].k;HashList[adr].py=NameList[i].py;HashList[adr].si=1; }else//沖突 {do {d=(d+NameList[i].k%10+1)%M;//偽隨機探測再散列法處理沖突sum=sum+1;//查找次數加1 }while(HashList[d].k!=0);HashList[d].k=NameList[i].k;HashList[d].py=NameList[i].py;HashList[d].si=sum+1; } }}模塊二：查找voidFindList()//查找{ charname[20]={0};ints0=0,r,sum=1,adr,d;printf("請輸入姓名的拼音:");scanf("%s",name);for(r=0;r<20;r++)//求出姓名的拼音所對應的整數(關鍵字)s0+=name[r];adr=s0%M;//使用哈希函數d=adr;if(HashList[adr].k==s0)//分3種情況進行判斷printf("\n姓名:%s關鍵字:%d查找長度為:1",HashList[d].py,s0);elseif(HashList[adr].k==0)printf("無此記錄!");else {intg=0;do {d=(d+s0%10+1)%M;//偽隨機探測再散列法處理沖突sum=sum+1;if(HashList[d].k==0) {printf("無此記錄!");g=1; }if(HashList[d].k==s0) {printf("\n姓名:%s關鍵字:%d查找長度為:%d",HashList[d].py,s0,sum);g=1; } }while(g==0); }}模塊三：顯示哈希表voidDisplay()//顯示哈希表{ inti;floataverage=0;printf("\n地址\t關鍵字\t\t搜索長度\tH(key)\t姓名\n");//顯示的格式for(i=0;i<50;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;i<HASH_LENGTH;i++)average+=HashList[i].si;average/=NAME_NO;printf("\n平均查找長度：ASL(%d)=%f\n",NAME_NO,average);}調試分析由于本程序的思路較簡單，主要是對哈希表的建立，查找和輸出，在寫程序時最重要的是正確書寫哈希函數和選擇適宜的處理沖突方法，可以有效減少查找長度，提高程序運行效率。下面本人就針對哈希函數的選擇以及沖突方法的選擇做一下簡單的論述：4.1哈希函數的選擇本人設計了如下幾種哈希函數：利用人名首字母的ASCII值-97作為該人名的關鍵字，而后后建立哈希函數hash(k)=k分析：利用此類哈希函數的優點是比擬簡單，可行而且易于想到，但是其也有比擬明顯的缺點，就是產生沖突的幾率比擬的大，因為可能有很多人的人名的首字母是相同的，因此此種方法要求建立的hash沖突比擬完善實用。將人名所有的字母的ASCII碼值進行相加作為關鍵字，而后建立哈希函數hash(k)=k%m[m為其隨機數]分析：此類哈希函數的思想相對來說比擬的復雜，利用所有字母的ASCII碼值的相加作為其關鍵字，但是其有一個很好的優點，就是產生沖突的幾率比擬的少，從而可以有效的減少信息的查找長度。去掉姓氏，利用人名的首字母的ASCII碼值-97作為關鍵字，而后建立哈希函數hash(k)=k分析：這種hash函數的建立是根據第一種函數改良而來的，它彌補了以前的缺乏：即產生沖突的幾率比擬的大，但同時它又極大的增加了此程序的復雜度。增加了程序運行的時間。去掉姓氏，將人名的所有字母的ASCII碼值進行相加作為關鍵字，而后建立哈希函數hash(k)=k%m[m為其隨機數]分析：此種哈希函數綜合了第二，第三種hash函數，它的思想比擬復雜不易想到，但是其可以將hash地址沖突率減少到一個很低的概率。極大的提高查找的效率，但是由于程序的復雜度較大，所以它所需要的運行時間也是很大的。4.2關于沖突處理的選擇本人設計了如下幾種沖突方法：針對于第一，第三種hash函數，本人認為可以利用雙hash函數探測法來處理沖突：即是略去第一個字母從下一個字母開始尋找關鍵字，建立hash函數，來處理沖突。分析：此種沖突處理方法比擬簡單，而且確實可行性比擬的高，但是由于hash函數的關系，此種沖突處理方法并不怎么使用。針對于第二，第四種hash函數，本人認為可以利用偽隨機數線性探測法來處理沖突：即是利用公式(k%m+1)%m來處理沖突。分析：此種沖突處理方法操作起來相對的比擬麻煩，而且還需要一個隨機數，但是其有一個比擬好的優點，它的處理后的沖突率幾乎為零，同時能有效的減少哈希表設計的長度。核心源程序清單和執行結果1.源程序代碼：#include<iostream>#include<string>usingnamespacestd;#defineHASH_LENGTH50//哈希表的長度#defineM47//取余隨機數#defineNAME_NO30//人名的個數typedefstruct{char*py;//名字的拼音intk;//名字所對應的關鍵字}NAME;NAMENameList[HASH_LENGTH];//全局變量NAMEtypedefstruct//哈希表{char*py;//名字的拼音intk;//拼音所對應的整數intsi;//查找長度}HASH;HASHHashList[HASH_LENGTH];//全局變量HASH/*姓名〔結構體數組〕初始化*/voidInitNameList(){char*f;intr,s0,i;for(i=0;i<HASH_LENGTH;i++){NameList[i].py=newchar[64];NameList[i].py[0]=0;}strcpy(NameList[0].py,"lihaojie");strcpy(NameList[1].py,"zhaona");strcpy(NameList[2].py,"shangqingfu");strcpy(NameList[3].py,"changqiongfang");strcpy(NameList[4].py,"liaobangyu");strcpy(NameList[5].py,"fenghao");strcpy(NameList[6].py,"huangtianyuan");strcpy(NameList[7].py,"luxiwu");strcpy(NameList[8].py,"huangxinglong");strcpy(NameList[9].py,"jiangxiaojia");strcpy(NameList[10].py,"guojie");strcpy(NameList[11].py,"liyexiao");strcpy(NameList[12].py,"lidaohui");strcpy(NameList[13].py,"lijue");strcpy(NameList[14].py,"lizhuoqun");strcpy(NameList[15].py,"linfujun");strcpy(NameList[16].py,"luobingbiao");strcpy(NameList[17].py,"luokeqing");strcpy(NameList[18].py,"nichao");strcpy(NameList[19].py,"panhuafeng");strcpy(NameList[20].py,"lixiaolong");strcpy(NameList[21].py,"songzhanhui");strcpy(NameList[22].py,"lichao");strcpy(NameList[23].py,"wanghaofeng");strcpy(NameList[24].py,"wangzhou");strcpy(NameList[25].py,"wangqinde");strcpy(NameList[26].py,"wangzejun");strcpy(NameList[27].py,"wangkeke");strcpy(NameList[28].py,"weixing");strcpy(NameList[29].py,"wurenke");for(i=0;i<NAME_NO;i++){s0=0;f=NameList[i].py;for(r=0;*(f+r)!='\0';r++)/*方法：將字符串的各個字符所對應的ASCII碼相加，所得的整數做為哈希表的關鍵字*/s0=*(f+r)+s0;NameList[i].k=s0;}}/*建立哈希表*/voidCreateHashList(){inti;for(i=0;i<HASH_LENGTH;i++){HashList[i].py=newchar[64];HashList[i].py[0]=0;HashList[i].k=0;HashList[i].si=0;}for(i=0;i<HASH_LENGTH;i++){intsum=0;intadr=(NameList[i].k)%M;//哈希函數intd=adr;if(HashList[adr].si==0)//如果不沖突{HashList[adr].k=NameList[i].k;HashList[adr].py=NameList[i].py;HashList[adr].si=1;}else//沖突{while(HashList[d].k!=0){d=(d+NameList[i].k%10+1)%M;//處理沖突sum=sum+1;//查找次數加1};HashList[d].k=NameList[i].k;HashList[d].py=NameList[i].py;HashList[d].si=sum+1;}}}/*查找模塊*/voidFindList(){stringname;ints0=0,r,sum=1,adr,d;cout<<"請輸入姓名的拼音:"<<endl;cin>>name;for(r=0;r<20;r++)//求出姓名的拼音所對應的整數(關鍵字)s0+=name[r];adr=s0%M;//使用哈希函數d=adr;if(HashList[adr].k==s0)//分3種情況進行判斷cout<<"姓名:"<<HashList[d].py<<""<<"關鍵字:"<<s0<<""<<"查找長度為:1"<<endl;elseif(HashList[adr].k==0)cout<<"無此記錄!"<<endl;else{intg=0;while(g==0){d=(d+s0%10+1)%M;//處理沖突sum=sum+1;if(HashList[d].k==0){cout<<"無此記錄!"<<endl;g=1;}if(HashList[d].k==s0){cout<<"姓名:"<<HashList[d].py<<""<<"關鍵字:"<<s0<<""<<"查找長度為:"<<sum<<endl;g=1;}};}}/*顯示哈希表*/voidDisplay(){inti;floataverage=0;cout<<"\n地址\t關鍵字\t\t搜索長度\tH(key)\t姓名\n";//顯示的格式for(i=0;i<50;i++){cout<<i<<"";cout<<"\t"<<HashList[i].k<<"";cout<<"\t\t"<<HashList[i].si<<"";cout<<"\t\t"<<(HashList[i].k%M)<<"";cout<<"\t"<<HashList[i].py<<"";cout<<"\n";}for(i=0;i<HASH_LENGTH;i++)average+=HashList[i].si;average/=NAME_NO;cout<<"平均查找長度：ASL("<<NAME_NO<<")="<<average<<endl;}/*主函數，調用其他功能函數*/intmain(){charx;InitNameList();CreateHashList();cout<<"d.顯示哈希表f.查找任意鍵退出請選擇："<<endl;while(cin>>x){if(x=='d'){Display();cout<<endl;}elseif(x=='f'){FindList();cout<<endl;}elsebreak;}for(inti=0;i<HASH_LENGTH;i++){free(NameList[i].py);free(HashList[i].py);}return0;}