使用哈希表技术判别两个源程序的相似性

实习六 使用哈希表技术判别两个源程序的相似性问题描述 对于两个C语言的源程序清单，用哈希表的方法分别统计两程序中使用C语言关键字的情况，并最终按定量的计算结果，得出两份源程序清单的相似性。基本要求 C语言关键字的哈希表自建，此题的工作只要是扫描给定的源程序，累计在每个源程序中C语言关键字出现的频度。在扫描源程序过程中，每遇到关键字就查找哈希表，并累加相应关键字出现的频度。为保证查找效率，建议自建哈希表的平均查找长度ASL不大于2。 扫描两个源程序所统计的所有关键字不同频度，可以得到两个向量。如下面简单的例子所示：VoidintforcharifelseWhile43437024254521关键字程序1种关键字频度程序2中关键字频度 0 1 2 3 4 5 6 7 8 9 哈希地址X1=4，3，0，4，3，0，7，0，0，2 X2=4，2，0，5，4，0，5，2，0，1通过计算向量X1和X2的相对距离来判断两个源程序的相似性，相对距离的计算方法是按例子所给数据，S0.13。显然当X1=X2时，S=0,反映出可能是同一个程序；S值越大，则两个程序的差别可能也越大。测试数据作几个编译和运行都无误的C程序，程序之间有相近的和差别大的，用上述方法求S,并对比差异程度。实现提示本题的很大工作量将是对源程序扫描，区分出C程序的每一关键字。可以为C语言关键字建一棵键树，扫描源程序和在键树种查找同步进行，也取得每一个关键字。问题讨论 这种判断方法只是提供一种辅助手段，即便S=0也可能不是同一程序，S的值很大，也可能算法完全是一样的。例如，一个程序使用while语句，另一个使用for 语句，但功能完全相同 。事实上， 当发现s的值很小时，就应该以人工干预来区分。