天津科技大學數(shù)據結構與算法課程設計報告-源程序的相似性

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

2、 2 關鍵字頻度4205405201X1=4,3,0,4,3,0,7,0,0,2X2=4,2,0,5,4,0,5,2,0,1設 s 是向量 X1和 X 的相對距離， s=sqrt( (x2)，當 X1=X2時， s=0，反映出可能21i-x 2i)是同一個程序；s 值越大，則兩個程序的差別可能也越大。三、概要設計為了實現(xiàn)上述功能，可以用結構體表示哈希表，因此需要哈希表的抽象數(shù)據類型。哈希表抽象數(shù)據類型的定義：ADT hashtable數(shù)據對象： D=ai |a i ElemType, 且各不相同， i=1,2.,n,n 0數(shù)據關系： R=基本操作：Hashfunc(char str);Hash

3、find(char *words);creathash(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);end ADT;.本程序實現(xiàn)模塊主程序模塊哈希表程序模塊：實現(xiàn)哈希表的抽象數(shù)據類型調用關系圖如下：主程序模塊哈希表程序模塊計算相似度和向量的幾何距離的模塊四、詳細設計1、各個子函數(shù)的設計（ 1）創(chuàng)建哈希表函數(shù)函數(shù)原型： void creathash(void);輸入：讀

4、取存儲了32 個關鍵字的文件keyword.txt思路：通過對 keyword.txt 文件逐行賦值給創(chuàng)建的 str 字符數(shù)組，并將該數(shù)組調入 Hashfunc 函數(shù)。（ 2）將關鍵字根據哈希函數(shù)放入哈希表中的指定位置的函數(shù)函數(shù)原型： void Hashfunc(char str);思路：對調進來的 str 數(shù)組通過調用 getkey 函數(shù)得到該關鍵詞的 key 值后放入哈希表中的特定位置，并用線性探索來解決沖突。（ 3）在哈希表中找是否該 words 為關鍵字，并統(tǒng)計頻度的函數(shù)函數(shù)原型： int Hashfind(char *words);思路：將調進來的word 字符數(shù)組先調用getkey

5、 函數(shù)獲取 key 值，然后在哈希表里查找是否存在該字符串，如果存在則該關鍵字對應的頻度加1。（ 4）重置哈希表函數(shù)函數(shù)原型： void resethash(int n);功能：當 n 為 0 時，將指向哈希表中關鍵字的指針置成Null ，同時將頻度全部置為0.而當 n 為 1 時，僅僅將頻度置為0。（ 5）獲取單詞key 的函數(shù)函數(shù)原型： int getkey(char *str,int len);思路：用 key1 存儲關鍵字的首字母，key2 存儲關鍵字的末字母，然后通過哈希函數(shù)得到 key 的值并返回。（ 6）判斷是否為字母的函數(shù);.函數(shù)原型： int isletter(char ch

6、);思路：如果調進來的ch 字符的 ASCII 值在 az 或 AZ 范圍內的話則返回1，否則返回0。（ 7）讀取源程序文件中的單詞的函數(shù)函數(shù)原型： int readc(char * filename);思路：為了讀取源程序文件中的單詞，所以一個字符一個字符的，如果讀的超過最大關鍵字長度將會跳過當前識別區(qū)域，讀取下一個單詞，將得到的該單詞調入Hashfind函數(shù)，來判斷是否為關鍵字，并統(tǒng)計頻度。（ 8）將頻度拷貝到數(shù)組里的函數(shù)函數(shù)原型： void copycount(int x,int n);功能：將哈希表中關鍵字的頻度復制到x 數(shù)組中，以便進行后面相似度等的計算。（ 9）檢查兩個源程序是否相

7、似的函數(shù)函數(shù)原型： void check(int *x1, int *x2);思路：對調進來的x1 和 x2 數(shù)組進行相似度計算，若相似度大于設定好的閾值，則再進行幾何距離計算，最后給出兩個文件是否相似的判斷。（ 10）取模函數(shù)函數(shù)原型： float Mol(int *x);思路：通過求向量模值的數(shù)學知識求x 數(shù)組的模。（ 11）點積函數(shù)函數(shù)原型： int Dot(int *x1, int *x2)思路：通過點積的數(shù)學知識對兩個向量求點積。（ 12）求相似度 S 的函數(shù)函數(shù)原型： float S(int *x1,int *x2);思路：根據題目給的求相似度的公式求x1 和 x2 數(shù)組的相似度。

8、（ 13）求距離 D的函數(shù)函數(shù)原型： float D(int *x1, int *x2);思路：用題目給的球幾何距離的公式求x1 和 x2 數(shù)組的幾何距離。2、主函數(shù)偽碼int main()char filename1="test1.txt"char filename2="test2.txt"char filename3="test3.txt"int x1hashlen,x2hashlen,x3hashlen; /*存儲頻度的數(shù)組，用于相似度S 的計算*/resethash(0);/*完全重置哈希表，即哈希指針置為NULL，頻度置為

9、0*/creathash();/通過文件 ckey.txt創(chuàng)建哈希表readc(filename1);/讀取第一個測試源程序文件copycount(x1,hashlen);/講統(tǒng)計好的頻度復制給x 數(shù)組resethash(1);/僅僅將頻度 count 置為 0readc(filename2);/同上copycount(x2,hashlen);resethash(1);.readc(filename3);copycount(x3,hashlen);cout<<"t"<<"哈希序號 "<<"t"<

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

