《数据结构》课程设计报告书

利用hash技术统计c源程序中的关键字出现的频度。

班级：计算机

姓名。指导教师。

成绩。清华大学计算机系。

2012 年 12 月 31 日。

目录。一、题目描述 1

1.1问题描述 1

1.2实现要求 1

二、题目分析 1

2.1hash函数 1

2.2关键技术 2

2.3利用hash函数统计c源程序中关键字出现频度的设计思想 2

2.4处理冲突的方法 3

三、设计思路 3

3.1设计图示 3

3.2函数功能说明 4

3.2函数功能说明 5

四、关键部分实现细节 5

五、调试分析 8

六、程序运行结果 9

七、心得体会 11

参考文献 11

扫描c源程序，利用hash技术统计该源程序中的关键字出现的频度。

先用hash表存储c语言中32个关键字，再扫描c源程序取出每个单词，利用hash查找技术统计该程序中的关键字出现的频度。发生hash冲突用线性探测法解决。设hash函数为：

hash（key）=[key的第一个字母序号)*100+(key的最后一个字母序号)] mod 41。

hash函数就是把任意长度的输入通过散列算法，变换成固定长度的输出的一种转换。该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一地确定输入值。

hash函数主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的编码里。因此也可以说，hash函数就是一种数据内容和数据存放地址之间的映射关系。

统计c源程序中关键字出现的频度，主要分为这样几个关键技术：

是选择合适的hash函数。常用的hash函数有直接定址法、除留余数法、数字分析法、平方取余法等众多种类，分别适合不同的问题要求。hash函数选择的好坏对发生冲突的概率有着很大影响，因而在很大程度上影响程序运行的效率。

是如何将所有关键字使用hash函数存入比较数组中。是字符串模式匹配技术。即如何在众多程序**中选择出c语言的关键字。

是文件输入输出技术。这是整个方法的前提，即需要统计关键字个数的c源程序必须从文件中读入，才能进行处理。处理后的结果还需要写入文件中进行保存。

使用hash技术必须首先选择hash函数。基于对问题的分析，在此我们选用除留取余法建立hash函数。因为直接定址法虽然简单但会造成内存单元的大量浪费，而数字分析法、平方取中法等方法过于复杂，本身对时间资源的消耗过大，在本问题中使用并不值得。

我们建立的hash函数为：

hash（key）=[key的第一个字母序号)*100+(key的最后一个字母序号)]%41

其中key为关键字，在本问题中为c源程序的关键字。c语言关键字是c语言的保留的一些单词，这些单词都有了固定的意义和用途，不可以作为变量或者自定义类型或类名来使用。其特点是都有小写字母构成。

定义一个多维数组，数组第一行存放关键字，数组第二行存储hash函数处理后关键字结点地址，用hash函数存储关键字。

选择再好的hash函数也有出现冲突的可能，因此还必须选择一种解决hash冲突的方法。处理冲突的方法一般有开放定址法、线性探测法、二次探测法、链地址法等。为了简单起见，我选择了线性探测法，即当发生冲突时，从冲突发生位置的下一个位置起，依次寻找空的hash地址，如果该地址为空，就把该关键字存入相应的地址中。

图1函数层次调用图。

int open(char *filename)——打开含关键字的cpp文件。

int findhash(char *keyword)——在hash表中查找关键字找出关键字位置。

int creathash(char *keyword)——建立hash表，keyword是一个数组。

int insert(int key) —在hash表中插入关键字。

void menu()—现实菜单。

void printscreen(int key)——输出关键字。

int letternot(char ch)——判断单词是否扫描结束。

int keywordsnot(char *word)——判断是否为关键字。

int gethashvalue(char *keyword)——得到关键字的哈希函数值。

int open(char *filename)

char word[maxlength],ch;

int i;

file *read指向file类的指针*read

if((read=fopen(filename,"r"))null) /只读方式读取文件，如果为空。

while(!feof(read判断文件是否结束，到末尾函数值为"真"即非0

word[i]='0';

if(keywordsnot(word))

fclose(read);

printf("文件中关键字已经存入表中，请继续！")

int findhash(char *keyword) /在hash表中查找关键字。

int key,find,findcoll=0;

if(!keywordsnot(keyword)) 是否关键字。

return -1;

key=gethashvalue(keyword);

if(strcmp(test[key].keyword,keyword)==0)

return key;

for(find=key+1;find线性探测法。

findcollfindcoll统计冲突次数。

if(strcmp(test[find].keyword,keyword)==0)

for(find=0;find

return -1;

int creathash(char *keyword) /建立hash表，keyword是一个数组。

int key;

if(!keywordsnot(keyword)) 判断是否关键字。

return -1

《数据结构》课程设计报告书

数据结构课程设计报告书

《数据结构》课程设计报告书

数据结构课程设计报告书

其他用户还读了