プログラミング珠玉第15章散リストhash文字列の適用


#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;
}