1、自己在网上找到一些C语言程序，分别为test1.txt,test2.txt,test3.txt等。运行结果应为输出每个源程序关键字的出现的频度和源程序之间的相似度以及向量的几何距离。二需求分析1.本程序用来通过建立哈希表求源程序关键字的出现的频度和源程序之间的相似度以及向量的几何距离。三概要设计为了实现上述功能，可以用结构体表示哈希表，因此需要哈希表的抽象数据类型。 哈希表抽象数据类型的定义： ADT hashtable数据对象：D=ai|aiElemType,且各不相同，i=1,2.,n,n0 数据关系：R= 基本操作： Hashfunc（char str）;Hashfind（char *w
2、ords）;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 3.本程序实现模块 主程序模块 哈希表程序模块：实现哈希表的抽象数据类型 调用关系：计算相似度和向量的几何距离的模块四详细设计1.各个子函数的设计1）创建哈希表函数 函数原型：void creathash（void）; 输入：读取存储了32个关键字的文件ckey.txt 思路：
3、通过对ckey.txt文件逐行赋值给创建的str字符数组，并将该数组调入Hashfunc函数。 （2）将关键字根据哈希函数放入哈希表中的指定位置的函数 void Hashfunc（char str）; 思路：对调进来的str数组通过调用getkey函数得到该关键词的key值后放入哈希表中的特定位置，并用线性探索来解决冲突。（3）在哈希表中找是否该words为关键字，并统计频度的函数 函数原型：int Hashfind（char *words）;将调进来的word字符数组先调用getkey函数获取key值，然后在哈希表里查找是否存在该字符串，如果存在则该关键字对应的频度加1. （4）重置哈希表函
4、数void resethash（int n）; 功能：当n为0时，将指向哈希表中关键字的指针置成Null，同时将频度全部置为0.而当n为1时，仅仅将频度置为0.（5）获取单词key的函数int getkey（char *str,int len）;用key1存储关键字的首字母，key2存储关键字的末字母，然后通过哈希函数得到key的值并返回。 （6）判断是否为字母的函数int isletter（char ch）;如果调进来的ch字符的ASCII值在az或AZ范围内的话则返回1，否则返回0. （7）读取源程序文件中的单词的函数 int readc（char * filename）;为了读取源程序文
5、件中的单词，所以一个字符一个字符的，如果读的超过最大关键字长度将会跳过当前识别区域，读取下一个单词，将得到的该单词调入Hashfind函数，来判断是否为关键字，并统计频度。 （8）将频度拷贝到数组里的函数void copycount（int x,int n）;将哈希表中关键字的频度复制到x数组中，以便进行后面相似度等的计算。 （9）检查两个源程序是否相似的函数void check（int *x1, int *x2）;对调进来的x1和x2数组进行相似度计算，若相似度大于设定好的阈值，则再进行几何距离计算，最后给出两个文件是否相似的判断。（10）取模函数float Mol（int *x）;通过求向
6、量模值的数学知识求x数组的模 （11）点积函数int Dot（int *x1, int *x2）;通过点积的数学知识对两个向量求点积 （12）求相似度S的函数float S（int *x1,int *x2）;根据题目给的求相似度的公式求x1和x2数组的相似度 （13）求距离D的函数float D（int *x1, int *x2）;用题目给的球几何距离的公式求x1和x2数组的几何距离2主函数伪码int main（） char filename1=test1.txt; char filename2=test12.txt char filename3=test13.txt int x1hashle
7、n,x2hashlen,x3hashlen; /存储频度的数组，用于相似度S的计算 resethash（0）; /完全重置哈希表，即哈希指针置为NULL，频度置为0 creathash（）; /通过文件ckey.txt创建哈希表 readc（filename1）; /读取第一个测试源程序文件 copycount（x1,hashlen）; /讲统计好的频度复制给x数组 resethash（1）; /仅仅将频度count置为0 readc（filename2）; /同上 copycount（x2,hashlen）; readc（filename3）; copycount（x3,hashlen）;
8、coutt哈希序号 t关键字频度1频度2频度3endl; for （int i = 0; i 41; i+） if（hashti.hash1!=NULL） coutihashti.hash1x1ix2ix3i filename1和filename2的相似情况为： check（x1,x2）; /检查相似度filename3 check（x1,x3）; check（x2,x3）; return 0;3.调用关系图SDMolDotgetkeyislettermain（）hashfuncresethashcreathashreadccopycounthashfindcheck五调试分析1.遇到的问题分
9、析1）=与=的问题 赋值号与等号的问题虽然平时一直都会注意，但是有时候粗心也容易犯错，就比如在该语句中：if（fp=fopen（ckey.txt,r）=NULL）写成了if（fp=fopen（）=NULL），导致运行时出现下图看到过一本讲编程的书说为了避免这种错误，可以#define = equal，这样就变成了if（fp=fopen（）equalNULL）。虽然这样确实可以避免该类错误，但是我觉的也没有太大的必要，只要平时注意点小心点就是了。而且如果在visual studio2012上编程时，一般是不允许出现fopen这种不安全函数的，要使用它推荐的fopen_s函数，使用如下2）第二个问
10、题出现在creathash函数中，也比较难找。当时程序没有红色的那两句，while （fgets（str,size,fp）!=NULL） /读取一行写入一行 if （str=NULL） break; length=strlen（str）; strlength-1=0; Hashfunc（str）; fclose（fp）;接下来的是没有那两句的运行后的窗口截图如果加上那两句红色的语句后的运行窗口就是这样的后来调试时发现，（就拿文件ckey.txt中的第一个关键字为例）在没有那两句红色语句时，调试窗口是这样显示的说明在执行逐行读取关键字的那段代码时，它把每一行的换行号也读进了str数组里，导致输出
11、时，每个关键字都做了换行，便有了上面的第一个截图。所以我的解决办法就是加入红色的那两句，即length=strlen（str）; strlength-1= 也就是把最后的换行号替换为0.3）第三个问题出现在readc函数中。在下面代码中原本没有注销的那一语句。所以导致这样的结果：即统计不到源程序文件中的关键字的频度，均显示为0.然后进行调试发现（就以读取到的第一个单词include为例）：从调试窗口可看出读取完一个完整的单词后，它自己不能给该word数组赋值0来结束，这样导致的结果将会发生在Hashfind函数中的strcmp函数中，即通过上网查资料后知道，strcmp函数进行两字符串比较时是
12、两个字符串自左向右逐个字符相比（按ASCII值大小相比较），直到出现不同的字符或遇为止。而我的hashtkey.hash1数组里的字符串为i,n,c,l,u,d,e0,而words数组为i,n,c,l,u,d,e，所以比较的结果是它们不相等，就统计不到关键字的频度。所以我的解决办法即注销的那句：wordsi=对每次读到的单词后都加一个0。4）第四个问题出现在求几何距离的D函数。原本我是这样写的floatD（int*X1,int*X2）*X;X=Sub（X1,X2）;returnMol（X）;int *Sub（int *X1, int *X2）int XN, i = 0;for （i = 0;
13、N;Xi= X1i - X2i;return X;float Mol（int *X）int i = 0, sum = 0;sum += Xi * Xi;return （float）pow（sum,0.5）;这样运行的结果就是求出来的几何距离是个很奇怪的随机数，每运行一次得出的结果都不一样。原因在于在Sub函数中X数组是个局部变量，返回的X只能是个指针，此时它已经不代表刚才指向的那个数组了，然后调进Mol函数中，进行的操作也只是对X的地址进行操作，因为地址是随机数，所以返回的也是个随机数。我所以我将这D和Sub两个函数直接合并为一个D函数float D（int *x1, int *x2） /求几
14、何距离 int xN, i = 0; for （i = 0; i+） /向量相减 xi= x1i - x2i; return Mol（x）; /再求模2.复杂度的分析 本程序中没有用到循环嵌套，所以每个函数的时间复杂度基本为O（n），空间复杂度也基本为O（n）。六使用说明，本程序的主要功能就是统计源程序之间的相似度，所以使用者只需要将要检测的源程序的txt文件放入该程序的工程文件夹中然后在修改读取的文件名便可直接运行了。七测试结果结果与实际结果相符，故可以认为该程序是成功的。八心得与体会。 1.通过本实验让我用程序对文件的操作有了更深的理解，知道了如果直接的逐行读取文件的话，换行号也会被读进去
15、的。 2.对局部变量有了更好的理解。 3学会了建立哈希表的过程，以及更好的掌握了调试这一功能。4.由于本程序的编写和调试我是在visual studio2012进行的，所以上述截图均为在该编辑环境中进行的。使用visual studio编程体会到了其功能之强大和方便。而且也更安全，例如它一般不允许fopen，strcpy这种不安全函数，所以原本我用的是和这种visual 推荐的安全函数。只是后来将代码拷贝的VC+后这些安全函数不能用后，我又换了回来，但其他的基本不用改。九附完整源程序/ 哈希表统计源程序的相似度#includeiostreamstdlib.hstringmath.h#defin
16、e N 32 /关键字个数#define size 256#define maxlen 9 /关键字数组长度#define hashlen 41 /哈希表长度#define Smax 0.9 /相似度s的阈值#define Dmin 2 /D的阈值struct hashtable /结构体数组哈希表 char *hash1; /指向关键字的指针 int count; /记录频度hashthashlen;using namespace std; /将关键字根据哈希函数放入哈希表中的指定位置 /在哈希表中找是否该words为关键字，并统计频度 /创建哈希表 /判断是否为字母 /取模函数 /点积函数
17、 /求距离D的函数 /求相似度S的函数 /读取源程序文件中的单词 /获取该单词的key /重置哈希表 /将频道拷贝到数组里 /检查两个源程序是否相似void resethash（int n） /重置哈希表 if（n=0） /完全重置哈希表 for（int i=0;41;i+） hashti.hash1=NULL; hashti.count=0; else if （n=1） /仅仅重置频度void copycount（int x,int n） /拷贝频度 n; xi=hashti.count;int getkey（char *str,int len） /根据哈希函数获取该单词的key char
18、key1,key2; int key; key1=str0; key2=strlen-1; key=（int）（key1*100+key2）%41; return key;void creathash（void） /对文件ckey.txt中的32个关键字创建哈希表 FILE *fp; int length; char strsize; /暂时存储关键字字符的数组 char *s=NULL; size; stri= if（fp=fopen（）=NULL） coutcant creat file!n exit（0）; while （fgets（str,size,fp）! /调试后发现的，没有这里就
19、停止运行了void Hashfunc（char str） /将关键字根据哈希函数放入哈希表中的指定位置 int key,len; len=strlen（str）; key=getkey（str,len）; while （hashtkey%41.hash1! key+; /线性探索 hashtkey%41.hash1=（char*）malloc（sizeof（char）*（len+1）; strcpy（hashtkey%41.hash1,str）;int Hashfind（char *words） /在哈希表中找是否该words为关键字，并统计频度 int key,len,find; len=s
20、trlen（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+） /如果不在key位置则向往后线性查找，然后再从头找 /线性探查法顺序查找哈希表中是否已存在关键字 if（hashtfind.hash1! if（strcmp（hashtfind.hash1,words）=0） hashtfind.count+; re
