哈希表-算法-hash表-C++實(shí)現(xiàn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)哈希表算法hash表問(wèn)題描述：針對(duì)某個(gè)集體（比如你所在的班級(jí)）中的“人名”設(shè)計(jì)一個(gè)哈希表，使得平均查找長(zhǎng)度不超過(guò)R，完成相應(yīng)的建表和查表程序?；疽螅杭僭O(shè)人名為中國(guó)人姓名的漢語(yǔ)拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長(zhǎng)度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測(cè)再散列發(fā)處理沖突。#include #include #include /#include #define HASH_LEN 50 /哈希表的長(zhǎng)度 #define M 47 #define N

2、AME_NO 30 /人名的個(gè)數(shù) typedef struct NAME char *py; /名字的拼音 int k; /拼音所對(duì)應(yīng)的整數(shù) NAME; NAME NameListHASH_LEN; typedef struct hterm /哈希表 char *py; /名字的拼音 int k; /拼音所對(duì)應(yīng)的整數(shù) int si; /查找長(zhǎng)度 HASH; HASH HashListHASH_LEN; /*-姓名（結(jié)構(gòu)體數(shù)組）初始化-*/ void InitNameList() NameList0.py=zhanghongshuai;NameList1.py=xurensong;NameLis

3、t2.py=huangxiangyu;NameList3.py=luoqi;NameList4.py=zhangsan;NameList5.py=lisi;NameList6.py=wangwu;NameList7.py=renwei;NameList8.py=zhangchu;NameList9.py=wangmengyuan;NameList10.py=libaohua;NameList11.py=zhaoyanlong;NameList12.py=jwangyuxin;NameList13.py=duyanmo;NameList14.py=wangmingyang;NameList15.

4、py=lijiawei;NameList16.py=hesiyu;NameList17.py=zhanghailong;NameList18.py=lixinyu;NameList19.py=songdiyao;NameList20.py=zhaomingzhi;NameList21.py=zhangchenglong;NameList22.py=sunjie;NameList23.py=zhangdongmei;NameList24.py=antianyu;NameList25.py=zhulaiao;NameList26.py=wangyuting;NameList27.py=wangxi

5、liang;NameList28.py=zhangdeshuai;NameList29.py=xumingming; char *f; int r,s0; for (int i=0;iNAME_NO;i+)/ 求出各個(gè)姓名的拼音所對(duì)應(yīng)的整數(shù) s0=0; f=NameListi.py; for (r=0;*(f+r) != 0;r+) /方法：將字符串的各個(gè)字符所對(duì)應(yīng)的ASCII碼相加，所得的整數(shù)做為哈希表的關(guān)鍵字 s0=*(f+r)+s0; NameListi.k=s0; /*-建立哈希表-*/ void CreateHashList() for (int i=0; iHASH_LEN;i+)

6、/哈希表的初始化 HashListi.py=; HashListi.k=0; HashListi.si=0; for (int i=0; i=NAME_NO;) int sum=0; int adr=(NameListi.k) % M; /哈希函數(shù) int d=adr; if(HashListadr.si=0) /如果不沖突 HashListadr.k=NameListi.k; HashListadr.py=NameListi.py; HashListadr.si=1; else /沖突 do d=(d+(NameListi.k)%10+1)%M; /偽散列 sum=sum+1; /查找次數(shù)加

7、1 while (HashListd.k!=0); HashListd.k=NameListi.k; HashListd.py=NameListi.py; HashListd.si=sum+1; i+; /*-查找-*/ void FindList() printf(nn請(qǐng)輸入姓名的拼音: ); /輸入姓名 char name20=0; scanf(%s,name); int s0=0; for (int r=0;r20;r+) /求出姓名的拼音所對(duì)應(yīng)的整數(shù)(關(guān)鍵字) s0+=namer; int sum=1; int adr=s0 % M; /使用哈希函數(shù) int d=adr; if(Has

8、hListadr.k=s0) /分3種情況進(jìn)行判斷 printf(n姓名:%s 關(guān)鍵字:%d 查找長(zhǎng)度為: 1,HashListd.py,s0); else if (HashListadr.k=0) printf(無(wú)該記錄!); else int g=0; do d=(d+s0%10+1)%M; /偽散列 sum=sum+1; if (HashListd.k=0) printf(無(wú)記錄! ); g=1; if (HashListd.k=s0) printf(n姓名:%s 關(guān)鍵字:%d 查找長(zhǎng)度為:%d,HashListd.py,s0,sum); g=1; while(g=0); /*-顯示哈希

9、表-*/ void Display() printf(nn地址t關(guān)鍵字tt搜索長(zhǎng)度tH(key)tt拼音 n); /顯示的格式 for(int i=0; i15; i+) printf(%d ,i); printf(t%d ,HashListi.k); printf(tt%d ,HashListi.si); printf(tt%d ,(HashListi.k)%M); printf(t %s ,HashListi.py); printf(n); / printf(按任意鍵繼續(xù)顯示.n); /由于數(shù)據(jù)比較多，所以分屏顯示（以便在Win9xDOS下能看到所有的數(shù)據(jù)） / getch(); for(

10、 int i=15; i30; i+) printf(%d ,i); printf(t%d ,HashListi.k); printf(tt%d ,HashListi.si); printf(tt%d ,(HashListi.k)%M); printf(t %s ,HashListi.py); printf(n); / printf(按任意鍵繼續(xù)顯示.n); / getch(); for( int i=30; i40; i+) printf(%d ,i); printf(t%d ,HashListi.k); printf(tt%d ,HashListi.si); printf(tt%d ,(H

11、ashListi.k)%M); printf(t %s ,HashListi.py); printf(n); /printf(按任意鍵繼續(xù)顯示.n); /getch(); for( int i=40; i50; i+) printf(%d ,i); printf(t%d ,HashListi.k); printf(tt%d ,HashListi.si); printf(tt%d ,(HashListi.k)%M); printf(t %s ,HashListi.py); printf(n); float average=0; for (int i=0;iHASH_LEN;i+) average

12、+=HashListi.si; average/=NAME_NO; printf(nn平均查找長(zhǎng)度：ASL(%d)=%f nn,NAME_NO,average); /*-主函數(shù)-*/ main() /* :SetConsoleTitle(哈希表操作); /Windows API函數(shù),設(shè)置控制臺(tái)窗口的標(biāo)題 HANDLE hCon = :GetStdHandle(STD_OUTPUT_HANDLE); /獲得標(biāo)準(zhǔn)輸出設(shè)備的句柄 :SetConsoleTextAttribute(hCon, 10|0); /設(shè)置文本顏色 */ printf(n-哈希表的建立和查找-); InitNameList(); CreateHashList (); while(1) printf(nn); printf( 1. 顯示哈