辅导C程序、辅导C编程、辅导计算机C语言
- 首页 >> C/C++编程\#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define TOTAL 39 //39个关键字
#define MAXLEN 10 //关键字长度
#define HASHLEN 41 //哈希表长度
typedef struct //哈希表 结构体
{
char keyword[MAXLEN]; //关键字
int count; //记录频度
int con; //记录冲突次数
}HASH;
//全局变量
int cont=0; //统计关键词个数
char KeyWords[TOTAL][MAXLEN]={"asm","auto","break","case","cdecl","char",
"const","continue","default","do","double",
"else","enum","extern","far","float","for",
"goto","huge","if","int","interrupt","long",
"near","pascal","register","return","short",
"signed","sizeof","static","struct","switch",
"typedef","union","unsigned","void","volatile",
"while"}; //C语言中的39个关键字存入二维数组中
HASH HS[HASHLEN]; //建立结构体HS
//函数声明
void Show(int key);
int Read(char *filename);
int isLetter(char ch);
int isKeyWords(char *word);
int FindHX(char *keyword);
int CreatHX(char *keyword);
int GetFreePos(int key);
int GetKey(char *keyword);
void main()
{
char orz;
int flag=1,i,count,key,has;
char filename[128],word[MAXLEN];
while(flag)
{
printf("\t\tA.读取一个文件\n");
printf("\t\tB.输出Hash表(关键字总数，冲突次数)\n");
printf("\t\tC.查询某关键字在Hash表中的情况\n");
printf("\t\tD.显示Hash表中的冲突关键字\n");
printf("\t\tE.显示C语言关键字的Hash函数值(作为对照)\n");
printf("\t\tF.退出\n\n");
printf("\t\t请输入序号(A--F):");
scanf("%c",&orz);
switch(orz)
{
case 'a':
case 'A':
system("cls"); //清屏函数
printf("请输入要读取的文件名(文件必须与程序在同一目录下):"); //比如输入：a.cpp
scanf("%s",&filename);
Read(filename);
printf("\n按任意键返回...");
getch();
system("cls");
break;
case 'b':
case 'B':
getchar();
system("cls");
printf("每次显示5行，请按回车键继续！\n");
for(i=0;i<HASHLEN;i++)
{
Show(i);
if((i+1)%5==0)
getchar(); //为了清晰，每次显示5行
}
printf("关键字总数为: %d\n",cont);
printf("\n按任意键返回...");
getch();
system("cls");
break;
case 'c':
case 'C':
system("cls");
printf("请输入你想要查找的关键字： ");
scanf("%s",&word);
printf("\n");
Show(FindHX(word));
printf("\n按任意键返回...");
getch();
system("cls");
break;
case 'd':
case 'D':
system("cls");
printf("\t冲突关键字列表\n\n");
count=0;
for(i=0;i<HASHLEN;i++)
{
if(strlen(HS[i].keyword)>0)
{
key=GetKey(HS[i].keyword);
if(key!=i)
{
count++;
printf("\t关键字:%s",HS[i].keyword);
printf("\t哈希表当前位置:%d",i);
printf("\t冲突次数:%d\n",HS[i].con);
}
}
}
if(count==0)
printf("没有冲突\n");
else
printf("\n\t\t\t冲突关键字共:%d个\n",count);
printf("\n按任意键返回...");
getch();
system("cls");
break;
case 'e':
case 'E':
getchar();
system("cls");
printf(" C语言中的关键字和其在哈希表的位置:\n");
for(i=0;i<TOTAL;i++)
{
has=GetKey(KeyWords[i]);
printf("[%-2d]%-11s",has,KeyWords[i]);
if((i+1)%5==0)
printf("\n");
}
printf("\n");
printf("\n按任意键返回...");
getch();
system("cls");
break;
case 'f':
case 'F':
flag=0;
break;
default:
system("cls");
}
}
}
int Read(char *filename)
{
char word[MAXLEN],ch;
int i;
FILE *read; //建立一个指像FILE类型结构体的指针变量
if((read=fopen(filename,"r"))==NULL) //以只读方式读取文件，如果为空执行下面的语句
{
printf("\n文件不存在,请确认好再输入!");
return -1; //跳出Read函数
}
while(!feof(read)) //feof()检测文件是否结束，到末尾函数值为“真”即非0
{
i=0;
ch=fgetc(read); //读取一个字符
while(isLetter(ch)==0&&feof(read)==0)
ch=fgetc(read); //如果不是字母就接着读取,关键字都是由字母组成的
while(isLetter(ch)==1&&feof(read)==0)
{
if(i==MAXLEN)
{
while(isLetter(ch)==1&&feof(read)==0)
{
ch=fgetc(read); //超过MAXLEN的长度则一定不为关键字，把余下连一起的字母都读取
}
i=0;
break;
}
else
{
word[i++]=ch; //把读取到的字母存入word数组中
ch=fgetc(read);
}
}
word[i]='\0';
if(isKeyWords(word))
{
CreatHX(word);
}
}
fclose(read);
printf("\n读取成功，文件中关键字已经存入hash表，请继续操作");
}
int isLetter(char ch) //判断是否是字母，因为关键字都是英文单词
{
if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))
return 1; //是字母就返回1
else
return 0; //不是字母就返回0
}
int FindHX(char *keyword) //查找哈希表，分块查找
{
int key,find,tem=0;
if(!isKeyWords(keyword)) //用于查找制定关键字时判断是否为关键字
return -1;
key=GetKey(keyword);
if(strcmp(HS[key].keyword,keyword)==0)
return key;
for(find=key+1;find<HASHLEN;find++)
{ //线性探查法顺序查找哈希表中是否已存在关键字
tem++; //统计冲突次数
if(strcmp(HS[find].keyword,keyword)==0)
{
HS[find].con=tem; //若有相等的就把冲突的次数存入数组的con中
return find;
}
}
for(find=0;find<key;find++) //后面的找不到再从前面开始找
{
tem++;
if(strcmp(HS[find].keyword,keyword)==0)
{
HS[find].con=tem;
return find;
}
}
return -1;
}
int CreatHX(char *keyword) //建立哈希表,加个*是因为word是一个数组
{
int key;
if(!isKeyWords(keyword)) //不是关键字跳出此函数
return -1;
key=GetKey(keyword); //计算哈希值，根据所给哈希函数计算得出的结果
if(strlen(HS[key].keyword)>0) //判断关键字表中该位置是否存在关键字，strlen用于计算()内的字符串长度
{ //已经存在有关键字
if(strcmp(HS[key].keyword,keyword)==0)
{ //再判断哈希表中该位置的关键字是否相同
HS[key].count++; //相同就频度加1
return 1; //跳出函数
}
key=FindHX(keyword); //不相同，继续查找
if(key<0) //没有找到相等的keyword
{
key=GetFreePos(GetKey(keyword));
if(key<0) //哈希表满或者计算的哈希值有问题
return -1;
strcpy(HS[key].keyword,keyword); //将关键字插入哈希表
}
if(key<0)
return -1;
HS[key].count++;
}
else //该位置为空，直接将关键字插入该位置中
{
strcpy(HS[key].keyword,keyword);
HS[key].count++;
}
return 1;
}
int GetFreePos(int key) //在哈希表中给关键字找个位置插进去
{
int find,tem=0;
if(key<0||key>=HASHLEN)
return -1;
for(find=key+1;find<HASHLEN;find++) //先找后面的位置
{
tem++;
if(strlen(HS[find].keyword)==0) //若这个地方为空
{
HS[find].con=tem; //把冲突的次数存入con中
return find;
}
}
for(find=0;find<key;find++) //若后面没有地方可以插入，再找前面的位置
{
tem++;
if(strlen(HS[find].keyword)==0)
{
HS[find].con=tem;
return find;
}
}
return -1; //哈希表已满
}
void Show(int key)
{
if(key<0||key>=HASHLEN)
{
printf("关键字不存在!\n");
return;
}
if(strlen(HS[key].keyword)==0)
{
printf("哈希表位置: %d 记录是空的!\n",key);
return;
}
printf("哈希表位置: %d 关键字: %-11s出现次数: %d\n",key,HS[key].keyword,HS[key].count);
cont++;
}
int GetKey(char *keyword) //哈希函数
{ //Hash函数为：Hash(Key)=[(Key的首字母序号)*100+(Key的尾字母序号)] Mod 41
return ( keyword[0]*100+keyword[strlen(keyword)-1] ) % 41;
}
int isKeyWords(char *word) //判断是否关键字
{
int i;
for(i=0;i<TOTAL;i++)
if(strcmp(word,KeyWords[i])==0)
return 1;
return 0;
}