找回密码
 立即注册

本文来自

范文频道

范文频道

订阅|关注

爱米村范文频道致力于整理并分享给用户平时常用的范文,比如自我介绍范文,入党申请书范文,个人简历范文,工作总结范文,思想汇报范文等等,要找范文就来文章库范文频道

天津科技大学数据结构与算法课程设计报告

[复制链接]
180 心中太阳 发表于 2017-9-13 13:10:46
导读:数据结构与算法课程设计报告,设计题目:源程序的相似性,数据结构与算法课程设计报告14101103-傅开煤,对于两个C++语言的源程序代码,用哈希表的方法分别统计两个程序中使用C++语言关键字的情况,得出两份程序的相似性,统计在每个源程序中C++关键字出现的频度,得到两个向量X1和X2,通过计算向量X1和X2的相对距离来判断两个源程序的相似性,关键字VoidIntForCharifelsewhi

数据结构与算法 课程设计报告


设计题目:源程序的相似性

专 业 计算机科学与技术 学 号 14101103 姓 名 傅开煤



2017 年 1 月 10 日
数据结构与算法课程设计报告 14101103-傅开煤
源程序的相似性
一、问题描述
对于两个C++语言的源程序代码,用哈希表的方法分别统计两个程序中使用C++语言关键字的情况,并最终按定量的计算结果,得出两份程序的相似性。
二、需求分析
建立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]
设s是向量X1和X2的相对距离,s=sqrt( ∑(x1[i]-x2[i]) 2 ),当X1=X2时,s=0,反映出可能是同一个程序;s值越大,则两个程序的差别可能也越大。
三、概要设计

为了实现上述功能,可以用结构体表示哈希表,因此需要哈希表的抽象数据类型。 哈希表抽象数据类型的定义: ADT hashtable{
数据对象:D={ai|ai∈ElemType,且各不相同,i=1,2...,n,n≥0} 数据关系:R=φ 基本操作:
Hashfunc(char str[]);
Hashfind(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

第 1 页 共 11 页

数据结构与算法课程设计报告 14101103-傅开煤

本程序实现模块 主程序模块
哈希表程序模块:实现哈希表的抽象数据类型 调用关系图如下:
主程序模块
计算相似度和向量
哈希表程序模块
的几何距离的模块
四、详细设计

1、各个子函数的设计 (1)创建哈希表函数
函数原型:void creathash(void);
输入:读取存储了32个关键字的文件keyword.txt
思路:通过对keyword.txt文件逐行赋值给创建的str字符数组,并将该数组调入Hashfunc函数。
(2)将关键字根据哈希函数放入哈希表中的指定位置的函数 函数原型:void Hashfunc(char str[]);
思路:对调进来的str数组通过调用getkey函数得到该关键词的key值后放入哈希表中的特定位置,并用线性探索来解决冲突。
(3)在哈希表中找是否该words为关键字,并统计频度的函数
函数原型:int Hashfind(char *words); 思路:将调进来的word字符数组先调用getkey函数获取key值,然后在哈希表里查找是否存在该字符串,如果存在则该关键字对应的频度加1。 (4)重置哈希表函数
函数原型:void resethash(int n);
功能:当n为0时,将指向哈希表中关键字的指针置成Null,同时将频度全部置为0.而当n为1时,仅仅将频度置为0。 (5)获取单词key的函数
函数原型:int getkey(char *str,int len);
思路:用key1存储关键字的首字母,key2存储关键字的末字母,然后通过哈希函数得到key的值并返回。
(6)判断是否为字母的函数

第 2 页 共 11 页
数据结构与算法课程设计报告 14101103-傅开煤
函数原型:int isletter(char ch);
思路:如果调进来的ch字符的ASCII值在a~z或A~Z范围内的话则返回1,否则返回0。 (7)读取源程序文件中的单词的函数
函数原型:int readc(char * filename);
思路:为了读取源程序文件中的单词,所以一个字符一个字符的,如果读的超过最大关键字长度将会跳过当前识别区域,读取下一个单词,将得到的该单词调入Hashfind函数,来判断是否为关键字,并统计频度。 (8)将频度拷贝到数组里的函数
函数原型:void copycount(int x[],int n);
功能:将哈希表中关键字的频度复制到x数组中,以便进行后面相似度等的计算。 (9)检查两个源程序是否相似的函数
函数原型:void check(int *x1, int *x2);
思路:对调进来的x1和x2数组进行相似度计算,若相似度大于设定好的阈值,则再进行几何距离计算,最后给出两个文件是否相似的判断。 (10)取模函数
函数原型:float Mol(int *x);
思路:通过求向量模值的数学知识求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[]={\ char filename2[]={\ char filename3[]={\ int x1[hashlen],x2[hashlen],x3[hashlen]; /*存储频度的数组,用于相似度S的计算*/ resethash(0); /*完全重置哈希表,即哈希指针置为NULL,频度置为0*/ creathash(); //通过文件ckey.txt创建哈希表 readc(filename1); //读取第一个测试源程序文件 copycount(x1,hashlen); //讲统计好的频度复制给x数组 resethash(1); //仅仅将频度count置为0 readc(filename2); //同上 copycount(x2,hashlen); resethash(1);
第 3 页 共 11 页
数据结构与算法课程设计报告 14101103-傅开煤 readc(filename3); copycount(x3,hashlen); cout
温馨提示:
1、在论坛里发表的文章仅代表作者本人的观点,与本网站立场无关。
2、论坛的所有内容都不保证其准确性,有效性,时间性。阅读本站内容因误导等因素而造成的损失本站不承担连带责任。
3、若因线路及非本站所能控制范围的故障导致暂停服务期间造成的一切不便与损失,论坛不负任何责任。
4,本网站内容均摘自其他网站,如涉及侵权定当第一时间删除
5、如侵犯您的权益请联系936144721@qq.com



上一篇:冬季加一层窗户温度能提高多少
下一篇:滇池边将划定垂钓和放生区域 设放生滑道或亲水台阶
转载请说明出处,本文地址:http://bbs.imicun.com/thread-15462648-1-1.html
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表