哈希表技術(shù)判別源程序的相似性--實(shí)驗(yàn)報(bào)告

1、哈希表技術(shù)判別兩 個(gè)源程序的相似性實(shí)驗(yàn)報(bào)告Admi nistrator 2014-12-26一. 問題描述實(shí)驗(yàn)題目：對(duì)于兩個(gè) C語言的源程序清單，用哈希表的方法分別統(tǒng)計(jì)兩程序中使用C語言關(guān)鍵字的情況，并最終按定量的計(jì)算結(jié)果，得出兩份源程序的相似性。要求與提示：C語言關(guān)鍵字的哈希表可以自建，也可以采用下面的哈希函數(shù)作為參考：Hash（key）=（key第一個(gè)字符序號(hào)*100+key最后一個(gè)字符序號(hào)）41表長m取43。此題的工作主要是掃描給定的源程序，累計(jì)在每個(gè)源程序中C語言關(guān)鍵字出現(xiàn)的頻度。為保證查找效率，建議自建哈希表的平均查找長度不大于2。掃描兩個(gè)源程序所統(tǒng)計(jì)的所有關(guān)鍵字不同頻度，可以得到兩

2、個(gè)向量。如下面簡單的例子所示：關(guān)鍵字voidiritforcharifelaewhile程序1中關(guān)鍵字頻度4：343702程序2中關(guān)犍字頻度4254521哈希地址012345678g根據(jù)程序1和程序2中關(guān)鍵字出現(xiàn)的頻度，可提取到兩個(gè)程序的特征向量X1和X2,其中X1= (4 3 0 4 3 0 7 0 0 2)X2= (4 2 0 5 4 0 5 2 0 1)一般情況下，可以通過計(jì)算向量Xi和Xj的相似值來判斷對(duì)應(yīng)兩個(gè)程序的相似性，相似值的判別函數(shù)計(jì)算公式為：其A I "質(zhì)/肌覽的值介于o.nZ間，也稱廣義余弦，即 S<X =cose. X =X 時(shí)，（X r X 1 -1.

3、0-0: XX,并別恨大時(shí).S ）接近S 時(shí)姿近耐器 如Xl=«l 0廠莊2=（。丄）"則SXXj = OJ 6=»/2t町以用下山啲二維的團(tuán)示來直觀地衣示向戢的HI似用L色烏|：u章相做度示意圏fr此惜況卜一，連而粳做進(jìn)一步的韋恵*亦卜一圖所嚇;國3. 4向星JL何和離從圖中石: 圧悴S（扎，乂和g（芷龜）的估雄If的，但席規(guī)上必更郴忱囚此當(dāng)£值搖近工的時(shí)僦.為邂免惺判和個(gè)性5J能是夬州很小模值很大的囪量X應(yīng)當(dāng)再次計(jì)亂Z何的“幾科距離“ D（X,XJB Jt計(jì)祥含貰均：也尤八X討T K上J（£ 疋訂（*廠X#）<3-21最后的相似性判別

4、計(jì)算可分兩步完成：第一步用式（3-1）計(jì)算S,把接近1的保留，拋棄接近。的情況（把不相似的排除）；第二步對(duì)保留下來的特征向量，再用式（3-2）計(jì)算D,如D值也比較小，說明兩者對(duì)應(yīng)的程序確實(shí)可能相似（慎重肯定相似的）。S和D的值達(dá)到什么門限才能決定取舍？需要積累經(jīng)驗(yàn)，選擇合適的闌值。3）測試數(shù)據(jù)：做兒個(gè)編譯和運(yùn)行都無誤的C程序，程序之問有相近的和差別大的，用上述方法求S并對(duì)比差異程度。4）輸入輸出：輸入為若干個(gè)c源程序，輸出為程序問的相似度以及向量的幾何距離?；疽螅航⒐１恚y(tǒng)計(jì)源程序中關(guān)鍵字出現(xiàn)的頻度，并計(jì)算多個(gè)源程序之間的相似 度。測試數(shù)據(jù)：自己在網(wǎng)上找到一些C語言程序，分別為test

