天津科技大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告-源程序的相似性

1、數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目：源程序的相似性專 業(yè)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)號(hào)14101103姓名.傅開煤2017年亠月日源程序的相似性一、問(wèn)題描述對(duì)于兩個(gè)C+語(yǔ)言的源程序代碼，用哈希表的方法分別統(tǒng)計(jì)兩個(gè)程序中使用 鍵字的情況，并最終按定量的計(jì)算結(jié)果，得出兩份程序的相似性。C+語(yǔ)言關(guān)二、需求分析建立C+語(yǔ)言關(guān)鍵字的哈希表，統(tǒng)計(jì)在每個(gè)源程序中向量X1和X2,通過(guò)計(jì)算向量 X1和X2的相對(duì)距離來(lái)判斷兩個(gè)源程序的相似性。 例如：C+關(guān)鍵字出現(xiàn)的頻度，得到兩個(gè)關(guān)鍵字程序1關(guān)鍵字頻度VoidIntForCharifelsewhiledobreakclass程序2關(guān)鍵字頻度X1=4,3,0,4,3,0,7,

2、0,0,2X2=4,2,0,5,4,0,5,2,0,1設(shè)s是向量X1和X2的相對(duì)距離，是同一個(gè)程序；s值越大，則兩個(gè)程序的差別可能也越大。s=sqrt(刀(Xi-x2i)2 ），當(dāng)X1=X2 時(shí)，s=0,反映出可能三、概要設(shè)計(jì)為了實(shí)現(xiàn)上述功能，可以用結(jié)構(gòu)體表示哈希表，因此需要哈希表的抽象數(shù)據(jù)類型。 哈希表抽象數(shù)據(jù)類型的定義：ADT hashtable數(shù)據(jù)對(duì)象:D=ai |a i C ElemType,且各不相同，i=1,2.,n,n > 0數(shù)據(jù)關(guān)系:基本操作:Hashfu nc(char str); Hashfi nd(char *words); creathash(void); res

3、ethash(i nt n); isletter(char ch); readc(char * file name); getkey(char *str,i nt len); cop yco un t(i nt x,i nt n); check(i nt *x1, i nt *x2);end ADT本程序?qū)崿F(xiàn)模塊主程序模塊哈希表程序模塊：實(shí)現(xiàn)哈希表的抽象數(shù)據(jù)類型 調(diào)用關(guān)系圖如下：哈希表程序模塊計(jì)算相似度和向量的幾何距離的模塊四、詳細(xì)設(shè)計(jì)1、各個(gè)子函數(shù)的設(shè)計(jì)（1 ）創(chuàng)建哈希表函數(shù)函數(shù)原型：void creathash（void）;輸入：讀取存儲(chǔ)了32個(gè)關(guān)鍵字的文件keyword.txt思路：通過(guò)

4、對(duì) keyword.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)來(lái)的str數(shù)組通過(guò)調(diào)用getkey函數(shù)得到該關(guān)鍵詞的key值后放入哈希表中的特定位置，并用線性探索來(lái)解決沖突。（3） 在哈希表中找是否該words為關(guān)鍵字，并統(tǒng)計(jì)頻度的函數(shù)函數(shù)原型：int Hashfi nd（char *words）;思路：將調(diào)進(jìn)來(lái)的word字符數(shù)組先調(diào)用 getkey函數(shù)獲取key值，然后在哈希表里查找 是否存在該字符串，如果存在則該關(guān)鍵字對(duì)應(yīng)的頻度加

5、（4 ）重置哈希表函數(shù)函數(shù)原型：void resethash（i nt n）;Null，同時(shí)將頻度全部置為0.功能：當(dāng)n為0時(shí)，將指向哈希表中關(guān)鍵字的指針置成而當(dāng)n為1時(shí)，僅僅將頻度置為0。（5 ）獲取單詞key的函數(shù)函數(shù)原型：in t getkey（char *str, in t le n）;思路：用key1存儲(chǔ)關(guān)鍵字的首字母，key2存儲(chǔ)關(guān)鍵字的末字母，然后通過(guò)哈希函數(shù)得 到key的值并返回。（6 ）判斷是否為字母的函數(shù)函數(shù)原型：int isletter(char ch);思路：如果調(diào)進(jìn)來(lái)的ch字符的ASCII值在az或AZ范圍內(nèi)的話則返回1，否則返回0。(7) 讀取源程序文件中的單詞的函

