keiko233
keiko233
2017-04-06 03:06
浏览 540

关于hash表存储c源程序关键字时读入cpp文件出现异常问题

代码网上找的应该没问题,新建一个项目后读入文件时出现异常图片说明
#include
#include
#include
#include
#include
#include
#include
using namespace std;

const int TOTAL = 32; //32个关键字
const int MAXLEN = 10; //关键字长度
const int HASHLEN = 41; //哈希表长度

int cont = 0; //统计哈希表中的关键字个数

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);
void ResetHX();
int GetKey(char *keyword);

char KeyWords[TOTAL][MAXLEN] = //构造二维数组存储32个关键字
{
"auto","break","case","char","const","continue",
"default","do","double","else","enum","extern",
"float","for","goto","if","int","long","register",
"return","short","signed","sizeof","static",
"struct","switch","typedef","union","unsigned",
"void","volatile","while",
};
/***********************************************************************
typedef struct HASH
{
char keyword[MAXLEN];
int count; //出现次数(频度)
int con; //冲突次数
}HASH HS[HASHLEN];

/****************************************************************************/
class HASH //哈希表类
{
public:
char keyword[MAXLEN];
int count; //出现次数(频度)
int con; //冲突次数
};
HASH HS[HASHLEN];

int main()
{
char filename[128], word[MAXLEN];
int i, key, count;
ResetHX(); //先清空哈希表
cout << "请输入要读取的文件名(文件必须与程序在同一目录下):";
cin >> filename;
cout << endl;
Read(filename);//read函数从一个文件读字节到一个指定的存储器区域,由长度参数确定要读的字节数
for (i = 0; i Show(i);
cout cout cin >> word;
cout << endl;
Show(FindHX(word));
cout << "\t冲突关键字列表" << endl << endl;
count = 0;
for (i = 0; i {
if (strlen(HS[i].keyword)>0)
{
key = GetKey(HS[i].keyword);
if (key != i)
{
count++;
cout << "\t[关键字]: " << HS[i].keyword << endl;
cout << "\t[哈希表当前位置]: " << i << endl;
cout << "\t[冲突次数]: " << HS[i].con << endl << endl;
}
}
}
if (count == 0)
cout << "没有冲突" << endl;
else
cout << "\t冲突关键字共:" << count << "个" << endl;
return 0;
}

void Show(int key)//显示出某关键字的频度
{
if (key= HASHLEN)
{
cout << "关键字不存在!" << endl;
return;
}
if (strlen(HS[key].keyword) == 0)
{
cout << "哈希表位置:" << key << " 记录是空的" << endl;
return;
}
cout << "哈希表位置: " << key << " 关键字: "
<< HS[key].keyword << " 出现次数 " << HS[key].count << endl;
cont++;
}

int Read(char *filename) //读取文件
{
char word[MAXLEN], ch;
int i;
FILE *read;

if ((read = fopen(filename, "r")) == NULL)  //只读方式打开一个文本文件,只允许读数据   
{
    cout << "文件不存在,请确认好再输入!" << endl;
    return -1;
}
ResetHX();  //读取文件前先清空哈希表
while (!feof(read))  //feof()是文件结束检测函数,如果没有结束,返回值是0,结束了是1
{
    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);
            }
            i = 0;
            break;
        }
        //超过关键字长度将跳过当前识别区域,读取后一单词
        else
        {  //将连续读取的字母存在数组里,组成一个单词
            word[i++] = ch;
            ch = fgetc(read);
        }
    }
    word[i] = '\0'; //字符数组的结束标志
    if (isKeyWords(word))
    {
        CreatHX(word);
    }
}
fclose(read);
cout << "读取成功,文件中关键字已经存入hash表,请继续操作" << endl;

return 1;

}

int isLetter(char ch) //判断是否是字母,因为关键字都是英文单词
{
if ((ch >= 'a'&&ch <= 'z') || (ch >= 'A'&&ch <= 'Z')) return 1;
else return 0;
//是字母就返回1,否则返回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;
        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) //建立哈希表
{
int key;
if (!isKeyWords(keyword)) return -1;
key = GetKey(keyword); //计算哈希值

if (strlen(HS[key].keyword)>0) //判断关键字表中该位置是否存在关键字
{    //已经存在有关键字
    if (strcmp(HS[key].keyword, keyword) == 0)
    {  //再判断哈希表中该位置的关键字是否相同
        HS[key].count++;
        return 1;
    }
    key = FindHX(keyword);  //不相同,继续查找
    if (key<0)
    {
        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= HASHLEN) return -1;
for (find = key + 1; find<HASHLEN; find++) //先找后面的位置
{
tem++;
if (strlen(HS[find].keyword) == 0) {
HS[find].con = tem;
return find;
}
}

for (find = 0; find<key; find++)  //再找前面的位置
{
    tem++;
    if (strlen(HS[find].keyword) == 0) {
        HS[find].con = tem;
        return find;
    }
}
return -1; //哈希表已满

}

void ResetHX() //重置哈希表,
{
int i;
for (i = 0; i<HASHLEN; i++)
{
strcpy(HS[i].keyword, ""); //不能用等号赋值
HS[i].count = 0;
HS[i].con = 0;
}
}

int GetKey(char *keyword) //哈西函数
{ //Hash函数为:Hash(Key)=[(Key的首字母序号)*100+(Key的尾字母序号)] Mod 41
return (keyword[0] * 100 + keyword[strlen(keyword) - 1]) % 41; //这里不要忘了减1
}

int isKeyWords(char *word) //判断是否关键字
{
int i;
for (i = 0; i<TOTAL; i++)
if (strcmp(word, KeyWords[i]) == 0) return 1;
return 0;
}

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

相关推荐