5、1.txt,test2.txt,test3.txt等。運(yùn)行結(jié)果應(yīng)為輸出每個(gè)源程序關(guān)鍵字的出現(xiàn)的頻度和源程序之間的相似度以及向量的幾何 距離。二. 需求分析1. 本程序用來通過建立哈希表求源程序關(guān)鍵字的出現(xiàn)的頻度和源程序之間的相似度以及向 量的幾何距離。2. 用戶可以將源程序的.txt文件放入hashtable文件夾中，運(yùn)行程序就可以輸出每個(gè)源程序 關(guān)鍵字的出現(xiàn)的頻度和源程序之間的相似度以及向量的幾何距離。三. 概要設(shè)計(jì)為了實(shí)現(xiàn)上述功能，可以用結(jié)構(gòu)體表示哈希表，因此需要哈希表的抽象數(shù)據(jù)類型。哈希表抽象數(shù)據(jù)類型的定義：ADT hashtable數(shù)據(jù)對(duì)象：D=ai |a i ElemType,且各不

6、相同，i=1,2.,n,n >0數(shù)據(jù)關(guān)系：R=0基本操作：Hashfu nc(char str);Hashfi nd(char *words); creathash(void); resethash(i nt n); isletter(char ch);readc(char * file name); getkey(char *str,i nt len); copyco un t(i nt x,i nt n); check(i nt *x1, i nt *x2);end ADT3. 本程序?qū)崿F(xiàn)模塊主程序模塊哈希表程序模塊：實(shí)現(xiàn)哈希表的抽象數(shù)據(jù)類型 調(diào)用關(guān)系：主程序模塊|哈希表程序模塊計(jì)算

7、相似度和向量的幾何距離的模塊四詳細(xì)設(shè)計(jì)1.各個(gè)子函數(shù)的設(shè)計(jì)1) 創(chuàng)建哈希表函數(shù)函數(shù)原型：void creathash(void);輸入：讀取存儲(chǔ)了32個(gè)關(guān)鍵字的文件 ckey.txt思路：通過對(duì) ckey.txt文件逐行賦值給創(chuàng)建的str字符數(shù)組，并將該數(shù)組調(diào)入Hashfunc 函數(shù)。(2) 將關(guān)鍵字根據(jù)哈希函數(shù)放入哈希表中的指定位置的函數(shù)函數(shù)原型：void Hashfu nc(char str);思路：對(duì)調(diào)進(jìn)來的str數(shù)組通過調(diào)用getkey函數(shù)得到該關(guān)鍵詞的key值后放入哈希表中的特定位置，并用線性探索來解決沖突。(3) 在哈希表中找是否該words為關(guān)鍵字，并統(tǒng)計(jì)頻度的函數(shù)函數(shù)原型：in

8、t Hashfi nd(char *words);思路：將調(diào)進(jìn)來的word字符數(shù)組先調(diào)用getkey函數(shù)獲取key值，然后在哈希表里查找是否存在該字符串，如果存在則該關(guān)鍵字對(duì)應(yīng)的頻度加1.(4) 重置哈希表函數(shù)函數(shù)原型：void resethash(i nt n);Null，同時(shí)將頻度全部置為功能：當(dāng)n為0時(shí)，將指向哈希表中關(guān)鍵字的指針置成0.而當(dāng)n為1時(shí)，僅僅將頻度置為 0.( 5)獲取單詞 key 的函數(shù)函數(shù)原型： int getkey(char *str,int len);思路：用 key1 存儲(chǔ)關(guān)鍵字的首字母， key2 存儲(chǔ)關(guān)鍵字的末字母，然后通過哈希函 數(shù)得到 key 的值并返回。

9、(6) 判斷是否為字母的函數(shù)函數(shù)原型： int isletter(char ch);思路：如果調(diào)進(jìn)來的ch字符的ASCII值在az或AZ范圍內(nèi)的話則返回1,否則返回 0.(7) 讀取源程序文件中的單詞的函數(shù)函數(shù)原型： int readc(char * filename);思路：為了讀取源程序文件中的單詞，所以一個(gè)字符一個(gè)字符的，如果讀的超過最 大關(guān)鍵字長度將會(huì)跳過當(dāng)前識(shí)別區(qū)域，讀取下一個(gè)單詞，將得到的該單詞調(diào)入Hashfind 函數(shù)，來判斷是否為關(guān)鍵字，并統(tǒng)計(jì)頻度。(8) 將頻度拷貝到數(shù)組里的函數(shù)函數(shù)原型： void copycount(int x,int n);功能：將哈希表中關(guān)鍵字的頻度復(fù)