6、數(shù)函數(shù)原型：int readc(char * file name);如果讀的超過(guò)最大關(guān)Hashfind 函數(shù),思路：為了讀取源程序文件中的單詞， 所以一個(gè)字符一個(gè)字符的， 鍵字長(zhǎng)度將會(huì)跳過(guò)當(dāng)前識(shí)別區(qū)域，讀取下一個(gè)單詞，將得到的該單詞調(diào)入 來(lái)判斷是否為關(guān)鍵字，并統(tǒng)計(jì)頻度。(8) 將頻度拷貝到數(shù)組里的函數(shù)函數(shù)原型：void cop ycou nt(i nt x,i nt n);功能：將哈希表中關(guān)鍵字的頻度復(fù)制到x數(shù)組中，以便進(jìn)行后面相似度等的計(jì)算。(9) 檢查兩個(gè)源程序是否相似的函數(shù)函數(shù)原型：void check(i nt *x1, i nt *x2);思路：對(duì)調(diào)進(jìn)來(lái)的x1和x2數(shù)組進(jìn)行相似度計(jì)算

7、，若相似度大于設(shè)定好的閾值，則再進(jìn)行幾何距離計(jì)算，最后給出兩個(gè)文件是否相似的判斷。(10) 取模函數(shù)函數(shù)原型：float Mol(i nt *x);思路：通過(guò)求向量模值的數(shù)學(xué)知識(shí)求x數(shù)組的模。(11) 點(diǎn)積函數(shù)函數(shù)原型：int Dot(i nt *x1, i nt *x2)思路：通過(guò)點(diǎn)積的數(shù)學(xué)知識(shí)對(duì)兩個(gè)向量求點(diǎn)積。(12) 求相似度S的函數(shù)函數(shù)原型：float S(i nt *x1,i nt *x2);思路：根據(jù)題目給的求相似度的公式求x1和x2數(shù)組的相似度。(13) 求距離D的函數(shù)函數(shù)原型：float D(i nt *x1, i nt *x2);思路：用題目給的球幾何距離的公式求x1和x2數(shù)

8、組的幾何距離。2、主函數(shù)偽碼int mai n()char file name1="test1.txt"char file name2="test2.txt"char file name3="test3.txt"int x1hashle n,x2hashle n,x3hashle n; /* 算*/resethash(0); /* creathash(); / readc(file name1); / cop yco un t(x1,hashle n);resethash(1); / readc(file name2); / cop

9、yco un t(x2,hashle n);resethash(1);存儲(chǔ)頻度的數(shù)組，用于相似度S的計(jì)完全重置哈希表，即哈希指針置為NULL頻度置為0*/通過(guò)文件ckey.txt創(chuàng)建哈希表讀取第一個(gè)測(cè)試源程序文件講統(tǒng)計(jì)好的頻度復(fù)制給x數(shù)組僅僅將頻度count置為0同上/readc(file name3);cop yco un t(x3,hashle n);cout<<"t"<<"哈希序號(hào)"<<" t"<<" 關(guān)鍵字"<<" t"<

10、<" 頻度 1"<<" t"<<" 頻度 2"<<" t"<<" 頻度 3"<<endl;for (int i = 0; i < 41; i+)if(hashti.hash1!=NULL)t"<<hash ti .hash1<<"cout<<"t"<<i<<"t"<<x1i<<&qu

11、ot;t"<<x2i<<"t"<<x3i<<e ndl;cout<<file name1<<"和"<<file name2<<"的相似情況為："<<e ndl;check(x1,x2); /檢查相似度cout<<file name1<<"和"<<file name3<<"的相似情況為："<<e ndl;check(x1,

12、x3);cout<<file name2<<"和"<<file name3<<"的相似情況為："<<e ndl;check(x2,x3);return 0;3、調(diào)用關(guān)系圖調(diào)用關(guān)系圖如下:readccopycounresethaislettemain()creathashhashfi nd1p rgetkeyhashfu ncDotcheckDMol五、編碼實(shí)現(xiàn)1.使用函數(shù) void resethash(int n)來(lái)重置哈希表void resethash(i nt n) /if(n=0)/重置哈

