# 代码相似性检测系统 **Repository Path**: Boeing-777/Code-similarity-detection-system ## Basic Information - **Project Name**: 代码相似性检测系统 - **Description**: No description available - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 2 - **Forks**: 0 - **Created**: 2020-12-29 - **Last Updated**: 2022-03-28 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README **课程设计题目：设计实现一个代码相似性检测系统（***）** 姓名：陈权 班级：软件194 学号 ：2019082402 代码地址： https://gitee.com/Chen-Quan-704290901/Code-similarity-detection-system **一．问题描述：** 1.题目内容： 对于两个C++语言的源程序代码，用哈希表的方法分别统计两个程序中使用C++语言关键字的情况，并最终按定量的计算结果，得出两个程序的相似性。 2.基本要求：建立C++语言关键字的哈希表，统计在每个源程序中C++关键字出现的频度, 得到两个向量X1和X2，通过计算向量X1和X2的相对相似度来判断两个源程序的相似性。 例如: 关键字： Void Int For Char if else while do break class 程序1关键字频度： 4 3 0 4 3 0 7 0 0 2 程序2关键字频度： 4 2 0 5 4 0 5 2 0 1 X1=[4,3,0,4,3,0,7,0,0,2] X2=[4,2,0,5,4,0,5,2,0,1] 设d是向量X1和X2的相对距离，如使用欧式距离d，当X1=X2时，d=0, 反映出可能是同一个程序；d值越大，则两个程序的差别可能也越大。试分析计算结果，得出两个程序的相似性。 测试数据: 选择若干组编译和运行都无误的C++程序，程序之间有相近的和差别大的，用合适的度量方法, 对比两个程序的相似性。 3.考核要求： （1）从源代码中分解单词，判断是否为关键字要采用效率高的方法，设计的哈希函数尽量产生较少的冲突。任选处理冲突的方法，选择的测试数据要尽量包含多种情况，并能够处理异常。 （2）建立源代码用户标识符表，比较两个源代码用户标识符出现的频度，综合关键字频度和用户标识符频度判断两个程序的相似性。比较（1）（2）的结果。 （3）度量相关性最常见的距离度量方法有欧式距离和街区距离。欧式距离计算公式为 d=sqrt( ∑(xi1-xi2)2 ) （两个向量的各分量平方和开根号），街区距离的计算公式为d = ∑|X1i-X2i| (两个向量的各分量绝对值求和)。 （4）使用特征向量的距离d能够分析两个文档的相似程度，但在机器学习等领域更多采用相似度而不是距离方法度量两个对象（文档）关系（距离越小，文档越相关；相似度越大，文档越相关）。从距离d到相似度s的转换，可以采用指数函数实现，如s=可以实现距离d到相似度s的映射，其中，k仅为了更加准确而所设置的参数，该参数的取值，你可以通过循环遍历方法确定。C语言中e为底数的指数函数是exp(),因此，距离到相似度转换使用C语言实现的语句为s=exp(-k*d);（C语言中该指数函数对应头文件为math.h）。请你根据（3）、（4）中介绍的两种距离度量方法和两种相似度计算方法，进行文档相关性的计算，比较在文档相关性度量中距离度量和相似度距离是否效果相同，根据实验结果给出你认为的最好的度量方法。 **二．需求分析：** 1.软件的基本功能：选择两个程序文件打开，程序可以统计这两个程序文件中关键字和标识符的频度数，根据频度数计算街区距离和欧拉距离，最终计算两个程序的相似度 2.输入/输出形式：用户通过控制台，根据提示输入，然后根据输入的数据，数据计算的结果； 3.输入形式：按控制台的按钮后，弹出对话窗，从对话窗中选择程序文件； 4.输出形式：在控制台中显示出距离和相似度 5.测试数据要求：选择若干组编译和运行都无误的C++程序，程序之间有相近的和差别大的，用合适的度量方法, 对比两个程序的相似性。 **三．概要设计** 1.抽象数据类型： 闭散列表 ```cpp struct hashtable //结构体数组哈希表 { char* hash1; //指向关键字或标识符的指针 int count; //记录关键字频度数 int count1; //记录标识符频度数 }; ``` 关键字散列函数key = (int)(key1 * 100 + key2) % 41;（key1，key2是关键字的首尾字母） 标识符散列函数key = (int)(key1 * 100 + key2) % 81;（key1，key2是标识符的首尾字母） 处理冲突的方法：线性探测法 2.主程序流程 ![](https://lexiangla.com/assets/b1edc0764f6511eb9d661676f8edba2d) 3.模块调用关系： ![](https://lexiangla.com/assets/d669c8284f6511ebbee072ea46642145) **四．详细设计** 1.实现概要设计的数据类型： ```cpp class MainWindow { public: void Hashfunc(char str[]); //将关键字根据哈希函数放入哈希表的指定位置 void Hashfunc1(char str[]); //将关键字根据哈希函数放入哈希表的指定位置 int Hashfind(char* words); //在哈希表中找是否该word为关键字，并记录频度 int Hashfind1(char* words); //在哈希表中找是否该word为关键字，并记录频度 void creathash(void); //创建哈希表 int getkey(char* str, int len); //读取该单词的关键码 int getkey1(char* str, int len); //读取该单词的关键码 void resethash(int n); //重置哈希表 private: hashtable hasht[HASHLEN]; //哈希表数组 hashtable hasht1[200]; //哈希表数组 }; ``` 2.主程序以及其它模块的算法描述： 主程序具体代码： ```cpp int main(int argc, char *argv[]) { QApplication a(argc, argv); MainWindow w; w.show(); return a.exec(); } ``` 主函数只有显示窗口和操作函数 3.其他模块的算法描述： （1）核心函数一：int readc(int I); 功能：从程序中筛选出英文单词 函数的伪代码： 1.读取一个字符 1.1如果字符不是字母且len=0，继续读取，直到是字母为止； 1.2如果是字母 1.2.1存储字母的数组未满，则存储读取的字母； 1.2.2 存储字母的数组满，退出循环，把字母当成下个单词的首字母 算法的效率：这个算法效率我觉得不太好，现在我也没有找到更好的方法；算法的时间复杂度为：O(n2) （2）核心函数二：int Hashfind(char* words) 功能：判断单词是否为关键字并统计频数 函数的伪代码： 1.根据单词计算出它在哈希表中的位置key 1.1：Key处为nullptr,则该单词不是关键字 1.2：key处不空，判断单词是否为关键字或标识符 1.2.1：是关键字或标识符就统计频数 1.2.2：不是就线性探测，最后找不到，再返回0 算法的效率：这个算法效率还行；算法的时间复杂度为：O(n) （3）核心代码三：double OM_similarity(int k);（计算相似度） 功能：计算相似度 该函数需要用到公式：s=exp(-k*d) K值是需要遍历的，遍历的范围我无法确定，所以这个函数我无法完成，或者说不会 算法的效率：这个算法效率还行；算法的时间复杂度为：O(n) （4）其他的函数和代码，不在详细介绍，操作函数，我做了健壮处理；设计界面的函数也坚持简洁的模式，操作也是可视化和按钮化，操作简单，逻辑很清晰；我觉得用户体验挺好的； **五．编码和调试分析：** 1.编码与调试过程中遇到的问题及解决方法： 【问题一】从程序中无法正确筛选出单词 解决方法：经过认真分析得知，字符串最后一个为”\0”,所以每读取完一个单词， 最后都要加上’\0’; 解决此问题得核心代码： //将最后一个字符赋值'\0'表示字符结束 ```cpp words[i] = '\0'; ``` 【问题二】两个程序关键字得频数存储混乱 解决方法：经过认真分析得，引入x1[]和x2[]两个数组存储，并写一个拷贝函数；这样做有利于后面距离和相似度计算时，直接引用x1和x2;这样做是代码更加整洁高效； 解决此问题的核心代码： 在类中，加入int x1[],x2[]；这两个数据成员 拷贝函数代码如下： ```cpp //拷贝频数 void MainWindow::copycount(int x[], int n){ //将哈希表中的每个频数赋到数组X[]中 for (int i = 0; i < n; i++){ x[i] = hasht[i].count; } } ``` 【问题三】读取文件时总是，提示没有此文件； 解决方法：fopen的参数类型是const char *类型;所以你必须把string类型转成const char*类型； 解决此问题的核心代码： /* * 因为fopen（const char*）的参数是const char*类型， * 所以需要做如下两个转化 */ //将QString类型的字符串转成string类型 string name1= file1.toStdString(); //将string类型的字符串转成const char*; const char* NAM = name1.c_str(); if ((fp1 = fopen(NAM, "r")) == NULL) 【问题四】读取关键字文件的末尾会多读取一次，换句话说，关键字会多读一次 解决方法：写一个判断最后一个是否已经读取的函数 【问题五】：出现野指针问题； 解决方法：结构体中 hash1指针必须申请内存空间 数组第一个元素的地址给了hasht[key%41].hash1指针不能用hasht[key % 41].hash1 = str 必须用strcpy函数；进行深度拷贝 解决此问题的核心代码： //创建一个长度为len+1的一个数组 hasht[key % 41].hash1 = (char*)malloc(sizeof(char) * (len + 1)); //数组第一个元素的地址给了hasht[key%41].hash1指针 strcpy(hasht[key % 41].hash1, str); 2.待解决的问题： 【未解决问题一】相似性计算中K值无法确定 【未解决问题二】筛选单词的方法不高效； 【未解决问题三】QT中对话框未学会，所以当只选择了一个程序文件， 却按了检查按钮，无法弹出对话框 **六．使用说明** 进入主界面，根据提示进行操作； 完全没有什么特殊的注意事项 **七．测试结果** 1.两个程序文件完成相同结果如图一所示 ![](https://lexiangla.com/assets/eeee4f5e4f6511eb9a2f7a6e059368c3) 图一 2.两个程序完全不相同如图二所示 ![](https://lexiangla.com/assets/fa961f4e4f6511eb9a2c5a46da877d34) 图二 3.不完全相同的两个程序文件如图三所示 ![](https://lexiangla.com/assets/0a619dea4f6611ebb6d90af3c59716ac) 图三 **八．自学知识** 在课设设计过程中，特别是在代码编写和调试的过程中，自学了很多知识，比如QT; QT中各种控件的使用，其中QT中信号与槽有点难学，看了好几遍才看懂；还有就是我做完课设才懂，信号和槽有两种设计方式，其中一种是自己设计的，另一种是默认的；默认的直接添加就好了；构建哈希表的过程中，查找函数学到了一种和书上不同的方法；最后，还有控制台的一些设置，比如小标题，字体和窗口颜色；清屏函数，暂停函数，各种文件操作。 **九．课程设计心得体会** 这次课设让我的编程能力进一步提高了，学会了将自己所学的知识灵活地运用，明白了自己独立解决问题地重要性；二，要相信自己，别人学会地东西，你通过自己地努力也可以做到，比如QT，朋友和室友都在学QT做图形界面，我刚开始不想做，后来发现他们做得很不错，我的太陋了，所以我也尝试去学，一两天就把图形界面做出来了；三，要向身边比较厉害的朋友请教，他们之所以能够做得那么好，肯定是遇到各种困难，最后自己解决了，这样你可以少走很多弯路； 参考书：    [1]《c++面向对象程序设计》 清华大学出版社   谭浩强著  [2]《数据结构-从概念到C++实现（第三版）清华大学出版社    王红梅、 王慧 王新颖 编著 [3]《Qt5开发及实例》