哈希表設(shè)計(jì)與實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

課程名稱：數(shù)據(jù)結(jié)構(gòu)XXXXXXXX本科學(xué)生課程設(shè)計(jì)（論文）題目哈希表的設(shè)計(jì)與實(shí)現(xiàn)姓名XXX學(xué)號(hào)XXXXXXXXXXXX學(xué)部計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)、年級(jí)計(jì)算機(jī)科學(xué)與技術(shù)大二指導(dǎo)教師XX2010年11月

摘要隨著信息技術(shù)的發(fā)展，關(guān)于各種程序中的數(shù)據(jù)結(jié)構(gòu)也是層出不窮，對(duì)于項(xiàng)目某一方面的計(jì)算或者是某一方面的研究，出現(xiàn)了專門的數(shù)據(jù)結(jié)構(gòu)，哈希表就是其中之一，哈希表作為另類的一種數(shù)據(jù)結(jié)構(gòu)，其作用也是區(qū)別于其它同類的數(shù)據(jù)結(jié)構(gòu)的，它是由兩部分組成的：鍵(key)和值，通過鍵可以迅速的查找到你需要的值。常見的構(gòu)造哈希函數(shù)的方法有直接定址法除留余數(shù)法平方取中法數(shù)字分析法等。一般創(chuàng)建哈希表時(shí)可能會(huì)出現(xiàn)很多的沖突，常用的處理沖突的方法為開放定址法再哈希法鏈地址法建立一個(gè)公共溢出區(qū)。關(guān)鍵詞:數(shù)據(jù)結(jié)構(gòu)；哈希表；鍵(key)；