13、希表 完全重置哈希表for(i nt i=0;i<41;i+)hashti.hash仁NULL; hashti.co un t=0;else if (n=1)/僅僅重置頻度f(wàn)or(i nt i=0;i<41;i+) hashti.co un t=0;2.使用 void copycount(int x,int n)來(lái)將頻度拷貝到數(shù)組里的函數(shù)void cop yco un t(i nt x,i nt n) /for (int i = 0; i < n; i+) xi=hashti.co unt;拷貝頻度3.使用 int getkey(char *str,int len) int

14、getkey(char *str,i nt len) /來(lái)獲取單詞key的函數(shù) 根據(jù)哈希函數(shù)獲取該單詞的_keychar key1,key2;int key;key1=str0;key2=strle n-1;key=(i nt)(key1*100+key2)%41;return key;4.使用void creathash(void)來(lái)創(chuàng)建哈希表函數(shù)對(duì)文件keyword.txt 中的32個(gè)關(guān)鍵字創(chuàng)建哈希表void creathash(void) / FILE *fp;暫時(shí)存儲(chǔ)關(guān)鍵字字符的數(shù)組int len gth;char strsize; /char *s=NULL;for (int i =

15、 0; i < size; i+)stri='0'if(fp=fo pen ("keyword.txt",T')=NULL)cout<<"ca n't creat file!' n" exit(0);while (fgets(str,size,fp)!=NULL)if (str=NULL)break;len gth=strle n( str);strle ngth-1='O' /Hashfu nc(str);fclose(fp);/讀取一行寫入一行調(diào)試后發(fā)現(xiàn)的，沒(méi)有這里就停止運(yùn)行了

16、5.使用void Hashfunc(char str)來(lái)將關(guān)鍵字根據(jù)哈希函數(shù)放入哈希表中的指定位置的函數(shù)將關(guān)鍵字根據(jù)哈希函數(shù)放入哈希表中的指定位置/void Hashfu nc(char str) int key,le n;len=strle n(str);key=getkey(str,le n);while (hashtkey%41.hash1!=NULL)線性探索/key+;hashtkey%41.hash1=(char*)malloc(sizeof(char)*(le n+1); strcpy(hashtkey%41.hash1,str);6.使用int Hashfind(char*wo

17、rds)來(lái)在哈希表中找是否該words為關(guān)鍵字，并統(tǒng)計(jì)頻度的函數(shù)int Hashfi nd(char *words) /int key,le n,find;len=strle n( words);key=getkey(words,le n);while(hashtkey.hash1=NULL)key+;key=key%41;if(strcm p( hashtkey.hash1,words)=0)在哈希表中找是否該 words為關(guān)鍵字，并統(tǒng)計(jì)頻度hashtkey.co un t+; return 1;for(fin d=key+1;fi nd<hashle n;fin d+) /*然后再?gòu)?/p>

18、頭找*/線性探查法順序查找哈希表中是否已存在關(guān)鍵字if(hashtfi nd.hash1!=NULL)if(strc mp (hashtfi nd.hash1,words)=0)hashtfi nd.co un t+;return 1;如果不在key位置則向往后線性查找,for(fin d=0;fi nd<key;fi nd+)if (hashtfi nd.hash1!=NULL)if(strc mp (hashtfi nd.hash1,words)=0)hashtfi nd.co un t+; return 1;return 0;7.使用 int readc(char * file n

19、ame) int readc(char *file name)/讀取源程序文件中的單詞來(lái)讀取源程序文件中的單詞的函數(shù)FILE *fp仁NULL;char wordsmaxle n,ch;int i;if(fp1=fo pen (file name,"r")=NULL)cout<<"ca n not creat file!' n" exit(0);while (!feof(fp1) /i=0;ch=fgetc(fp1); /結(jié)束返回1一個(gè)字符一個(gè)字符的讀while (isletter(ch)=0&&feof(fp1)=0

20、) ch=fgetc(fp1);while (isletter(ch)=1 &&feof(fp1)=0)if (i=maxle n) / elsewhile (isletter(ch)=1 &&feof(fp1)=0)ch=fgetc(fp1);i=0;break;超過(guò)最大關(guān)鍵字長(zhǎng)度將會(huì)跳過(guò)當(dāng)前識(shí)別區(qū)域，讀取下一個(gè)單詞wordsi+=ch; ch=fgetc(fp1);wordsi='0'Hashfind (words); /* 將得到的該單詞調(diào)入 Hashfind函數(shù)，來(lái)判斷是否為關(guān)鍵 字，并統(tǒng)計(jì)頻度*/fclose(fpl);return 0

21、;8.使用 float Mol(int *x)來(lái)取模函數(shù)float Mol(i nt *x) /取模函數(shù)int i = 0, sum = 0;for (i = 0; i < N; i+)sum += (xi * xi);return (float )po w(float)sum,0.5);int Dot(i nt *x1, i nt *x2) 點(diǎn)積函數(shù)int i = 0, sum = 0;for (i = 0; i < N; i+)sum += x1i * x2i;return sum;/9.使用 float S(int *x1,int *x2)、float D(int *x1,

22、int *x2)和 void check(int *x1,int *x2) 來(lái)分別求相似度 S的函數(shù)、求幾何距離 D函數(shù)和檢查兩個(gè)源程序是否相似的函數(shù) float S(int *x1,int *x2)return Dot(x1, x2)/(Mol(x1)*Mol(x2); /float D(i nt *x1, i nt *x2) /求相似度S求幾何距離int xN, i = 0;for (i = 0; i < N; i+) / xi= x1i - x2i;return Mol(x); /向量相減再求模void check(i nt *x1, i nt *x2)float xs = 0,

23、xd = 0;xs = S(x1, x2);cout<<"相似度 xs="<<xs<<endl;if (xs > Smax) / 先判斷S,若S大于閾值再計(jì)算幾何距離 xd = D(x1, x2);cout<<"幾何距離 xd="<<xd<<endl;if (xd < Dmi n) /如果幾何距離小于閾值則判斷為相似cout << "這兩個(gè)文件內(nèi)容確實(shí)可能相似"<<e ndl;Xelsecout << "這

24、兩個(gè)文件內(nèi)容可能不相似"<<e ndl;return;cout << "這兩個(gè)文件內(nèi)容不相似"<<e ndl; / 否則不相似 return;六、實(shí)驗(yàn)結(jié)果與分析實(shí)驗(yàn)上機(jī)測(cè)試結(jié)果如下圖所示: ' ©Use說(shuō)博開燉De曲（3小數(shù)険構(gòu)弓S送課設(shè)Debu或數(shù)據(jù)結(jié)構(gòu)與算送課說(shuō)ew哈希序號(hào)關(guān)鍵字頻度1頻度2頻度30enum0001estern0002goto0003int2136214long1015signed0006sizeof0007switch2123union00010char51511void1271212au

25、to00013const00014short00015double00016struct0I017typedef0101Svolatile00023for86824if13171325do20226break1041029while63630default01031return21233else65634register00035Unsigned00037static0I03Scase1141139continue00040float I000test 1. txt和test2, txt的相似情況為：相似度兀滬0. 920b07幾何距離莖1149這兩個(gè)文件內(nèi)容可能不相似搜狗拼音輸入法全：t的相似情況為：仔“一 1test 1. txt和test2. txt的相似悄況為： 相似度直護(hù)0. 920507幾何距離xd=13. 1149這兩個(gè)文件內(nèi)容可能不相似test 1. txt和tests, t其t的相似情況為： 相似度丫滬1/L伺駆離xd - 0這兩個(gè)文件內(nèi)穽確實(shí)可能相似tests, txt和tEst擊txt的相似情況為： 相似度乳滬920507幾何距離xdT3* 1149這兩個(gè)文件內(nèi)容可能不相似請(qǐng)按任竜鍵繼續(xù)，* * a狗拼音輸入法全：分析：實(shí)驗(yàn)上機(jī)運(yùn)行結(jié)果與實(shí)際結(jié)