1、 数据结构课程设计报告数据结构课程设计报告 1.基于散列表的程序相近度检测系统 哈希表哈希表 2.公司招聘模拟系统 队列队列 班 级: 软件 102 班 姓 名: 指导教师: 成 绩: 2012 年 6 月 18 日 目录目录 必做题 3 需求分析 . 3 设计要求： . 3 概要设计： 3 1.流程图： 4 2.哈希表及其中一些函数. 5 3.程序中主要功能函数 5 a.主函数 5 b.文件处理函数 5 c. 输出文件函数 7 调试分析 . 8 1.调试过程中遇到的问题. 8 2.算法的时空分析 . 8 3.经验和体会 8 测试结果 . 8 参考文献： .10 源代码附录： .10 自选题
2、.20 需求分析 20 概要设计 20 详细设计 21 1.流程图：.21 2.函数： 21 a.main()函数21 b.void print (STU *p) 22 3.插入函数22 调试分析： .22 1.调试过程中遇到的问题22 2. 算法的时空分析 22 3.经验和体会 .22 测试结果 23 参考文献： .24 源代码附录： .24 必做题必做题 正文正文 需求分析 对于两个 C 程序，设计并实现两种不同的基于散列表的检测算法，计算两个程序的相近度，并分析 比较两种算法的效率。 设计要求设计要求： 1. 分别读取两个 C 程序文件（InFile1.cpp, InFile2.cpp）
3、 ，识别其中的关键字并统计频度，分 别生成两个文件，保存关键字名称和对应频度（OutFile1.txt, OutFile2.txt） 。 2. 自行设计散列函数，分别利用开放地址法和链地址法构建 C 语言关键字的散列表。在扫 描源程序的过程中，每遇到关键字就查找相应散列表，并累加相应关键字出现的频度。 3. 根据统计的两个程序中关键字不同频度，可以得到两个向量。 如下面简单的两个 C 程序关键字统计结果的例子（假定只考虑以下个关键字） 关键字 void float int char for if else do while 程序 1 关键字频度 3 4 4 6 2 3 程序 2 关键字频度 3
4、 2 5 4 1 2 X1=3，4，0，4， 0，6，2，0，3 X2=3，2，0，5，0，4，1，0，2 X1X2=0，2，0，-1，0，2，1，0，1 通过计算向量 X1 和 X2 的相对距离来判断两个源程序的相似性， 相对距离 s的计算方法是 （ T 表示向量的转置） 显然当 X1=X2 时，s=0，反映出可能是同一程序；s 值越大，则两个程序的差别可能也越大。 4.利用开放地址法和链地址法两种方法实现，分别输出 s 和两种方法计算 s 所用的时间，分析比较 两种方法的效率。 概要设计： 该程序用到的数据结构主要是哈希表，其次是顺序表(数组) 4 哈希表中存放着 char，do，doub
5、le ，else，float，for，if，int，long，return，short，sizeof，static， struct，switch，typedef，void，while18 个关键字。 数组有两种：一种是在读取文件时暂时用来存放关键字 数组元素为字符型 ：一种是在统计关键字个数的并将之存入数组，数组元素为整型 详细设计： 1.流程图流程图： 开始 定义字符数组char filename128,wordMAXLEN 调用Read(filename)函数对源文件 进行处理 isKeyWords(word)判断是否是关键字 CreatHX(word) YES NO 调用show(int
6、 key)输出各个关键字的 频度并将源文件的频度存入数组a b 调用OUT_FILE(char *filename) 将源文件关键字及频度导出到 文件outfile1.txt outfile2.txt 计算相似度s=arryMod(c)/ arryMod(b)*arryMod(a)输出s 结束 5 2.哈希表及其中一些函数哈希表及其中一些函数 3.程序中主要功能函数程序中主要功能函数 a.主函数主函数 功能：调用其他函数，几个 case 语句实现程 序的分支； 主函数开始时候定义了两个变量：clock_t start, finish 在程序开始执行部分插入 start = clock(); 结束处插入 finish = clock(); 最后由 duration = (double)(finish - start) / CLOCKS_PER_SEC; 可得程序执行的时间。 b.文件处理函