10、制到 x 數(shù)組中，以便進(jìn)行后面相似度等的計(jì)算。(9) 檢查兩個(gè)源程序是否相似的函數(shù)函數(shù)原型： void check(int *x1, int *x2);思路：對(duì)調(diào)進(jìn)來的 x1 和 x2 數(shù)組進(jìn)行相似度計(jì)算，若相似度大于設(shè)定好的閾值，則 再進(jìn)行幾何距離計(jì)算，最后給出兩個(gè)文件是否相似的判斷。( 1 0)取模函數(shù)函數(shù)原型： float Mol(int *x);思路：通過求向量模值的數(shù)學(xué)知識(shí)求 x 數(shù)組的模( 1 1)點(diǎn)積函數(shù)函數(shù)原型： int Dot(int *x1, int *x2);思路：通過點(diǎn)積的數(shù)學(xué)知識(shí)對(duì)兩個(gè)向量求點(diǎn)積(12) 求相似度S的函數(shù)函數(shù)原型： float S(int *x1,in

11、t *x2);思路：根據(jù)題目給的求相似度的公式求x1和x2數(shù)組的相似度(13) 求距離D的函數(shù)函數(shù)原型： float D(int *x1, int *x2);思路：用題目給的球幾何距離的公式求 x1 和 x2 數(shù)組的幾何距離2主函數(shù)偽碼int main()char filename1="test1.txt"char filename2="test12.txt"char filename3="test13.txt"int x1hashlen,x2hashlen,x3hashlen;/存儲(chǔ)頻度的數(shù)組，用于相似度S的計(jì)算resethash(

12、0);/完全重置哈希表，即哈希指針置為NULL頻度置為0creathash();/通過文件ckey.txt 創(chuàng)建哈希表 readc(filename1);試源程序文件 copycount(x1,hashlen);頻度復(fù)制給 x 數(shù)組 resethash(1);count 置為 0 readc(filename2); copycount(x2,hashlen); resethash(1); readc(filename3); copycount(x3,hashlen); cout<<"t"<<" 哈希序號(hào) "<<&quo

13、t;/t"<<" 關(guān)鍵字 "<<"讀取第一個(gè)測講統(tǒng)計(jì)好的僅僅將頻度 同上t"<<" 頻度 1"<<"t"<<" 頻度 2"<<" t"<<" 頻度 3"<<endl; for (int i = 0; i < 41; i+)if(hashti.hash1!=NULL)cout<<"t"<<i<<

14、;"t"<<hashti.hash1<<"t"<<x1i<<"t"<<x2i<<" t"<<x3i<<endl;cout<<filename1<<" check(x1,x2);和"<<file name2<<"的相似情況為：/"<<endl;相似度cout<<filename1<<"和 &

15、quot;<<filename3<<"的相似情況為："<<endl;check(x1,x3);cout<<filename2<<"和 "<<filename3<<"的相似情況為："<<endl;check(x2,x3);檢查return 0;3. 調(diào)用關(guān)系圖readcisletterhashfi ndgetkeycopycountresethashcreathashhashfu ncSDotcheckDMol五調(diào)試分析1.遇到的問題分析1)

16、 ='與=的問題賦值號(hào)與等號(hào)的問題雖然平時(shí)一直都會(huì)注意，但是有時(shí)候粗心也容易犯錯(cuò)，就比如在 該 語 句 中 ：if(fp=fope n("ckey.txt","r")=NULL)寫 成 了if(fp=fope n( "ckey.txt","r")=NULL)，導(dǎo)致運(yùn)行時(shí)出現(xiàn)下圖Microsoft Visual C + + Debug LibraryDebug Assertion FailedlProgram F;數(shù)另詰溝皇臉h日5htabIELbughashtabIe.exeFile;Lin 居：50Exp

