Hash冲突并统计关键字的频率.doc

Hash冲突并统计关键字的频率数据结构实验报告一、 问题扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现频度。用线性探测法解决Hash冲突。设Hash函数为：Hash(key)=(key的第一个字母序号)*100+(key的最后一个字母序号) MOD 41二、 算法思想描述.c文件提取单词查找统计显示1. 总体思路图1 总体思路2. 细节描述(1) 创建Hash表所有的关键字已经写入了名为guanjianzi.txt的文件中，通过提取单词，将所有的关键字插入Hash表中。本程序采用开放地址法解决Hash冲突。关键字共有32个：char, double, enum, float, int, long, short, signed, struct, union, unsigned, void, break, case, continue, default, do, else, for, goto, if, return, switch, while, auto, extern, register, static, const, sizeof, typedef, volatile(2) 扫描某C文件在a.c文件中提取出单词，判断是否为关键字，若是则统计加一，直至文件结束。提取单词：根据单词都是由连在一起的字母组成这一原理，用语句while( (cz) & (c!=EOF) ) c=fgetc(ft); 跳过非字母的字符。当读到字母时，用while( c=a & c=z )st.chi=c;c=fgetc(ft);i+;将所有连在一起的字母存在st.ch数组中，在进行下一步操作。在提取单词时，为了实现在注释内的关键字不计，用以下代码实现：if(c=/) c=fgetc(ft);if(c=/) / /后的不计doc=fgetc(ft);while(c!=10);if(c=*)doc=fgetc(ft);if(c=*) / /* */后的不计c=fgetc(ft);if(c=/)break;else continue;while(1);(3) 显示Hash表通过循环显示出a.c文件中所包含的关键字，及其哈希地址和出现频度。输出时过滤没有出现的（频度为0）的关键字。3. 流程图判断是否为关键字SearchHash(.)Y统计加1 开 始读文件guanjianzi.txt文件是否结尾N 提取关键字单词插入关键字至Hash表InsertHash(.)扫描a.c文件文件是否结尾YNY提取单词N输出Hash表结 束Create()Scan()PrintHash()main()图2 流程图三、 程序结构1. 数据结构typedef struct char ch10; /关键字int num; /该关键字出现次数HSTable;HSTable HTMAXSIZE;HT 为一维数组表示的哈希表。2. 函数调用层次结构main函数Create函数Scan函数PrintHash函数InsertHash函数SearchHash函数调用调用调用调用调用调用H函数（求Hash地址）调用图3 函数调用层次结构3. 函数功能说明Create函数：创建Hash表Scan函数：扫描某文件，统计其中各关键字出现次数PrintHash函数：显示Hash表InsertHash函数：将一个单词作为关键字插入Hash表中SearchHash函数：在Hash表中查找是否包含某个单词，即查找该单词是否为关键字。H函数：计算某单词的Hash地址。依据函数Hash(key)=(key的第一个字母序号)*100+(key的最后一个字母序号) MOD 41四、 测试结果与分析上述程序在Visual C+ 6.0环境下加以实现。经过多次测试，程序运行正确。例如：输入C程序 a.c，运行结果如图4所示，图中显示了文件a.c所包含的关键字及其个数。图4 运行结果五、 收获与体会通过这次课程设计:1. 我又进一步巩固了C语言的基础，尤其是文件那部分。2. 通过程序加深了对Hash查找方面知识的认识。更深一层次了解了Hash查找的优缺点。3. 做课程设计达