哈希表技術(shù)判別源程序的相似性實驗報告

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

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

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

3、取舍?需要積累經(jīng)驗，選擇合適的闌值。3)測試數(shù)據(jù):做兒個編譯和運(yùn)行都無誤的C程序，程序之問有相近的和差別大的，用上述方法求S}并對比差異程度。4)輸入輸出:輸入為若干個c源程序，輸出為程序問的相似度以及向量的幾何距離?；疽螅航⒐１?，統(tǒng)計源程序中關(guān)鍵字出現(xiàn)的頻度，并計算多個源程序之間的相似度。測試數(shù)據(jù)：自己在網(wǎng)上找到一些C語言程序，分別為test1.txt,test2.txt,test3.txt等。運(yùn)行結(jié)果應(yīng)為輸出每個源程序關(guān)鍵字的出現(xiàn)的頻度和源程序之間的相似度以及向量的幾何距離。二．需求分析1.本程序用來通過建立哈希表求源程序關(guān)鍵字的出現(xiàn)的頻度

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

5、ai∈ElemType,且各不相同，i=1,2...,n,n≥0}數(shù)據(jù)關(guān)系：R=φ基本操作：Hashfunc(charstr[]);Hashfind(char*words);creathash(void);r

6、esethash(intn);isletter(charch);readc(char*filename);getkey(char*str,intlen);copycount(intx[],intn);check(int*x1,int*x2);}endADT3.本程序?qū)崿F(xiàn)模塊主程序模塊哈希表程序模塊：實現(xiàn)哈希表的抽象數(shù)據(jù)類型主程序模塊調(diào)用關(guān)系：哈希表程序模塊計算相似度和向量的幾何距離的模塊四．詳細(xì)設(shè)計1.各個子函數(shù)的設(shè)計1）創(chuàng)建哈希表函數(shù)函數(shù)原型：voidcreathash(void);輸入：讀取存儲了32個關(guān)鍵字的文件ckey.txt思路：通過對cke

7、y.txt文件逐行賦值給創(chuàng)建的str字符數(shù)組，并將該數(shù)組調(diào)入Hashfunc函數(shù)。（2）將關(guān)鍵字根據(jù)哈希函數(shù)放入哈希表中的指定位置的函數(shù)函數(shù)原型：voidHashfunc(charstr[]);思路：對調(diào)進(jìn)來的str數(shù)組通過調(diào)用getkey函數(shù)得到該關(guān)鍵詞的key值后放入哈希表中的特定位置，并用線性探索來解決沖突。（3）在哈希表中找是否該words為關(guān)鍵字，并統(tǒng)計頻度的函數(shù)函數(shù)原型：intHashfind(char*words);思路：將調(diào)進(jìn)來的word字符數(shù)組先調(diào)用getkey函數(shù)獲取key值，然后在哈希表里查找是否存在該字符串，如果存在則該關(guān)鍵字對

8、應(yīng)的頻度加1.（4）重置哈希表函數(shù)函數(shù)原型：voidresethash(intn);功能：當(dāng)n為0時，將指向哈希表中關(guān)鍵字的指針置成Null，同時將頻度全部置為0.而當(dāng)n為1時，僅僅將頻度置為0.（5）獲取單詞key的函數(shù)函數(shù)原型：intgetkey(char*str,intlen);思路：用key1存儲關(guān)鍵字的首字母，key2存儲關(guān)鍵字的末字母，然后通過哈希函數(shù)得到key的值并返回。（6）判斷是否為字母的函數(shù)函數(shù)原型：intisletter(charch);思路：如果調(diào)進(jìn)來的ch字符的ASCII值在a~z或A~Z范圍內(nèi)的話則返回1，否則返回0.（7）

9、讀取源程序文件中的單詞的函數(shù)函數(shù)原型：intreadc(char*filename);思路：為