利用哈希技术统计C源程序关键字出现频度2016.docVIP

：利用哈希技术统计C源程序关键字出现频度 目录 需求分析说明·····················3 总体设计·························3 详细设计························4 实现部分························5 程序测试·························10 总结·································11 一、需求分析说明 1.课程设计目的 本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 2.题目要求 1)题目内容： 利用Hash技术统计某个C源程序中的关键字出现的频度 2)基本要求： 扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度。用线性探测法解决Hash冲突。设Hash函数为： Hash(key)[(key的第一个字母序号)*100+(key的最后一个字母序号)] MOD 41 二、总体设计 算法思想描述 首先读取关键字文件以建立二叉排序树以供后续查询，每个树节点保存一个关键字字符串及指向左右子树的指针。同时创建一Hash表，每个节点除应保存关键字字符串外，还应保存关键字频数及该存储单元冲突次数。然后扫描一个C源程序，每次扫描一行，从中循环分离出每个单词，每次均查找其是否为关键字，若是，则按计算公式计算其KEY值并在Hash表中进行相应操作，若该节点为空则插入否者比较其是否与现有关键字相同，若相同则增加其频数，否则增加其冲突次数并继续线性探测下一个存储单元，完了继续操作下一个分离出来的单词，如此循环运行直至扫描结束。编写本程序时，使用了二叉树创建、二叉树查找、Hash表的建立和操作及文件操作等基本算法。 三、详细设计 (程序结构 //Hash表存储结构 typedef struct node //定义 { char s[20]; int num,time; //num为频数，time为冲突次数 }node; //二叉排序树结构定义 typedef struct nod //定义 { char s[20]; struct nod *left,*right; }nod; int max; //max为Hash表长度 函数说明： nod *creat()： 读关键字文件，按照关键字中字符字母先后顺序建立二叉排序树，每个节点中保存一个关键字； void init(node *head)： 初始化Hash表各节点数据域； void deal(node *head,nod *parent,char filename[])： 扫描源文件，分离出每个单词，检验是否为关键字；并根据检验结果来决定是否调用strdeal函数，以对Hash做适当更改； void strcp(node *head,char s[],int k)： 将新查找到的关键字复制到Hash表中第k个节点存储单元； void strdeal(node *head,char s[],int k)： 判断Hash表中第k个单元中有无关键字，若无则将当前关键字存入该单元，返回；否则比较两关键字是否相等，相等则将该单元频数加一，返回；不相等则将该单元冲突数加一并循环线性探测下一个存储单元； int strcmp(char t[],char s[])： 字符串比较； void prin(nod *head)： 以左根右的顺序将二叉排序树打印在屏幕上； 四、实现部分 #include iostream.h #include string #include iomanip.h using namespace std; const int TOTAL=39; //39个关键字 const int MAXLEN=10; //关键字长度 const int HASHLEN=41; //哈希表长度 int cont=0; //统计哈希表中的关键字个数 void jiemian(); void Show(int key); void Select(int choice); int Read(char *filename); int Input(); int isL