数据结构与算法课程设计报告-利用哈希技术统计C源程序关键字出现频度

数据结构与算法课程设计报告

题目：利用哈希技术统计C源程序关键字出现频度

学生姓名： 学 号： ______ 班 级： ____ 指导教师： _

2012年 6 月 18 日

数据结构与算法课程设计报告

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

(1)题目内容：

利用Hash技术统计某个C源程序中的关键字出现的频度 (2)基本要求：

扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度。用线性探测法解决Hash冲突。设Hash函数为： Hash(key)[(key的第一个字母序号)*100+(key的最后一个字母序号)] MOD 41

一、对题目的分析

哈希表是为了便于快速搜索而组织的值组合的集合。Hash Table是一种数组，可以用任意简单变量值来访问其元素，这种数组叫做关联数组，也叫哈希表。值对的集合。

理想的情况下是希望不经过任何比较，一次存储就能得到所查到的记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。

基本要求：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）存在一一对应的关系，于是用这个数组单元来存储这个元素。使用hash表存储关键字时难免会有不同的关键字对应同一关键码的情况，因此必须有个处理冲突的办法。

Hash函数：

Hash(key)[(key的第一个字母序号)*100+(key的最后一个字母序号)] MOD 41

二、处理冲突的方法

处理冲突的办法—线性探测法 用线性探法解决冲突时，把有冲突的关键字往后推移直到有空位置的关键码时再插入到hash表中。 C语言关键字:

C语言关键字是C语言的保留的一些单词，这些单词都有了固定的意义和用途，不可以作为变量或者自定义类型或类名来使用。其特点是都有小写字母构成。 C语言关键字有哪些：

double int struct break else long switch case enum

register char extern return union const float short unsigned continue for signed void default goto sizeof volatile do while static if auto case

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

Hash(Key)=[(Key第一个字符在1-26个字母中的序号)*100+(Key最后一个字符在1-26个字母中的序号)%41

如此得到如for对应地址3，if对应于地址4，int对应地址18等等。 哈希表 H(key)=keyMOD41 处理冲突为线性探测再散列。

数据结构与算法课程设计报告

三、算法设计及部分函数

打开含关键字的CPP文件： int Open(char *filename) {

char word[MaxLength],ch; int i;

FILE *read; //指向FILE类的指针*read { }

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

i=0;

ch=fgetc(read); //读取一个字符 while(LetterNot(ch)==0&&feof(read)==0)

ch=fgetc(read); //如果不是字母就接着读取,关键字都是由字母组成的 while(LetterNot(ch)==1&&feof(read)==0) {

if(i==MaxLength) {

while(LetterNot(ch)==1&&feof(read)==0) {

ch=fgetc(read); //超过MAXLEN的长度则一定不为关键字，把余下连一

cout<if((read=fopen(filename,\"r\"))==NULL) //只读方式读取文件，如果为空

起的字母都读取

}

fclose(read);

}

word[i]='\\0';

if(KeywordsNot(word)) { }

CreatHash(word); } else { }

word[i++]=ch; //把读取到的字母存入word数组中 ch=fgetc(read); } i=0; break;

数据结构与算法课程设计报告

}

cout<在Hash表中查找关键字找出关键字位置：

int FindHash(char *keyword) //在Hash表中查找关键字 { }

建立Hash表：

int CreatHash(char *keyword) //建立Hash表,keyword是一个数组 {

int key;

if(!KeywordsNot(keyword)) //判断是否关键字

return -1;

key=GetHashValue(keyword); //计算Hash值

if(strlen(Test[key].keyword)>0) //Hash表中该位置存在关键字 {

if(strcmp(Test[key].keyword,keyword)==0) //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;findfor(find=0;findreturn -1;

FindColl++;

if(strcmp(Test[find].keyword,keyword)==0) { }

Test[find].coll=FindColl; return find;

FindColl++; //FindColl统计冲突次数 if(strcmp(Test[find].keyword,keyword)==0) { }

Test[find].coll=FindColl; //把冲突次数存入coll return find;

数据结构与算法课程设计报告

}

}

}

Test[key].count++; //频度加1 return 1; //跳出函数

key=FindHash(keyword); //不相同，继续查找 if(key<0) //没有找到相等的keyword { }

if(key<0)

return -1; Test[key].count++;

key=Insert(GetHashValue(keyword));

if(key<0) //Hash表满或者计算的Hash值有问题

return -1;

strcpy(Test[key].keyword,keyword); //将关键字插入Hash表

