프로 그래 밍 주옥: 15.1 해시 표 통계 문자열 의 출현 횟수 실현 - - 문제 풀이 총화

#include 
#include 
#include 
#include 

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