1、 数据结构课程设计报告数据结构课程设计报告 利用利用 Hash技术和二分查找技术统计某个技术和二分查找技术统计某个 c 程序中关键字出现的频度程序中关键字出现的频度 班级：班级：06 级 5 班 目录目录 1题目- -3 2算法思想-3 3程序结构-3 4测试结果-6 5收获与体会-7 一、一、 题目题目 扫描 c 源程序， 利用 hash 技术和二分查找技术统计该源程序中的关键字出 现的频度，并比较各自查找的次数。 （1） 、先用 Hash 表存储 c 语言中 32 个关键字，再扫描 c 源程序取出每个单词， 利用 Hash 查找技术统计该程序中的关键字出现的频度。 发生 Hash 冲突用线
2、性探 测法解决。设 Hash 函数为： Hash（key）=(key 的第一个字母序号)*100+(key 的最后一个字母序号) MOD 41。 （2） 、用顺序表存储 c 语言中的关键字，把 c 源程序取出每个单词利用二分查找 技术统计该程序中的关键字的出现频度。 二、二、 算法思想算法思想 1、 Hash 表的建立表的建立 首先按照 c 语言中关键字 （共 32 个） ， 根据 Hash 函数： Hash （key） =(key 的第一个字母序号)*100+(key 的最后一个字母序 号) MOD 41，申请 一个类数组， 长度为 41， 类中有一个 string 型 用来存储关键字和 i
3、nt 类型 用来存储出现的频率，并初始化为 0。 2、 HashHash 冲突解决冲突解决 用线性探测法解决。把整个数组看成一个循环的数组，当发生冲突时， 从发生冲突的位置的下一个位置起， 依次寻找空的散列地址,再把关键字 存入。 3、 顺序表的建立顺序表的建立 二分查找要求所查的关键字必须有序，所以按照关键字的大小从小到大 排列（用 string 类型直接比较）。c 语言中关键字共 32 个，故定数组 长度为 32。排序方法采用插入排序。 4、 文件的读入文件的读入 要从文件中读取单词是非常关键的一步，其中要考虑的因素很多。，如 “/.”,“/*.*/”,“” 注释符号内出现的关键字不算， 甚至会出现注释符号嵌套，还有关键字和数字、下划线、大写字母相连， 故应特殊考虑。具体查看代码。 三、三、 程序结构程序结构 程序中的一些变量：程序中的一些变量： KeyHash KeysHashList41 存放关键字的Hash表，用于Hash查找 int HashCount=0 记录 Hash 查找的比较次数 KeyBin KeysBinList32 存放关键字的顺序表，用于二分查找 int BinCount=0 记录二分查找的次数 class KeyHash Hash存储关键字的类 p