else //该位置没有关键字 { }

return 1;

strcpy(Test[key].keyword,keyword); Test[key].count++;

在Hash表中插入关键字：

int Insert(int key) //在Hash表中插入关键字 {

int find,FindColl=0;

if(key<0||key>=LengthofHash)

return -1;

for(find=key+1;findfor(find=0;findFindColl++;

if(strlen(Test[find].keyword)==0) {

Test[find].coll=FindColl; FindColl++;

if(strlen(Test[find].keyword)==0) //若这个地方为空 {

Test[find].coll=FindColl; //把冲突的次数存入coll中 return find; }

数据结构与算法课程设计报告

}

}

}

return find;

return -1; //Hash表已满

四、算法的实现

a)引用库函数定义变量 #include #include #include #include using namespace std;

const int LengthofHash=41; //Hash表长度 int keycount=0; //统计Hash表中的关键字总数 const int Total=38; //38个关键字 const int MaxLength=20;

char KeyWords[Total][MaxLength]= //列举38个关键字 {

\"bool\\"class\\"double\\"float\

\"interrupt\\"register\\"static\\"unsigned\ };

b)类的构造及类的对象 class ConuntNum { public:

int coll; //collision冲突次数 int count; //出现次数（频度） char keyword[MaxLength]; };

ConuntNum Test[LengthofHash];

c)函数的声明部分 void Menu();

void PrintScreen(int key); int Open(char *filename);

数据结构与算法课程设计报告

int LetterNot(char ch); int KeywordsNot(char *word); int FindHash(char *keyword); int CreatHash(char *keyword); int Insert(int key);

int GetHashValue(char *keyword); d)在Hash表中分块查找

int FindHash(char *keyword) //在Hash表中查找关键字 { }

int key,find,FindColl=0;

if(!KeywordsNot(keyword)) //是否关键字

return -1;

„„„„

五、源代码

#include #include #include #include using namespace std;

const int LengthofHash=41; //Hash表长度 int keycount=0; //统计Hash表中的关键字总数 const int Total=38; //38个关键字 const int MaxLength=20;

char KeyWords[Total][MaxLength]= //列举38个关键字 {

\"bool\\"class\\"double\\"float\

\"interrupt\\"register\\"static\\"unsigned\ };