17、resdon： str != MULLFor nformatton on houv your program car cause an assertion failure-. $亡亡 the Vkusl C+ documentation on asserts.(Pfes& Retry to dbug the application中止舛葩(R)«M<B看到過一本講編程的書說為了避免這種錯(cuò)誤，可以#define = equal，這樣就變成了if(fp=fope n( "ckey.txt","r")equalNULL)。雖然這樣確實(shí)可

18、以避免該類錯(cuò)誤，但是我覺的也沒有太大的必要，只要平時(shí)注意點(diǎn)小心點(diǎn)就是了。而且如果在visual studio2012上編程時(shí)，一般是不允許出現(xiàn)fopen這種不安全函數(shù)的，要使用它推薦的fopen_s函數(shù)，使用如 下errno_t err:if (err-fopen_s t&fp, rF:WEiial Studio codeWHashWckey. txt % "e") ) 1=0) 'coutcan't ere at f lie iXri"exit (0):2) 第二個(gè)問題出現(xiàn)在creathash函數(shù)中，也比較難找。當(dāng)時(shí)程序沒有紅色的那兩句,

19、while (fgets(str,size,fp)!=NULL)/if (str=NULL)break;len gth=strle n( str);strle ngth-1='0：讀取一行寫入一行Hashfu nc(str); fclose(fp);接下來的是沒有那兩句的運(yùn)行后的窗口截圖bbC:wi 口 d owssyste m32cmd.exe哈希序號(hào)1floata頻度i頻度2U2tiF or050004vo Ltlie8&ault0Q7du0隹adoubleaEl7typedef0&11breakaa12rctjistGr3&13returnaa14if如果

20、加上那兩句紅色的語句后的運(yùn)行窗口就是這樣的C:wi ndowssystem 3 2cmd.exe哈希序號(hào)012710111Z131415161718232425262?Z? 自閭關(guān)畤frnutnint lonar ined s izenF quitch un ion chai* UD±d AUtO const &hoi*t double struct typedef volatile f ur*(1。 break float uh Lie頻度1002000阿000000a000000&10 0 0后來調(diào)試時(shí)發(fā)現(xiàn)，（就拿文件ckey.txt中的第一個(gè)關(guān)鍵字為例）ckey

21、lxt -記事本文件(F) 錨舊艷式Q直春M 勰動(dòng)H)auto b 匚 wak case char cons t continue default do double else enuin estern floa t for goto if int long register return shor t signed sizeof static struct switch typedef在沒有那兩句紅色語句時(shí)，調(diào)試窗口是這樣顯示的1 4 X闔nxn*rhar呂魏窗口胃部變晝 饑程 擡塊.說明在執(zhí)行逐行讀取關(guān)鍵字的那段代碼時(shí)，它把每一行的換行號(hào)也讀進(jìn)了str數(shù)組里,導(dǎo)致輸出時(shí)，每個(gè)關(guān)鍵字都做了換

22、行，便有了上面的第一個(gè)截圖。所以我的解決辦法就是加入紅色的那兩句，即length=strlen(str); strlength-1='O：也就是把最后的換行號(hào)替換為0 '.3) 第三個(gè)問題出現(xiàn)在 readc函數(shù)中。在下面代碼中原本沒有注銷的那一語句。1=0；wards i-n-=ch; rh=fgetc(fpl):/words if l;*/ Hashf ind (鴨qrd):felosa|fpl):所以導(dǎo)致這樣的結(jié)果:C:windowsAsystem32ctTid.exe哈希序號(hào)黃鍵字頻度i頻度20enuri001exterriAM2int003longf004&&#

23、163;griecl00&Srj.HeDF00&quitch7un Lon19char11wid12Aura13const丄415double1&&truGt001?def001Bvolatlie陌02,3f or0024if0025du002&break002?float0027uh lie00即統(tǒng)計(jì)不到源程序文件中的關(guān)鍵字的頻度，均顯示為0.然后進(jìn)行調(diào)試發(fā)現(xiàn)（就以讀取到的第一個(gè)單詞in elude為例）：M誨口轄期從調(diào)試窗口可看出讀取完一個(gè)完整的單詞后，它自己不能給該 word數(shù)組賦值0 '來結(jié)束,這樣導(dǎo)致的結(jié)果將會(huì)發(fā)生在Hashfind函數(shù)

