编程珠玑： 15.1实现一个哈希表统计字符串出现次数 -------解题总结

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>

using namespace std;
/*
问题:统计书中的单词及出现次数，实现一个数据结构进行存储
分析：典型的信息检索中的倒排索引问题。可以采用链表数组实现： 哈希 + 拉链法
      一种做法是：根据给定的单词个数n，选取最接近n的质数k,然后对字符串进行散列，
	  h = 31 * h + charValue;
	  求得字符串的哈希值后，用h % k 得到散列后的哈希值

输入:
10(单词个数)
zhu wen ping ma chao ma yan ma xi ping 
输出:(单词以及单词出现次数)
zhu:1, wen:1, ping:2, ma:3, chao:1, yan:1, xi:1

关键：
1 哈希表的实现：根据给定的单词个数n，选取最接近n的质数k,然后对字符串进行散列，
	  h = 31 * h + charValue;
	  求得字符串的哈希值后，用h % k 得到散列后的哈希值

2
接下来是要建立散列表，散列表的长度，散列中的乘数为31
散列值计算公式:设一个字符串val共有n个字符，则计算的哈希值为
h = 31 ^ (n-1) * val[0] + 31 ^ (n-2) * val[1] + 31 ^ (n-3) * val[2] + ...+ val[n-1]  
选用31作为乘数的原因是：
  1】对于任意数i， 31 * i = (i << 5) - i,可以用移位和减法代替乘法，可以优化
  2】31是质数，只能被1和自身整除，既要保证31乘以字符串不能溢出，又要保证哈希地址较大，来减少冲突，
  综合来说：31是个不错的乘数

3 素数筛选法
	int* primeArr = new int[num + 1];//用于判定是否为素数的数组，初始化为0，表示都是质数
	// sizeof(指针)都是4,strlen只是用来计算字符串长度，整形指针不行 
	int* visitArr = new int[num + 1];//初始化为0，表示都没有访问过
	memset(primeArr , 0 , sizeof(primeArr) * (num + 1));
	memset(visitArr , 0 , sizeof(visitArr) * (num + 1));
	int k;
	for(int i = 2 ; i <= num ; i++ )
	{
		k = i;//k是倍数,从i开始算，不要从2开始， i*i与2*i的比较，起始2*i已经在第一轮计算过了
		while(k * i <= num)
		{
			//如果没有访问过
			if(0 == visitArr[i])
			{
				visitArr[k * i] = 1;//是k*i不是i
				primeArr[k * i] = 1;//表示是合数
			}
			//如果访问过，就不再处理
			k++;
		}
	}
*/

/*
寻找 <= 某个数的最大质数,
采用素数筛选法来:初始设置每个数都是质数，从2开始，将2设置为质数，2的所有倍数全部设置为合数
然后遍历3，如果3已经访问过，那么就不遍历
素数：
*/
int getPrimeNumber(int num)
{
	if(num <= 0)
	{
		return -1;
	}
	int* primeArr = new int[num + 1];//用于判定是否为素数的数组，初始化为0，表示都是质数
	// sizeof(指针)都是4,strlen只是用来计算字符串长度，整形指针不行 
	int* visitArr = new int[num + 1];//初始化为0，表示都没有访问过
	memset(primeArr , 0 , sizeof(primeArr) * (num + 1));
	memset(visitArr , 0 , sizeof(visitArr) * (num + 1));
	int k;
	for(int i = 2 ; i <= num ; i++ )
	{
		k = i;//k是倍数,从i开始算，不要从2开始， i*i与2*i的比较，起始2*i已经在第一轮计算过了
		while(k * i <= num)
		{
			//如果没有访问过
			if(0 == visitArr[i])
			{
				visitArr[k * i] = 1;//是k*i不是i
				primeArr[k * i] = 1;//表示是合数
			}
			//如果访问过，就不再处理
			k++;
		}
	}
	int i;
	//到这里，已经通过素数筛选法，获得了所有质数，凡是primeArr[i]为0都是质数，我们只需要从num向前搜索最接近的质数即可
	for(i = num - 1; i >= 2 ; i--)
	{
		if(0 == primeArr[i])
		{
			break;
		}
	}
	delete[] primeArr;
	delete[] visitArr;
	return i;
}

