《数据结构课程设计(江西理工)》由会员分享，可在线阅读，更多相关《数据结构课程设计(江西理工)（27页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告1基于散列表的程序相近度检测系统哈希表2.公司招聘模拟系统一一队列班级：软件102班姓 名： 江政波 指导教师：董跃华井福荣成 绩：立妇Q 乂岁信息工程学院2012年6月18日目录必做题3需求分析3设计要求：3概要设计：31.流程图：42哈希表及其中一些函数53.程序中主要功能函数5a. 主函数5b. 文件处理函数5c. 输出文件函数7调试分析81. 调试过程中遇到的问题82. 算法的时空分析83. 经验和体会8测试结果8参考文献：10源代码附录10自选题20需求分析20概要设计20详细设计211流程图：212.函数：21a. main ()函数21b. void prin
2、t (STU *p)223.插入函数22调试分析：221. 调试过程中遇到的问题222. 算法的时空分析223. 经验和体会22测试结果23参考文献24源代码附录：24必做题正文需求分析对于两个C程序，设计并实现两种不同的基于散列表的检测算法，计算两个程序的相近度，并分析 比较两种算法的效率。设计要求：1. 分别读取两个C程序文件（InFilel.cpp, InFile2.cpp）,识别其中的关键字并统计频度，分 别生成两个文件，保存关键字名称和对应频度（OutFile1.txt, OutFile2.txt）。2. 自行设计散列函数，分别利用开放地址法和链地址法构建C语言关键字的散列表。在扫
3、描源程序的过程中，每遇到关键字就查找相应散列表，并累加相应关键字出现的频度。3. 根据统计的两个程序中关键字不同频度，可以得到两个向量。如下面简单的两个C程序关键字统计结果的例子（假定只考虑以下9个关键字）关键字voidfloatintcharfor辻elsedowhile程序1关键字频度340406203程序2关键字频度320504102X1=3, 4，0，4， 0，6，2，0，3X2=3, 2，0，5，0，4，1，0，2XlX2=0, 2，0，-1，0，2，1，0，1通过计算向量X1和X2的相对距离来判断两个源程序的相似性，相对距离s的计算方法是（T表示向量的转置）显然当X1=X2时，s=
4、0,反映出可能是同一程序；s值越大，则两个程序的差别可能也越大。 4利用开放地址法和链地址法两种方法实现，分别输出s和两种方法计算s所用的时间，分析比较 两种方法的效率。概要设计：该程序用到的数据结构主要是哈希表，其次是顺序表（数组）哈希表中存放着 char, do, double , else, float, for, if, int, long, return, short, sizeof, static, struct, switch, typedef, void, while18 个关键字。数组有两种：一种是在读取文件时暂时用来存放关键字数组元素为字符型:一种是在统计关键字个数的并将之
5、存入数组，数组元素为整型详细设计：1流程图:isKeyWords(word)判断是否是关键字” YESCreatHX(word)调用 OUT_FILE(char *filename) 将源文件关键字及频度导出到 文件 outfile1.txt outfile2.txt调用show(int key)输出各个关键字的频度并将源文件的频度存入数组a计算相似度s=arryMod(c)/结束2哈希表及其中一些函数3程序中主要功能函数a主函数功能：调用其他函数，几个case语句实现程 序的分支；主函数开始时候定义了两个变量：clock_t函数原型作用void HSclear()清空哈希表int FindH
6、X(char *keyword)杳找在哈希表中的位置int CreatHX(char *keyword)创建哈希表int GetFreePos(int key)处理冲突，为关键字寻 找位置插入void Show(int key)输出关键字及其频度int GetKey(char *keyword)构造的哈希函数start, finish在程序开始执行部分插入start = clock();结束处插入finish = clock();最后由 duration = (double)(finish - start) / CLOCKS_PER_SEC;可得程序执行的时间。b文件处理函数功能：主要过滤掉C
7、+源文件中的注释，换 行，空格等字符int isKeyWords(char *word)判断是否是关键字int Read(char *filename)char wordMAXLEN,ch,chl;int i;FILE *read; if(read=fopen(filename,r)=NULL)printf(n文件不存在，请确认好再输入!); return -1;while(!feof(read)i=0; ch=fgetc(read);if (ch=/)chl=fgetc(read);if(chl=/) while(ch1!=n) ch1=fgetc(read);else if (ch1=*)
8、ch1=fgetc(read); while(ch1!=*) ch1=fgetc(read);if(ch1=*)ch=fgetc(read); if(ch=/) break;while(isLetter(ch)=O&feof(read)=0)ch=fgetc(read);while(isLetter(ch)= 1&feof(read)=0)if(i=MAXLEN)while(isLetter(ch)=1&feof(read)=0) ch=fgetc(read);i=0; break;elsewordi+=ch; ch=fgetc(read);wordi=0;if(isKeyWords(word
9、)CreatHX(word);fclose(read);c.输出文件函数功能：将得到的源文件中关键字及其频度导出到文件中void OUT_FILE(char *filename)FILE *fp=fopen(filename,w);int i;for(i=0;ivHASHLEN;i+)if(HSi.keyword!= &HSi.count!=0)fprintf(fp,%s:%-3dn ,HSi.keyword,HSi.count);fclose(fp); D.计算相似度把两个源文件的关键字数分别存入两个数组a18 ,b18中然后对数组进行其模操 作等：相似度：S=arryMod(c)/arryMod(b)*arryMod(a);int arrySub(int arry118,int arry218,int arry18)/ 两个数组相减int i=0;for(;i18;i+) arryi=arry1i-arry2i;float arryMod(int arry3)对数组求模float Mod;int mod=0;int i;for(i=0;i#include st