24、中的strcmp函數(shù)中，即FTitchar 柿 ord?int keyj len,f ini.1 enF st r 1 en (wa r As):key=etkey (vords, len):whilr- (hasht key. hash 1 -MBLL)key+ ;key=key41.i i (st rciip (hasht k ey. hash w. i Is) =0)!hasht key * count+：ESt llfll 1 :for (find=jey+L : fen ; f ind.+)f線性探晉法li it (liasht £in.dj . tiash I !=J.

25、.Ll.)if (stramp (hashi: f ind. liashl、w r'is)=D)通過上網(wǎng)查資料后知道，strcmp函數(shù)進(jìn)行兩字符串比較時(shí)是兩個(gè)字符串自左向右逐個(gè)字符相比(按ASCII值大小相比較)，直到出現(xiàn)不同的字符或遇'0'為止。而我的 hashtkey.hash1 數(shù)組里的字符串為i, n,c,l,u,d,e0 '而 words 數(shù)組為i, n,c,l,u,d,e，所以比較的結(jié)果是它們不相等，就統(tǒng)計(jì)不到關(guān)鍵字的頻度。所以我的解決辦法即注銷的那句：wordsi='0：對(duì)每次讀到的單詞后都加一個(gè)0 '。4) 第四個(gè)問題出現(xiàn)在求幾何

26、距離的D函數(shù)。原本我是這樣寫的float D(int *X1, int *X2)int *X;X=Sub(X1, X2);return Mol(X);int *Sub(i nt *X1, i nt *X2)int XN, i = 0;for (i = 0; i < N; i+) Xi= X1i - X2i;return X; float Mol(i nt *X)int i = 0, sum = 0;for (i = 0; i < N; i+) sum += Xi * Xi;retur n (float)pow(sum,0.5);這樣運(yùn)行的結(jié)果就是求出來的幾何距離是個(gè)很奇怪的隨機(jī)數(shù)，

27、每運(yùn)行一次得出的結(jié)果都不一樣。原因在于在Sub函數(shù)中X數(shù)組是個(gè)局部變量， 返回的X只能是個(gè)指針，此時(shí)它已經(jīng)不代 表剛才指向的那個(gè)數(shù)組了，然后調(diào)進(jìn) Mol函數(shù)中，進(jìn)行的操作也只是對(duì) X的地址進(jìn)行操作，因?yàn)榈刂肥请S機(jī)數(shù)，所以返回的也是個(gè)隨機(jī)數(shù)。我所以我將這 D和Sub兩個(gè)函數(shù)直接合并為一個(gè)D函數(shù)float D(i nt *x1, i nt *x2)/int xN, i = 0;for (i = 0; i < N; i+)/xi= x1i - x2i;return Mol(x);/2.復(fù)雜度的分析本程序中沒有用到循環(huán)嵌套，所以每個(gè)函數(shù)的時(shí)間復(fù)雜度基本為 基本為0 (n)。六.使用說明，本程序的

