解決哈希沖突

解決哈希沖突一、需求分析1、本程序由用戶輸入運(yùn)行命令和數(shù)據(jù)，運(yùn)行結(jié)果顯示在其后。2、程序執(zhí)行的命令包括：1）輸入相關(guān)信息，構(gòu)造一個(gè)指針型向量；2）輸入數(shù)據(jù)，保存在哈希表中；3）輸出用鏈地址法解決哈希沖突的結(jié)果。2、測試數(shù)據(jù)輸入：TNM（T表示hash表空間，N表示Hash函數(shù)的模，輸入的數(shù)據(jù)個(gè)數(shù)）865輸入的數(shù)據(jù)：7，13，10，16，22二、概要設(shè)計(jì)#include<iostream>usingnamespacestd;structChain{intm;Chain*next;};intT,M,N;intkey(intm,intn){returnm%n;}voidcreate(ChainChainHash[],intT,intM,intN){Chain*p;p=newChain;coutvv"輸入數(shù)據(jù)：\n";for(inti=0;i<M;i++){Chain*q=newChain;q->next=NULL;cin>>q->m;if(ChainHash[key(q->m,N)].next!=NULL){p=&ChainHash[key(q->m,N)];while(p->next!=NULL){p=p->next;}p->next=q;}else{ChainHash[key(q->m,N)].next=q;}}}voidout_put(Chaina){Chain*p=a.next;if(p==NULL){coutvv"A"vvendl;}else{while(p!=NULL){cout<<"->"<<p->m;p=p->next;}cout<<endl;}}voidoutput(Chaina[],intT){for(inti=0;i<T;i++){cout<<i;out_put(a[i]);}}voidmain(){intT=0,M=0,N=0;ChainChainHash[30];coutvv"輸入Hash表空間:T=";cin?T;coutvv"輸入Hash函數(shù)的模:N=";cin?N;coutvv"輸入的數(shù)據(jù)個(gè)數(shù)M=";cin?M;for(inti=0;i<T;i++){ChainHash[i].next=NULL;}create(ChainHash,T,M,N);output(ChainHash,T);coutvv"ASL=(l*2+2*2+3)/M="vv(l*2+2*2+3)/Mvvendl;}四、調(diào)試分析在編寫時(shí)程序時(shí)，沒有認(rèn)真考慮鏈表的連接問題，總是出現(xiàn)鏈表連不上的情況。經(jīng)過調(diào)試分析后，我終于找到了問題的所在。不但解決了問題，同時(shí)還加深了我對鏈表存儲(chǔ)結(jié)構(gòu)的理解。還有，在編寫的時(shí)候，對于用鏈地址法解決哈希沖突是第一次，所以剛開始不知該如何下手。之后，經(jīng)過查資料和認(rèn)真