代码如下,在计算冲突次数和查找次数的时候,HS.con和count两个变量都不能正确更新,不知道哪里有问题,请教各位大神,谢谢!
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include <cstring>
using namespace std;
const int TOTAL = 32;
const int MAXLEN = 10;
const int HASHLEN = 41;
int cont = 0;
class HashTable
{
public:
char keyword[MAXLEN];
int count;
int num;
};
HashTable HS[HASHLEN];
char KeyWords[TOTAL][MAXLEN] = {
"char", "double", "enum", "float", "int", "long", "short", "signed",
"struct", "union", "unsigned", "void", "break", "case", "continue",
"default", "do", "else", "for", "goto", "if", "return","switch","while",
"auto", "extern", "register", "static", "const", "sizeof", "typedef", "volatile"
};
template <class T>
class HASH {
public:
void Show(int key);
int CreatHX(char *keyword);
int GetFreePos(int key);
void ResetHX();
int GetKey(char *keyword);
int isKeyWords(char *word);
int Read(char *filename);
int isLetter(char ch);
int FindHX(char *keyword);
private:
int key;
char *keyword;
char *word;
char ch;
};
template <class T>
void HASH<T>::Show(int key)
{
if(key<0 || 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++;
}
template <class T>
int HASH<T>::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);
}
template<class T>
int HASH<T>::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].num = tem;
return(find);
}
}
for ( find = 0; find < key; find++ )
{
tem++;
if(strlen(HS[find].keyword)==0)
{
HS[find].num = tem;
return find;
}
}
return -1;
}
template<class T>
void HASH<T>::ResetHX()
{
int i;
for(i=0;i<HASHLEN;i++)
{
strcpy(HS[i].keyword,"");
HS[i].count=0;
HS[i].num=0;
}
}
template<class T>
int HASH<T>::GetKey(char *keyword)
{
return ((keyword[0]*100 + keyword[strlen(keyword)-1]) % 41);
}
template<class T>
int HASH<T>::isKeyWords(char *word)
{
int i;
for(i=0;i<TOTAL;i++)
if(strcmp(word,KeyWords[i])==0)
return 1;
return 0;
}
template<class T>
int HASH<T>::isLetter(char ch)
{
if((ch>='a' && ch <= 'z')||(ch > 'A' && ch <= 'Z'))
return 1;
else
return 0;
}
template<class T>
int HASH<T>::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].num = tem;
return(find);
}
}
for ( find = 0; find < key; find++ )
{
tem++;
if ( strcmp( HS[find].keyword, keyword ) == 0 )
{
HS[find].num = tem;
return(find);
}
}
return(-1);
}
template<class T>
int HASH<T>::Read( char *filename )
{
char word[MAXLEN], ch;
int i;
FILE *read;
fstream myfile;
myfile.open(filename);
if ( !myfile )
{
cout<<"文件不存在,请确认好再输入!"<<endl;
return(-1);
}
ResetHX();
while ( !feof( read ) )
{
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 main()
{
HASH<char> hash;
char filename[128], word[MAXLEN];
int i = 0, count = 0;
int key;
char j, y;
cout << "请输入要读取的文件 : ";
cin>>filename;
cout<<endl;
hash.Read( filename );
for ( i = 0; i < HASHLEN; i++ )
{
hash.Show( i );
getchar();
}
cout<<"关键字总数为 :"<<cont<<endl;
cout<<"请输入你想要查找的关键字 :";
cin>>word;
cout<<endl;
hash.Show( hash.FindHX( word ) );
cout<<"C语言中的关键字和其在hash表的位置 : "<<endl;
for ( i = 0; i < TOTAL; i++ )
{
cout<<setiosflags( ios::left ) <<"["<<setw(2)<<hash.GetKey(KeyWords[i])<<"] "
<<setiosflags(ios::left)<<setw( 11 )<<KeyWords[i];
if((i+1) % 4 == 0)
cout<<endl;
}
cout<<"是否显示冲突关键字列表? y(是)其它(否):";
cin>>j;
if(j=='y')
{
cout<<"冲突关键字列表"<<endl;
for(i=0;i<HASHLEN;i++)
{
if(strlen(HS[i].keyword)>0)
{
key=hash.GetKey(HS[i].keyword);
if(key!=i)
{
count++;
cout<<setiosflags(ios::left)<<setw(14)<<"\t[关键字]:"
<<HS[i].keyword<<setiosflags( ios::left ) << setw( 20 ) << "\t[哈希表当前位置] :"
<< i << setiosflags( ios::left ) << setw( 20 ) << "\t[冲突次数] :"<< HS[i].num<<endl;
}
}
if ( count == 0 )
cout<<"没有冲突"<<endl;
else
cout<<"\t 冲突关键字共 : "<<count<< "个"<< endl;
}
}
else
cout<<"不显示冲突关键字列表,但已存在!"<<endl;
return 0;
}