11、lt;"t"<<x1i<<"t"<<x2i<<"t"<<x3i<<endl;cout<<filename1<<"和 "<<filename2<<"的相似情況為："<<endl;check(x1,x2);/檢查相似度cout<<filename1<<" 和 "<<filename3<<" 的

12、相似情況為： "<<endl; check(x1,x3);cout<<filename2<<"和 "<<filename3<<"的相似情況為："<<endl;check(x2,x3);return 0;3、調用關系圖調用關系圖如下：copycounreadcresethacreathashislettemain()hashfindhashfunccheckgetkeyS DDotMol;.五、編碼實現(xiàn)1. 使用函數(shù)void resethash(int n)來重置哈希表voi

13、d resethash(int n)/重置哈希表if(n=0)/完全重置哈希表for(int i=0;i<41;i+)hashti.hash1=NULL;hashti.count=0;else if (n=1)/僅僅重置頻度for(int i=0;i<41;i+)hashti.count=0;2. 使用 void copycount(int x,int n)來將頻度拷貝到數(shù)組里的函數(shù)void copycount(int x,int n)/拷貝頻度for (int i = 0; i < n; i+)xi=hashti.count;3. 使用 int getkey(char *s

14、tr,int len)來獲取單詞key 的函數(shù)int getkey(char *str,int len)/根據哈希函數(shù)獲取該單詞的keychar key1,key2;int key;key1=str0;key2=strlen-1;key=(int)(key1*100+key2)%41;return key;.4. 使用 void creathash(void)來創(chuàng)建哈希表函數(shù)void creathash(void)/對文件 keyword.txt中的 32 個關鍵字創(chuàng)建哈希表FILE *fp;int length;char strsize;/暫時存儲關鍵字字符的數(shù)組char *s=NULL;f

15、or (int i = 0; i < size; i+)stri='0'if(fp=fopen("keyword.txt","r")=NULL)cout<<"can't creat file!n"exit(0);while (fgets(str,size,fp)!=NULL)/讀取一行寫入一行if (str=NULL)break;length=strlen(str);strlength-1='0' / 調試后發(fā)現(xiàn)的，沒有這里就停止運行了 Hashfunc(str);fclose

16、(fp);5. 使用 void Hashfunc(char str) 來將關鍵字根據哈希函數(shù)放入哈希表中的指定位置的函數(shù)void Hashfunc(char str)/ 將關鍵字根據哈希函數(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);.6. 使用 int Hashfind(c

17、har *words) 來在哈希表中找是否該 words 為關鍵字，并統(tǒng)計頻度的函數(shù)int Hashfind(char *words) /在哈希表中找是否該words 為關鍵字，并統(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;find<hashlen;find+)/*如果不在key 位

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

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

20、ch)=1&&feof(fp1)=0)if (i=maxlen)while (isletter(ch)=1&&feof(fp1)=0)ch=fgetc(fp1);i=0;break; / 超過最大關鍵字長度將會跳過當前識別區(qū)域，讀取下一個單詞elsewordsi+=ch;ch=fgetc(fp1);wordsi='0'Hashfind(words);/*將得到的該單詞調入Hashfind函數(shù)， 來判斷是否為關鍵字，并統(tǒng)計頻度*/fclose(fp1);return 0;8. 使用 float Mol(int *x)來取模函數(shù)float Mol(i

21、nt *x)/取模函數(shù);.int i = 0, sum = 0;for (i = 0; i < N; i+)sum += (xi * xi);return (float)pow(float)sum,0.5);int Dot(int *x1, int *x2)/點積函數(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, int *x2)和 void check(int *x1,int *x2)來分別求相似

22、度S 的函數(shù)、求幾何距離D 函數(shù)和檢查兩個源程序是否相似的函數(shù)float S(int *x1,int *x2)return Dot(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=&quo

23、t;<<xs<<endl;if (xs > Smax) /先判斷 S，若 S 大于閾值再計算幾何距離xd = D(x1, x2);cout<<" 幾何距離xd="<<xd<<endl;if (xd < Dmin) /如果幾何距離小于閾值則判斷為相似cout << "這兩個文件內容確實可能相似"<<endl;.elsecout << "這兩個文件內容可能不相似"<<endl;return;cout << "這兩個文件內容不相似"<<endl;/否則不相似return;六、實驗結果與分析實驗上機測試結果如下圖所示：;.分析： 實驗上機運行結果與實際結果相符，即可以認為該程序是正確無誤的。七、總結在本次的課程設計上機操作的時候， 在調試每個模塊設計的時候， 有些模塊由于本人的粗心大意把 =與 =的問題弄混淆了，使調試