資源描述：
《哈希表技術(shù)判別源程序的相似性--實驗分析報告.docx》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、哈希表技術(shù)判別源程序的相似性--實驗報告————————————————————————————————作者：————————————————————————————————日期：23哈希表技術(shù)判別兩個源程序的相似性實驗報告USER2014-12-2623一.問題描述實驗題目：對于兩個C語言的源程序清單，用哈希表的方法分別統(tǒng)計兩程序中使用C語言關(guān)鍵字的情況，并最終按定量的計算結(jié)果，得出兩份源程序的相似性。要求與提示：C語言關(guān)鍵字的哈希表可以自建，也可以采用下面的哈希函數(shù)作為參考：Hash(key
2、)=(key第一個字符序號*100+key最后一個字符序號)%41表長m取43。此題的工作主要是掃描給定的源程序，累計在每個源程序中C語言關(guān)鍵字出現(xiàn)的頻度。為保證查找效率，建議自建哈希表的平均查找長度不大于2。掃描兩個源程序所統(tǒng)計的所有關(guān)鍵字不同頻度，可以得到兩個向量。如下面簡單的例子所示：根據(jù)程序1和程序2中關(guān)鍵字出現(xiàn)的頻度，可提取到兩個程序的特征向量X1和X2，其中X1=(4304307002)TX2=(4205405201)T一般情況下，可以通過計算向量Xi和Xj的相似值來判斷對應(yīng)兩個程序
3、的相似性，相似值的判別函數(shù)計算公式為:23最后的相似性判別計算可分兩步完成:第一步用式(3-1)計算S，把接近1的保留，拋棄接近。的情況(把不相似的排除);第二步對保留下來的特征向量，再用式(3-2)計算D，如D值也比較小，說明兩者對應(yīng)的程序確實可能相似(慎重肯定相似的)。S和D的值達到什么門限才能決定取舍?需要積累經(jīng)驗，選擇合適的闌值。3)測試數(shù)據(jù):做兒個編譯和運行都無誤的C程序，程序之問有相近的和差別大的，用上述方法求S}并對比差異程度。4)輸入輸出:輸入為若干個c源程序，輸出為程序問的相似
4、度以及向量的幾何距離。基本要求：建立哈希表，統(tǒng)計源程序中關(guān)鍵字出現(xiàn)的頻度，并計算多個源程序之間的相似度。測試數(shù)據(jù)：自己在網(wǎng)上找到一些C語言程序，分別為test1.txt,test2.txt,test3.txt等。運行結(jié)果應(yīng)為輸出每個源程序關(guān)鍵字的出現(xiàn)的頻度和源程序之間的相似度以及向量的幾何距離。二．需求分析231.本程序用來通過建立哈希表求源程序關(guān)鍵字的出現(xiàn)的頻度和源程序之間的相似度以及向量的幾何距離。2.用戶可以將源程序的.txt文件放入hashtable文件夾中，運行程序就可以輸出每個源程序
5、關(guān)鍵字的出現(xiàn)的頻度和源程序之間的相似度以及向量的幾何距離。三．概要設(shè)計為了實現(xiàn)上述功能，可以用結(jié)構(gòu)體表示哈希表，因此需要哈希表的抽象數(shù)據(jù)類型。哈希表抽象數(shù)據(jù)類型的定義：ADThashtable{數(shù)據(jù)對象：D={ai
6、ai∈ElemType,且各不相同，i=1,2...,n,n≥0}數(shù)據(jù)關(guān)系：R=φ基本操作：Hashfunc(charstr[]);Hashfind(char*words);creathash(void);resethash(intn);isletter(charch);readc(
7、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)系：哈希表程序模塊計算相似度和向量的幾何距離的模塊四．詳細設(shè)計1.各個子函數(shù)的設(shè)計1）創(chuàng)建哈希表函數(shù)函數(shù)原型：voidcreathash(void);輸入：讀取存儲了32個關(guān)鍵字的文件ckey.txt思路：通過對ckey.txt文件逐行
8、賦值給創(chuàng)建的str字符數(shù)組，并將該數(shù)組調(diào)入Hashfunc函數(shù)。（2）將關(guān)鍵字根據(jù)哈希函數(shù)放入哈希表中的指定位置的函數(shù)23函數(shù)原型：voidHashfunc(charstr[]);思路：對調(diào)進來的str數(shù)組通過調(diào)用getkey函數(shù)得到該關(guān)鍵詞的key值后放入哈希表中的特定位置，并用線性探索來解決沖突。（3）在哈希表中找是否該words為關(guān)鍵字，并統(tǒng)計頻度的函數(shù)函數(shù)原型：intHashfind(char*words);思路：將調(diào)進來的word字符數(shù)組先調(diào)用getkey函數(shù)獲取key值，然后在哈希表
9、里查找是否存在該字符串，如果存在則該關(guān)鍵字對應(yīng)的頻度加1.（4）重置哈希表函數(shù)函數(shù)原型：voidresethash(intn);功能：當n為0時，將指向哈希表中關(guān)鍵字的指針置成Null，同時將頻度全部置為0.而當n為1時，僅僅將頻度置為0.（5）獲取單詞key的函數(shù)函數(shù)原型：intgetkey(char*str,intlen);思路：用key1存儲關(guān)鍵字的首字母，key2存儲關(guān)鍵字的末字母，然后通過哈希函數(shù)得到key的值并返回。（6）判斷是否為字母的函數(shù)函數(shù)原型：intisletter(char
