プログラミング珠玉第15章散リストhash文字列の適用
1442 ワード
#define HASH 29989
#define MULT 31
struct hashNode
{
char* strWord;
int nCount;
hashNode* pNext;
hashNode()
{
strWord = 0;
nCount = 0;
pNext = 0;
}
};
typedef hashNode* hashNodePtr;
// hash
unsigned int hashFunc(char* str)
{
unsigned int h = 0;
for (char* p = str; *p; p++)
{
h = h * MULT + *p;
}
return h % HASH;
}
void InputWord(char* strWord)
{
unsigned hashPos = hashFunc(strWord);
if (hashPos<0 || hashPos >= HASH)
{
cout << "igonoe: " << strWord << endl;
return;
}
for (hashNodePtr ptr = bin[hashPos]; ptr != NULL; ptr = ptr->pNext)
{
if (ptr->strWord != NULL && strcmp(ptr->strWord, strWord) == 0)
{
ptr->nCount++;
return;
}
}
hashNodePtr tempPtr = new hashNode();
int nWordLen = strlen(strWord);
tempPtr->strWord = new char[nWordLen+1];
strcpy(tempPtr->strWord, strWord);
tempPtr->nCount = 1;
tempPtr->pNext = bin[hashPos];
bin[hashPos] = tempPtr;
}
void OutputWordCount()
{
for (int index = 0; index < HASH; index++)
{
hashNodePtr ptr = bin[index];
while(ptr != NULL)
{
if (ptr->strWord != NULL)
{
cout << ptr->nCount << ": " << ptr->strWord << endl;
}
ptr = ptr->pNext;
}
}
}
hashNodePtr bin[HASH];
int main()
{
while(cin >> buff)
{
InputWord(buff);
}
OutputWordCount();
return 0;
}