目錄TOC\o"1-3"\u第1章 前言與系統(tǒng)實(shí)現(xiàn) 21.1前言 21.2系統(tǒng)實(shí)現(xiàn) 31.2.1開發(fā)環(huán)境 31.2.2VisualC++環(huán)境的安裝 3第2章系統(tǒng)功能分析 42.1系統(tǒng)功能需求分析 42.2任務(wù)定義 4第3章總體設(shè)計(jì) 53.1系統(tǒng)數(shù)據(jù)結(jié)構(gòu) 53.2主要算法流程圖 63.2.1以姓名為關(guān)鍵字的CreateHashList()函數(shù)流程圖 63.2.2哈希表查找算法流程圖 73.2.3主程序流程圖 8第4章詳細(xì)設(shè)計(jì)和編碼 94.1節(jié)點(diǎn)的建立 94.2對(duì)哈希函數(shù)的定義 94.3創(chuàng)建哈希表算法、代碼如下所示: 104.3.1算法 104.3.2代碼 104.4哈希查找 114.5顯示哈希表 144.6主菜單設(shè)計(jì) 164.7主函數(shù)設(shè)計(jì) 16第5章程序運(yùn)行測(cè)試 195.1程序主界面 195.2哈希表初始化 195.3按姓名查找記錄 215.4顯示哈希表全部記錄 22總結(jié) 23參考文獻(xiàn) 24前言與系統(tǒng)實(shí)現(xiàn)1.1前言在信息化時(shí)代的今天，計(jì)算機(jī)技術(shù)已經(jīng)是發(fā)展到一個(gè)很可觀的地步了，特別是面向窗口的操作系統(tǒng)的出現(xiàn)，使得程序設(shè)計(jì)更加的容易了。在過去計(jì)算機(jī)內(nèi)存容量小，CPU計(jì)算速度慢，關(guān)于程序設(shè)計(jì)中的數(shù)據(jù)結(jié)構(gòu)也因此提出來很多的關(guān)于解決這方面的問題。哈希表就是其中之一，哈希表是一個(gè)由關(guān)鍵字與值組成的特殊的一種數(shù)據(jù)結(jié)構(gòu)。它的出現(xiàn)主要是為了解決在結(jié)構(gòu)中查找記錄時(shí)需要進(jìn)行一系列和關(guān)鍵字的比較,這一類查找方法是建立在“比較”的基礎(chǔ)上的，在順序等的查找中，查找的效率是依賴于查找過程中所比較的次數(shù)。理想的情況是希望不經(jīng)過任何的比較一次存取便能得到所查記錄，那就必須在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系，使得每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。因而在查找時(shí)只要根據(jù)這個(gè)對(duì)應(yīng)關(guān)系找到給定的值的像。若結(jié)構(gòu)中存在關(guān)鍵字和該值相等的記錄，則所要查找的數(shù)就必定就是這個(gè)所查找到的記錄。哈希函數(shù)是建立哈希表的一個(gè)重要的成員，它的構(gòu)造方法分為以下幾種：直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法、隨機(jī)數(shù)法。本程序中主要用的是除余取留法,除留取余法主要是取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p出后所得余數(shù)為哈希地址即:H(key)=keyMODp,p<=m，這是一種最簡(jiǎn)單，也是一種最常用的構(gòu)造函數(shù)的方法，它不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊、平方中等運(yùn)算之后取模。在哈希表的建立中，很容易出現(xiàn)同義詞，這些同義詞的出現(xiàn)也導(dǎo)致了建立哈希表時(shí)沖突的出現(xiàn)，如果不解決這些沖突那么建立好的哈希表與預(yù)料的哈希表不同。關(guān)于處理沖突的方法主要有：開放定址法、再哈希法、鏈地址法。本程序中主要用的就是鏈地址法萊解決沖突的。1.2系統(tǒng)實(shí)現(xiàn)本程序是在Vc++6.0環(huán)境下編寫測(cè)試運(yùn)行的。1.2.1開發(fā)環(huán)境表1-1列出了系統(tǒng)硬件配置，表6-2列出了系統(tǒng)軟件配置。設(shè)備名稱配置CPUE12002.6GHz內(nèi)存128MB硬盤40GB 表1.1組裝臺(tái)式機(jī)配置設(shè)備名稱版本操作系統(tǒng)WindowsXPsp3開發(fā)環(huán)境VisualStudioC++6.0設(shè)計(jì)工具VC++表1.2軟件環(huán)境1.2.2VisualC++環(huán)境的安裝在計(jì)算機(jī)中安裝VisualC++安裝程序，VisualC++應(yīng)用程序的開發(fā)主要有兩種模式，一種是WINAPI方式，另一種則是MFC方式，傳統(tǒng)的WINAPI開發(fā)方式比較繁瑣，而MFC則是對(duì)WINAPI再次封裝，所以MFC相對(duì)于WINAPI開發(fā)更具備效率優(yōu)勢(shì)。本軟件中因?yàn)槌绦蛑饕菫榱藢?shí)現(xiàn)某個(gè)算法所以這里沒有用到MFC。第2章系統(tǒng)功能分析2.1系統(tǒng)功能需求分析實(shí)現(xiàn)本程序需要解決以下幾個(gè)問題：1.設(shè)計(jì)一個(gè)結(jié)點(diǎn)使該結(jié)點(diǎn)包括電話號(hào)碼、用戶名、QQ等結(jié)點(diǎn)信息。2.利用用戶名為關(guān)鍵字建立哈希表，哈希函數(shù)用除留余數(shù)法構(gòu)照。3.利用鏈表法處理沖突問題。4.實(shí)現(xiàn)用哈希法查找并顯示給定姓名的記錄。5.顯示哈希表中的全部記錄。2.2任務(wù)定義由功能需求分析知，本設(shè)計(jì)主要要求以用戶名為關(guān)鍵字建立哈希表，并實(shí)現(xiàn)查找功能。所以本設(shè)計(jì)的核心問題是如何解決散列的問題，亦即設(shè)計(jì)一個(gè)良好的哈希表。根據(jù)題目的要求采用鏈地址法散列算法。當(dāng)出現(xiàn)同義詞沖突時(shí)，使用鏈表結(jié)構(gòu)把同義詞鏈接在一起，即同義詞的存儲(chǔ)地址不是散列表中其他的空地址。首先，解決的是定義鏈表結(jié)點(diǎn)，在鏈地址法中，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由六個(gè)域組成，而由于該程序需要用用戶名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點(diǎn)它是charstrName[20];charstrClass[20];charstrPhone[11];charstrqq[10];intnum;charstrAddress六個(gè)數(shù)據(jù)域和structName*next一個(gè)地址域組成。構(gòu)造哈希表的函數(shù)主要是用除留取余法來構(gòu)造哈希函數(shù)的。沖突的解決采用鏈地址法，具體的實(shí)現(xiàn)思想是，所有同義詞構(gòu)成一個(gè)單鏈表，再由一個(gè)表頭結(jié)點(diǎn)指向這個(gè)單鏈表的第一個(gè)結(jié)點(diǎn)。這些表頭結(jié)點(diǎn)組成一個(gè)一維數(shù)組，即哈希表。數(shù)組元素的下標(biāo)對(duì)應(yīng)由散列函數(shù)求出的散列地址。第3章總體設(shè)計(jì)3.1系統(tǒng)數(shù)據(jù)結(jié)構(gòu)本設(shè)計(jì)涉及到的數(shù)據(jù)結(jié)構(gòu)為：哈希表。程序中建立了兩個(gè)結(jié)構(gòu)體，要求輸入電話號(hào)碼、用戶名、QQ、地址、四個(gè)信息，給structName結(jié)構(gòu)體變量，在創(chuàng)建哈希表時(shí)哈希函數(shù)用除留余數(shù)法構(gòu)照，并把structName結(jié)構(gòu)體中的數(shù)據(jù)賦值給哈希表結(jié)構(gòu)體。在鏈地址法中，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由六個(gè)域組成，鏈地址法結(jié)點(diǎn)結(jié)構(gòu)如表：strName[20]numstrAddress[30]strPhone[11]strClass[20]Nqqnext表3.1其中哈希表是以用戶名為關(guān)鍵字next指針是用來指向下一個(gè)結(jié)點(diǎn)的地址。具體的存儲(chǔ)結(jié)構(gòu)如下圖所示:圖3.1數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)圖3.2主要算法流程圖3.2.1以姓名為關(guān)鍵字的CreateHashList()函數(shù)流程圖建立第一個(gè)結(jié)點(diǎn)建立第一個(gè)結(jié)點(diǎn)開始結(jié)束初始化結(jié)構(gòu)體指針域?yàn)镹ULL定義i=0i<30intadr=(NameList[i].num)%M;HashList[adr].next！=NULLi++解決沖突結(jié)點(diǎn)的建立structHlist*q;pName*p,*m;q指向所要插入結(jié)點(diǎn)的地址，m指向所要插入結(jié)點(diǎn)指針的下一地址查找該地址的最后一個(gè)地址圖3.23.2.2哈希表查找算法流程圖查找到的數(shù)據(jù)結(jié)束開始輸出查找到的信息查找到的數(shù)據(jù)結(jié)束開始輸出查找到的信息定義數(shù)組name整型變量adr=0,s=0,r=0r<20adr=s%M;輸入查找姓名s+=name[r];r++HashList[adr].next!=NULL無該記錄判斷記錄的關(guān)鍵字與s相等HashList[adr].next)->next==NULL地址中單鏈表的循環(huán)遍歷查找圖3.33.2.3主程序流程圖Main()Main()定義int變量i,f=0InitNameList();Menu（）主菜單開始無限循環(huán)輸入選擇1-4選擇1選擇2選擇3選擇4defaultCreateHashList();CreateHashList();f==1f==1f=1哈希表未初始化哈希表未初始化Display();SearchList();return0選擇錯(cuò)誤，請(qǐng)從新輸入結(jié)束圖3.4第4章詳細(xì)設(shè)計(jì)和編碼4.1節(jié)點(diǎn)的建立定義結(jié)構(gòu)體如下所示:typedefstructName{ charstrName[20];//姓名charstrClass[20];//班級(jí) charstrPhone[11];//手機(jī)號(hào)碼 charstrAddress[30];//地址 charNqq[10];//QQ intnum;//關(guān)鍵字 structName*next;}pName;pNameNameList[HASH_LEN];pNamek;structHlist{ pName*next;}HashList[HASH_LEN];4.2對(duì)哈希函數(shù)的定義本程序設(shè)計(jì)一個(gè)hash()函數(shù)，本設(shè)計(jì)中按照題意要求知對(duì)散列函數(shù)選擇的是除留余數(shù)法，即對(duì)關(guān)鍵字進(jìn)行模運(yùn)算，將計(jì)算結(jié)果所得的余數(shù)作為關(guān)鍵字（或結(jié)點(diǎn)）的存儲(chǔ)地址，即H(key)=keymodp,在程序中p取的值為范圍內(nèi)的最大的素?cái)?shù)，以用戶名為關(guān)鍵字建立哈希函數(shù)CreateHash()，利用強(qiáng)制類型轉(zhuǎn)換將用戶名的每一個(gè)字母的ASCLL碼值相加并且除以范圍內(nèi)最大的素?cái)?shù)，將計(jì)算出來的數(shù)作為該結(jié)點(diǎn)的地址賦給adr。然后通過以下幾種方式就可以完成哈希表程序的設(shè)計(jì)了。4.3創(chuàng)建哈希表算法、代碼如下所示:4.3.1算法建立結(jié)點(diǎn)，并添加結(jié)點(diǎn)，利用鏈地址法解決沖突。建立結(jié)點(diǎn)應(yīng)包括動(dòng)態(tài)申請(qǐng)內(nèi)存空間。向結(jié)點(diǎn)中輸入信息。同時(shí)將結(jié)點(diǎn)中的next指針等于null。添加結(jié)點(diǎn)，首先需要利用哈希函數(shù)計(jì)算出地址即關(guān)鍵字，其次將該結(jié)點(diǎn)插入以關(guān)鍵字為地址的鏈表后。4.3.2代碼voidCreateHashList(){ inti;for(i=0;i<HASH_LEN;i++) { HashList[i].next=NULL; } for(i=0;i<2;i++) { structHlist*q; pName*p,*m; intadr=(NameList[i].num)%M;//哈希函數(shù) if(HashList[adr].next==NULL)//表明不沖突 {HashList[adr].next=&NameList[i]; } else//表明沖突 { q=&HashList[adr]; m=q->next; while(m->next!=NULL) { m=m->next; } p=(pName*)malloc(sizeof(pName));strcpy(p->strName,NameList[i].strName); strcpy(p->strPhone,NameList[i].strPhone); strcpy(p->strAddress,NameList[i].strAddress); strcpy(p->Nqq,NameList[i].Nqq); p->num=NameList[i].num; m->next=p;//單鏈表向后指 } }}4.4哈希查找想要實(shí)現(xiàn)查找功能，需要一個(gè)查找函數(shù)，以用戶名為關(guān)鍵字來實(shí)現(xiàn)查找，首先，需要利用hash函數(shù)來計(jì)算出地址。再通過比對(duì)，如果該地址中的用戶名拼音字符相加的num與查找的相同則輸出該結(jié)點(diǎn)的所有信息，否則輸出“無此記錄”。具體實(shí)現(xiàn)代碼如下所示:voidSearchList(){ system("cls"); char*f; printf("\n\n請(qǐng)輸入你要查找姓名（拼音）");//輸入姓名 charname[20]; scanf("%s",name); f=name; ints=0,r; for(r=0;*(f+r)!='\0';r++)//求出姓名的拼音所對(duì)應(yīng)的整數(shù)也就是關(guān)鍵字 { s+=(int)*(f+r);//利用字符與整數(shù)的自動(dòng)轉(zhuǎn)換相加字符的ASCII碼 } intadr=s%M;//使用哈希函數(shù) if(HashList[adr].next==NULL)//通過指針的指向判斷一個(gè)單鏈表中是否存在要查找的數(shù) { printf("無該記錄"); } else { if((HashList[adr].next)->next==NULL) { if((HashList[adr].next)->num==s) { inti=1;printf(“\n姓名:%s”,(HashList[adr].next)->strName);printf(“班級(jí):%s”,(HashList[adr].next)->strClass);printf(“電話:%s”,(HashList[adr].next)->strPhone);printf(“QQ:%s”,HashList[adr].next)->Nqq);printf(“地址:%s\n”,(HashList[adr].next)->strAddress);printf(“關(guān)鍵字:%d”,(HashList[adr].next)->num);printf(“查找長(zhǎng)度:%d”,i); } } else {pName*m; inti=1;m=HashList[adr].next; while(m->next!=NULL)//循環(huán)該單鏈表查找出你所要查找的數(shù)據(jù)并把他們輸出 { if(m->num==s) {Printf(“\n姓名:%s”,m->strName);Printf(“班級(jí):%s”,m->strClass);Printf(“電話:%s”,m->strPhone);Printf(“QQ：%s”,m->Nqq);Printf(“地址:%s”,m->strAddress);Printf(“關(guān)鍵字:%d”,m->num);printf("查找長(zhǎng)度:%d",i); break; } m=m->next; i++; } } }}4.5顯示哈希表通過姓名關(guān)鍵字，循環(huán)查找有值的下標(biāo)并輸出來,具體設(shè)計(jì)代碼如下：voidDisplay(){system("cls"); inti,s,j,adr,n=0; char*f; structHlist*m; structName*k; charname[20]; printf("\n\n下標(biāo)地址\t關(guān)鍵字\tH(key)\t拼音班級(jí)QQ地址電話\n");//顯示的格式 for(i=0;i<2;i++) { s=0; strcpy(name,NameList[i].strName); f=name; for(j=0;*(f+j)!='\0';j++) {s+=(int)*(f+j); } adr=s%M; m=&HashList[adr]; if(m->next!=NULL) {k=m->next; n+=1;while(k->next!=NULL) { printf("下標(biāo)地址:%d",i); printf("\t%d",k->num); printf("\t%d",(k->num)%M); printf("\t%s",k->strName); printf("%s",k->strClass); printf("%s",k->Nqq); printf("%s",k->strAddress); printf("%s",k->strPhone); printf("\n"); k=k->next; }printf("下標(biāo)地址:%d",i); printf("\t%d",k->num); printf("\t%d",(k->num)%M); printf("\t%s",k->strName);printf("%s",k->strClass); printf("%s",k->Nqq); printf("%s",k->strAddress); printf("%s",k->strPhone); printf("\n"); } }}4.6主菜單設(shè)計(jì)根據(jù)題目中的要求我們只要寫出哈希表的初始化查找顯示三個(gè)功能，代碼如下所示:voidMenu(){printf("\n哈希表的建立和查找操作"); printf("\n\n"); printf("1.哈希表初始化\n"); printf("2.顯示哈希表\n"); printf("3.查找\n"); printf("4.退出\n");}4.7主函數(shù)設(shè)計(jì)主函數(shù)是一個(gè)軟件運(yùn)行的入口，其通過調(diào)用自定義函數(shù)來完成相應(yīng)的功能,其實(shí)現(xiàn)代碼如下所示:intmain(intargc,char*argv[]){ inti,f=0; while(1) {Menu();scanf("%d",&i); switch(i) { case1:InitNameList();CreateHashList(); f=1; break; case2:if(f==1) { Display(); break; } else { printf("哈希表未初始化請(qǐng)先初始化再操作"); }break; case3:if(f==1) { SearchList(); } else { printf("哈希表未初始化請(qǐng)先初始化再操作"); } break; case4:return0; default:printf("請(qǐng)輸入正確的選項(xiàng)"); break; } }}第5章程序運(yùn)行測(cè)試5.1程序主界面圖5.1程序主界面5.2哈希表初始化測(cè)試數(shù)據(jù)(正確):姓名:kaluo班級(jí):305電話:123456789地址:長(zhǎng)沙涉外QQ:282265478姓名:tianxia

班級(jí):306電話:987654321地址:長(zhǎng)沙理工QQ:974562228姓名:xiantu

班級(jí):3076電話:987654322地址:長(zhǎng)沙學(xué)院QQ:974562222測(cè)試數(shù)據(jù)(錯(cuò)誤):姓名:張三(否拼音)

班級(jí):3077電話:987654322地址:長(zhǎng)沙學(xué)院QQ:974562222姓名:李四(否拼音)

班級(jí):3078電話:987654322地址:長(zhǎng)沙學(xué)院QQ:97