使用哈希表技術(shù)判別兩個源程序的相似性.doc

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

1、實(shí)習(xí)六使用哈希表技術(shù)判別兩個源程序的相似性［問題描述］對于兩個C語言的源程序清單，用哈希表的方法分別統(tǒng)計(jì)兩程序中使用C語言關(guān)鍵字的情況，并最終按定量的計(jì)算結(jié)果，得出兩份源程序清單的相似性。［基本要求］C語言關(guān)鍵字的哈希表自建，此題的工作只要是掃描給定的源程序，累計(jì)在每個源程序中C語言關(guān)鍵字出現(xiàn)的頻度。在掃描源程序過程中，每遇到關(guān)鍵字就查找哈希表，并累加相應(yīng)關(guān)鍵字出現(xiàn)的頻度。為保證查找效率，建議自建哈希表的平均查找長度ASL不大于2。掃描兩個源程序所統(tǒng)計(jì)的所有關(guān)鍵字不同頻度，可以得到兩個向量。如下面簡單的例子所示：Voidintforchar

2、ifelseWhile43437024254521關(guān)鍵字程序1種關(guān)鍵字頻度程序2中關(guān)鍵字頻度0123456789哈希地址X1=[4，3，0，4，3，0，7，0，0，2]X2=[4，2，0，5，4，0，5，2，0，1]通過計(jì)算向量X1和X2的相對距離來判斷兩個源程序的相似性，相對距離的計(jì)算方法是按例子所給數(shù)據(jù)，S≈0.13。顯然當(dāng)X1=X2時，S=0,反映出可能是同一個程序；S值越大，則兩個程序的差別可能也越大。[測試數(shù)據(jù)]作幾個編譯和運(yùn)行都無誤的C程序，程序之間有相近的和差別大的，用上述方法求S,并對比差異程度。[實(shí)現(xiàn)提示]本題的很大工作量

3、將是對源程序掃描，區(qū)分出C程序的每一關(guān)鍵字。可以為C語言關(guān)鍵字建一棵鍵樹，掃描源程序和在鍵樹種查找同步進(jìn)行，也取得每一個關(guān)鍵字。[問題討論]這種判斷方法只是提供一種輔助手段，即便S=0也可能不是同一程序，S的值很大，也可能算法完全是一樣的。例如，一個程序使用while語句，另一個使用for語句，但功能完全相同。事實(shí)上，當(dāng)發(fā)現(xiàn)s的值很小時，就應(yīng)該以人工干預(yù)來區(qū)分。