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

《哈希表技術(shù)判別源程序地相似性實(shí)驗(yàn)報(bào)告材料》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

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

2、源程序所統(tǒng)計(jì)的所有關(guān)鍵字不同頻度，可以得到兩個(gè)向量。如下面簡(jiǎn)單的例子所示：根據(jù)程序1和程序2中關(guān)鍵字出現(xiàn)的頻度，可提取到兩個(gè)程序的特征向量X1和X2，其中X1=(4304307002)TX2=(4205405201)T一般情況下，可以通過(guò)計(jì)算向量Xi和Xj的相似值來(lái)判斷對(duì)應(yīng)兩個(gè)程序的相似性，相似值的判別函數(shù)計(jì)算公式為:最后的相似性判別計(jì)算可分兩步完成:第一步用式(3-1)計(jì)算S，把接近1的保留，拋棄接近。的情況(把不相似的排除);第二步對(duì)保留下來(lái)的特征向量，再用式(3-2)計(jì)算D，如D值也比較小，說(shuō)明兩者對(duì)應(yīng)的程序確實(shí)

3、可能相似(慎重肯定相似的)。S和D的值達(dá)到什么門(mén)限才能決定取舍?需要積累經(jīng)驗(yàn)，選擇合適的闌值。3)測(cè)試數(shù)據(jù):做兒個(gè)編譯和運(yùn)行都無(wú)誤的C程序，程序之問(wèn)有相近的和差別大的，用上述方法求S}并對(duì)比差異程度。4)輸入輸出:輸入為若干個(gè)c源程序，輸出為程序問(wèn)的相似度以及向量的幾何距離?；疽螅航⒐１?，統(tǒng)計(jì)源程序中關(guān)鍵字出現(xiàn)的頻度，并計(jì)算多個(gè)源程序之間的相似度。測(cè)試數(shù)據(jù)：自己在網(wǎng)上找到一些C語(yǔ)言程序，分別為test1.txt,test2.txt,test3.txt等。運(yùn)行結(jié)果應(yīng)為輸出每個(gè)源程序關(guān)鍵字的出現(xiàn)的頻度和源程序之間的

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

5、ai∈ElemType,且各不相同，i=1,2...,n,n≥0}數(shù)據(jù)關(guān)系：R=φ

6、基本操作：Hashfunc(charstr[]);Hashfind(char*words);creathash(void);resethash(intn);isletter(charch);readc(char*filename);getkey(char*str,intlen);copycount(intx[],intn);check(int*x1,int*x2);}endADT3.本程序?qū)崿F(xiàn)模塊主程序模塊哈希表程序模塊：實(shí)現(xiàn)哈希表的抽象數(shù)據(jù)類(lèi)型主程序模塊調(diào)用關(guān)系：哈希表程序模塊計(jì)算相似度和向量的幾何距離的模塊四．詳細(xì)

7、設(shè)計(jì)1.各個(gè)子函數(shù)的設(shè)計(jì)1）創(chuàng)建哈希表函數(shù)函數(shù)原型：voidcreathash(void);輸入：讀取存儲(chǔ)了32個(gè)關(guān)鍵字的文件ckey.txt思路：通過(guò)對(duì)ckey.txt文件逐行賦值給創(chuàng)建的str字符數(shù)組，并將該數(shù)組調(diào)入Hashfunc函數(shù)。（2）將關(guān)鍵字根據(jù)哈希函數(shù)放入哈希表中的指定位置的函數(shù)函數(shù)原型：voidHashfunc(charstr[]);思路：對(duì)調(diào)進(jìn)來(lái)的str數(shù)組通過(guò)調(diào)用getkey函數(shù)得到該關(guān)鍵詞的key值后放入哈希表中的特定位置，并用線(xiàn)性探索來(lái)解決沖突。（3）在哈希表中找是否該words為關(guān)鍵字，并統(tǒng)

8、計(jì)頻度的函數(shù)函數(shù)原型：intHashfind(char*words);思路：將調(diào)進(jìn)來(lái)的word字符數(shù)組先調(diào)用getkey函數(shù)獲取key值，然后在哈希表里查找是否存在該字符串，如果存在則該關(guān)鍵字對(duì)應(yīng)的頻度加1.（4）重置哈希表函數(shù)函數(shù)原型：voidresethash(intn);功能：當(dāng)n為0時(shí)，將指向哈希表中關(guān)鍵字的指針置成Null，同時(shí)將頻度全部置為0.而當(dāng)n為1時(shí)，僅僅將頻度置為0.（5）獲取單詞key的函數(shù)函數(shù)原型：intgetkey(char*str,intlen);思路：用key1存儲(chǔ)關(guān)鍵字的首字母，key2

9、存儲(chǔ)關(guān)鍵字的末字母，然后通過(guò)哈希函數(shù)得到key的值并返回。（6）判斷是否為字母的函數(shù)函數(shù)原型：intisletter(charch);思路：如果調(diào)進(jìn)來(lái)的ch字符的ASCII值在a~z或A~Z范圍內(nèi)的話(huà)則返回1，否則返回0.（7）讀取源程序文件中的單詞的函數(shù)函數(shù)原型：intreadc(char*filename);思路：為了讀取源程