class ConuntNum { public:

int coll; //collision冲突次数

数据结构与算法课程设计报告

int count; //出现次数（频度） char keyword[MaxLength]; };

ConuntNum Test[LengthofHash];

//先声明后使用 void Menu();

void PrintScreen(int key); int Open(char *filename); int LetterNot(char ch); int KeywordsNot(char *word); int FindHash(char *keyword); int CreatHash(char *keyword); int Insert(int key);

int GetHashValue(char *keyword);

void main() {

char opt;

int option=1,i,count,key,has;

char filename[50],word[MaxLength]; { Menu(); cin>>opt;

switch(opt) {

case '1':

system(\"cls\");

while(option)

cout<<\"请输入文件名:\";

cin>>filename; Open(filename);

cout<break;

case '2':

system(\"cls\");

cout<<\"按回车键继续显示！\"<PrintScreen(i);

if((i+1)%10==0) }

getchar(); //10行一循环

数据结构与算法课程设计报告

cout<<\"CPP文件中关键字总数为:\"<cout<system(\"cls\"); break;

case '3': system(\"cls\");

cout<<\"冲突关键字列表:\"<for(i=0;i{

if(strlen(Test[i].keyword)>0) }

cout<<\"没有冲突\"<{

key=GetHashValue(Test[i].keyword); if(key!=i) }

{

count++;

cout<<\"\关键字\"<cout<<\"\冲突次数:\"<if(count==0)

else

cout<cout<system(\"cls\"); break;

case '4':

system(\"cls\");

cout<<\"输入你想要查找的关键字： \"<cin>>word; cout<PrintScreen(FindHash(word));

cout<system(\"cls\"); break;

case '5':

option=0; break;

数据结构与算法课程设计报告

}

}

}

default:

system(\"cls\");

int Open(char *filename) {

char word[MaxLength],ch; int i;

FILE *read; //指向FILE类的指针*read { }

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

i=0;

ch=fgetc(read); //读取一个字符 while(LetterNot(ch)==0&&feof(read)==0) {

if(i==MaxLength) {

while(LetterNot(ch)==1&&feof(read)==0) {

ch=fgetc(read); //超过MAXLEN的长度则一定不为关键字，把余下连一

ch=fgetc(read); //如果不是字母就接着读取,关键字都是由字母组成的 while(LetterNot(ch)==1&&feof(read)==0) cout<if((read=fopen(filename,\"r\"))==NULL) //只读方式读取文件，如果为空

起的字母都读取

}

word[i]='\\0';

if(KeywordsNot(word)) {

} else { }

word[i++]=ch; //把读取到的字母存入word数组中 ch=fgetc(read); } i=0; break;

数据结构与算法课程设计报告

}

}

}

CreatHash(word);

fclose(read);

cout<int LetterNot(char ch) //判断是否是字母 { }

int FindHash(char *keyword) //在Hash表中查找关键字 {

int key,find,FindColl=0;

if(!KeywordsNot(keyword)) //是否关键字

return -1;

if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))

return 1; return 0;

else

key=GetHashValue(keyword);

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

return key;

for(find=key+1;findfor(find=0;findreturn -1;

FindColl++;

if(strcmp(Test[find].keyword,keyword)==0) { }

Test[find].coll=FindColl; return find;

FindColl++; //FindColl统计冲突次数 if(strcmp(Test[find].keyword,keyword)==0) { }

Test[find].coll=FindColl; //把冲突次数存入coll return find;

数据结构与算法课程设计报告

}

int CreatHash(char *keyword) //建立Hash表,keyword是一个数组 { }

int Insert(int key) //在Hash表中插入关键字 {

int find,FindColl=0;

if(key<0||key>=LengthofHash) {

return -1; int key;

if(!KeywordsNot(keyword)) //判断是否关键字

return -1;

key=GetHashValue(keyword); //计算Hash值

if(strlen(Test[key].keyword)>0) //Hash表中该位置存在关键字 { }

else //该位置没有关键字 { }

return 1;

strcpy(Test[key].keyword,keyword); Test[key].count++;

if(strcmp(Test[key].keyword,keyword)==0) //Hash表中该位置的关键字相同 { }

key=FindHash(keyword); //不相同，继续查找 if(key<0) //没有找到相等的keyword { }

if(key<0)

return -1;

key=Insert(GetHashValue(keyword));

if(key<0) //Hash表满或者计算的Hash值有问题

return -1;

Test[key].count++; //频度加1 return 1; //跳出函数

strcpy(Test[key].keyword,keyword); //将关键字插入Hash表

Test[key].count++;

for(find=key+1;find数据结构与算法课程设计报告

}

}

FindColl++;

if(strlen(Test[find].keyword)==0) //若这个地方为空 {

Test[find].coll=FindColl; //把冲突的次数存入coll中 return find; }

for(find=0;findreturn -1; //Hash表已满

FindColl++;

if(strlen(Test[find].keyword)==0) { }

Test[find].coll=FindColl; return find;

int KeywordsNot(char *word) //判断是否关键字 { }

void PrintScreen(int key) {

if(key<0||key>=LengthofHash) { }

if(strlen(Test[key].keyword)==0) { }

表位置: \"<cout<<\"关键字不存在!\"<for(i=0;iif(strcmp(word,KeyWords[i])==0)

return 1;

return 0;

cout<<\"Hash

数:\"<数据结构与算法课程设计报告

}

keycount++;

int GetHashValue(char *keyword) { int HashValue;

HashValue=(keyword[0]*100+keyword[strlen(keyword)-1])%41; }

void Menu() {

cout<<\"\\**********************************\"<cout<<\"\\* 1.读取CPP文件 *\"<cout<<\"\\* 请选择(1--5): *\"<return HashValue;

cout<<\"\\* 5.退出 *\"<cout<<\"\\**********************************\"<六、程序运行结果截图

图1 程序运行界面

数据结构与算法课程设计报告

图2 载入含关键字的CPP

图3 输出Hash表中的关键字

数据结构与算法课程设计报告

图4 显示冲突的关键字

图5 查找关键字在Hash表中的位置

七、课程设计心得体会

这次课程设计让我了解到自己在Hash表这一块有着许多的不足，在各方面都缺乏最重要的知识。

通过这次课程设计,我了解到自己在实践操作方面还有很多不足，在实践过程中老师和同学给了我很大的帮助和鼓励，学会了团结精神的重要性，以及做事必须一丝不苟，遇到困难不能半途而废要有不惧困难探求真理，踏踏实实的解决问题。

参考文献：

李根强 编著，《数据结构（C++版）》 （第二版）， 中国水利水电出版社

数据结构与算法课程设计报告