там. Я пытаюсь получить столкновение и сравнить время в поиске хэша. Тем не менее, это не сработает. Кто-нибудь может указать, в чем проблема? Спасибо большое. Вот мой код
#include <cstring>
#include <iostream>
#include <iomanip>
using namespace std;
const int TOTAL=32; //32 keywords
const int MAXLEN=10; //length of keyword
const int HASHLEN=41; //length of HASH table
const char* KeyWords[TOTAL] =
{
"auto","double","int","struct","break","else","long","switch",
"case","enum","register","typedef","char","extern","return","union",
"const","float","short","unsigned","continue","for","signed","void",
"default","goto","sizeof","volatile","do","if","while","static",
};
class HASH
{
public:
char keyword[MAXLEN];
int count; //occurrence number
int con; //collision times
};
HASH HS[HASHLEN];//declaration
int isLetter(char ch);
int isKeyWords(char *word);
int FindHX(char *keyword); //search Hash table
int CreatHX(char *keyword); //create Hash table
int GetFreePos(int key); //get free position when having collision
void ResetHX();
int GetKey(char *keyword); //get Hash value of keywords
int ShowHashTable(int key); //show search results
int isLetter(char ch)
{
if( (ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z') ) return 1;
else return 0;
}
int FindHX(char *keyword, int &cmp_count) //search Hash table
{
int key,find,tem=0;
if(!isKeyWords(keyword)) return -1;
key=GetKey(keyword);
if(strcmp(HS[key].keyword,keyword)==0)
{
cmp_count++;
return key;
}
for(find=key+1;find<HASHLEN;find++) //if keyword exsits
{
cmp_count++; //count compare times
tem++; //count collision times
if(strcmp(HS[find].keyword,keyword)==0)
{
HS[find].con=tem;
return find;
}
}
for(find=0;find<key;find++)
{
cmp_count++;
tem++;
if(strcmp(HS[find].keyword,keyword)==0)
{
HS[find].con=tem;
return find;
}
}
return -1;
}
int CreatHX(char *keyword) //create Hash table
{
int key;
if(!isKeyWords(keyword)) return -1;
key=GetKey(keyword); //get Hash value of keywords
if(strlen(HS[key].keyword)>0) //if the keyword exists
{
if(strcmp(HS[key].keyword,keyword)==0) //if equals to position in Hash table
{
HS[key].count++;
return 1;
}
key=FindHX(keyword, cmp_count); //not equal
if(key<0)
{
key=GetFreePos(GetKey(keyword));
if(key<0) return -1;
strcpy(HS[key].keyword,keyword); //insert keyword into Hash table
}
if(key<0) return -1;
HS[key].count++;
}
else //if position is empty, insert keyword
{
strcpy(HS[key].keyword,keyword);
HS[key].count++;
}
return 1;
}
int GetFreePos(int key) //get free position
{
int find,tem=0;
if(key<0||key>=HASHLEN) return -1;
for(find=key+1;find<HASHLEN;find++) //positions afterwards
{
tem++;
if(strlen(HS[find].keyword)==0)
{
HS[find].con=tem;
return find;
}
}
for(find=0;find<key;find++) //position forewards
{
tem++;
if(strlen(HS[find].keyword)==0)
{
HS[find].con=tem;
return find;
}
}
return -1; //Hash table is full
}
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) //get Hash value of keywords
{
//Hash(Key)=[(initial letter)*100+(tail letter)] 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;
}
int ShowHashTable(int key) //show results
{
int hash_count = 0;
if(key < 0 || key >= HASHLEN)
{
cout << "Error! Invalid key word!" << endl;
return 0;
}
if(strlen(HS[key].keyword) == 0)
{
cout << "[" << key << "]" << setw(12) << "N/A" << endl;
return 0;
}
cout << "[" << key << "]" << setw(12) << HS[key].keyword << setw(12) << "Count: " << HS[key].count << endl;
hash_count++;
return hash_count;
}
#include <iostream>
#include <cstring>
#include "HashSearch.h"extern HASH HS[MAXLEN];
using namespace std;
int hash_count = 0;
for(int i = 0; i < HASHLEN; i++)
{
hash_count = hash_count + ShowHashTable(i);
}
cout << "Amount of key words: " << hash_count << endl << endl;
int conf_count = 0;
cout << setiosflags(ios::left) << setw(15) << "[Index]" << setiosflags(ios::left) << setw(20)
<< "[KeyWords]" << setiosflags(ios::left) << setw(20) << "[Conflicts]" << endl;
for(int i = 0; i < HASHLEN; i++)
{
if(strlen(HS[i].keyword) > 0)
{
int key = Hash(HS[i].keyword);
if(key != i)
{
conf_count++;
//cout << HS[i].con << endl;
cout << setiosflags(ios::left) << setw(15) << i << setiosflags(ios::left) << setw(25)
<< HS[i].keyword << setiosflags(ios::left) << setw(20) << HS[i].con << endl;
}
}
}
if(conf_count == 0)
cout << "No conflicts!" << endl;
else
cout << "Amount of conflict keywords: " << conf_count << endl << endl;
Сначала я импортировал исходный текстовый файл и создал хэш-таблицу. Кажется, все идет хорошо. Но когда я хочу получить время сравнения и время столкновения, переменные HS.con (для подсчета времени столкновения) и cmp_count (для подсчета времени сравнения) не накапливаются правильно. Значение остается 0, если смотреть в режиме отладки. И как я могу получить правильный счет?
Задача ещё не решена.