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

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

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

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

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

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

6、了讀取源程序文件中的單詞，所以一個字符一個字符的，如果讀的超過最大關(guān) 鍵字長度將會跳過當(dāng)前識別區(qū)域，讀取下一個單詞，將得到的該單詞調(diào)入Hashfind函數(shù)， 來判斷是否為關(guān)鍵字，并統(tǒng)計頻度。將頻度拷貝到數(shù)組里的函數(shù)函數(shù)原型：void copycount(int x,int n);功能：將哈希表中關(guān)鍵字的頻度復(fù)制到x數(shù)組中，以便進(jìn)行后面相似度等的計算。檢查兩個源程序是否相似的函數(shù)函數(shù)原型：void check(int *x1, int *x2);思路：對調(diào)進(jìn)來的x1和x2數(shù)組進(jìn)行相似度計算，若相似度大于設(shè)定好的閾值，則再進(jìn) 行幾何距離計算，最后給出兩個文件是否相似的判斷。取模函數(shù)函數(shù)原型：flo

7、at Mol(int *x);思路：通過求向量模值的數(shù)學(xué)知識求x數(shù)組的模。點(diǎn)積函數(shù)函數(shù)原型：int Dot(int *x1, int *x2)思路：通過點(diǎn)積的數(shù)學(xué)知識對兩個向量求點(diǎn)積。求相似度S的函數(shù)函數(shù)原型：float S(int *x1,int *x2);思路：根據(jù)題目給的求相似度的公式求x1和x2數(shù)組的相似度。求距離D的函數(shù)函數(shù)原型：float D(int *x1, int *x2);思路：用題目給的球幾何距離的公式求x1和x2數(shù)組的幾何距離。2、主函數(shù)偽碼 int main()(char filename1=test1.txt;char filename2 = test2.txt;ch

8、ar filename3 = test3.txt;int x1hashlen,x2hashlen,x3hashlen; /*存儲頻度的數(shù)組，用于相似度 S 的計 算*/resethash(0);/*完全重置哈希表，即哈希指針置為NULL，頻度置為0*/creathash();/通過文件ckey.txt創(chuàng)建哈希表readc(filenamel); /讀取第一個測試源程序文件copycount(x1,hashlen); /講統(tǒng)計好的頻度復(fù)制給x數(shù)組resethash(l);/僅僅將頻度count置為0readc(filename2);/同上copycount(x2,hashlen);resetha

9、sh(1);readc(filename3);copycount(x3,hashlen);coutt哈希序號t關(guān)鍵字t頻度 1t頻度 2t頻度 3endl;for (int i = 0; i 41; i+)(if(hashti.hash1!=NULL)(couttithashti.hash1tx1itx2itx3iendl;coutfilename1和filename2 的相似情況為：endl;check(x1,x2);/檢查相似度coutfilename1和filename3 的相似情況為：endl;check(x1,x3);coutfilename2和filename3 的相似情況為：en

10、dl;check(x2,x3);return 0;3、調(diào)用關(guān)系圖調(diào)用關(guān)系圖如下:getkey五、編碼實(shí)現(xiàn)1.使用函數(shù)void resethash(int n)來重置哈希表 void resethash(int n)重置哈希表if(n=0)/完全重置哈希表for(int i=0;i41;i+)hashti.hash1=NULL;hashti.count=0;else if (n=1)/僅僅重置頻度for(int i=0;i41;i+)hashti.count=0; 2.使用void copycount(int x,int n)來將頻度拷貝到數(shù)組里的函數(shù) void copycount(int x,

11、int n)/拷貝頻度for (int i = 0; i n; i+)xi=hashti.count;使用 int getkey(char *str,int len)來獲取單詞 key 的函數(shù)int getkey(char *str,int len)/根據(jù)哈希函數(shù)獲取該單詞的keychar key1,key2;int key;keyl=str0;key2=strlen-1;key=(int)(key1*100+key2)%41;return key;使用 void creathash(void)來創(chuàng)建哈希表函數(shù)void creathash(void)/對文件keyword.txt中的32個關(guān)鍵

12、字創(chuàng)建哈希表(FILE *fp; int length; char strsize;/暫時存儲關(guān)鍵字字符的數(shù)組char *s=NULL; for (int i = 0; i size; i+) ( stri=0; if(fp=fopen(keyword.txt,r)=NULL) ( coutcant creat file!n; exit(0); while (fgets(str,size,fp)!=NULL)/讀取一行寫入一行( if (str=NULL) ( break; length=strlen(str); strlength-1 = 0;/調(diào)試后發(fā)現(xiàn)的，沒有這里就停止運(yùn)行了Hashfu

13、nc(str); fclose(fp); 使用voidHashfunc(char str)來將關(guān)鍵字根據(jù)哈希函數(shù)放入哈希表中的指定位置的函 數(shù)void Hashfunc(char str)/將關(guān)鍵字根據(jù)哈希函數(shù)放入哈希表中的指定位置int key,len; len=strlen(str); key=getkey(str,len); while (hashtkey%41.hash1!=NULL)(key+;/線性探索hashtkey%41.hash1 = (char*)malloc(sizeof(char)*(len+1);strcpy(hashtkey%41.hash1,str);使用int

14、Hashfind(char *words)來在哈希表中找是否該words為關(guān)鍵字，并統(tǒng)計頻度的 函數(shù)int Hashfind(char *words) /在哈希表中找是否該words為關(guān)鍵字，并統(tǒng)計頻度(int key,len,find;len=strlen(words);key=getkey(words,len);while(hashtkey.hash1二二NULL)key+;key=key%41;if(strcmp(hashtkey.hash1,words)=0)(hashtkey.count+;return 1;for(find=key+1;findhashlen;find+)/*如果不

15、在key位置則向往后線性查找，然后再從頭找*/(/線性探查法順序查找哈希表中是否已存在關(guān)鍵字if(hashtfind.hash1!=NULL)(if(strcmp(hashtfind.hash1,words)=0)(hashtfind.count+;return 1;for(find=0;findkey;find+)(if (hashtfind.hash1!=NULL)(if(strcmp(hashtfind.hash1,words)=0)(hashtfind.count+;return 1;return 0使用int readc(char * filename)來讀取源程序文件中的單詞的函數(shù)

16、 int readc(char *filename) /讀取源程序文件中的單詞FILE *fp1=NULL; char wordsmaxlen,ch; int i; if(fp1=fopen (filename,r)二二NULL) coutcan not creat file!n; exit(0); while (!feof(fp1)/結(jié)束返回 1 i=0; ch=fgetc(fp1);/一個字符一個字符的讀while (isletter(ch)=0&feof(fp1)=0) ch=fgetc(fp1); while (isletter(ch)=1&feof(fp1)=0) if (i=max

17、len) while (isletter(ch)=1&feof(fp1)=0) ch=fgetc(fp1); i=0; break; 超過最大關(guān)鍵字長度將會跳過當(dāng)前識別區(qū)域，讀取下一個單詞 else wordsi+=ch; ch=fgetc(fp1); wordsi=0; Hashfind (words);/*將得到的該單詞調(diào)入Hashfind函數(shù)，來判斷是否為關(guān)鍵字，并統(tǒng)計頻度*/ fclose(fpl) return 0;使用float Mol(int *x)來取模函數(shù) float Mol(int *x)/取模函數(shù)int i = 0, sum = 0;for (i = 0; i N; i+

18、)sum += (xi * xi);return (float)pow(float)sum,0.5)int Dot(int *x1, int *x2)/點(diǎn)積函數(shù)int i = 0, sum = 0; for (i = 0; i N; i+)sum += x1i * x2i;return sum;使用 float S(int *x1,int *x2)、float D(int *x1, int *x2)和 void check(int *x1, int *x2)來分別求相似度S的函數(shù)、求幾何距離D函數(shù)和檢查兩個源程序是否相似的函數(shù) float S(int *x1,int *x2) return D

19、ot(x1, x2)/(Mol(x1)*Mol(x2); /求相似度 Sfloat D(int *x1, int *x2)/求幾何距離int xN, i = 0;for (i = 0; i N; i+) 向量相減 xi= x1i - x2i;return Mol(x);/再求模void check(int *x1, int *x2) float xs = 0, xd = 0;xs = S(x1, x2);cout相似度 xs=xs Smax) /先判斷S,若S大于閾值再計算幾何距離 (xd = D(x1, x2);cout幾何距離 xd=xdendl;if (xd Dmin) /如果幾何距離小

20、于閾值則判斷為相似 cout 這兩個文件內(nèi)容確實(shí)可能相似endl;elsecout 這兩個文件內(nèi)容可能不相似endl;return;cout 這兩個文件內(nèi)容不相似endl;/否則不相似return;六、實(shí)驗(yàn)結(jié)果與分析實(shí)驗(yàn)上機(jī)測試結(jié)果如下圖所示:U C:Users傅開|Desktop|g構(gòu)與算法課設(shè)Debug|S構(gòu)與算法課設(shè).exe12 3 4 50123456783456901345789011111111122222333333334enum extern goto int long signed sizeof switch union char void auto const short

21、double struct typedef volatile for if do break while default return else register unsigned staticcase continue floatl2no 116026000100testl. txt和test2. txt的相似情況為 相似度xs=0. 920507 幾向距離xd=13. 1149這兩個文件內(nèi)容可能不相似搜疝排音圣：角似情況為分析：實(shí)驗(yàn)上機(jī)運(yùn)行結(jié)果與實(shí)際結(jié)果相符，即可以認(rèn)為該程序是正確無誤的。七、總結(jié)在本次的課程設(shè)計上機(jī)操作的時候，在調(diào)試每個模塊設(shè)計的時候，有些模塊由于本人的 粗心大意把=與=的問題弄混淆了，使調(diào)試出現(xiàn)了報錯。這是由于本人平時沒