/*
接下来是要建立散列表，散列表的长度，散列中的乘数为31
散列值计算公式:设一个字符串val共有n个字符，则计算的哈希值为
h = 31 ^ (n-1) * val[0] + 31 ^ (n-2) * val[1] + 31 ^ (n-3) * val[2] + ...+ val[n-1]  
选用31作为乘数的原因是：
  1】对于任意数i， 31 * i = (i << 5) - i,可以用移位和减法代替乘法，可以优化
  2】31是质数，只能被1和自身整除，既要保证31乘以字符串不能溢出，又要保证哈希地址较大，来减少冲突，
  综合来说：31是个不错的乘数
*/
const int MULT = 31;
typedef struct Node
{
	Node():_next(NULL),_word(""),_count(0),_isNULL(true){}
	void setNULL(bool flag)
	{
		_isNULL = flag;
	}
	Node* _next;//指向下一个结点
	//char* _word;//字符串，用字符指针会出现乱码
	string _word;
	int _count;//该字符串出现次数
	bool _isNULL;//初始化建立结点的时候设置结点默认为空，以后每次实例化的结点都必须设置该空为false
}Node;

//对字符串进行哈希，返回在哈希表中的下标
int getHash(char* str , int primeNum)
{
	unsigned int hashValue = 0;
	if(NULL == str || primeNum < 2)
	{
		return hashValue;
	}
	for( ; *str ; str++)
	{
		char ch = *str;
		hashValue = MULT * hashValue + ch;
	}
	return (hashValue % primeNum);
}

void countWords(Node* hashTable, int primeNum , vector<string> words)
{
	if(NULL == hashTable || primeNum < 2 || words.empty())
	{
		return;
	}
	//对每个单词生成链表
	int size = words.size();
	string sWord;
	char* word;
	int hashIndex;
	Node* node;
	for(int i = 0 ; i < size ; i++)
	{
		sWord = words.at(i);
		word = (char*)sWord.c_str();
		hashIndex = getHash(word , primeNum);
		//如果哈希表中对应位置的结点为空，则需要新建结点
		if(hashTable[hashIndex]._isNULL)
		{
			Node* newNode = new Node();
			newNode->_word = sWord;
			newNode->_isNULL = false;
			newNode->_count = 1;//设置计数器为1
			hashTable[hashIndex] = *newNode;
		}
		else
		{
			//判断对应结点如果不为空，则找到该单词()，并累加计数
			bool isFind = false;
			Node* previouNode = NULL;
			for(node = &hashTable[hashIndex] ; node != NULL ; )
			{
				//如果找到该单词
				if( node->_word == sWord)
				{
					node->_count++;
					isFind = true;
					break;
				}
				previouNode = node;
				node = node->_next;
			}
			//如果一直找不到，说明对应同一个哈希下标，出现了不同的字符串，需要将当前结点加入到首部(发现死循环)，插入到尾部
			if(!isFind)
			{
				Node* newNode = new Node();
				newNode->_word = sWord;
				newNode->_isNULL = false;
				newNode->_count = 1;//设置计数器为1
				previouNode->_next = newNode;
				//newNode->_next = &hashTable[hashIndex];//插入到首部需要获取地址，似乎陷入了死循环
				//hashTable[hashIndex] = *newNode;
			}
		}
	}
}

void releaseHashTable(Node* hashTable , int size)
{
	//先删除每个结点的链表，最后删除整个哈希表
	if(NULL == hashTable || size <= 0)
	{
		return;
	}
	for(int i = 0 ; i < size ; i++)
	{
		Node* node = &hashTable[i];
		//由于这里没有头结点，只需要再删除当前结点之前保存指向下一个结点的指针即可
		while(node)
		{
			Node* nextNode = node->_next;
			delete node;
			node = nextNode;
		}
	}
	delete[] hashTable;		
}

void print(Node* hashTable , int size)
{
	if(NULL == hashTable || size <= 0)
	{
		cout << "NO result" << endl;
		return;
	}
	for(int i = 0 ; i < size ; i++)
	{
		Node* node = &hashTable[i];
		if(NULL == node || node->_isNULL )
		{
			continue;
		}
		//由于这里没有头结点，只需要再删除当前结点之前保存指向下一个结点的指针即可
		while(node)
		{
			cout << node->_word << ":" << node->_count << ",";
			node = node->_next;
		}
	}
	cout << endl;
}

void process()
{
	int wordNum;
	vector<string> words;
	string word;
	while(cin >> wordNum)
	{
		for(int i = 0 ; i < wordNum ; i++)
		{
			cin >> word;
			words.push_back(word);
		}
		//输入完单词后，下面就开始统计，需要先建立散列表，寻找最大质数p
		int primeNum = getPrimeNumber(wordNum);//计算接近单词个数n的最大质数
		
		//创建哈希表
		Node* hashTable = new Node[primeNum];

		//统计单词和出现次数的哈希表
		countWords(hashTable , primeNum , words);
		//打印结果
		print(hashTable , primeNum);
		//先删除每个结点，在删除
		releaseHashTable(hashTable , primeNum);
	}
}

int main(int argc , char* argv[])
{
	process();
	getchar();
	return 0;
}