28、主要功能就是統(tǒng)計(jì)源程序之間的相似度，求幾何距離向量相減再求模0(n),空間復(fù)雜度也所以使用者只需要將要檢測的源程序的txt文件放入該程序的工程文件夾中計(jì)算fl (FO卜墩掲結(jié)構(gòu)實(shí)驗(yàn) hashtable大小Debug2014/12/2& 星期ickeyntxt2014/12/2星期亠文4必檔1 <B雪劃0 hashtable.cpp2014/12/21.CPP文件g kb+* haGhtabla.dep2014/12/2&B.U.VC + + 6 Project4 KB hashtableTcb2014/12/26 星期¥匚十十 Intellisens,.41 K

29、Bhashtable, opt2O14/12/2&.U.OPT爻蚌4S KB_ haihtable.plg2014/12/2&B.U.，PLG文件1 KBtC5t1 tXt2014/12/3星朝1 KBtest2.txt234修4星期“1 KBte?t3.b<t2014/12/4 星眼,.1 KBtestl 1 .txtL T2014/12/43 KBtestl 2.txt.=2014/12/4 <.2 KBtesti 3.txt2014/1/4星期34乂植2 K8test21.txt2014/12/4星期乂4 乂稿4 KBtest22.txt2014/12/4 B

30、.3 KBte±t2 士 txt2014/12/4星朝亠乂奉乂植3 K8然后在修改讀取的文件名便可直接運(yùn)行了。 七測試結(jié)果H口沖J P關(guān)鍵字瓠度1頻度28enum0001extern0002int211e3longa3&4s igrned&00bsizeof£switchaa07unionaa010ClldFa0011uoida2312auto90013const母B014sliorta00IEdoublea90structa111?t j/pedef母22ISvolatilea0023f Ol*12424ifa3125do母BQ26breaka00a?f

31、loats9029uhilea1Q3Gdefault母a031return12033e Is e3994registeraaQ35mi? irntd0母B37statica0038case&0039cont inue&ae4Gsroto0Q8tcstl .Et和.txt的利似情況為：=0.872503迸兩f文件內(nèi)春不相位的擁似情況為：.txt相似度 xs=0.83770fi 迸兩個(gè)文件內(nèi)容不相似ItestlZ .m和te$tl3 . txt;的相愎情i兄為-似度 xs =0.927684|TL 何距離 x(l=4*79583 橋如并音螢薙半：穌才md" F:鑿據(jù)站構(gòu)實(shí)

32、驗(yàn) hashtab1eDebughashtd ble .exe'結(jié)果與實(shí)際結(jié)果相符，故可以認(rèn)為該程序是成功的。八心得與體會(huì)。1. 通過本實(shí)驗(yàn)讓我用程序?qū)ξ募牟僮饔辛烁畹睦斫?，知道了如果直接的逐行讀取文件 的話，換行號(hào)也會(huì)被讀進(jìn)去的。2. 對(duì)局部變量有了更好的理解。3學(xué)會(huì)了建立哈希表的過程，以及更好的掌握了調(diào)試這一功能。4.由于本程序的編寫和調(diào)試我是在visual studio2012 進(jìn)行的，所以上述截圖均為在該編輯環(huán)境中進(jìn)行的。使用 visual studio編程體會(huì)到了其功能之強(qiáng)大和方便。而且也更安全，例如它一般不允許 fopen , strcpy這種不安全函數(shù)，所以原本我用的

33、是Errnq_t err;if C(err-faperL.s,'r：Visu.al Studio codeWHshXXckey* txt'j "r") J=0)亡a'± err felt file ! _n":exit (0)；st rcpy_s Oiasht ke沖41. h弱hllen+l7 s : rj :這種visual推薦的安全函數(shù)。只是后來將代碼拷貝的VC+后這些安全函數(shù)不能用后，我又換了回來，但其他的基本不用改。九附完整源程序/哈希表統(tǒng)計(jì)源程序的相似度#in clude"iostream" #i

34、nclude"stdlib.h" #i nclude"stri ng"#i nclude"math.h"關(guān)鍵字個(gè)數(shù)關(guān)鍵字?jǐn)?shù)組長度哈希表長度相似度s的閾值的閾值#defi ne N 32/#defi ne size 256#defi ne maxle n 9/#defi ne hashlen 41/#defi ne Smax 0.9/#defi ne Dmin 2Dstruct hashtable/char *hash1;/int count;/結(jié)構(gòu)體數(shù)組哈希表指向關(guān)鍵字的指針 記錄頻度void Hashfu nc(char str);

35、/亠疋位置int Hashfi nd(char *words);/統(tǒng)計(jì)頻度void creathash(void);/int isletter(char ch);/float Mol(i nt *x);/int Dot( int *x1, i nt *x2);/hashthashle n;using n amespace std;將關(guān)鍵字根據(jù)哈希函數(shù)放入哈希表中的指在哈希表中找是否該 words為關(guān)鍵字，并創(chuàng)建哈希表判斷是否為字母取模函數(shù)點(diǎn)積函數(shù)float D(int *x1, int *x2);/求距離 D 的函數(shù)float S(int *x1,int *x2);/求相似度 S 的函數(shù)int

36、 readc(char * filename);/讀取源程序文件中的單詞int getkey(char *str,int len);/獲取該單詞的 keyvoid resethash(int n);/重置哈希表void copycount(int x,int n);/將頻道拷貝到數(shù)組里void check(int *x1, int *x2);/檢查兩個(gè)源程序是否相似int main()char filename1="test1.txt"char filename2="test12.txt"存儲(chǔ)頻度的數(shù)組，用完全重置哈希通過文件 ckey.txt 讀取第一

37、個(gè)測試源 講統(tǒng)計(jì)好的頻度 僅僅將頻度 同上char filename3="test13.txt"int x1hashlen,x2hashlen,x3hashlen; / 于相似度 S 的計(jì)算resethash(0); /表，即哈希指針置為NULL,頻度置為0creathash(); / 創(chuàng)建哈希表readc(filename1); / 程序文件copycount(x1,hashlen); / 復(fù)制給 x 數(shù)組resethash(1); /count 置為 0 readc(filename2); /copycount(x2,hashlen);resethash(1);read

38、c(filename3);copycount(x3,hashlen);關(guān)鍵字 "<<" t"<<" 頻度 1"<<" t"<<"cout<<"t"<<" 哈希序號(hào) "<<" t"<<"頻度 2"<<" t"<<" 頻度 3"<<endl;for (int i = 0;

39、 i < 41; i+)cout<<"t"<<i<<"if(hashti.hash1!=NULL)t"<<hashti.hash1<<"t"<<x1i<<" t"<<x2i<<" t"<<x3i<<endl; cout<<filename1<<" 和 "<<filename2<<"

40、的相似情況為： "<<endl;check(x1,x2); / 檢查相似 度cout<<filename1<<"和 "<<filename3<<" 的相似情況為："<<endl;check(x1,x3);cout<<filename2<<"和 "<<filename3<<" 的相似情況為： "<<endl;check(x2,x3); return 0;void resetha

41、sh(int n) /if(n=0) /for(int i=0;i<41;i+)hashti.hash1=NULL; hashti.count=0;else if (n=1) /for(int i=0;i<41;i+)hashti.count=0;void copycount(int x,int n) /for (int i = 0; i < n; i+)xi=hashti.count;int getkey(char *str,int len)/詞的 keychar key1,key2;int key;key1=str0;key2=strlen-1; key=(int)(ke

42、y1*100+key2)%41;return key;重置哈希表完全重置哈希表僅僅重置頻度拷貝頻度根據(jù)哈希函數(shù)獲取該單void creathash(void) 鍵字創(chuàng)建哈希表 FILE *fp; int length; char strsize; char *s=NULL; for (int i = 0; i < size; i+) stri='0' if(fp=fopen("ckey.txt","r")=NULL) /對(duì)文件 ckey.txt 中的 32 個(gè)關(guān)暫時(shí)存儲(chǔ)關(guān)鍵字字符的數(shù)組cout<<"can

43、9;t creat file!n" exit(0);while (fgets(str,size,fp)!=NULL) /if (str=NULL)break;length=strlen(str); strlength-1='0'止運(yùn)行了Hashfunc(str); fclose(fp);讀取一行寫入一行/調(diào)試后發(fā)現(xiàn)的，沒有這里就停void Hashfunc(char str) 放入哈希表中的指定位置 int key,len; len=strlen(str); key=getkey(str,len); while (hashtkey%41.hash1!=NULL) ke

44、y+;/hashtkey%41.hash1=(char*)malloc(sizeof(char)*(len+1); strcpy(hashtkey%41.hash1,str);將關(guān)鍵字根據(jù)哈希函數(shù)線性探索在哈希表中找是否該如果不在 key 位線性探查法順序查找哈希表int Hashfind(char *words) / words 為關(guān)鍵字，并統(tǒng)計(jì)頻度int key,len,find; len=strlen(words); key=getkey(words,len); while(hashtkey.hash1=NULL)key+; key=key%41;if(strcmp(hashtkey.h

45、ash1,words)=0)hashtkey.count+;return 1;for(find=key+1;find<hashlen;find+) / 置則向往后線性查找，然后再從頭找/ 中是否已存在關(guān)鍵字if(hashtfind.hash1!=NULL) if(strcmp(hashtfind.hash1,words)=0) hashtfind.count+; return 1;for(find=0;find<key;find+)if (hashtfind.hash1!=NULL)if(strcmp(hashtfind.hash1,words)=0)hashtfind.count+;return 1;return 0;int isletter (char ch)判斷 / 是否 ch 為字母if(ch>='a'&&am